Time: 11am Friday, 4th May, 2012
Location: SIT 124 Boardroom
Speaker: Julian Mestre, University of Sydney
Consider scheduling jobs on an unreliable machine that can experience unexpected changes in processing speed or even full breakdowns. We aim for a universal solution that performs well without adaptation for any possible machine behavior. For the objective of minimizing the total weighted completion time, we design a polynomial time deterministic algorithm that finds a universal scheduling sequence with a solution value within 4 times the value of an optimal clairvoyant algorithm that knows the machine behavior in advance. A randomized version of this algorithm attains a ratio of e. We show that both results are best possible among universal solutions. We also study some generalization of the basic problem and show that our solution is not only universal with respect to machine behavior but also with respect to the objective function.
This is joint work with L. Epstein, A. Levin, A. Marchetti-Spaccamela, N. Megow, M. Skutella, and L. Stougie