NEW LOWER AND UPPER-BOUNDS FOR ONLINE SCHEDULING

We investigate the problem of on-line scheduling a set of independent jobs on m parallel and identical machines with the objective of minimi zing the overall finishing time. In this note, we are mainly intereste d in the cases where m is small. We derive results on the inevitable w orst-case deviations from the optimum as encountered by any on-line al gorithm. For m = 2 and m = 3, Graham's List Scheduling heuristic is kn own to be best possible. For m = 4, we will derive almost matching upp er and lower bounds on the best possible worst-case guarantee for any on-line algorithm.