ISSN:
1436-6304
Keywords:
Job-shop
;
polynomial algorithm
;
Job-Shop
;
polynomialer Algorithmus
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung Für das Zweimaschinen-Job-Shop-Problem ohne Arbeitsunterbrechnungen und den Zielfunktionen Σf i bzw. maxf i , wobei dief i monotone Funktionen der Fertigstellungszeiten der Jobsi sind, werden für den Fall fester Jobanzahlen polynomiale Algorithmen angegeben. Dies beantwortet insbesondere die bislang offene Frage nach dem Komplexitätsstatus des obigen Problems für die ZielfunktionenL max, Σw i U i , und Σw i U. Schließlich zeigen wir, daß das Problem mit beliebiger regulärer Zielfunktion ebenfalls polynomial lösbar ist.
Notes:
Abstract For the nonpreemptive two machine job-shop scheduling problem with a fixed number of jobs and objective functions Σf i and maxf i , wheref i are nondecreasing functions of the finish times of jobsi, polynomial algorithms are presented. This answers previous open questions about the complexity status of the corresponding problems with objective functionsL max, Σw i U i , and Σw i U. We generalize these results by showing that the problem with any regular criterion can be solved in polynomial time.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01539799
