Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.08.2016 | Ausgabe 4/2016

Journal of Scheduling 4/2016

Lawler’s minmax cost algorithm: optimality conditions and uncertainty

Zeitschrift:
Journal of Scheduling > Ausgabe 4/2016
Autoren:
Nadia Brauner, Gerd Finke, Yakov Shafransky, Dzmitry Sledneu

Abstract

The well-known \(O(n^2)\) minmax cost algorithm of Lawler (MANAGE SCI 19(5):544–546, 1973) was developed to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We propose two results related to Lawler’s algorithm. Lawler’s algorithm delivers one specific optimal schedule while there can exist other optimal schedules. We present necessary and sufficient conditions for the optimality of a schedule for the problem with strictly increasing cost functions. The second result concerns the same scheduling problem under uncertainty. The cost function for each job is of a special decomposable form and depends on the job completion time and on an additional numerical parameter, for which only an interval of possible values is known. For this problem we derive an \(O(n^2)\) algorithm for constructing a schedule that minimizes the maximum regret criterion . To obtain this schedule, we use Lawler’s algorithm as a part of our technique.

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

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

Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 4/2016

Journal of Scheduling 4/2016 Zur Ausgabe

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Wieviel digitale Transformation steckt im Informationsmanagement? Zum Zusammenspiel eines etablierten und eines neuen Managementkonzepts

Das Management des Digitalisierungsprozesses ist eine drängende Herausforderung für fast jedes Unternehmen. Ausgehend von drei aufeinander aufbauenden empirischen Untersuchungen lesen Sie hier, welche generellen Themenfelder und konkreten Aufgaben sich dem Management im Rahmen dieses Prozesses stellen. Erfahren Sie hier, warum das Management der digitalen Transformation als separates Konzept zum Informationsmanagement zu betrachten
und so auch organisatorisch separiert zu implementieren ist. Jetzt gratis downloaden!

Bildnachweise