کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871196 | 1440180 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A polynomial algorithm for the homogeneously non-idling scheduling problem of unit-time independent jobs on identical parallel machines
ترجمه فارسی عنوان
یک الگوریتم چند جملهای برای یک مسئله زمانبندی یکنواخت غیر تردد کارهای مستقل یکسانی در ماشینهای موازی مشابه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برنامه ریزی موازی، نمودار کارگردانی پیچیدگی الگوریتمی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we consider the homogeneous m-machine scheduling problem where unit-time jobs have to be scheduled within their time windows so that, for any subset of machines, the set of the time units at which at least one machine is busy, is an interval. For this problem, a time assignment of the jobs satisfying the time windows constraints is a schedule if it has a pyramidal profile and is a k-schedule if this profile property is satisfied up to level k only. We develop a generic algorithm to solve the problem and show it is correct using a proof that mainly relies on a necessary and sufficient condition for a schedule to exist proved in a previous paper. We finally show that the generic algorithm is polynomial. We conclude by giving the directions of ongoing works and by bringing open questions related to different variants of the basic non-idling m-machine scheduling problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 243, 10 July 2018, Pages 132-139
Journal: Discrete Applied Mathematics - Volume 243, 10 July 2018, Pages 132-139
نویسندگان
Philippe Chrétienne, Alain Quilliot,