Approximability and in-approximability results for no-wait shop scheduling

Abstract

We investigate the approximability of no-wait shop scheduling problems under the makespan criterion. In a flow shop, all jobs pass through the machines in the same ordering. In the more general job shop, the routes of the jobs are job-dependent. We present a polynomial time approximation scheme (PTAS) for the no-wait flow shop problem on any fixed number of machines. Unless P = NP, this result cannot be extended to the job shop problem on a fixed number of machines: We show that the no-wait job shop problem is APX-hard on (i) two machines with at most five operations per job, and on (ii) three machines with at most three operations per job.