Packet Routing and Scheduling

Zu den wichtigsten Fragestellungen in der kombinatorischen Optimierung gehren Schedulingprobleme. In dieser Arbeit wird das Maschinenscheduling betrachtet. Gewhnlich sind in derartigen Problemen eine Menge von Jobs und eine Menge von Maschinen gegeben. Die Aufgabe besteht darin, die Jobs den Maschinen zuzuweisen und fr jede Maschine einen Schedule zu bestimmen. Der Schedule legt fest, zu welchen Zeiten die Maschine die ihr zugewiesenen Jobs bearbeitet. Hufig mssen Nebenbedingungen beachtet werden. Typische Nebenbedingungen sind Zeiten, bis zu denen bestimmte Jobs fertig gestellt sein mssen (deadlines), dass einige Jobs erst bearbeitet werden knnen, wenn bestimmte andere Jobs fertig gestellt sind (precedence constraints), oder dass einige Jobs erst ab einer gegebenen Zeit verfgbar sind (release dates). Ein Schedulingproblem, das in der vorliegenden Arbeit besonders betrachtet wird, ist das Packet Routing Problem. Hier mssen gegebene Pakete entlang von gegebenen Pfaden in einem Graphen mglichst schnell an ihr Ziel transportiert werden. Die Bandbreiten der Kanten werden als begrenzt angenommen. Der zu berechnende Schedule legt fest, zu welchen Zeitpunkten die Pakete die Kanten ihres jeweiligen Pfades passieren. Hierbei knnen die Kanten als Maschinen und die Pakete als Menge von Jobs mit Vorgngerbeziehungen (precedence constraints) interpretiert werden. Teil I dieser Arbeit behandelt Resultate fr dieses Problem. Zuerst werden Approximationsalgorithmen fr verschiedene Flle des Problems vorgestellt. Zunchst sind dies Algorithmen fr den Spezialfall, dass der zugrunde liegende Graph ein Baum ist. Die gewonnen Einsichten erweisen sich als sehr hilfreich fr den allgemeinen Fall. Fr diesen wird eine obere Schranke an die Lnge eines optimalen Schedules in Abhngigkeit der unteren Schranken "Congestion" und "Dilation" bewiesen. Weiterhin wird gezeigt, dass das Problem NP-schwer zu approximieren ist, sogar auf der sehr einfachen Graphenklasse der gerichteten Bume. Schlielich wird das periodische Packet Routing Problem untersucht, in dem gegebene Tasks periodisch neue Pakete erzeugen, die durch ein Netzwerk transportiert werden mssen. Teil II dieser Arbeit behandelt weitere Schedulingprobleme. Zuerst wird das Flow Scheduling Problem untersucht, das dynamische Flsse und Scheduling vereint. Gegebene Jobs mssen hier in einem dynamischen Fluss von einer Quelle zu einer Senke transportiert werden. Das Ziel ist, die gewichtete Summe der Ankunftszeiten der Jobs zu minimieren. Danach werden Resultate fr das Periodic Maintenance Problem gezeigt. Die Forschung an diesem Problem entstand durch eine Kooperation mit einem Industriepartner aus der Luftfahrtindustrie. Die Aufgabe besteht darin, Tasks, die Computerprogramme modellieren, auf die verschiedenen Prozessoren des Bordcomputers eines Flugzeugs zu verteilen. Fr jeden Prozessor muss auerdem ein Schedule definiert werden. Fr verschiedene Flle des Problems werden Approximations- und Komplexittsresultate angegeben, insbesondere einen 2-Approximationsalgorithmus fr den in der Praxis wichtigen Fall von harmonischen Periodenlngen. Schlielich wird das Problem betrachtet, Jobs gegebenen Maschinen zuzuweisen, bei denen die Ausfhrungszeiten eines Jobs auf den verschiedenen Maschinen unterschiedlich sein knnen und im allgemeinen keinerlei Struktur aufweisen (unrelated machines). Die besten bisher bekannten Anstze basieren auf linearen Programmen (LPs). In der Arbeit wird gezeigt, dass selbst das strkste bekannte LP, das sogenannte Konfigurations-LP, nicht helfen kann, den besten bekannten Approximationsfaktor zu verbessern. Dies gilt selbst fr den Spezialfall, dass jeder Job auf maximal zwei Maschinen ausgefhrt werden kann (unrelated graph balancing). Fr das verwandte Problem des MaxMin-Balancing wird ein rein kombinatorischer 2-Approximationsalgorithmus mit nur quadratischer Laufzeit vorgestellt.

