Decentralized throughput scheduling


Jong, Jasper de and Uetz, Marc and Wombacher, Andreas (2012) Decentralized throughput scheduling. [Report]

open access
Abstract:Motivated by the organization of online service systems, we study models for throughput scheduling in a decentralized setting. In throughput scheduling, we have a set of jobs j with values w(j), processing times p(j), and release dates r(j) and deadlines and d(j), 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 [r(j),d(j)]. While several approximation algorithms with different performance guarantees exist for this and related models, we are interested in the situation where subsets of servers are governed by selfish players. We give a universal result that bounds the price of decentralization, in the sense that any local a-approximation algorithms yield equilibria that are at most a factor (a+1) away from the global optimum, and this bound is tight. For models with identical machines, we improve this bound to approximately (a+1/2). We also address some variations of the problem.
Item Type:Report
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page