A Heuristic for a Scheduling Problem with Communication Delays

Operations Research · 1997 · Volume 45 · Issue 1

Abstract

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.

Keywords

production/scheduling, precedence constraints, interprocessor communication delays, approximations/heuristics, continuous relaxation of an integer linear program

Enable JavaScript for citation tools and additional paper interactions.