On-line Load Balancing for Related Machines

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