کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10332230 | 687196 | 2005 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of preemptive minsum scheduling on unrelated parallel machines
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We show that the problems of minimizing total completion time and of minimizing the number of late jobs on unrelated parallel machines, when preemption is allowed, are both NP-hard in the strong sense. The former result settles a long-standing open question and is remarkable since the non-preemptive version is known to be solvable in polynomial time. A special case of the unrelated machine model is the identical machine model with the restriction that a job can only be processed on a specific subset of the machines. We show that in this model the problem of minimizing total completion time, when preemption is allowed, can be solved in polynomial time by proving that the use of preemption is redundant.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Algorithms - Volume 57, Issue 1, September 2005, Pages 37-48
Journal: Journal of Algorithms - Volume 57, Issue 1, September 2005, Pages 37-48
نویسندگان
René Sitters,