you're reading...

SACT talk: Universal scheduling on a single machine

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



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: