nach oben

Journal of Scheduling

Erschienen in:

01.06.2015

A note on the Coffman–Sethi bound for LPT scheduling

verfasst von: James D. Blocher, Sergey Sevastyanov

Erschienen in: Journal of Scheduling | Ausgabe 3/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Makespan minimization on a set of parallel machines is one of the most widely studied problems in scheduling theory. A new result is presented which improves on the classical Coffman–Sethi a posteriori bound on the relative error of the LPT algorithm. It is shown that the ratio of these two bounds (the old one to the new one) can be arbitrarily large.

Vorheriger Artikel A note on the preemptive scheduling to minimize total completion time with release time and deadline constraints

Nächster Artikel Erratum to: A survey on offline scheduling with rejection

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Chen, B. (1993). A note on LPT scheduling. Operations Research Letters, 14, 139–142.CrossRef

Coffman, E. G., & Sethi, R. (1976). A generalized bound on LPT sequencing. Revue Francaise d’ Automatique Informatique, Recherche Operationnelle Supplement, 10, 17–25.

Garey, M. R., & Johnson, D. S. (1978). Strong NP-completeness results: Motivation, examples and implications. Journal of the Association for Computing Machinery, 25, 499–508.CrossRef

Graham, R. L. (1969). Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17(2), 416–429.

Pinedo, M. (2012). Scheduling: Theory, algorithms and systems (4th ed.). New York, NY: Springer.CrossRef

Titel: A note on the Coffman–Sethi bound for LPT scheduling
verfasst von: James D. Blocher
Sergey Sevastyanov
Publikationsdatum: 01.06.2015
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 3/2015
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-015-0419-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2015

Energetic reasoning for energy-constrained scheduling with a continuous resource

A note on -hardness of preemptive mean flow-time scheduling for parallel machines

Schedule generation scheme for solving multi-mode resource availability cost problem by modified particle swarm optimization

Minimizing the expected makespan of a project with stochastic activity durations under resource constraints

A note on the preemptive scheduling to minimize total completion time with release time and deadline constraints

The impact of core precedences in a cyclic RCPSP with precedence delays