Abstract
We investigate the problem of minimizing the makespan (resp. the sumof completion time) fort hemultiprocessor 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 task soft he precedence graph have unit execution times, where the multiprocessor is composed of an unrestricted number of machines, and where cde notes the communication de lay between two tasks i and j submitted to aprecedence constraint and to be processed by two different machines. The problembe comes polynomial whe never them ake span 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 un itary tasks in the presence of large communication delays.We provide apolynomial-time approximation algorithm with performance ratio 2(c+1) 3 with c≥2.