The price of anarchy for minsum related machine scheduling

R.P. Hoeksma; Marc Jochen Uetz

doi:10.1007/978-3-642-29116-6_22

The price of anarchy for minsum related machine scheduling

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

23 Citations (Scopus)

11 Downloads (Pure)

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 language	Undefined
Title of host publication	9th International Workshop on Approximation and Online Algorithms, WAOA 2011
Editors	R Solis-Oba, G Persiano
Place of Publication	Heidelberg
Publisher	Springer
Pages	261-273
Number of pages	12
ISBN (Print)	978-3-642-29115-9
DOIs	https://doi.org/10.1007/978-3-642-29116-6_22
Publication status	Published - 2012
Event	9th International Workshop on Approximation and Online Algorithms 2011 - Saarbrücken, Germany Duration: 8 Sept 2011 → 9 Sept 2011 Conference number: 9

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag
Volume	7164
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Workshop on Approximation and Online Algorithms 2011
Abbreviated title	WAOA 2011
Country/Territory	Germany
City	Saarbrücken
Period	8/09/11 → 9/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

Access to Document

10.1007/978-3-642-29116-6_22

http://eprints.eemcs.utwente.nl/secure2/22006/01/71640261.pdf

Cite this

@inproceedings{690f8152a2bd471db5cd1058e745c9eb,

title = "The price of anarchy for minsum related machine scheduling",

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.",

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",

author = "R.P. Hoeksma and Uetz, \{Marc Jochen\}",

note = "10.1007/978-3-642-29116-6\_22 ; 9th International Workshop on Approximation and Online Algorithms 2011 ; Conference date: 08-09-2011 Through 09-09-2011",

year = "2012",

doi = "10.1007/978-3-642-29116-6\_22",

language = "Undefined",

isbn = "978-3-642-29115-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "261--273",

editor = "R Solis-Oba and G Persiano",

booktitle = "9th International Workshop on Approximation and Online Algorithms, WAOA 2011",

address = "Germany",

}

Hoeksma, RP & Uetz, MJ 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. Lecture Notes in Computer Science, vol. 7164, Springer, Heidelberg, pp. 261-273, 9th International Workshop on Approximation and Online Algorithms 2011, Saarbrücken, Germany, 8/09/11. https://doi.org/10.1007/978-3-642-29116-6_22

The price of anarchy for minsum related machine scheduling. / Hoeksma, R.P.; Uetz, Marc Jochen.
9th International Workshop on Approximation and Online Algorithms, WAOA 2011. ed. / R Solis-Oba; G Persiano. Heidelberg: Springer, 2012. p. 261-273 (Lecture Notes in Computer Science; Vol. 7164).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - The price of anarchy for minsum related machine scheduling

AU - Hoeksma, R.P.

AU - Uetz, Marc Jochen

N1 - Conference code: 9

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - METIS-289647

KW - IR-80764

KW - Related Machines

KW - EWI-22006

KW - Price of Anarchy

KW - DMMP-DeCOM: Design and Complexity of Optimal Mechanisms

KW - CR-G.2

KW - Minsum Scheduling

U2 - 10.1007/978-3-642-29116-6_22

DO - 10.1007/978-3-642-29116-6_22

M3 - Conference contribution

SN - 978-3-642-29115-9

T3 - Lecture Notes in Computer Science

SP - 261

EP - 273

BT - 9th International Workshop on Approximation and Online Algorithms, WAOA 2011

A2 - Solis-Oba, R

A2 - Persiano, G

PB - Springer

CY - Heidelberg

T2 - 9th International Workshop on Approximation and Online Algorithms 2011

Y2 - 8 September 2011 through 9 September 2011

ER -