کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
477856 | 1446205 | 2007 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The single machine batching problem with identical family setup times to minimize maximum lateness is strongly NP-hard
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 177, Issue 2, 1 March 2007, Pages 1302–1309
Journal: European Journal of Operational Research - Volume 177, Issue 2, 1 March 2007, Pages 1302–1309
نویسندگان
L.F. Lu, J.J. Yuan,