A POLYNOMIAL ALGORITHM FOR THE 2 MACHINE JOB-SHOP SCHEDULING PROBLEM WITH A FIXED NUMBER OF JOBS

Autor(en): BRUCKER, P
Stichwörter: 2 MACHINE JOB-SHOP; Operations Research & Management Science; POLYNOMIAL ALGORITHM
Erscheinungsdatum: 1994
Herausgeber: SPRINGER VERLAG
Journal: OR SPEKTRUM
Volumen: 16
Ausgabe: 1
Startseite: 5
Seitenende: 7
Zusammenfassung: 
It is shown that the job-shop problem with two machines and a fixed number of k jobs with makespan criterion J2n = kC(max) is polynomially solvable. Sotskov and Shakhlevich (1993) have shown that problem J3n = 3C(max) is NP-hard. Furthermore it is well known that Jn=2C(max) in polynomially solvable. Thus, our result settles the remaining open question concerning the complexity status of job-shop problems with fixed numbers of jobs and machines.
ISSN: 01716468
DOI: 10.1007/BF01719698

Show full item record

Page view(s)

1
Last Week
0
Last month
0
checked on Feb 22, 2024

Google ScholarTM

Check

Altmetric