کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
477464 1446163 2008 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Single-machine scheduling against due dates with past-sequence-dependent setup times
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Single-machine scheduling against due dates with past-sequence-dependent setup times
چکیده انگلیسی

Recently Koulamas and Kyparisis [Koulamas, C., Kyparisis, G.J., in press. Single-machine scheduling with past-sequence-dependent setup times. European Journal of Operational Research] introduced past-sequence-dependent setup times to scheduling problems. This means that the setup time of a job is proportionate to the sum of processing times of the jobs already scheduled. Koulamas and Kyparisis [Koulamas, C., Kyparisis, G.J., in press. Single-machine scheduling with past-sequence-dependent setup times. European Journal of Operational Research] were able to show for a number of single-machine scheduling problems with completion time goals that they remain polynomially solvable. In this paper we extend the analysis to problems with due dates. We demonstrated that some problems remain polynomially solvable. However, for some other problems well-known polynomially solution approaches do not guarantee optimality any longer. Consequently we concentrated on finding polynomially solvable special cases.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 191, Issue 2, 1 December 2008, Pages 587–592
نویسندگان
, ,