AN ONLINE SCHEDULING HEURISTIC WITH BETTER WORST CASE RATIO THAN GRAHAM LIST SCHEDULING

被引：76

作者：

GALAMBOS, G ^{[1
]}

WOEGINGER, GJ ^{[1
]}

机构：

[1] GRAZ TECH UNIV,INST THEORET INFORMAT,A-8010 GRAZ,AUSTRIA

来源：

SIAM JOURNAL ON COMPUTING | 1993年 / 22卷 / 02期

关键词：

COMBINATORIAL PROBLEMS; SCHEDULING; WORST CASE BOUNDS; ONLINE ALGORITHMS;

D O I：

10.1137/0222026

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The problem of on-line scheduling a set of independent jobs on m machines is considered. The goal is to minimize the makespan of the schedule. Graham's List Scheduling heuristic [R. L Graham, SIAM J. Appl. Math., 17(1969), pp. 416-429] guarantees a worst case performance of 2 - 1/m for this problem. This worst case bound cannot be improved for m = 2 and m = 3. For m greater-than-or-equal-to 4, approximation algorithms with worst case performance at most 2 - 1/m - epsilon(m) are presented, where epsilon(m) is some positive real depending only on m.

引用

页码：349 / 355

页数：7