New lower and upper bounds for on-line scheduling

The authors 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, they are mainly interested in the cases where m is small. The authors 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, the authors will derive almost matching upper and lower bounds on the best possible worst-case guarantee for any on-line algorithm.