Abstract
We propose a new approach for the proof of classical scheduling problem with communication delay. We study the problem of minimizing the makespan for the multiprocessor scheduling problem in the presence of a communication delay. We consider the problem in which all the tasks, in the precedence graph admit an unit execution time and the multiprocessor system is constituted by an unrestricted number of processors. The communication delays between two adjacency tasks i and j which are executed on two different processors is equal to one unit of time (UET-UCT model). In such a context, we prove that there is no heuristic with performance guarantee smaller than 7/6 (resp. 9/8) for the minimization of the length of the schedule (resp. the sum of the completion time).