کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10348313 | 699390 | 2012 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Scheduling jobs on identical machines with agreement graph
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Scheduling jobs on identical machines with agreement graph Scheduling jobs on identical machines with agreement graph](/preview/png/10348313.png)
چکیده انگلیسی
We consider the following problem of scheduling with agreements: a set of jobs must be scheduled non-preemptively on identical machines subject to constraints that only some specific jobs can be scheduled concurrently on different machines. These constraints are represented by an agreement graph and the aim is to minimize the makespan. This problem is NP-hard. We study the complexity of the problem for two machines and arbitrary bipartite agreement graphs, in particular we prove the NP-hardness of the open problem proposed in the literature which is the case of two machines with processing times at most 3. We propose list algorithms with empirical results for the problem in the general case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 39, Issue 2, February 2012, Pages 382-390
Journal: Computers & Operations Research - Volume 39, Issue 2, February 2012, Pages 382-390
نویسندگان
Mohamed Bendraouche, Mourad Boudhar,