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: | Munier A., Konig J.C. |
Keywords: | heuristics |
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.