SHORT SHOP SCHEDULES

We consider the open shop, job shop, and flow shop scheduling problems with integral processing times. We give polynomial-time algorithms to determine if an instance has a schedule of length at most 3, and show that deciding if there is a schedule of length at most 4 is NP-comple te. The latter result implies that, unless P = NP. there does not exis t a polynomial-time approximation algorithm for any of these problems that constructs a schedule with length guaranteed to be strictly less than 5/4 times the optimal length. This work constitutes the first non trivial theoretical evidence that shop scheduling problems are hard to solve even approximately.