| Article ID: | iaor2008171 |
| Country: | United Kingdom |
| Volume: | 6 |
| Issue: | 5 |
| Start Page Number: | 483 |
| End Page Number: | 490 |
| Publication Date: | Sep 2003 |
| Journal: | Journal of Scheduling |
| Authors: | Cheng T.C. Edwin, Yuan J.J., Ng C.T. |
| Keywords: | computational analysis |
In this paper, we consider the single machine batching problem with family setup times to minimize maximum lateness. While the problem was proved to be binary NP-hard in 1978, whether the problem is strongly NP-hard is a long-standing open question. We show that this problem is strongly NP-hard.