کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871749 1440189 2018 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
ترجمه فارسی عنوان
زمانبندی کارهای طولی با نمودارهای ناسازگار مکعب در سه ماشین یکنواخت
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In the paper we consider the problem of scheduling n identical jobs on 3 uniform machines with speeds s1,s2, and s3 to minimize the schedule length. We assume that jobs are subjected to some kind of mutual exclusion constraints, modeled by a cubic incompatibility graph. We show that if the graph is 2-chromatic then the problem can be solved in O(n2) time. If the graph is 3-chromatic, the problem becomes NP-hard even if s1>s2=s3. However, in this case there exists a 10/7-approximation algorithm running in O(n3) time. Moreover, this algorithm solves the problem almost surely to optimality if 3s1/4≤s2=s3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 234, 10 January 2018, Pages 210-217
نویسندگان
, ,