Price of anarchy for machine scheduling games with sum of completion times objective

Hoeksma, Ruben (2010) Price of anarchy for machine scheduling games with sum of completion times objective.

[img]
Preview
PDF
510kB
Abstract:The uniformly related machine scheduling model with sum of completion times objective is well known and its optimal solution is easy to nd. However, this solution requires a central administrator that schedules the jobs on the machines. We look at this model from a game theoretical point of view and introduce for each job a selsh agent, which chooses the machine which processes the job, and is only interested in minimizing the completion time of its own job. Our interest lies in the price of anarchy for this game. That is, the ratio between the objective value of the optimal solution and the objective value of the Nash equilibrium of the game.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:54 computer science
Programme:Applied Mathematics MSc (60348)
Link to this item:http://purl.utwente.nl/essays/59756
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page