zbMATH — the first resource for mathematics

Decentralized throughput scheduling. (English) Zbl 1384.90052
Spirakis, Paul G. (ed.) et al., Algorithms and complexity. 8th international conference, CIAC 2013, Barcelona, Spain, May 22–24, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38232-1/pbk). Lecture Notes in Computer Science 7878, 134-145 (2013).
Summary: 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 \(w _{j }\), processing times \(p _{ij }\) on machine \(i\), release dates \(r _{j }\) and deadlines \(d _{j }\), 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 \([r _{j },d _{j }]\). 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 \(\alpha \)-approximation algorithm, \(\alpha \geq 1\), yields Nash equilibria that are at most a factor (\(\alpha + 1\)) away from the global optimum, and this bound is tight. For identical machines, we improve this bound to \(\root\alpha\of e/(\root\alpha\of e-1)\approx (\alpha+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.
For the entire collection see [Zbl 1263.68023].

90B35 Deterministic scheduling theory in operations research
68W25 Approximation algorithms
91A10 Noncooperative games
Full Text: DOI