کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
394594 665814 2010 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Scheduling with a common due-window: Polynomially solvable cases
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
Scheduling with a common due-window: Polynomially solvable cases
چکیده انگلیسی

The single machine scheduling problem to minimize maximum weighted absolute deviations of job completion times from a common due-date, is known to be NP-hard. However, two special cases have been shown to have polynomial time solutions: the case of unit processing time jobs, and the case of due-date assignment for a given job sequence. We extend both cases to a setting of a common due-window. We show that the unit-job problem includes 12 different sub-cases, depending on the size and location of the (given) due-window. Scheduling and due-window assignment for a given job sequence is solved for a single machine, for parallel identical machines and for flow-shops. For each of the above cases, an appropriate special-structured linear program is presented.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 180, Issue 8, 15 April 2010, Pages 1492–1505
نویسندگان
, ,