A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines

Paul Mireault, James B. Orlin and Rakesh V. Vohra
Additional contact information
Paul Mireault: University of Montreal, Quebec, Canada
James B. Orlin: Massachusetts Institute of Technology, Cambridge, Massachusetts
Rakesh V. Vohra: Ohio State University, Columbus, Ohio

Operations Research, 1997, vol. 45, issue 1, 116-125

Abstract: We consider the problem of minimizing the makespan when scheduling tasks on two uniform parallel machines, where one machine is q times as efficient on each task as is the other. We compute the maximum relative error of the LPT (largest processing time first) heuristic as an explicit function of q . In the special case that the two machines are identical ( q = 1), our problem and heuristic reduce to the problem and heuristic analyzed by Graham (Graham, R. 1969. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17 416–429.).

Keywords: scheduling; approximations/heuristic; multiple machine (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.45.1.116 (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:116-125

Access Statistics for this article

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