New algorithms for related machines with temporary jobs

We consider the on-line problem of assigning temporary jobs to related machines. In this model, machines have speeds and the jobs are weighted and may be temporary (i.e. may expire after some unknown finite amount of time). The cost of an assignment is the maximum load on a machine at any time . We present two new algorithms: a 6 + 2√(5) ≈ 10.47-competitive deterministic algorithm and a 9.572-competitive randomized algorithm. The previously known best upper bound is achieved by a 20-competitive deterministic algorithm whose randomized version is 5e = 13.59-competitive.