کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4959017 | 1445465 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minmax scheduling with acceptable lead-times: Extensions to position-dependent processing times, due-window and job rejection
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In this paper we study several extensions of the minmax DIF model. First, we consider general position-dependent job processing times. Then we extend the model to a setting of a due-window for acceptable lead-times. Here, the assumption is that a time interval exists, such that due-dates assigned to be within this interval are not penalized. The last extension of the DIF model is to a setting allowing job-rejection. This option reflects many real-life situations, where the scheduler may decide to process only a subset of the jobs, and the rejected jobs are penalized. The first two extensions are shown to be polynomially solvable: we introduce solution algorithms requiring O(n3) and O(n4) time, respectively, where n is the number of jobs. The last extension (assuming job-rejection) is proved to be NP-hard in the ordinary sense, and an efficient pseudo-polynomial dynamic programming algorithm is introduced.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 83, July 2017, Pages 150-156
Journal: Computers & Operations Research - Volume 83, July 2017, Pages 150-156
نویسندگان
Enrique Gerstl, Baruch Mor, Gur Mosheiov,