Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

14.02.2017 | Ausgabe 3/2017

Journal of Scheduling 3/2017

The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays

Zeitschrift:
Journal of Scheduling > Ausgabe 3/2017
Autoren:
Aurélien Carlier, Claire Hanen, Alix Munier Kordon

Abstract

We consider a finite set of unit time execution tasks with release dates, due dates and precedence delays. The machines are partitioned into k classes. Each task requires one machine from a fixed class to be executed. The problem is the existence of a feasible schedule. This general problem is known to be \(\mathcal {NP}\)-complete; many studies were devoted to the determination of polynomial time algorithms for some special subcases, most of them based on a particular list schedule. The Garey–Johnson and Leung–Palem–Pnueli algorithms (respectively GJ and LPP in short) are both improving the due dates to build a priority list. They are modifying them using necessary conditions until a fixed point is reached. The present paper shows that these two algorithms are different implementations of the same generic one. The main consequence is that all the results valid for GJ algorithm are also for LPP and vice versa.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 3/2017

Journal of Scheduling 3/2017 Zur Ausgabe

Premium Partner

    Bildnachweise