# zbMATH — the first resource for mathematics

A heuristic for a scheduling problem with communication delays. (English) Zbl 0892.90104
Summary: 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\over 3}$$.

##### MSC:
 90B35 Deterministic scheduling theory in operations research
Full Text: