The price of anarchy for minsum related machine scheduling

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

18 Citations (Scopus)

Abstract

We address the classical uniformly related machine scheduling problem with minsum objective. The problem is solvable in polynomial time by the algorithm of Horowitz and Sahni. In that solution, each machine sequences its jobs shortest first. However when jobs may choose the machine on which they are processed, while keeping the same sequencing rule per machine, the resulting Nash equilibria are in general not optimal. The price of anarchy measures this optimality gap. By means of a new characterization of the optimal solution, we show that the price of anarchy in this setting is bounded from above by 2. We also give a lower bound of e/(e-1). This complements recent results on the price of anarchy for the more general unrelated machine scheduling problem, where the price of anarchy equals 4. Interestingly, as Nash equilibria coincide with shortest processing time first (SPT) schedules, the same bounds hold for SPT schedules. Thereby, our work also fills a gap in the literature.
Original languageUndefined
Title of host publication9th International Workshop on Approximation and Online Algorithms, WAOA 2011
EditorsR Solis-Oba, G Persiano
Place of PublicationHeidelberg
PublisherSpringer
Pages261-273
Number of pages12
ISBN (Print)978-3-642-29115-9
DOIs
Publication statusPublished - 2012
Event9th International Workshop on Approximation and Online Algorithms 2011 - Saarbrücken, Germany
Duration: 8 Sep 20119 Sep 2011
Conference number: 9

Publication series

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

Conference

Conference9th International Workshop on Approximation and Online Algorithms 2011
Abbreviated titleWAOA 2011
CountryGermany
CitySaarbrücken
Period8/09/119/09/11

Keywords

  • METIS-289647
  • IR-80764
  • Related Machines
  • EWI-22006
  • Price of Anarchy
  • DMMP-DeCOM: Design and Complexity of Optimal Mechanisms
  • CR-G.2
  • Minsum Scheduling

Cite this

Hoeksma, R. P., & Uetz, M. J. (2012). The price of anarchy for minsum related machine scheduling. In R. Solis-Oba, & G. Persiano (Eds.), 9th International Workshop on Approximation and Online Algorithms, WAOA 2011 (pp. 261-273). (Lecture Notes in Computer Science; Vol. 7164). Heidelberg: Springer. https://doi.org/10.1007/978-3-642-29116-6_22