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 .