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", 
    "inLanguage": "en", 
    "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", 
      "main contribution", 
      "unrelated machines", 
      "programming relaxation", 
      "programming formulation", 
      "machine", 
      "programming", 
      "stretch factor", 
      "same quality", 
      "release time", 
      "maximization", 
      "scheduling", 
      "deadlines", 
      "jobs", 
      "version", 
      "solution", 
      "quality", 
      "results", 
      "profit", 
      "improvement", 
      "one", 
      "time", 
      "approximation", 
      "contribution", 
      "formulation", 
      "nature", 
      "corresponding ones", 
      "straightforward consequence", 
      "al", 
      "ratio", 
      "relaxation", 
      "consequences", 
      "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-05-20T07:21", 
    "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/article/article_342.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.

123 TRIPLES      21 PREDICATES      75 URIs      65 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 Ndef9360f150e48bd96a6c7090e7bd8ed
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:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf N93182202f96542709dc89110b4447e91
13 Nd6f7867f4a6e4a5ab1016cce38064f2f
14 sg:journal.1036683
15 schema:keywords Bar-Noy
16 al
17 algorithm
18 approximation
19 better performance ratio
20 consequences
21 contribution
22 corresponding ones
23 deadlines
24 factors
25 formulation
26 improvement
27 integer programming formulation
28 jobs
29 linear programming
30 linear programming relaxation
31 machine
32 main contribution
33 maximization
34 more machines
35 multi-phase algorithm
36 nature
37 one
38 optimal solution
39 performance ratio
40 polynomial algorithm
41 problem
42 profit
43 programming
44 programming formulation
45 programming relaxation
46 pseudo-polynomial algorithm
47 quality
48 ratio
49 real-time scheduling
50 relaxation
51 release time
52 results
53 same quality
54 scheduling
55 solution
56 straightforward consequence
57 stretch factor
58 throughput maximization
59 time
60 unrelated machines
61 version
62 schema:name Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling
63 schema:pagination 307-323
64 schema:productId N09675b9479fe45cea2d53564e18f9bb9
65 N8e521d6ba62043969e55757d9f47592e
66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037941601
67 https://doi.org/10.1023/a:1009822211065
68 schema:sdDatePublished 2022-05-20T07:21
69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
70 schema:sdPublisher N4ae67b4cb47b45088b75f23370a7e869
71 schema:url https://doi.org/10.1023/a:1009822211065
72 sgo:license sg:explorer/license/
73 sgo:sdDataset articles
74 rdf:type schema:ScholarlyArticle
75 N09675b9479fe45cea2d53564e18f9bb9 schema:name doi
76 schema:value 10.1023/a:1009822211065
77 rdf:type schema:PropertyValue
78 N4ae67b4cb47b45088b75f23370a7e869 schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 N8e521d6ba62043969e55757d9f47592e schema:name dimensions_id
81 schema:value pub.1037941601
82 rdf:type schema:PropertyValue
83 N93182202f96542709dc89110b4447e91 schema:issueNumber 3
84 rdf:type schema:PublicationIssue
85 Ncb535c1552e8433998c118c97c0594f6 rdf:first sg:person.0763403270.10
86 rdf:rest rdf:nil
87 Nd6f7867f4a6e4a5ab1016cce38064f2f schema:volumeNumber 4
88 rdf:type schema:PublicationVolume
89 Ndef9360f150e48bd96a6c7090e7bd8ed rdf:first sg:person.01274506210.27
90 rdf:rest Ncb535c1552e8433998c118c97c0594f6
91 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
92 schema:name Mathematical Sciences
93 rdf:type schema:DefinedTerm
94 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
95 schema:name Pure Mathematics
96 rdf:type schema:DefinedTerm
97 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
98 schema:name Applied Mathematics
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
101 schema:name Numerical and Computational Mathematics
102 rdf:type schema:DefinedTerm
103 sg:journal.1036683 schema:issn 1382-6905
104 1573-2886
105 schema:name Journal of Combinatorial Optimization
106 schema:publisher Springer Nature
107 rdf:type schema:Periodical
108 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
109 schema:familyName Berman
110 schema:givenName Piotr
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
112 rdf:type schema:Person
113 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.430387.b
114 schema:familyName Dasgupta
115 schema:givenName Bhaskar
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
117 rdf:type schema:Person
118 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA
119 schema:name Department of Computer Science and Engineering, Pennsylvania State University, 16802, University Park, PA, USA
120 rdf:type schema:Organization
121 grid-institutes:grid.430387.b schema:alternateName Department of Computer Science, Rutgers University, 08102, Camden, NJ, USA
122 schema:name Department of Computer Science, Rutgers University, 08102, Camden, NJ, USA
123 rdf:type schema:Organization
 




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


...