Online Scheduling-Spiele

Abstract

Ziel dieser Arbeit ist die Modellierung von online Scheduling-Spielen. Es gibt viele verschiedene Arten von Scheduling-Problemen. Wir betrachten Probleme, bei denen eine Menge von Jobs Maschinen zugewiesen werden müssen. Jeder Job wird dann von der Maschine bearbeitet, der er zugeteilt wurde. In der Praxis treten Scheduling- und Lastbalancierungsprobleme häufig in der Form auf, dass die Jobs nicht zentral auf die Maschinen oder auch Ressourcen verteilt werden, sondern, dass jeder Job einem sogenannten Spieler gehört, der eine Maschine selbstständig für seinen Job auswählt. Dies ist insbesondere bei öffentlichen Netzwerken, wie zum Beispiel dem Internet, der Fall. Bei solchen Netzwerken werden einzelne Dienste teilweise von mehreren verschiedenen Servern angeboten. Ein Benutzer kann sich dann frei einen dieser Server zur Bearbeitung aussuchen. Damit findet keine zentrale Verteilung der Jobs mehr statt.<br /> In dieser Arbeit werden wir solche Systeme in klassische spieltheoretische Modelle einbetten und analysieren. Im Gegensatz zu den offline Scheduling-Spielen, die von Koutsoupias und Papadimitriou cite{koutsoupias99worstcase} eingeführt wurden, werden wir ein allgemeineres Modell einführen, das dazu verwendet werden kann, offline und online Modelle zu beschreiben. Bei dieser Modellierung können die Spieler nicht die Reihenfolge, mit der die Jobs auf einer Maschine bearbeitet werden, beeinflussen. Diese ist durch das für das konkrete Spiel fest vorgegebene Maschinenmodell definiert. Die Wahl des Maschinenmodells beeinflusst bei solchen Spielen nicht nur die Abarbeitungsreihenfolge auf den Maschinen, sondern indirekt auch die Strategien, die ein rationaler Spieler auswählen würde. Somit werden die Lösungen, die von den Strategien rationaler Spieler erzeugt werden, durch das gewählte Maschinenmodell beeinflusst. Wir werden zeigen, dass unsere Modellierung es erlaubt, die von Koutsoupias und Papadimitriou eingeführten Spiele mittels eines speziellen Maschinenmodells zu beschreiben. Zudem werden wir online Scheduling-Spiele beschreiben und verschiedene Maschinenmodelle für diese online Spiele analysieren.