کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
393841 665690 2013 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Parallel machine scheduling and common due window assignment with job independent earliness and tardiness costs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
Parallel machine scheduling and common due window assignment with job independent earliness and tardiness costs
چکیده انگلیسی

We study problems of scheduling n jobs on m identical parallel machines, in which a common due window has to be assigned to all jobs. If a job is completed within the due window, then it incurs no scheduling cost. Otherwise, an earliness or tardiness cost is incurred. The job completion times as well as the due window location and size are integer valued decision variables. The objective is to find a job schedule as well as location and size of the due window such that a sum of costs associated with job earliness, job tardiness and due window location and size is minimized. The costs are arbitrary nondecreasing and job independent functions. We establish a number of properties of optimal solutions and derive dynamic programming algorithms, which are pseudopolynomial if the number of machines is a constant. The single machine case, in which the due window size cost is a discretely convex or concave nondecreasing function and all the other cost functions are linear, is shown to be polynomially solvable.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 224, 1 March 2013, Pages 109–117
نویسندگان
, , , , ,