Inapproximability results for no-wait job shop scheduling

We investigate the approximability of the no-wait job shop scheduling problem under the makespan criterion. We show that this problem is -hard (i) for the case of two machines with at most five operations per job, and (ii) for the case of three machines with at most three operations per job. Hence, these problems do not possess a polynomial time approximation scheme, unless .