A heuristic for a scheduling problem with communication delays

A heuristic for a scheduling problem with communication delays

0.00 Avg rating0 Votes
Article ID: iaor20003462
Country: United States
Volume: 45
Issue: 1
Start Page Number: 145
End Page Number: 147
Publication Date: Jan 1997
Journal: Operations Research
Authors: ,
Keywords: heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.