Samenvatting
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.
Originele taal-2 | Engels |
---|---|
Pagina's (van-tot) | 221-230 |
Aantal pagina's | 10 |
Tijdschrift | Operations Research Letters |
Volume | 16 |
Nummer van het tijdschrift | 4 |
DOI's | |
Status | Gepubliceerd - 1994 |