Jasper de Jong — Decentralized Throughput Scheduling
|Time:||Wednesday, May 15, 2013, 12:45-13:30|
|Location:||Room 311, Citadel|
Motivated by the organization of distributed service systems, we study models for throughput scheduling in a decentralized setting. In throughput scheduling, a set of jobs j with values wj, processing times pij on machine i, release dates rj and deadlines dj, is 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 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 give a universal result that bounds the price of decentralization: Any local α-approximation algorithm, yields Nash equilibria that are at most a factor α+1 away from the global optimum, and this bound is tight. For identical machines, we improve this bound to approximately α+1/2, which is shown to be tight, too. The latter result is obtained by considering subgame perfect equilibria of a corresponding sequential game. We also address some variations of the problem.