Online Real-Time Preemptive Scheduling of Jobs with Deadlines View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2000

AUTHORS

Bhaskar DasGupta , Michael A. Palis

ABSTRACT

In this paper, we derive bounds on performance guarantees of online algorithms for real-time preemptive scheduling of jobs with deadlines on K machines when jobs are characterized in terms of their minimum stretchf actor α (or, equivalently, their maximum execution rate r = 1/α). We consider two well known preemptive models that are of interest from practical applications: the hard real-time scheduling model in which a job must be completed if it was admitted for execution by the online scheduler, and the firm real-time scheduling model in which the scheduler is allowed not to complete a job even if it was admitted for execution by the online scheduler. In both models, the objective is to maximize the sum of execution times of the jobs that were executed to completion, preemption is allowed, and the online scheduler must immediately decide, whenever a job arrives, whether to admit it for execution or reject it. We measure the competitive ratio of any online algorithm as the ratio of the value of the objective function obtained by this algorithm to that of the best possible offline algorithm. We show that no online algorithm can have a competitive ratio greater than 1-(1/α)+ε for hard real-time scheduling with K ≥ 1 machines and greater than 1- (3/(4[α]) + ε for firm real-time scheduling on a single machine, where ε > 0 may be arbitrarily small, even if the algorithm is allowed to know the value of á in advance. On the other hand, we exhibit a simple online scheduler that achieves a competitive ratio of at least 1-(1/α) in either of these models with K machines. The performance guarantee of our simple scheduler shows that it is in fact an optimal scheduler for hard real-time scheduling with K machines. We also describe an alternative scheduler for firm real-time scheduling on a single machine in which the competitive ratio does not go to zero as α approaches 1. Both of our schedulers do not know the value of α in advance. More... »

PAGES

96-107

Book

TITLE

Approximation Algorithms for Combinatorial Optimization

ISBN

978-3-540-67996-7
978-3-540-44436-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44436-x_11

DOI

http://dx.doi.org/10.1007/3-540-44436-x_11

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1006803205


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Rutgers University, Camden, 08102, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Computer Science, Rutgers University, Camden, 08102, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "DasGupta", 
        "givenName": "Bhaskar", 
        "id": "sg:person.0763403270.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Rutgers University, Camden, 08102, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Computer Science, Rutgers University, Camden, 08102, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Palis", 
        "givenName": "Michael A.", 
        "id": "sg:person.014544155027.25", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014544155027.25"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "In this paper, we derive bounds on performance guarantees of online algorithms for real-time preemptive scheduling of jobs with deadlines on K machines when jobs are characterized in terms of their minimum stretchf actor \u03b1 (or, equivalently, their maximum execution rate r = 1/\u03b1). We consider two well known preemptive models that are of interest from practical applications: the hard real-time scheduling model in which a job must be completed if it was admitted for execution by the online scheduler, and the firm real-time scheduling model in which the scheduler is allowed not to complete a job even if it was admitted for execution by the online scheduler. In both models, the objective is to maximize the sum of execution times of the jobs that were executed to completion, preemption is allowed, and the online scheduler must immediately decide, whenever a job arrives, whether to admit it for execution or reject it. We measure the competitive ratio of any online algorithm as the ratio of the value of the objective function obtained by this algorithm to that of the best possible offline algorithm. We show that no online algorithm can have a competitive ratio greater than 1-(1/\u03b1)+\u03b5 for hard real-time scheduling with K \u2265 1 machines and greater than 1- (3/(4[\u03b1]) + \u03b5 for firm real-time scheduling on a single machine, where \u03b5 > 0 may be arbitrarily small, even if the algorithm is allowed to know the value of \u00e1 in advance. On the other hand, we exhibit a simple online scheduler that achieves a competitive ratio of at least 1-(1/\u03b1) in either of these models with K machines. The performance guarantee of our simple scheduler shows that it is in fact an optimal scheduler for hard real-time scheduling with K machines. We also describe an alternative scheduler for firm real-time scheduling on a single machine in which the competitive ratio does not go to zero as \u03b1 approaches 1. Both of our schedulers do not know the value of \u03b1 in advance.", 
    "editor": [
      {
        "familyName": "Jansen", 
        "givenName": "Klaus", 
        "type": "Person"
      }, 
      {
        "familyName": "Khuller", 
        "givenName": "Samir", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44436-x_11", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-67996-7", 
        "978-3-540-44436-7"
      ], 
      "name": "Approximation Algorithms for Combinatorial Optimization", 
      "type": "Book"
    }, 
    "keywords": [
      "real-time scheduling model", 
      "online scheduler", 
      "online algorithm", 
      "hard real-time scheduling", 
      "scheduling model", 
      "real-time scheduling", 
      "competitive ratio", 
      "execution time", 
      "offline algorithm", 
      "performance guarantees", 
      "preemptive scheduling", 
      "scheduler", 
      "preemptive model", 
      "algorithm", 
      "execution", 
      "scheduling", 
      "objective function", 
      "machine", 
      "jobs", 
      "practical applications", 
      "deadlines", 
      "guarantees", 
      "preemption", 
      "model", 
      "applications", 
      "bounds", 
      "interest", 
      "terms", 
      "time", 
      "objective", 
      "sum", 
      "function", 
      "completion", 
      "ratio", 
      "values", 
      "paper"
    ], 
    "name": "Online Real-Time Preemptive Scheduling of Jobs with Deadlines", 
    "pagination": "96-107", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1006803205"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44436-x_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44436-x_11", 
      "https://app.dimensions.ai/details/publication/pub.1006803205"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_305.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44436-x_11"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-44436-x_11'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-44436-x_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44436-x_11'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-44436-x_11'


 

This table displays all metadata directly associated to this object as RDF triples.

108 TRIPLES      23 PREDICATES      62 URIs      55 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44436-x_11 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N5e6814e86dda4055ae5fa416890a5310
4 schema:datePublished 2000
5 schema:datePublishedReg 2000-01-01
6 schema:description In this paper, we derive bounds on performance guarantees of online algorithms for real-time preemptive scheduling of jobs with deadlines on K machines when jobs are characterized in terms of their minimum stretchf actor α (or, equivalently, their maximum execution rate r = 1/α). We consider two well known preemptive models that are of interest from practical applications: the hard real-time scheduling model in which a job must be completed if it was admitted for execution by the online scheduler, and the firm real-time scheduling model in which the scheduler is allowed not to complete a job even if it was admitted for execution by the online scheduler. In both models, the objective is to maximize the sum of execution times of the jobs that were executed to completion, preemption is allowed, and the online scheduler must immediately decide, whenever a job arrives, whether to admit it for execution or reject it. We measure the competitive ratio of any online algorithm as the ratio of the value of the objective function obtained by this algorithm to that of the best possible offline algorithm. We show that no online algorithm can have a competitive ratio greater than 1-(1/α)+ε for hard real-time scheduling with K ≥ 1 machines and greater than 1- (3/(4[α]) + ε for firm real-time scheduling on a single machine, where ε > 0 may be arbitrarily small, even if the algorithm is allowed to know the value of á in advance. On the other hand, we exhibit a simple online scheduler that achieves a competitive ratio of at least 1-(1/α) in either of these models with K machines. The performance guarantee of our simple scheduler shows that it is in fact an optimal scheduler for hard real-time scheduling with K machines. We also describe an alternative scheduler for firm real-time scheduling on a single machine in which the competitive ratio does not go to zero as α approaches 1. Both of our schedulers do not know the value of α in advance.
7 schema:editor N9f81613d1e6e4e30aa6fc6b33e0a862f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N2fab1e435f8c480d886cff0a7869dab5
12 schema:keywords algorithm
13 applications
14 bounds
15 competitive ratio
16 completion
17 deadlines
18 execution
19 execution time
20 function
21 guarantees
22 hard real-time scheduling
23 interest
24 jobs
25 machine
26 model
27 objective
28 objective function
29 offline algorithm
30 online algorithm
31 online scheduler
32 paper
33 performance guarantees
34 practical applications
35 preemption
36 preemptive model
37 preemptive scheduling
38 ratio
39 real-time scheduling
40 real-time scheduling model
41 scheduler
42 scheduling
43 scheduling model
44 sum
45 terms
46 time
47 values
48 schema:name Online Real-Time Preemptive Scheduling of Jobs with Deadlines
49 schema:pagination 96-107
50 schema:productId N87632f447c5f4f44b8033684d8522dd4
51 N8db5b0a47a8e4a3c87c76b14b794b7c8
52 schema:publisher Ne37ab34fe9e6492cb7e2817ccbb08897
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006803205
54 https://doi.org/10.1007/3-540-44436-x_11
55 schema:sdDatePublished 2022-05-20T07:45
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher Ne5a82babdd4044ef9a5451b8e687269c
58 schema:url https://doi.org/10.1007/3-540-44436-x_11
59 sgo:license sg:explorer/license/
60 sgo:sdDataset chapters
61 rdf:type schema:Chapter
62 N2fab1e435f8c480d886cff0a7869dab5 schema:isbn 978-3-540-44436-7
63 978-3-540-67996-7
64 schema:name Approximation Algorithms for Combinatorial Optimization
65 rdf:type schema:Book
66 N5e6814e86dda4055ae5fa416890a5310 rdf:first sg:person.0763403270.10
67 rdf:rest Nd3feb429180a42eaa143438ddaba865b
68 N65c341e50c4f4016adb7ac2d6b377288 rdf:first Nc9d6f95b6f9c4eaaa6af96d7da7dee1d
69 rdf:rest rdf:nil
70 N87632f447c5f4f44b8033684d8522dd4 schema:name dimensions_id
71 schema:value pub.1006803205
72 rdf:type schema:PropertyValue
73 N8db5b0a47a8e4a3c87c76b14b794b7c8 schema:name doi
74 schema:value 10.1007/3-540-44436-x_11
75 rdf:type schema:PropertyValue
76 N9f81613d1e6e4e30aa6fc6b33e0a862f rdf:first Nf66da8b03d444ab39b09906cd59df961
77 rdf:rest N65c341e50c4f4016adb7ac2d6b377288
78 Nc9d6f95b6f9c4eaaa6af96d7da7dee1d schema:familyName Khuller
79 schema:givenName Samir
80 rdf:type schema:Person
81 Nd3feb429180a42eaa143438ddaba865b rdf:first sg:person.014544155027.25
82 rdf:rest rdf:nil
83 Ne37ab34fe9e6492cb7e2817ccbb08897 schema:name Springer Nature
84 rdf:type schema:Organisation
85 Ne5a82babdd4044ef9a5451b8e687269c schema:name Springer Nature - SN SciGraph project
86 rdf:type schema:Organization
87 Nf66da8b03d444ab39b09906cd59df961 schema:familyName Jansen
88 schema:givenName Klaus
89 rdf:type schema:Person
90 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
91 schema:name Information and Computing Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
94 schema:name Artificial Intelligence and Image Processing
95 rdf:type schema:DefinedTerm
96 sg:person.014544155027.25 schema:affiliation grid-institutes:grid.430387.b
97 schema:familyName Palis
98 schema:givenName Michael A.
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014544155027.25
100 rdf:type schema:Person
101 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.430387.b
102 schema:familyName DasGupta
103 schema:givenName Bhaskar
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
105 rdf:type schema:Person
106 grid-institutes:grid.430387.b schema:alternateName Department of Computer Science, Rutgers University, Camden, 08102, NJ, USA
107 schema:name Department of Computer Science, Rutgers University, Camden, 08102, NJ, USA
108 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...