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

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 ....

Full description

Saved in:
Bibliographic Details
Published in:Operations research 1997-01, Vol.45 (1), p.116-125
Main Authors: Mireault, Paul, Orlin, James B, Vohra, Rakesh V
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
approximations/heuristic
Exact sciences and technology
Heuristic
Heuristics
Linear programming
Machinery
multiple machine
Operational research and scientific management
Operational research. Management science
Operations research
Optimization
Production scheduling
Scheduling
Scheduling, sequencing
Studies
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.).
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.45.1.116