We consider the on-line version of the original m-machine scheduling p
roblem: given m machines and n positive real jobs, schedule the n jobs
on the m machines so as to minimize the makespan, the completion time
of the last job. In the on-line version, as soon as job j arrives, it
must be assigned immediately to one of the m machines. We present two
main results. The first is a (2 - epsilon)-competitive deterministic
algorithm for all m. The competitive ratio of all previous algorithms
approaches 2 as m --> infinity. Indeed, the problem of improving the c
ompetitive ratio for large m had been open since 1966, when the first
algorithm for this problem appeared. The second result is an optimal r
andomized algorithm for the case m = 2. To the best of our knowledge,
our 4/3-competitive algorithm is the first specifically randomized alg
orithm for the original, m-machine, on-line scheduling problem. (C) 19
95 Academic Press, Inc.