Jon Lee, Vahab S. Mirrokni, et al.
SIAM Journal on Discrete Mathematics
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.
Jon Lee, Vahab S. Mirrokni, et al.
SIAM Journal on Discrete Mathematics
Alexander Kononov, Sergey Sevastyanov, et al.
Journal of Scheduling
Marcin Bienkowski, Jarosław Byrka, et al.
Journal of Scheduling
Carlile Lavor, Jon Lee, et al.
Optimization Letters