A parametric worst case analysis of the LPT heuristic for two uniform machines

A parametric worst case analysis of the LPT heuristic for two uniform machines

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

Reviews

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