New lower and upper bounds for on-line scheduling

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...

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 1994-11, Vol.16 (4), p.221-230
Main Authors: Chen, Bo, van Vliet, André, Woeginger, Gerhard J.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Exact sciences and technology
On-line algorithms
Operational research and scientific management
Operational research. Management science
Operations research
Scheduling
Scheduling, sequencing
Worst-case analysis
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: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.
ISSN:0167-6377
1872-7468
DOI:10.1016/0167-6377(94)90071-X