Scheduling Algorithmen

Eine Approximation für das Job-Shop Scheduling

Inhalt

• Der shifting-bottlenecks Algorithmus
• Approximation durch lokale Optimierung
• Ein 5x5 Beispiel für beide Approximationen

 

Da alle heute bekannten Algorithmen zur optimalen Lösung von Scheduling Problemen sehr aufwendig sind, besteht vielfach der Wunsch nach einer Approximation. Diese ist einfacher zu berechnen als die optimale Lösung, jedoch muss man sich damit abfinden, dass sie weniger gut ist. Hier werden zwei Algorithmen beschrieben, welche solche Approximationen für das Job-Shop Scheduling Problem berechnen.

 

Der shifting-bottlenecks Algorithmus

Die Idee hinter dieser Approximation ist die folgende: Am Anfang löst man die schwierigen Fälle, am Schluss (wenn viel mehr Nebenbedingungen bestehen) fügt man die einfacheren Fälle ein. Im Fall des Job-Shop Scheduling wird also nach und nach diejenige Maschine ausgewählt, welche am schwierigsten zu optimieren ist. Sie wird als Flaschenhals (=bottleneck, daher der Name dieses Algorithmus) aller Maschinen angesehen.

Für diese Approximation berechnet man für jeden einzelnen Task aller Aufgaben die Werte tv, th und tt (sie wurden im Kapitel über den branch-and-bound Algorithmus bereits beschrieben). Die folgende Abbildung zeigt den ersten Schritt auf: Welche Maschine ist für sich alleine am schwierigsten zu optimieren. Eine optimale Anordnung minimiert die Zeit, welche von Anfang an verstreicht, bis der letzte Task und dessen tail (siehe oben) beendet sind.

Abbildung 1: Links sind die einzelnen Tasks verteilt auf ihre Maschinen dargestellt. Diese Tasks müssen möglichst optimal angeordnet werden. Die Reihenfolge der Tasks innerhalb der drei Aufgaben muss nicht berücksichtigt werden, da zu Beginn jede Maschine für sich alleine optimiert wird.

Man sieht in der Abbildung, dass die Maschine M0 den schlechtesten optimalen Wert hat, sie ist demzufolge der erste Flaschenhals. Nun sucht man die nächste Maschine aus. Die Bedingungen bleiben die gleichen, nur kommt eine neue Bedingung dazu: Die Reihenfolge auf der neuen Maschine muss so gewählt werden, dass sie mit der zuerst ausgewählten Maschine harmoniert. Das heisst, es muss die beste gültige Lösung mit jeweils zwei Maschinen berechnet werden. Gewählt wird die Maschine, welche im optimalen Fall am längsten benötigt. Auf diese Weise wählt man nach und nach alle Maschinen aus.

 

Approximation durch lokale Optimierung

Die Idee hinter dieser Approximation ist die folgende: Es ist möglich, auf einer einzigen Maschine alle Reihenfolgen der Tasks auszuprobieren und miteinander zu vergleichen. Man probiert natürlich nicht alle aus, sondern verwendet das branch-and-bound Verfahren.

Man hält auf allen Maschinen die Reihenfolge der Tasks fest, während man auf einer einzigen Maschine alle Varianten durchrechnet. Die Lösung mit der besten Zielfunktion merkt man sich. Dies tut man nun mit den restlichen Maschinen auch. Wenn man damit fertig ist, dann beginnt man wieder von vorne, und zwar so lange, bis sich die bisher beste Lösung nicht mehr verändert. Abbildung 2 illustriert einen einzelnen dieser Schritte.

Abbildung 2: Ein lokaler Optimierungsschritt führt von der oberen zur unteren Lösung. Nur auf der zweiten Maschine ändert sich die Reihenfolge der Tasks. Als Folge davon kann der dritte Task der blauen Aufgabe früher bearbeitet werden. Vorhin war dieser durch den zweiten blauen Task auf M1 blockiert.

Durch lokale Optimierung wird selten die optimale Lösung gefunden Diese ist in Abbildung 3 dargestellt, und kann ausgehend von der eben gefundenen Lösung nur erreicht werden, wenn auf allen drei Maschinen die Reihenfolge der Tasks verändert wird.

Abbildung 3: Es ist einfach zu sehen, warum diese Lösung optimal ist: Die Maschine M0 beginnt ganz am Anfang, endet ganz am Schluss und hat dazwischen keine freie Zeit mehr. Schneller geht es also nicht mehr.

Vergleicht man den Aufwand für die Berechnung der beiden Approximationsmethoden, so schneidet der shifting-bottlenecks Algorithmus besser ab.

 

Ein 5x5 Beispiel Für beide Approximationen

Als konkretes Beispiel für ein 5x5 Job-Shop Scheduling Problems wird jeweils die in der Einleitung spezifizierte Instanz verwendet.

Zuerst ein Beispiel für die Funktion des shifting-bottlenecks Algorithmus. In der Tabelle Sind alle Auswahlschritte aufgeführt. Die Abbildung 4 zeigt die daraus resultierende Lösung.

Schritt	optimale Werte für die Maschinen M0 M1 M2 M3 M4					ausgewählte Maschine	totale Zeit
ersten Flaschenhals suchen	16	16	17	14	14	M2	17 Sekunden
zweite Maschine hinzufügen	17	18	--	17	17	M1	18 Sekunden
dritte Maschine hinzufügen	18	--	--	18	18	M0	18 Sekunden
vierte Maschine hinzufügen	--	--	--	18	19	M4	19 Sekunden
letzte Maschine hinzufügen	--	--	--	19	--	M3	19 Sekunden

Abbildung 4: Die Approximation, welche mit dem shifting-bottlenecks Algorithmus gefunden wird. Der Zielfunktionswert liegt zwei Sekunden über dem optimalen Wert.

 

Nun wenden wir uns dem zweiten Algorithmus zu:
Die lokalen Optimierung wird in der interaktiven Vertiefung aus der Einleitung angewendet. Die Funktionsweise kann man dort sehr schön beobachten. Hier werden deshalb lediglich die Resultate zusammengefasst:

Schritt	Maschine und neue Permutation	Zielfunktionswert
0	M0 - M4: rot, grün, grau, gelb, blau	41 Sekunden
1	M4: rot, grau, grün, blau, gelb	37 Sekunden
2	M3: rot, grün, blau, gelb, grau	31 Sekunden
3	M1: grün, rot, grau, blau, gelb	27 Sekunden
4	M3: blau, rot, grün, gelb, grau	26 Sekunden
5	M4: grau, blau, rot, grün, gelb	25 Sekunden
6	M2: rot, gelb, grün, grau, blau	22 Sekunden

Abbildung 5: Die Approximation, welche durch lokale Optimierung gefunden wird. Der Zielfunktionswert liegt fünf Sekunden über dem optimalen Wert.