کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4951957 1441999 2017 26 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Parallel machine scheduling with restricted job rejection
ترجمه فارسی عنوان
برنامه ریزی ماشین موازی با رد کار محدود
کلمات کلیدی
برنامه ریزی، طرد شدن، الگوریتم های تقریبی، تجزیه و تحلیل بدترین مورد،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, ,