A Heuristic for a Scheduling Problem with Communication Delays

This paper addresses a scheduling problem with interprocessor communication delays: the jobs and the communication delays are of unit length. The number of processors is unbounded. The aim is to minimize the makespan.

We develop a new list scheduling heuristic and we prove that its worst-case relative performance is 4/3.