Der Online-Fall
Optimalität
Scheduling jobs one by one (Einen Auftrag nach dem anderen planen)
Unknown running times (Unbekannte Laufzeiten)
Jobs arrive over time (Aufträge treffen mit der Zeit ein)
Interval scheduling (Aufträge müssen in ein Intervall eingeplant werden)
Release times, Deadlines
Precedence constraints, Conflicting jobs
Preemptions, Restarts
Unterschiedliche Maschinengeschwindigkeiten
List Scheduling
Competitive Ratio von List Scheduling
Worst Case
Beweis der 2-1/m-komptitivität
Scheduling befasst sich mit dem Problem, Maschinen Aufträge
(Jobs) zuzuordnen.
Gegeben:
Eine Liste von Aufträgen, die meistens durch ihre Laufzeit charakterisiert sind
Maschinen, um diese Aufträge zu bearbeiten
Gesucht:
Eine Verteilung der Jobs auf die Maschinen, so dass eine vom genauen Problem abhängige Funktion einen optimalen wert annimmt.
Normalerweise weiß man natürlich
nicht, welche Aufträge eine Firma in Zukunft bekommen wird. Ein
Computer hat keine Informationen darüber, wie lange die
Programme noch laufen werden, also müssen hier
Schedulingentscheidungen getroffen werden, ohne alle Daten, die
benötigt werden, um eine optimale Entscheidung zu treffen, zu
kennen. Zudem ist es nicht immer sinnvoll, auch wenn sämtliche
Daten verfügbar sind, eine optimale Lösung zu suchen, da
viele Schedulingprobleme, in die Klasse der NP-Vollständigen
Probleme gehören und damit nur in exponentieller Zeit lösbar
sind.
Man muss also versuchen, eine möglichst optimale
Entscheidung zu treffen.
Bis jetzt wurde noch nicht gesagt, wie
denn eine optimale Lösung aussehen könnte. In vielen Fällen
möchte man die gesamte Bearbeitungszeit für alle Jobs
(makespan) minimieren, sucht also eine optimale Verteilung der Jobs
auf die zur Verfügung stehenden Maschinen.
Versetzt man sich
nun in die Perspektive eines Computeranwenders, dann ist die
Gesamtbearbeitungszeit eigentlich nur Nebensache: Es ist wohl kaum
einem Benutzer, der eigentlich nur ein kurzes Programm laufen lassen
möchte zumutbar, abwarten zu müssen, bis irgendeine
zeitaufwendige Berechnung beendet wurde, bevor das eigene Programm
bearbeitet wird. Daher versucht man in dieser Situation die
Antwortzeit (total flow time oder response time), also die Zeit, die
vom Programmstart bis zum erhalten des Ergebnisses, oder die
Wartezeit (waiting time) also Antwortzeit minus Laufzeit des
Programms, niedrig zu halten.
Zunächst unterscheidet man vier grundlegend verschiedene Probleme nach der Art der gegebenen Daten. Außerdem gibt es noch zusätzliche Einschränkungen oder Möglichkeiten, die man zusätzlich mit einigen der grundlegenden Varianten verbinden kann.
Hier sind die Jobs zunächst in einer Liste angeordnet und werden dem Algorithmus einer nach dem anderen in dieser Reihenfolge übergeben. Der Algorithmus muss daraufhin eine Entscheidung treffen, wann der Auftrag auf welche(n) Maschine(n) eingeplant wird. (Der Auftrag darf auch nach einem Nachfolgenden Auftrag eingeplant werden.) Dabei darf keine vorher getroffene Entscheidung revidiert werden. Man kann schnell erkennen, dass alle Aufträge in einer beliebigen Reihenfolge abgearbeitet werden dürfen, denn wenn ein Job in dieser Liste stehen würde, der erst nach einem bestimmten Job begonnen werden dürfte, der noch nicht eingeplant wurde, dann kann man keine sinnvolle Entscheidung treffen, da man von diesem anderen Auftrag nicht einmal die Laufzeit kennt, um diese noch vor dem aktuellen Auftrageinplanen zu können.
Das Hauptmerkmal dieser Variante ist, dass der Algorithmus ohne Kenntnis der Laufzeiten der Jobs auskommen muss, bis diese abgearbeitet sind. Dafür darf der Algorithmus auf die Daten aller verfügbaren Jobs zugreifen und diese entweder jetzt starten, oder den Start auf später verschieben. Zusätzlich kann man diese Variante mit "release times" (ein Job darf erst nach einem Zeitpunkt gestartet werden) und "precedence constraints" (verschiedene Jobs dürfen erst bearbeitet werden, nachdem andere beendet wurden) kombinieren. Falls es noch andere Merkmale gibt, die für die Ausführung des Jobs notwendig sind, sind diese bekannt, sobald der Job verfügbar wird.
Auch hier kann der Algorithmus auf alle verfügbaren Jobs zurückgreifen. Die Laufzeiten sind bekannt, also ist die einzige Onlineeigenschaft, dass der Algorithmus ohne Kenntnis der Jobs auskommen muss, die in der Zukunft kommen.
In allen vorhergehenden Varianten wurde angenommen, dass die Bearbeitung eines Jobs beliebig verschoben werden kann. In dieser Variante muss ein Job in einem bestimmten Zeitintervall bearbeitet werden, wenn dass nicht möglich ist, darf der Auftrag abgelehnt werden. Man kann leicht erkennen, dass die Bearbeitungszeit hier bedeutungslos ist, da sie durch die Jobs vorgegeben ist, stattdessen misst man normalerweise den Gesamtwert, oder die Anzahl der bearbeiteten Aufträge.
Jedem Job kann eine individuelle release time zugeordnet sein,
also ein Zeitpunkt, vor dem der Job nicht bearbeitet werden darf. Im
Online-Fall ist der Job vor der release time unbekannt.
Als
Deadline bezeichnet man den Zeitpunkt zu dem ein Job beendet sein
muss. Für die Onlinesituation kennt man nur kompetitive
Algorithmen für den Fall,dass alle Jobs eine gemeinsame Deadline
haben.
Häufig gibt es precedence constraints zwischen Jobs, die
häufig durch einen gerichteten, azyklischen Graphen gegeben
werden. Ein Job im Graph darf erst bearbeitet werden, nachdem alle
Vorgänger im Graphen bearbeitet wurden.
Conflicting Jobs
bezeichnet ein ähnliches Modell, in sich Jobs gegenseitig
ausschließen und nicht gleichzeitig bearbeitet werden dürfen.
Falls Preemptions erlaubt sind, darf die Bearbeitung eines Jobs
vorläufig eingestellt werden, und dann später wieder
aufgenommen werden. Dabei kann es notwendig sein, die Bearbeitung auf
der gleichen Maschine fortzusetzen.
Falls nur Restarts erlaubt
sind, darf die Bearbeitung eines Jobs vorzeitig beendet werden, die
Bearbeitung muss danach allerdings wieder am Anfang des Jobsanfangen.
Hierbei unterscheidet man verschiedene Fälle:
Bei
"uniformly related Maischens", haben alle Maschinen eine
individuelle, feste Geschwindigkeit. Falls ein Job mit der Laufzeit t
auf Maschine i mit der Geschwindigkeit 0<si<=1
ausgeführt werden soll, dann wird eine Bearbeitungszeit von t/si
auf dieser Maschine benötigt.
Bei "untertage Maischens"
haben die Maschinen keine für alle Jobs gleiche vorgegebene
Arbeitsgeschwindigkeit, sondern die Geschwindigkeit ist von dem
einzelnen Job abhängig.
"Restbreite Assignaten"
betrachtet den Fall, dass ein Job nicht auf allen Maschinen
bearbeitet werden kann, dafür sind die Maschinen alle gleich
schnell. Man kann dieses Problem auch durch untertage Maischens
modellieren, bei denen die Jobs entweder mit der Geschwindigkeit 1,
oder mit einer unendlich kleinen Geschwindigkeit bearbeitet werden.
Hier besteht ein Job aus einer Abfolge verschiedener Tasks (z.B. Arbeitsschritte in einer Werkstatt), die auf verschiedenen Maschinen ausgeführt werden müssen. Anhand weiterer Einschränkungen unterscheidet man hier 3 Untervarianten:
Bei "open Shop" dürfen die Tasks in einer beliebigen Reihenfolge bearbeitet werden.
"Flow Shop" schreibt eine Bearbeitungsreihenfolge der Tasks für alle Jobs gemeinsam vor.
Ein "job Shop" erlaubt für jeden Job eine eigene Bearbeitungsreihenfolge der Tasks.
List Scheduling ist ein deterministischer Greedy-Algorithmus aus
den Anfängen der Untersuchung von Schedulingproblemen und war
der erste Scheduling-Algorithmus, für den die Kompetitivität
bewiesen wurde.
Arbeitsweise:
Füge zunächst alle Jobs einer Liste (Sequenz) hinzu
Sobald eine Maschine Leerlauf hat, weise ihr den nächsten verfügbaren (alle Vorgänger wurden erledigt, und die release Time ist verstrichen) Job in der Liste zu.
Für den Algorithmus wird wird vorausgesetzt, dass man m identische Maschinen hat, auf denen Jobs, die durch ihre Laufzeit charakterisiert sind ausgeführt werden. Dabei versucht man die Gesamtbearbetungszeit (makespan) zu minimieren. List Scheduling kommt mit den ersten drei genannten Varianten (Scheduling jobs one by one, unknown running times und jobs arriving over time) zurecht. Für "scheduling jobs one by one" wird von List Scheduling bei weniger als 3 Maschinen die bestmögliche Onlinelösung gefunden. Auch für das Problem der unbekannten Laufzeiten liefert List Scheduling eine bestmögliche Approximation für einen deterministischen Algorithmus.
Im folgenden werden folgende Variablen verwendet:
m |
Anzahl der verfügbaren Maschinen |
TOpt |
Bearbeitungszeit, die der optimale offline Algorithmus zur Bearbeitung der vollständigen Sequenz benötigt |
T |
Laufzeit des letzten Jobs |
t |
Startzeitpunkt des letzten Jobs |
Zunächst nehmen wir mal an, wir
hätten eine Sequenz von m*(m-1) Jobs, mit jeweils einer Laufzeit
von 1 und einen Job mit einer Laufzeit von m, die alle bekannt sind
und alle zu jeder Zeit begonnen werden dürfen. Optimal kann man
diese Sequenz in einer Zeit von m abarbeiten. List Scheduling
verteilt zunächst die m*(m-1) Jobs gleichmäßig auf
die m Maschinen, wodurch alle Maschinen schon für (m-1)
Zeiteinheiten belegt sind. Erst danach wird der verbleibende Job
einer der nun freien Maschinen zugewiesen, wodurch man eine
Bearbeitungszeit für die gesamte Sequenz von m+m-1=2m-1 hat.
Hieran kann man schon erkennen, dass die Kompetivität von
List Scheduling nicht besser als 2-1/m sein kann.
Zunächst beschränken wir uns
weiterhin auf den Fall, dass alle Jobs zu jedem Zeitpunkt, unabhängig
von allen anderen gestartet werden dürfen, also weder precedence
contraints, noch release times vorliegen.
Wir wissen also, dass
TOpt>=t+T/m
da vor dem Zeitpunkt t alle Maschinen
belegt waren und deshalb der letzte Job nicht gestartet werden konnte
und T/m die Zeit ist, die der letzte Job benötigte, wenn man ihn
gleichmäßig auf alle Maschinen aufteilte.
Weiterhin
muss
TOpt>=T
sein, denn die Zeitspanne T schon
allein zur optimalen Bearbeitung vom letzten Auftrag benötigt.
Durch
Umformung erhält man:
t+T=t+T/m+(1-1/m)T
Nun kann man die weiter oben gefundenen Abschätzungenbenutzen und erhält:
t+T<=(2-1/m)TOpt
Den allgemeinen Fall, also mit release Times und precedence constraints kann man nun damit Beweisen, dass man sich induktiv eine Sequenz J von Jobs definiert: Das erste Element J1 dieser Sequenz sei der Job, der zuletzt endet. Falls Ji keinen Vorgänger im Abhänigkeitsgraphen hat, der nach der release Time von Ji endet, endet die Sequenz, ansonsten wird Ji+1 als der Vorgänger im Abhänigkeitsgraphen von Ji definiert, der zuletzt endet. Nun weiß man, dass auch ein optimaler Algorithmus nicht vor der release Time des (zeitlich) ersten Jobs dieser Sequenz (also derjenige mit dem höchsten Index) mit der Bearbeitung dieser Sequenz beginnen kann. Außerdem weiß man, dass diese Sequenz in genau dieser Reihenfolge abgearbeitet werden muss, denn ansonsten wären nicht alle Abhängigkeiten der Jobs untereinander erfüllt. Hierdurch sieht man, dass die Gesamtleerlaufzeit aller Maschienen durch den optimalen Makespan begrenzt ist und der Beweis von oben auch hier gilt.