The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard

In this paper, we consider the single machine batching problem with family setup times to minimize maximum lateness. Recently, Cheng et al. [T.C.E. Cheng, C.T. Ng, J.J. Yuan, The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard, Journal of Scheduling 6 (2003) 483–490] proved that this problem is strongly NP-hard. This answers a long-standing open problem posed by J. Bruno and P. Downey [Complexity of task sequencing with deadlines, setup times and changeover costs, SIAM Journal on Computing 7 (1978) 393–404]. By a modification of the proof in Cheng et al. (2003), we show that this problem is still strongly NP-hard when the family setup times are identical.