Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 1996 Copyright 1996 Universität Bonn, Institut für Informatik, Abt. V
8933

A note on On-line Load Balancing for related Machines
Piotr Berman, Marek Karpinski
[Download PostScript] [Download PDF]

We describe an on-line algorithm for scheduling permanent jobs on related machines. It achieves the competitive ratio of $3+\sqrt{8}\approx 5.828$ for the deterministic version, and $3.31/\ln 2.155 \approx 4.311$ for its randomized variant, improving the previous competitive ratios of 8 and $2e\approx 5.436$.

Last Change: 11/05/14 at 10:00:30
 English
Universität Bonn -> Institut für Informatik -> Abteilung V