Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2000-09

AUTHORS

Piotr Berman, Bhaskar Dasgupta

ABSTRACT

We consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem discussed here were already treated by Bar-Noy et al. (Proc. 31st ACM STOC, 1999, pp. 622–631; http://www.eng.tau.ac.il/∼amotz/). Our main contribution is to provide algorithms that do not use linear programming, are simple and much faster than the corresponding ones proposed in Bar-Noy et al. (ibid., 1999), while either having the same quality of approximation or improving it. More precisely, compared to the results of in Bar-Noy et al. (ibid., 1999), our pseudo-polynomial algorithm for multiple unrelated machines and all of our strongly-polynomial algorithms have better performance ratios, all of our algorithms run much faster, are combinatorial in nature and avoid linear programming. Finally, we show that algorithms with better performance ratios than 2 are possible if the stretch factors of the jobs are bounded; a straightforward consequence of this result is an improvement of the ratio of an optimal solution of the integer programming formulation of the JISP2 problem (see Spieksma, Journal of Scheduling, vol. 2, pp. 215–227, 1999) to its linear programming relaxation. More... »

PAGES

307-323

Identifiers

URI

http://scigraph.springernature.com/pub.10.1023/a:1009822211065

DOI

http://dx.doi.org/10.1023/a:1009822211065

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Rutgers University, 08102, Camden, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Computer Science, Rutgers University, 08102, Camden, 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"
      }
    ], 
    "datePublished": "2000-09", 
    "datePublishedReg": "2000-09-01", 
    "description": "We consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem discussed here were already treated by Bar-Noy et al. (Proc. 31st ACM STOC, 1999, pp. 622\u2013631; http://www.eng.tau.ac.il/\u223camotz/). Our main contribution is to provide algorithms that do not use linear programming, are simple and much faster than the corresponding ones proposed in Bar-Noy et al. (ibid., 1999), while either having the same quality of approximation or improving it. More precisely, compared to the results of in Bar-Noy et al. (ibid., 1999), our pseudo-polynomial algorithm for multiple unrelated machines and all of our strongly-polynomial algorithms have better performance ratios, all of our algorithms run much faster, are combinatorial in nature and avoid linear programming. Finally, we show that algorithms with better performance ratios than 2 are possible if the stretch factors of the jobs are bounded; a straightforward consequence of this result is an improvement of the ratio of an optimal solution of the integer programming formulation of the JISP2 problem (see Spieksma, Journal of Scheduling, vol. 2, pp. 215\u2013227, 1999) to its linear programming relaxation.", 
    "genre": "article", 
    "id": "sg:pub.10.1023/a:1009822211065", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1036683", 
        "issn": [
          "1382-6905", 
          "1573-2886"
        ], 
        "name": "Journal of Combinatorial Optimization", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "4"
      }
    ], 
    "keywords": [
      "better performance ratio", 
      "Bar-Noy", 
      "throughput maximization", 
      "real-time scheduling", 
      "multi-phase algorithm", 
      "pseudo-polynomial algorithm", 
      "linear programming", 
      "integer programming formulation", 
      "linear programming relaxation", 
      "more machines", 
      "performance ratio", 
      "polynomial algorithm", 
      "optimal solution", 
      "algorithm", 
      "unrelated machines", 
      "main contribution", 
      "programming relaxation", 
      "programming formulation", 
      "machine", 
      "programming", 
      "same quality", 
      "stretch factor", 
      "release time", 
      "maximization", 
      "scheduling", 
      "deadlines", 
      "jobs", 
      "version", 
      "solution", 
      "quality", 
      "results", 
      "profit", 
      "improvement", 
      "one", 
      "time", 
      "approximation", 
      "contribution", 
      "formulation", 
      "nature", 
      "corresponding ones", 
      "straightforward consequence", 
      "al", 
      "ratio", 
      "consequences", 
      "relaxation", 
      "factors", 
      "problem"
    ], 
    "name": "Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling", 
    "pagination": "307-323", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1037941601"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1023/a:1009822211065"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1023/a:1009822211065", 
      "https://app.dimensions.ai/details/publication/pub.1037941601"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-09-02T15:48", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_308.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1023/a:1009822211065"
  }
]
 

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.1023/a:1009822211065'

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.1023/a:1009822211065'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1009822211065'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1009822211065'


 

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

