| Article ID: | iaor20003464 |
| Country: | United States |
| Volume: | 45 |
| Issue: | 2 |
| Start Page Number: | 288 |
| End Page Number: | 294 |
| Publication Date: | Mar 1997 |
| Journal: | Operations Research |
| Authors: | Hurkens C.A.J., Williamson David P., Hoogeveen J.A., Hall Leslie A., Sevastjanov S.V., Shmoys D.B. |
| Keywords: | computational analysis |
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-complete. The latter result implies that, unless P = NP, there does not exist 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 nontrivial theoretical evidence that shop scheduling problems are hard to solve even approximately.