Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 225-229 |
| Number of pages | 5 |
| Journal | Journal of Scheduling |
| Volume | 4 |
| Issue number | 4 |
| Publication status | Published - 2001 |
Keywords
- Family scheduling
- Number of late jobs
- Strong NP-hardness
ASJC Scopus subject areas
- Artificial Intelligence
- Software
- Management Science and Operations Research
- General Engineering