122 TRIPLES      20 PREDICATES      74 URIs      64 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1023/a:1009822211065 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 anzsrc-for:0102
4 anzsrc-for:0103
5 schema:author Nb3e15f81b19e4f9b9e7daadfe52dc4eb
6 schema:datePublished 2000-09
7 schema:datePublishedReg 2000-09-01
8 schema:description We consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem discussed here were already treated by Bar-Noy et al. (Proc. 31st ACM STOC, 1999, pp. 622–631; http://www.eng.tau.ac.il/∼amotz/). Our main contribution is to provide algorithms that do not use linear programming, are simple and much faster than the corresponding ones proposed in Bar-Noy et al. (ibid., 1999), while either having the same quality of approximation or improving it. More precisely, compared to the results of in Bar-Noy et al. (ibid., 1999), our pseudo-polynomial algorithm for multiple unrelated machines and all of our strongly-polynomial algorithms have better performance ratios, all of our algorithms run much faster, are combinatorial in nature and avoid linear programming. Finally, we show that algorithms with better performance ratios than 2 are possible if the stretch factors of the jobs are bounded; a straightforward consequence of this result is an improvement of the ratio of an optimal solution of the integer programming formulation of the JISP2 problem (see Spieksma, Journal of Scheduling, vol. 2, pp. 215–227, 1999) to its linear programming relaxation.
9 schema:genre article
10 schema:isAccessibleForFree false
11 schema:isPartOf N636d85b67bf54499be921701dddbdd3b
12 N93cd896298314af89fa4b72565d407de
13 sg:journal.1036683
14 schema:keywords Bar-Noy
15 al
16 algorithm
17 approximation
18 better performance ratio
19 consequences
20 contribution
21 corresponding ones
22 deadlines
23 factors
24 formulation
25 improvement
26 integer programming formulation
27 jobs
28 linear programming
29 linear programming relaxation
30 machine
31 main contribution
32 maximization
33 more machines
34 multi-phase algorithm
35 nature
36 one
37 optimal solution
38 performance ratio
39 polynomial algorithm
40 problem
41 profit
42 programming
43 programming formulation
44 programming relaxation
45 pseudo-polynomial algorithm
46 quality
47 ratio
48 real-time scheduling
49 relaxation
50 release time
51 results
52 same quality
53 scheduling
54 solution
55 straightforward consequence
56 stretch factor
57 throughput maximization
58 time
59 unrelated machines
60 version
61 schema:name Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling
62 schema:pagination 307-323
63 schema:productId N44594b61733c4d73b321e9cb19aebd2a
64 N8a946cb171cd492ea5724cb01ffa9204
65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037941601
66 https://doi.org/10.1023/a:1009822211065
67 schema:sdDatePublished 2022-09-02T15:48
68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
69 schema:sdPublisher N6a489b302d7547ac9f9f00f6c27ca0d4
70 schema:url https://doi.org/10.1023/a:1009822211065
71 sgo:license sg:explorer/license/
72 sgo:sdDataset articles
73 rdf:type schema:ScholarlyArticle
74 N26cb18ef38b847598351e8c20e5127d6 rdf:first sg:person.0763403270.10
75 rdf:rest rdf:nil
76 N44594b61733c4d73b321e9cb19aebd2a schema:name doi
77 schema:value 10.1023/a:1009822211065
78 rdf:type schema:PropertyValue
79 N636d85b67bf54499be921701dddbdd3b schema:issueNumber 3
80 rdf:type schema:PublicationIssue
81 N6a489b302d7547ac9f9f00f6c27ca0d4 schema:name Springer Nature - SN SciGraph project
82 rdf:type schema:Organization
83 N8a946cb171cd492ea5724cb01ffa9204 schema:name dimensions_id
84 schema:value pub.1037941601
85 rdf:type schema:PropertyValue
86 N93cd896298314af89fa4b72565d407de schema:volumeNumber 4
87 rdf:type schema:PublicationVolume
88 Nb3e15f81b19e4f9b9e7daadfe52dc4eb rdf:first sg:person.01274506210.27
89 rdf:rest N26cb18ef38b847598351e8c20e5127d6
90 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
91 schema:name Mathematical Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
94 schema:name Pure Mathematics
95 rdf:type schema:DefinedTerm
96 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
97 schema:name Applied Mathematics
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
100 schema:name Numerical and Computational Mathematics
101 rdf:type schema:DefinedTerm
102 sg:journal.1036683 schema:issn 1382-6905
103 1573-2886
104 schema:name Journal of Combinatorial Optimization
105 schema:publisher Springer Nature
106 rdf:type schema:Periodical
107 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
108 schema:familyName Berman
109 schema:givenName Piotr
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
111 rdf:type schema:Person
112 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.430387.b
113 schema:familyName Dasgupta
114 schema:givenName Bhaskar
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
116 rdf:type schema:Person
117 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA
118 schema:name Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA
119 rdf:type schema:Organization
120 grid-institutes:grid.430387.b schema:alternateName Department of Computer Science, Rutgers University, 08102, Camden, NJ, USA
121 schema:name Department of Computer Science, Rutgers University, 08102, Camden, NJ, USA
122 rdf:type schema:Organization
 




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


...