Retsef Levi, Andrea Lodi, 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.
Retsef Levi, Andrea Lodi, et al.
Mathematics of Operations Research
Haim Kaplan, Moshe Lewenstein, et al.
FOCS 2003
Maxim Sviridenko
Information Processing Letters
Alexander Grigoriev, Maxim Sviridenko, et al.
IPCO 2005