Scheduling Algorithmen

Einleitung in das Job-Shop Scheduling

Inhalt

• Erklärung des Problems
• Darstellung als gerichteter, azyklischer Graph
• Steigerung der Komplexität
• Eine interaktive Animation zur weiteren Vertiefung

 

Erklärung des Problems

Die klassischen Scheduling Probleme finden wir in den Gebieten Fabrikations- und Transportplanung. Exemplarisch wird hier das sogenannte job-shop scheduling problem beschrieben (es wird als eines der schwierigsten Optimierungsprobleme überhaupt angesehen). Es geht prinzipiell darum, eine Menge von Arbeiten auf einer Anzahl von Maschinen auszuführen. Die Zielfunktion für dieses Problem heisst: Das Maximum aller Verarbeitungszeiten soll minimiert werden. Mit anderen Worten: Diejenige Maschine, welche am längsten arbeitet, soll so schnell wie möglich fertig sein. Dabei müssen einige Regeln beachtet werden:

• Es sollen n Aufgaben auf m Maschinen bearbeitet werden.
• Jede Arbeit besteht aus ebenfalls m Teilarbeiten, sogenannten Tasks. In welcher Reihenfolge diese Tasks abgearbeitet werden müssen, ist klar definiert. Die Bedingung dafür, wann mit der Arbeit an einem Task begonnen werden kann, ist also, dass der vorhergehende Task fertig ist (und dass die benötigte Maschine frei ist).
• Innerhalb einer Aufgabe muss jeder Task auf einer anderen Maschine ausgeführt werden. Welche Maschine das ist, steht von Anfang an fest.
• Keine Maschine kann mehrere Tasks gleichzeitig bearbeiten.
• Ein angefangener Task kann nicht unterbrochen werden.

Zur Komplexität solcher Probleme: Heute kann man Probleme dieser Art in der Grössenordnung von 10 Maschinen und 10 Aufgaben optimieren. Sobald diese Werte steigen, wird das Problem zu komplex und kann nicht mehr in vernünftiger Zeit gelöst werden. Abbildung 1 zeigt ein Beispiel für ein Job-Shop Scheduling Problem.

Abbildung 1: Links sind die vier Aufgaben dargestellt. Sie bestehen jeweils aus drei Tasks. Die zur Verfügung stehenden Maschinen sind M1, M2 und M3. Welcher Task auf welcher Maschine ablaufen muss, wird aus der Tabelle ersichtlich. Rechts sind zweimal die Zeitachsen der drei Maschinen dargestellt. In dieser Ansicht sieht man, welche Maschine zu welcher Zeit welchen Task bearbeitet.

Der Ablauf a in Abbildung 1 entsteht, wenn man alle Tasks ganz einfach der Reihe nach auswählt und sie zum frühest möglichen Zeitpunkt der entsprechenden Maschine zur Bearbeitung übergibt. Die Reihenfolge ist also: Zuerst A1 bis D1, dann A2 bis D2 und zum Schluss A3 bis D3. Auf diese Weise ist der zu minimierende Wert der Zielfunktion gleich sieben Zeiteinheiten (Die letzte Maschine ist nach sieben Zeiteinheiten fertig mit ihrer Arbeit). Der Ablauf b in Abbildung 1 resultiert aus einer Analyse der Situation in a. A3 kann erst gestartet werden, wenn A2 beendet wurde. Die Sequenz kann so umgestellt werden, dass M3 früher mit der Arbeit beginnen kann. Die gefundene Lösung benötigt eine Zeiteinheit weniger.

Man kann zeigen, dass die Sequenz b optimal gemäss der vorgegebenen Zielfunktion ist. Das heisst, es gibt keine gültige Lösung für dieses konkrete Problem, welche weniger Zeit benötigt. Bis mit dem ersten Task (im Beispiel A3) auf M3 begonnen werden kann, müssen die entsprechenden Vorgänger (das sind A1 und A2) abgeschlossen sein. Das dauert in jedem Fall mindestens zwei Zeiteinheiten. Da die analoge Überlegung auch für B3, C3 und D3 gilt, kann M3 nicht vor dem dritten Zeitintervall mit der Arbeit beginnen. Da M3 insgesamt vier Tasks sequentiell verarbeiten muss und nicht mehrere Tasks gleichzeitig verarbeiten kann, dauert die Verarbeitung mindestens sechs Zeiteinheiten.

 

Darstellung als gerichteter, azyklischer Graph

