language: en

On-line Load Balancing for Related Machines

Piotr Berman Moses Charikar Marek Karpinski
TR-97-007 January 1997

Abstract We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of 3 + p 8 5:828 for the deterministic version, and 3:31= ln 2:155 4:311 for its randomized variant, improving the previous competitive ratios of 8 and 2e 5:436. We also prove lower bounds of 2:4380 on the competitive ratio of deterministic algorithms and 1:8372 on the competitive ratio of randomized algorithms for this problem.

Dept. of Computer Science & Eng., Pennsylvania State University,
University Park, PA16802, USA
Email:berman@cse.psu.edu
Department of Computer Science, Stanford University,
Stanford, CA 94305-9045.

[Supported by Stanford School of Engineering Groswith Fellowship, an ARO MURI Grant DAAH04-96-1-0007 and NSF Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation, and Xerox Corporation.]

E-mail: moses@cs.stanford.edu.
Dept. of Computer Science, University of Bonn,
53117 Bonn,
and International Computer Science Institute,
Berkeley.

[This research was partially supported by the DFG Grant KA 673/4-1, by the ESPRIT BR Grants 7097 and EC-US 030.]

Email:marek@cs.uni-bonn.de