A BETTER LOWER-BOUND FOR ONLINE SCHEDULING

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 a job arrives, it must be assigned immediately to one of the m machines. We study the c ompetitive ratio of the best algorithm for m-machine scheduling. The l argest prior lower bound was that if m greater-than-or-equal-to 4, the n every algorithm has a competitive ratio at least 1 + 1 / square-root 2 almost-equal-to 1.707. We show that if m greater-than-or-equal-to 3 454, then the competitive ratio of every algorithm exceeds 1.837. The best upper bound on the competitive ratio is now 1.945.