Decentralized throughput scheduling

Jasper de Jong, Marc Jochen Uetz, Andreas Wombacher

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

Abstract

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 α-approximation algorithm, α ≥ 1, 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 ≈(α+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.
Original languageEnglish
Title of host publicationAlgorithms and Complexity
Subtitle of host publication8th International Conference, CIAC 2013, Barcelona, Spain, May 22-24, 2013. Proceedings
EditorsPaul G. Spirakis, Maria Serna
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages134-145
Number of pages12
ISBN (Electronic)978-3-642-38233-8
ISBN (Print)978-3-642-38232-1
DOIs
Publication statusPublished - 2013
Event8th International Conference on Algorithms and Complexity, CIAC 2013 - Barcelona, Spain
Duration: 22 May 201324 May 2013
Conference number: 8

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume7878
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th International Conference on Algorithms and Complexity, CIAC 2013
Abbreviated titleCIAC
CountrySpain
CityBarcelona
Period22/05/1324/05/13

Keywords

  • EWI-23251
  • DMMP-DSS: Mechanisms for Decentralized Service Systems
  • Price of Anarchy
  • Throughput Scheduling
  • IR-86964
  • Decentralization
  • METIS-297612

Fingerprint Dive into the research topics of 'Decentralized throughput scheduling'. Together they form a unique fingerprint.

Cite this