Klappentext

Zu den wichtigsten Fragestellungen in der kombinatorischen Optimierung gehören Schedulingprobleme. In dieser Arbeit wird das Maschinenscheduling betrachtet. Gewöhnlich sind in derartigen Problemen eine Menge von Jobs und eine Menge von Maschinen gegeben. Die Aufgabe besteht darin, die Jobs den Maschinen zuzuweisen und für jede Maschine einen Schedule zu bestimmen. Der Schedule legt fest, zu welchen Zeiten die Maschine die ihr zugewiesenen Jobs bearbeitet. Häufig müssen Nebenbedingungen beachtet werden. Typische Nebenbedingungen sind Zeiten, bis zu denen bestimmte Jobs fertig gestellt sein müssen (deadlines), dass einige Jobs erst bearbeitet werden können, wenn bestimmte andere Jobs fertig gestellt sind (precedence constraints), oder dass einige Jobs erst ab einer gegebenen Zeit verfügbar sind (release dates). Ein Schedulingproblem, das in der vorliegenden Arbeit besonders betrachtet wird, ist das Packet Routing Problem. Hier müssen gegebene Pakete entlang von gegebenen Pfaden in einem Graphen möglichst schnell an ihr Ziel transportiert werden. Die Bandbreiten der Kanten werden als begrenzt angenommen. Der zu berechnende Schedule legt fest, zu welchen Zeitpunkten die Pakete die Kanten ihres jeweiligen Pfades passieren. Hierbei können die Kanten als Maschinen und die Pakete als Menge von Jobs mit Vorgängerbeziehungen (precedence constraints) interpretiert werden. Teil I dieser Arbeit behandelt Resultate für dieses Problem. Zuerst werden Approximationsalgorithmen für verschiedene Fälle des Problems vorgestellt. Zunächst sind dies Algorithmen für den Spezialfall, dass der zugrunde liegende Graph ein Baum ist. Die gewonnen Einsichten erweisen sich als sehr hilfreich für den allgemeinen Fall. Für diesen wird eine obere Schranke an die Länge eines optimalen Schedules in Abhängigkeit der unteren Schranken "Congestion" und "Dilation" bewiesen. Weiterhin wird gezeigt, dass das Problem NP-schwer zu approximieren ist, sogar auf der sehr einfachen Graphenklasse der gerichteten Bäume. Schließlich wird das periodische Packet Routing Problem untersucht, in dem gegebene Tasks periodisch neue Pakete erzeugen, die durch ein Netzwerk transportiert werden müssen. Teil II dieser Arbeit behandelt weitere Schedulingprobleme. Zuerst wird das Flow Scheduling Problem untersucht, das dynamische Flüsse und Scheduling vereint. Gegebene Jobs müssen hier in einem dynamischen Fluss von einer Quelle zu einer Senke transportiert werden. Das Ziel ist, die gewichtete Summe der Ankunftszeiten der Jobs zu minimieren. Danach werden Resultate für das Periodic Maintenance Problem gezeigt. Die Forschung an diesem Problem entstand durch eine Kooperation mit einem Industriepartner aus der Luftfahrtindustrie. Die Aufgabe besteht darin, Tasks, die Computerprogramme modellieren, auf die verschiedenen Prozessoren des Bordcomputers eines Flugzeugs zu verteilen. Für jeden Prozessor muss außerdem ein Schedule definiert werden. Für verschiedene Fälle des Problems werden Approximations- und Komplexitätsresultate angegeben, insbesondere einen 2-Approximationsalgorithmus für den in der Praxis wichtigen Fall von harmonischen Periodenlängen. Schließlich wird das Problem betrachtet, Jobs gegebenen Maschinen zuzuweisen, bei denen die Ausführungszeiten eines Jobs auf den verschiedenen Maschinen unterschiedlich sein können und im allgemeinen keinerlei Struktur aufweisen (unrelated machines). Die besten bisher bekannten Ansätze basieren auf linearen Programmen (LPs). In der Arbeit wird gezeigt, dass selbst das stärkste bekannte LP, das sogenannte Konfigurations-LP, nicht helfen kann, den besten bekannten Approximationsfaktor zu verbessern. Dies gilt selbst für den Spezialfall, dass jeder Job auf maximal zwei Maschinen ausgeführt werden kann (unrelated graph balancing). Für das verwandte Problem des MaxMin-Balancing wird ein rein kombinatorischer 2-Approximationsalgorithmus mit nur quadratischer Laufzeit vorgestellt.