کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
439231 690470 2008 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Complexity and approximation for precedence constrained scheduling problems with large communication delays
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Complexity and approximation for precedence constrained scheduling problems with large communication delays
چکیده انگلیسی

We investigate the problem of minimizing the makespan (resp. the sum of completion time) for the multiprocessor scheduling problem. We show that there is no hope of finding a ρ-approximation with ρ<1+1/(c+4) for minimization of the makespan (resp. 1+1/(2c+5) for total job completion time minimization) (unless P=NP) for the case where all the tasks of the precedence graph have unit execution times, where the multiprocessor is composed of an unrestricted number of machines, and where c denotes the communication delay between two tasks i and j submitted to a precedence constraint and to be processed by two different machines. The problem becomes polynomial whenever the makespan is at most (c+1). The (c+2) case is still partially open. Moreover, we both define and study a new scheduling approximation to schedule unitary tasks in the presence of large communication delays. We provide a polynomial-time approximation algorithm with performance ratio with c≥2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 401, Issues 1–3, 23 July 2008, Pages 107-119