A PARAMETRIC WORST-CASE ANALYSIS OF THE LPT HEURISTIC FOR 2 UNIFORM MACHINES

Authors
MIREAULT P ORLIN JB VOHRA RV
Citation
P. Mireault et al., A PARAMETRIC WORST-CASE ANALYSIS OF THE LPT HEURISTIC FOR 2 UNIFORM MACHINES, Operations research, 45(1), 1997, pp. 116-125
Citations number
9
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research → ACNP
ISSN journal
0030364X
Volume
45
Issue
1
Year of publication
1997
Pages
116 - 125
Database
ISI
SICI code
0030-364X(1997)45:1<116:APWAOT>2.0.ZU;2-S
Abstract
We consider the problem of minimizing the makespan when scheduling tas ks on two uniform parallel machines, where one machine is q times as e fficient on each task as is the other. We compute the maximum relative error of the LPT (largest processing time first) heuristic as an expl icit function of cl. In the special case that the two machines are ide ntical (q = 1), our problem and heuristic reduce to the problem and he uristic analyzed by Graham (1969).