کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
439231 | 690470 | 2008 | 13 صفحه PDF | دانلود رایگان |

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.
Journal: Theoretical Computer Science - Volume 401, Issues 1–3, 23 July 2008, Pages 107-119