NEW LOWER AND UPPER-BOUNDS FOR ONLINE SCHEDULING

被引：58

作者：

CHEN, B

VANVLIET, A

WOEGINGER, GJ

机构：

[1] ERASMUS UNIV ROTTERDAM,INST ECONOMETR,3000 DR ROTTERDAM,NETHERLANDS

[2] GRAZ TECH UNIV,INST THEORET COMP SCI,GRAZ,AUSTRIA

来源：

OPERATIONS RESEARCH LETTERS | 1994年 / 16卷 / 04期

关键词：

SCHEDULING; ONLINE ALGORITHMS; WORST-CASE ANALYSIS;

D O I：

10.1016/0167-6377(94)90071-X

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We investigate the problem of on-line scheduling a set of independent jobs on m parallel and identical machines with the objective of minimizing the overall finishing time. In this note, we are mainly interested in the cases where m is small. We derive results on the inevitable worst-case deviations from the optimum as encountered by any on-line algorithm. For m = 2 and m = 3, Graham's List Scheduling heuristic is known to be best possible. For m = 4, we will derive almost matching upper and lower bounds on the best possible worst-case guarantee for any on-line algorithm.

引用

页码：221 / 230

页数：10

共 7 条

[1]

BARTAL Y, 1992, 24TH P ACM S THEOR C, P51

[2]

CHEN B, 1993, 9374A ER U EC I REP

[3]

CHEN B, 1993, 9325A ER U EC I REP

[4]

Faigle U., 1989, Acta Cybernetica, V9, P107

[5] AN ONLINE SCHEDULING HEURISTIC WITH BETTER WORST CASE RATIO THAN GRAHAM LIST SCHEDULING [J].

GALAMBOS, G ;

WOEGINGER, GJ .

SIAM JOURNAL ON COMPUTING, 1993, 22 (02) :349-355

[6]

Garey M. R., 1979, COMPUTERS INTRACTABI

[7] BOUNDS FOR CERTAIN MULTIPROCESSING ANOMALIES [J].

GRAHAM, RL .

BELL SYSTEM TECHNICAL JOURNAL, 1966, 45 (09) :1563-+

← 1 →