| Article ID: | iaor2003961 |
| Country: | United Kingdom |
| Volume: | 4 |
| Issue: | 4 |
| Start Page Number: | 225 |
| End Page Number: | 229 |
| Publication Date: | Jul 2001 |
| Journal: | Journal of Scheduling |
| Authors: | Cheng T.C. Edwin, Shafransky Yakov M., Liu Zhaohui |
The single-machine family scheduling problem of minimizing the number of late jobs has been known to be NP-hard, but whether it is NP-hard in the strong sense is cited as an open problem in several reviews. In this note, we prove that this problem is strongly NP-hard even if all set-up times and processing times are one unit.