Complexity of Scheduling Shops with No Wait in Process

1 November 1979

journal article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research

Vol. 4 (4) , 448-457
https://doi.org/10.1287/moor.4.4.448

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.

Keywords

This publication has 0 references indexed in Scilit: