Complexity of shop-scheduling problems with fixed number of jobs: a survey
Autor(en): | Brucker, Peter Sotskov, Yu N. Werner, Frank |
Stichwörter: | ALGORITHM; Mathematics; Mathematics, Applied; Operations Research & Management Science | Erscheinungsdatum: | 2007 | Herausgeber: | SPRINGER HEIDELBERG | Journal: | MATHEMATICAL METHODS OF OPERATIONS RESEARCH | Volumen: | 65 | Ausgabe: | 3 | Startseite: | 461 | Seitenende: | 481 | Zusammenfassung: | The paper surveys the complexity results for job shop, flow shop, open shop and mixed shop scheduling problems when the number n of jobs is fixed while the number r of operations per job is not restricted. In such cases, the asymptotical complexity of scheduling algorithms depends on the number m of machines for a flow shop and an open shop problem, and on the numbers m and r for a job shop problem. It is shown that almost all shop-scheduling problems with two jobs can be solved in polynomial time for any regular criterion, while those with three jobs are NP-hard. The only exceptions are the two-job, m-machine mixed shop problem without operation preemptions (which is NP-hard for any non-trivial regular criterion) and the n-job, m-machine open shop problem with allowed operation preemptions (which is polynomially solvable for minimizing makespan). |
ISSN: | 14322994 | DOI: | 10.1007/s00186-006-0127-8 |
Zur Langanzeige
Seitenaufrufe
5
Letzte Woche
0
0
Letzter Monat
2
2
geprüft am 01.06.2024