New Challenges in Scheduling Theory

October 21 - 27, 2012 --- Centre CNRS "La Villa Clythia", Frejus, France

Decentralized Throughput Scheduling

SpeakerMarc Uetz

Coauthors: Jasper de Jong and Andreas Wombacher

We study models for throughput scheduling in a decentralized setting. In throughput scheduling, we have a set of jobs j with values wj , processing times pj , and release dates rj and deadlines dj , to be processed non-preemptively on a set of unrelated machines. The goal is to maximize the total value of jobs scheduled within their time window [rj , dj]. While several approximation algorithms with different performance guarantees exist for this and related models, we are interested in the situation where subsets of machines are governed by selfish players. We show that local α-approximation algorithms for each player yield Nash equilibria at most a factor (α+1) away from the global optimum, and this bound is tight. For identical machines, we can improve this bound to ≈ (α+1/2), when restricting to subgame perfect equilibria of sequential games. We also address several variations of the problem.