Decentralized throughput scheduling

Share/Save/Bookmark

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

[img]
Preview
PDF
339Kb
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
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/80711
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page