Ein Job-Shop Scheduling Problem wird häufig als gerichteter, azyklischer Graph modelliert. Die Knoten dieses Graphen repräsentieren die einzelnen Tasks. Die Kanten (in einem gerichteten Graphen sind dies Pfeile) definieren eine Reihenfolge. Ein Pfeil von X nach Y heisst: X wird vor Y bearbeitet. Abbildung 2 zeigt den Graphen für den Ablauf b aus Abbildung 1.

Abbildung 2: Die blaue Pfeile stellen die Abhängigkeiten der Tasks innerhalb einer Aufgabe dar. Die roten Pfeile bezeichnen die Reihenfolge, in welcher die drei Maschine die Tasks bearbeiten. Um schnell entscheiden zu können, ob der Graph wirklich azyklisch ist, kann man den Graphen verziehen. Dadurch entsteht eine Ansicht, wie sie Abbildung 3 zeigt.

Abbildung 3: Die Anfangs- und Endpunkte der Pfeile sind die selben, wie in Abbildung 2. Alle Kanten sind gerichtet und laufen von links nach rechts. Da kein Pfeil von rechts nach links läuft, muss der gerichtete Graph azyklisch sein.

Jeder gerichtete, azyklische Graph stellt eine gültige Lösung des Problems dar. Sind bei einem Graphen nicht alle Kanten gerichtet, so spricht man von einer partiellen Lösung. Sie ist nicht gültig, da in diesem Fall auf mindestens einer Maschine die Reihenfolge der Tasks nicht festgelegt ist.

 

Steigerung der Komplexität

Ein typischer Wesenszug aller Scheduling Probleme ist, dass immer alles noch komplizierter gemacht werden kann. Jedes Problem lässt sich durch Hinzufügen von weiteren Bedingungen noch etwas aufblasen. Man könnte beispielsweise den frühesten und spätesten Zeitpunkt festlegen, an welchem eine Aufgabe begonnen (oder analog dazu beendet) werden muss. Das kann auch auf der Ebene der Tasks geschehen. Wem das noch nicht reicht, der kann zudem festlegen, dass auch zwei Tasks aus verschiedenen Aufgaben voneinander abhängig gemacht werden können. Das bedeutet dann zum Beispiel, dass ein Task aus Aufgabe A zuerst beendet werden muss, bevor mit der Arbeit an einem bestimmten Task in Aufgabe B begonnen werden kann.

 

Eine interaktive Animation zur weiteren Vertiefung

Die folgende Abbildung definiert ein 5x5 Job-Shop Scheduling Problem. Die nachfolgende interaktive Optimierung visualisiert und löst genau dieses Problem.

Abbildung 4: Dargestellt sind fünf Aufgaben, welche aus jeweils fünf Tasks bestehen. Zu jedem dieser Tasks werden zwei Werte angegeben: die Maschine, auf welcher er ausgeführt werden muss und die Zeit, welche für seine Verarbeitung benötigt wird.

Die farbigen Balken stellen die Tasks einer Aufgabe dar (Die Farbe kennzeichnet die Aufgabe). Die Tasks können mit der Maus verschoben werden, um so eine bessere Lösung zu finden. Weiter steht die Möglichkeit der lokalen Optimierung zur Verfügung (Details im Kapitel über lokale Optimierung). Als Komfort stehen zusätzliche Funktionen zur Verfügung: Abspeichern von einigen Versionen, zurück zur Ausgangslage, einen Schritt rückwärts und eine optimale Lösung anzeigen.

Hinweise zur Benutzung:

• Dieses Applet setzt einen Java 1.1 fähigen Browser voraus.
• Die Ausgangslage entsteht folgendermassen: Zuerst werden alle Tasks der ersten Aufgabe (rot) auf die Maschinen verteilt. Darauf folgen auf allen Maschinen so früh wie möglich die Tasks der zweiten Aufgabe (grün) und so weiter, bis alle Tasks der letzten Aufgabe (blau) gesetzt sind.
• Manchmal blinken Paare von Tasks. Dies Bedeutet, dass die Reihenfolge der Bearbeitung mit den eingestellten Permutationen nicht eingehalten werden kann. Es entstehen Zyklen im gerichteten Graphen (siehe oben).
• Die lokale Optimierung kann einmal durchgeführt werden, oder so lange, bis keine Verbesserung durch lokale Optimierungen mehr erreicht werden kann.
• Ein verschobener Task wird immer vor demjenigen eingefügt, über oder vor dem die Maus beim Loslassen steht. Dabei wird ein gieriger Algorithmus verwendet, das heisst: Die Tasks werden soweit nach rechts gezogen, wie möglich. Sie hängen quasi an Federn.