| Article ID: | iaor20043596 |
| Country: | Belarus |
| Volume: | 1 |
| Start Page Number: | 37 |
| End Page Number: | 44 |
| Publication Date: | Mar 2004 |
| Journal: | Informatics |
| Authors: | Sotskov Yu. N. |
| Keywords: | networks: scheduling |
The paper surveys the complexity of job shop, flow shop, open shop and mixed shop scheduling problems when the number of jobs is less than or equal to the number of machines. Almost all the shop-scheduling problems with two jobs can be solved in polynomial time for any regular criterion, while those with three jobs are binary NP-hard. The 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 jobs m machines open shop problem with allowed operation preemptions, which is polynomially solvable for minimizing makespan.