دانلود مقاله ISI انگلیسی شماره 105647
ترجمه فارسی عنوان مقاله

زمانبندی کارهای طولی با نمودارهای ناسازگار مکعب در سه ماشین یکنواخت

عنوان انگلیسی
Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی
105647 2018 8 صفحه PDF
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Discrete Applied Mathematics, Volume 234, 10 January 2018, Pages 210-217

پیش نمایش مقاله
پیش نمایش مقاله  زمانبندی کارهای طولی با نمودارهای ناسازگار مکعب در سه ماشین یکنواخت

چکیده انگلیسی

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.