×

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
PDF BibTeX XML Cite
Full Text: DOI