An approximation algorithm for scheduling dependent tasks on m processors with small communication delays

This paper defines and studies an approximation algorithm for scheduling tasks with small communication delays on parallel processors. In a first step, a schedule for the relaxed problem instance with an unlimited number of processors is generated. Then this solution is used to solve the resource conflicts during the scheduling phase on m processors, with a rather unusual feature: a feasible task may be tactically delayed, even inducing idleness on a processor in order to wait for a more important task. The relative worst case performance of this algorithm is analysed with respect to the ratio between communication times and processing times and to the performance of the relaxed solution. It improves significantly the best known performance ratio of an algorithm for this problem (7/3 against 3)