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.
- Maximum lateness
- Multi-operation jobs
ASJC Scopus subject areas
- Industrial and Manufacturing Engineering
- Management Science and Operations Research