A parametric worst case analysis of the LPT heuristic for two uniform machines
成果类型：
Article
署名作者：
Mireault, P; Orlin, JB; Vohra, RV
署名单位：
Universite de Montreal; Massachusetts Institute of Technology (MIT); University System of Ohio; Ohio State University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.45.1.116
发表日期：
1997
页码：
116-125
关键词：
摘要：
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 (1969).