On the complexity of two machine job-shop scheduling with regular objective functions

Autor(en): Brucker, P
Kravchenko, SA
Sotskov, YN
Stichwörter: 3 JOBS; ALGORITHM; job-shop; Operations Research & Management Science; polynomial algorithm
Erscheinungsdatum: 1997
Herausgeber: SPRINGER
Volumen: 19
Ausgabe: 1
Startseite: 5
Seitenende: 10
For the nonpreemptive two machine job-shop scheduling problem with a fixed number of jobs and objective functions Sigma f(i) and max f(i), where f(i) are nondecreasing functions of the finish times of jobs i, polynomial algorithms are presented. This answers previous open questions about the complexity status of the corresponding problems with objective functions L(max), Sigma w(i) U-i, and Sigma w(i) T-i. We generalize these results by showing that the problem with any regular criterion can be solved in polynomial time.
ISSN: 01716468

Show full item record

Google ScholarTM