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