کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951957 | 1441999 | 2017 | 26 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Parallel machine scheduling with restricted job rejection
ترجمه فارسی عنوان
برنامه ریزی ماشین موازی با رد کار محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برنامه ریزی، طرد شدن، الگوریتم های تقریبی، تجزیه و تحلیل بدترین مورد،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper we study parallel-machine scheduling with job rejection, where the total processing time of the rejected jobs is required to be no greater than a predefined bound. The objective is to minimize the makespan of the accepted jobs plus the total penalty cost of the rejected jobs. The scheduling problem is NP-hard in the strong sense. We present a 2-approximation algorithm with a time complexity of O(nlogâ¡n) by making use of specific data structure. We also develop a polynomial time approximation scheme (PTAS). Due to the job rejection restriction, some techniques for knapsack problems are applied in the development of our PTAS.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 690, 22 August 2017, Pages 1-11
Journal: Theoretical Computer Science - Volume 690, 22 August 2017, Pages 1-11
نویسندگان
Xueling Zhong, Jinwen Ou,