Scheduling Algorithmen

Eine optimale Lösung für das Job-Shop Scheduling

Inhalt

• Eine Definition
• brute-force Algorithmen
• Der branch-and-bound Algorithmus
• Ein Beispiel

 

Eine Definition

Im Folgenden wird die Notation n x m Job-Shop Scheduling verwendet (wobei n und m identisch sein können). n ist die Anzahl der Aufgaben, welche erledigt werden müssen, m ist die Anzahl der Tasks, aus welcher jede der n Aufgaben zusammengesetzt ist. m ist auch gleich der Anzahl zur Verfügung stehender Maschinen. Das 3x3 Job-Shop Scheduling ist also das Problem, drei Aufgaben mit jeweils drei Tasks auf drei Maschinen möglichst schnell zu verarbeiten.

 

brute-force Algorithmen

"brute-force" heisst nichts anderes als "rohe Gewalt". Ein brute-force Algorithmus probiert alle theoretisch möglichen Lösungen aus, und wählt die beste aus. Für das Job-Shop Scheduling sind bis heute nur brute-force Algorithmen bekannt. Man kann damit nur sehr kleine Probleme lösen. Die Zahlen in Tabelle 1 zeigen den Grund: die enorme Komplexität.

Tabelle 1: Für jedes n bis zu 10 wird die theoretisch mögliche Anzahl der verschiedenen Anordnungen der Tasks auf den Maschinen ersichtlich. Für das 10x10 Job-Shop Scheduling ist dies eine Zahl mit 66 Stellen.

Kein Computer kann in vernünftiger Zeit alle möglichen Lösungen für das 10x10 Job-Shop Scheduling berechnen und miteinander vergleichen. Das Problem ist jedoch sehr schön parallelisierbar. Das heisst, dass man auf einem Rechner die erste Hälfte des Lösungsraumes und auf dem zweiten Rechner unabhängig vom ersten den Rest untersuchen kann. Die jeweils beste Lösung von beiden Rechnern vergleicht man. Die bessere von beiden ist die optimale Lösung. Würde man nicht zwei sondern eine Million Rechner verwenden so würde man zur Berechnung der optimalen Lösung auch nur noch einen Millionstel der Zeit benötigen. Jeder Rechner müsste also im Falle des 10x10 Job-Shop Scheduling noch etwas mehr als 396'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000 mögliche Lösungen berechnen und miteinander vergleichen. Das ist zur Zeit völlig unmöglich.

 

Der branch-and-bound Algorithmus

"branch-and-bound" heisst übersetzt "verzweigen und begrenzen". Die Grundidee ist, möglichst grosse Gruppen von Lösungen zu eliminieren, wenn sie nicht besser als die beste bisher gefundene Lösung sind. Es ist entscheidend, dass man ein möglichst gutes Kriterium findet, mit welchen Anordnungen der Tasks auf den Maschinen keine bessere Lösung mehr erreicht werden kann, ohne dabei aber mögliche optimale Lösungen zu verwerfen.

Für die Suche durch alle möglichen Lösungen wird dynamisch ein binärer Suchbaum erstellt. Jeder Knoten in diesem Baum stellt eine möglicherweise partielle Lösung dar. Partiell heisst, dass noch nicht auf allen Maschinen alle Reihenfolgen festgelegt worden sind (siehe Kapitel über die Modellierung). Der entsprechende Graph hat dementsprechend ungerichtete Kanten. Richtet man eine dieser Kanten aus, so werden aus der einen partiellen Lösung zwei neue Lösungen (für beide Richtungen der Kante eine). Dieser Vorgang wird als branching bezeichnet. So früh wie möglich versucht man nun, bei einem Knoten zu beweisen, dass keine bessere Lösung möglich ist, wie auch immer die entsprechende Kante gerichtet wird. Bei einem solchen Knoten muss man kein branching, sondern ein bounding ausführen. Man begrenzt den Suchraum, indem man hier nicht mehr weitersucht. Ein branch-Schritt vergrössert also die Menge der noch zu untersuchenden Lösungen, ein bound-Schritt verkleiner sie.

Das bounding wird nun etwas detaillierter betrachtet. Zuerst berechnet man für jeden einzelnen Task aller Aufgaben drei Werte.

• Der erste ist die Zeit, welche benötigt wird, um einen Task zu bearbeiten. Diese Zeit wird mit tv (v für Verarbeitungszeit) bezeichnet.
• Der zweite Wert gibt an, wieviel Zeit mindestens verstreichen muss, bis die Bearbeitung dieses Tasks beginnen kann. Dies ist abhängig von den tv der vorhergehenden Tasks innerhalb der Aufgabe. Diese Zeit wird mit th (h für head) bezeichnet.
• Der dritte Wert gibt an, wieviel Zeit nach der Bearbeitung des Tasks noch mindestens verstreichen muss, bis die gesamte Aufgabe dieses Tasks beendet werden kann. Analog zum vorherigen Wert ist dies abhängig von den tv der nachfolgenden Tasks innerhalb der Aufgabe. Die dritte Zeit wird mit tt (t für tail) bezeichnet.

Die nun folgende Abbildung definiert drei Aufgaben mit je drei Tasks, welche auf drei Maschinen (M0, M1 und M2) verarbeitet werden müssen. Für den jeweils ersten Task einer Aufgabe gilt: th = 0. Für den jeweils letzten Task einer Aufgabe gilt analog dazu: tt = 0.

Abbildung 1: Links sind die drei Aufgaben mit ihren Tasks dargestellt. Rechts wird definiert, welcher Task auf welcher Maschine laufen soll. Das Kästchen stellt den Task selber dar. Die Zeit th ist jeweils durch den Strich vor dem Task angedeutet, analog dazu tt durch den Strich nach dem Task.

Wie geht man nun konkret vor, wenn man ein bound-Schritt ausführen möchte? Man weiss für jeden Task A, den man auf einer Maschine M festlegt, wieviel Zeit mindestens noch vergehen wird, bis der letzte Task der entsprechenden Aufgabe fertig ist (tt von A). Zusammen mit der aktuellen Zeit, zu welcher die Verarbeitung von A gestartet wird, und mit der Verarbeitungszeit tv von A kann man sich ausrechnen, wie lange jede Lösung mit der aktuellen Reihenfolge auf M mindestens dauern wird. Ist dies länger als die beste bisher gefundene Lösung dauert, so begrenzt man den Lösungsraum bei diesem Knoten.

 

Ein Beispiel

Abbildung 2 illustriert die Analyse eines branch-Teilschrittes mit den Werten aus Abbildung 1. Wir nehmen an, dass die bisher beste Lösung in 9 Zeiteinheiten verarbeitet sei (es gibt eine solche Lösung, und sie ist nicht die optimale).

Abbildung 2: a zeigt eine Situation auf der Maschine M0. M0 benötigt 7 Zeiteinheiten, um die vorgegebene Reihenfolge zu bearbeiten. Folglich müsste hier gegebenenfalls ein branch-Schritt durchgeführt werden (die bisher beste Lösung dauert länger als 7 Zeiteinheiten). b zeigt die Situation mit den Werten th und tt. Jede gültige Lösung in Kombination mit der Reihenfolge auf M0 dauert mindestens 12 Zeiteinheiten. Mit dieser Reihenfolge kann demnach keine bessere Lösung erreicht werden.

Durch den einzelnen bound-Schritt fallen in diesem kleinen Beispiel 12 der 216 (= 6%) theoretisch möglichen Lösungen weg.