An on-line scheduling heuristic with better worst case ratio than Graham's list scheduling

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 - \frac{1} {m}...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 1993-04, Vol.22 (2), p.349-355
Main Authors: GALAMBOS, G, WOEGINGER, G. J
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Exact sciences and technology
Heuristic
Job shops
Load
Operational research and scientific management
Operational research. Management science
Schedules
Scheduling
Scheduling, sequencing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 - \frac{1} {m}$ for this problem. This worst case bound cannot be improved for $m = 2$ and $m = 3$. For $m \geqslant 4$, approximation algorithms with worst case performance at most $2 - \frac{1}{m} - \varepsilon _m $ are presented, where $\varepsilon _m $ is some positive real depending only on $m$.
ISSN:0097-5397
1095-7111
DOI:10.1137/0222026