| On-line Load Balancing for Related Machines 1 (Revised Version) (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| We consider the problem of scheduling permanent jobs on related machinesin an on-line fashion. We design a new algorithm that achievesthe competitive ratio for the deterministic version, and3:31=ln2:1554:311for its randomized variant, improving the previous competitive ratios of 8 and2e5:436. We also prove lower bounds of2:4380on the competitive ratio of deterministic algorithms and1:8372on the competitive ratio of randomized algorithms for this problem. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||