|
Abstract : |
We consider the on-line version of the original m-machine scheduling problem: 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 competitive ratio of the best algorithm for m-machine scheduling. The largest prior lower bound was that if m 4, then every algorithm has a competitive ratio at least 1+1= p 2 1:707. We show that if m is large enough, the competitive ratio of every algorithm exceeds 1:837. The best upper bound on the competitive ratio is now 1:945. 1, |
