University of Twente Student Theses
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]](http://essay.utwente.nl/style/images/fileicons/application_pdf.png) |
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: | https://purl.utwente.nl/essays/59756 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page