de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Hochschulschrift

Coordination Mechanisms for Unrelated Machine Scheduling

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons43960

Abed,  Fidaa
Algorithms and Complexity, MPI for Informatics, Max Planck Society;
International Max Planck Research School, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44648

Huang,  Chien-Chung
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Abed, F. (2011). Coordination Mechanisms for Unrelated Machine Scheduling. Master Thesis, Universität des Saarlandes, Saarbrücken.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0027-A1A2-B
Zusammenfassung
We investigate load balancing games in the context of unrelated machines scheduling. In such a game, there are a number of jobs and a number of machines, and each job needs to be scheduled on one machine. A collection of values pij are given, where pij indicates the processing time of job i on machine j. Moreover, each job is controlled by a selfish player who only wants to minimize the completion time of his job while disregarding other players' welfare. The outcome schedule is a Nash equilibrium if no player can unilaterally change his machine and reduce the completion time of his job. It is known that in an equilibrium, the performance of the system can be far from optimal. The degradation of the system performance in Nash equilibrium is defined as the price of anarchy (PoA): the ratio of the cost of the worst Nash equilibrium to the cost of the optimal scheduling. Clever scheduling policies can be designed to reduce PoA. These scheduling policies are called coordination mechanisms. It has been posed as an open question "what is the best possible lower bound when coordination mechanisms use preemption". In this thesis we prove a lower bound of ( logm log logm) for all symmetric preemptive coordination mechanisms. Moreover we study the lower bound for the unusual case when the coordination mechanisms are asymmetric and we get the same bound under the weak assumption that machines have no IDs. On the positive side we prove that the inefficiency-based mechanism can achieve a constant PoA when the maximum inefficiency of the jobs is bounded by a constant.