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

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

0.00 Avg rating—0 Votes
Article ID: iaor20084392
Country: Netherlands
Volume: 177
Issue: 2
Start Page Number: 1302
End Page Number: 1309
Publication Date: Mar 2007
Journal: European Journal of Operational Research
Authors: ,
Keywords: computational analysis
Abstract:

In this paper, we consider the single machine batching problem with family setup times to minimize maximum lateness. Recently, Cheng et al. proved that this problem is strongly NP-hard. This answers a long-standing open problem posed by J. Bruno and P. Downey. By a modification of the proof in Cheng et al., we show that this problem is still strongly NP-hard when the family setup times are identical.

Reviews

Required fields are marked *. Your email address will not be published.