THE EXACT LPT-BOUND FOR MAXIMIZING THE MINIMUM COMPLETION-TIME

被引：54

作者：

CSIRIK, J

KELLERER, H

WOEGINGER, G

机构：

[1] GRAZ TECH UNIV,INST MATH B,KOPERNIKUSGASSE 24,A-8010 GRAZ,AUSTRIA

[2] ATTILA JOZSEF UNIV,DEPT APPL COMP SCI,H-6701 SZEGED,HUNGARY

[3] GRAZ UNIV,INST STAT & OPERAT RES,A-8010 GRAZ,AUSTRIA

来源：

OPERATIONS RESEARCH LETTERS | 1992年 / 11卷 / 05期

基金：

匈牙利科学研究基金会;

关键词：

COMBINATORIAL PROBLEMS; SCHEDULING; SUBOPTIMAL ALGORITHMS;

D O I：

10.1016/0167-6377(92)90004-M

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the problem of assigning a set of jobs to a system of m identical processors in order to maximize the earliest processor completion time. It was known that the LPT-heuristic gives an approximation of worst case ratio at most 3/4. In this note we show that the exact worst case ratio of LPT is (3m - 1)/(4m - 2).

引用

页码：281 / 287

页数：7