**Monday, 15:45 - 16:10 h, Room: H 3004**

**Ruben Hoeksma**

Price of anarchy for minsum related machine scheduling

**Coauthor: Marc Uetz**

**Abstract:**

We consider related machine scheduling to minimize the total completion time *∑ C*_{j}. This problem is well known to be solved in polynomial time by a classical algorithm of Horowitz and Sahni. Instead of the centralized optimal solution, however, we are interested in the situation where each job individually chooses the machine on which it is processed. We analyze the quality of the resulting Nash equilibria in relation to the objective value in the optimal solution, also known as the price of anarchy. Complementing recent results by Cole et al. on the unrelated machine problem where the price of anarchy equals exactly *4*, we show that the local SPT rule results in a price of anarchy between *e/(e-1)* and *2*. To obtain the upper bound of *2*, we use a smoothness argument in the flavor of recent work of Roughgarden, blended with a new characterization of the structure of optimal solutions.

Talk 2 of the invited session Mon.3.H 3004

**"Interactions between optimization and game theory in scheduling"** [...]

Cluster 2

**"Combinatorial optimization"** [...]