### Abstract

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

Publication status | Published - 2012 |

Event | 9th International Workshop on Approximation and Online Algorithms 2011 - Saarbrücken, Germany Duration: 8 Sep 2011 → 9 Sep 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 | 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

### Cite this

*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

}

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

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 - 10.1007/978-3-642-29116-6_22

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

ER -