A Heuristic for a Scheduling Problem with Communication Delays

Alix Munier and Jean-Claude König
Additional contact information
Alix Munier: Université P. et M. Curie, Paris, France
Jean-Claude König: Université d'Evry, Evry, France

Operations Research, 1997, vol. 45, issue 1, 145-147

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 (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.1.145 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:45:y:1997:i:1:p:145-147

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().