Complexity of shop-scheduling problems with fixed number of jobs: a survey

What is it about?

This 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). 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).

Featured Image