کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871749 | 1440189 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
ترجمه فارسی عنوان
زمانبندی کارهای طولی با نمودارهای ناسازگار مکعب در سه ماشین یکنواخت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 234, 10 January 2018, Pages 210-217
نویسندگان
Hanna FurmaÅczyk, Marek Kubale,