Nikhil Bansal, José R. Correa, et al.
Mathematics of Operations Research
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.
Nikhil Bansal, José R. Correa, et al.
Mathematics of Operations Research
Dan A. Iancu, Mayank Sharma, et al.
Operations Research
Klaus Jansen, Roberto Solis-Oba, et al.
SIAM Journal on Discrete Mathematics
Jon Lee, Vahab S. Mirrokni, et al.
STOC 2009