کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4960214 | 1445968 | 2017 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Approximation algorithms for the workload partition problem and applications to scheduling with variable processing times
ترجمه فارسی عنوان
الگوریتم های تقریبی برای مشکل پارتیشن کاری و برنامه های کاربردی برای برنامه ریزی با زمان پردازش متغیر
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکل پارتیشن کاری برنامه ریزی، دستگاه های موازی مشابه زمان پردازش کنترل شده، الگوریتم های تقریبی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
In the Workload Partition Problem(WPP) we are given a set of n jobs to be scheduled on a set of m
identical parallel machines. Each job has its own workload and the scheduling cost on each machine is a convex function of the total workload of the jobs assigned to it. The objective is to minimize the total cost on the set of m machines. Shabtay and Kaspi (2006) showed that the WPP is equivalent to a scheduling problem on m identical machines with controllable processing times and with the scheduling criterion of minimizing the makespan. They also proved that the WPP is NP-hard when m=2. However, they left as an open question whether the problem is ordinary or strongly NP-hard. Moreover, they provided no practical tools to solve the problem. We bridge those gaps in the literature by showing that the WWP problem is strongly NP-hard when m is part of the input. Furthermore, we present two different approximation algorithms for solving the WWP problem. The first one is a fully polynomial time approximation scheme (FPTAS) for a fixed number of machines, while the second is a modification of the well-known longest processing time (LPT) heuristic. We show that our modified LPT heuristic guarantees a solution with a constant approximation ratio, whose value depends on the instance parameters.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 256, Issue 2, 16 January 2017, Pages 384-391
Journal: European Journal of Operational Research - Volume 256, Issue 2, 16 January 2017, Pages 384-391
نویسندگان
Daniel Oron, Dvir Shabtay, George Steiner,