Complexity of Scheduling Shops with No Wait in Process

Abstract

We show that obtaining minimum finish time schedules with no wait in process is NP-Hard for flow shops, job shops and open shops. Specifically, it is shown that the two processor job and open shop problems are NP-Hard even when jobs are restricted to have no task of length zero. The two processor flow shop problem is NP-Hard if jobs with only one task are permitted. Note that Gilmore and Gomory (Gilmore, P., R. Gomory. 1964. Sequencing a one state-variable machine: A solvable case of the travelling salesman problem. Oper. Res. 12 655–679.) have obtained a polynomial time algorithm for the two processor flow shop for the case where every job has two tasks. The 4-sum and 2-pair problems are also shown NP-Hard.