|
Abstract : |
One of the oldest and simplest variants of multiprocessor scheduling is the on-line scheduling problem studied by Graham in 1966. In this problem, the jobs arrive on-line and must be scheduled non-preemptively on m identical machines so as to minimize the makespan. The size of a job is known on arrival. Graham proved that the List Processing Algorithm which assigns each job to the currently least loaded machine has competitive ratio (2 \Gamma 1=m). Recently algorithms with smaller competitive ratios than List Processing have been discovered, culminating in Bartal, Fiat, Karloff, and Vohra's construction of an algorithm with competitive ratio bounded away from 2. Their algorithm has a competitive ratio of at most (2 \Gamma 1=70) 1:986 for all m; hence for m? 70, their algorithm is provably better than List Processing. We present a more natural algorithm that outperforms List Processing for any m 6 and has a competitive ratio of at most 1:945 for all m, which is significantly closer to the best known lower bound of 1:837 for the problem. We show that our analysis of the algorithm is almost tight by presenting a lower bound of 1:9378 on the algorithm's competitive ratio for large m. 1, |
