Department Mathematik
print
Navigationspfad
Inhaltsbereich

Forschungsgruppe TQA

Forschungsthema Scheduling

Problemstellung

Scheduling ist der Oberbegriff für eine große Klasse von Problemstellungen. Alle haben gemeinsam, dass für eine Menge von verfügbaren Maschinen und eine Menge von Jobs ein Zeitplan erstellt werden soll, mit dem alle Jobs abgearbeitet werden, und der bezüglich eines festgelegten Kriteriums optimal sein soll.

In der Industrie könnte das zum Beispiel heißen, Druckaufträge und die im Anschluss nötigen Schneid- und/oder Klebevorgänge auf den entsprechenden Maschinen einzuplanen. Auch ein Computer muss ein Problem dieser Art lösen, wenn er Prozessen Rechenzeit und Speicherplatz zuweist.

Üblicherweise werden Scheduling-Probleme klassifiziert anhand der < α|β|γ> Notation. Dabei wird in α die Maschinensituation beschrieben. Zum Beispiel haben wir drei identische Druckmaschinen und eine Klebe-Schneid-Maschine zur Verfügung oder wir befinden uns in einer Flow Shop - Umgebung, wo jeder Job die Maschinen nacheinander (in der selben Reihenfolge) durchlaufen muss. In den Fällen, für die sich die Arbeitsgruppe besonders interessieren, sind hier meistens eine Zahl von allgemeinen, unabhängigen Maschinen gegeben. In β werden Nebenbedingungen an den Plan und Informationen über die Jobs gegeben. Hier legt man zum Beispiel fest, ob die Zeiten, die Jobs zur Bearbeitung brauchen, von den Maschinen abhängen oder nicht, ob und wann jeder Job fertiggestellt sein muss, wann die Jobs zur Bearbeitung verfügbar sind und ob Jobs voneinander abhängig sein können. (Im Druckbeispiel oben kann zum Beispiel der "Schneidjob" für einen Bogen Papier erst nach dem "Druckjob" für diesen Bogen ausgeführt werden.) In γ wird die Zielfunktion festgelegt, die minimiert werden soll. Das ist zum Beispiel die Gesamtdauer des Plans oder auch die Anzahl der verspätet fertiggestellten Jobs. [Eine umfangreiche und gut durchsuchbare Sammlung von Ergebnissen im gesamten Scheduling Bereich kann man unter http://www-desir.lip6.fr/~durrc/query/ finden.]

Die Forschungsgruppe TQA beschäftigt sich wegen ihrer anwendungsorientierten Ausrichtung vor allem mit den sehr allgemeinen Problemen mit vielen möglichen Nebenbedingungen, also

  • α Maschinensituation: bei uns
    • Rm (m unabhängige Maschinen)
    • + Menge von vorab blockierten Zeiten für jede Maschine (was immer wieder für Schwierigkeiten sorgt, aber in der Realität oft gewünscht wird. Zum Beispiel könnten manche Maschinen feste Wartungszeiträume haben.)
  • β Nebenbedingungen: bei uns
    • dj (due date) Fertigstellungstermin für Job j
    • pjk (processing time) Bearbeitungszeit für Job j auf Maschine k
    • wj (weight) allgemeine Priorität des Jobs j
    • skij (setup time) Rüstzeit für Job j nach Job i auf Maschine k
    • rj (release date) Verfügbarkeitszeitpunkt von Job j
    • prec (precedence relations) gerichteter zyklenfreier Graph mit den Jobs als Knoten und den Vorgänger-/Nachfolgerbeziehungen als Kanten
    • lij (lag time) Zeit, die zwischen Ende von Job i und Anfang von Job j verstreichen muss (i Vorgänger von j)
    • μj Menge von möglichen Maschinen, auf denen Job j bearbeitet werden kann
  • γ Zielfunktion: In der Wirtschaft sollte man eigentlich meinen, dass die Zielfunktion, die es zu minimieren gilt, die Kosten des Plans beschreibt. Die Abhängigkeit dieser Kosten vom Plan ist aber für die Unternehmen selber nicht einfach festzustellen. Oft sind sinnvolle (Bestandteile von) Zielfunktionen:
    • Verspätungen/Nichteinhalten von Lieferterminen
    • Gesamtdauer des Plans, Gesamtdauer der auf den Maschinen verplanten Zeit, Rüstzeiten
    • Maschinenauslastung

Lösungsansätze /-methoden

Bei der Komplexität der Problemstellung ist nicht mehr zu erwarten, dass sich ein schneller und exakter Lösungsweg findet; da wir vor allem an praxistauglichen Lösungsansätzen interessiert sind, liegt der Schwerpunkt unserer bisherigen Forschung auf heuristischen Methoden.

Zu dem oben beschriebenen sehr allgemeinen Problem haben wir unter anderem zwei Algorithmen entwickelt, die auf heuristischen Methoden basieren. Diese (und viele andere heuristische Methoden) haben die folgenden Gemeinsamkeiten:

  1. [Eröffnungsverfahren] Es gibt eine Anfangslösung, der Algorithmus läuft dann in Runden; man merkt sich immer den besten bisher gesehenen Plan.
  2. [Verbesserungsverfahren] Es gibt eine Strategie, um von einer Lösung auf eine (möglicherweise bessere) Lösung zu kommen.
  3. [Abbruchkriterium]
Bevor man diese Grundstruktur mit konkretem Inhalt füllt, muss man sich überlegen, wie man eine Lösung repräsentiert. In der Literatur zu Schedulingproblemen findet man hier öfters Graphen (z.B in Darstellungen von Shifting Bottleneck), die den Zeitverlauf beschreiben. Also, wenn ein Job vor einem anderen auf derselben Maschine bearbeitet werden soll, so verbindet man diese durch eine orientierte Kante (Die tatsächliche Startzeit eines Jobs muss dann während der Planung noch nicht klar sein; erst wenn alle Reihenfolgen klar sind, sieht man auch, wann die Jobs bearbeitet werden müssen.). Man findet auch viele Darstellungen, die wirklich Schritt für Schritt die Jobs einplanen, indem sie ihnen einen Startzeitpunkt und eine Maschine zuweisen. Diese haben auch wir bisher überwiegend verwendet.

Unser erster Lösungsansatz folgt der Metaheuristik Simulierte Abkühlung und damit auch dem obigen Schema. Wenn man einen gültigen Plan erzeugt hat stehen einem dabei als Verbesserungsstrategien im Wesentlichen zwei Möglichkeiten zur Verfügung. Entweder man ändert für einen Job (und damit vermutlich auch für andere Jobs) nur die Startzeit, oder man verschiebt einen Job auf eine andere (mögliche) Maschine. Bei der simulierten Abkühlung wird im Gegensatz zu anderen lokalen Suchverfahren eine Lösung mit einer gewissen Wahrscheinlichkeit auch angenommen, wenn sie den Wert der Zielfunktion verschlechtert. Trotzdem hat sich in unseren Versuchen herausgestellt, dass es eine gute Idee ist, die Veränderungsstrategie zielgerichtet auszuwählen.

In unserem zweiten Lösungsansatz (der auch obigem Schema folgt) werden Pläne in einer Jobreihenfolge kodiert und die Veränderungen auch an dieser Reihenfolge anstatt direkt im Plan vorgenommen. Die möglichen Veränderungen sind dann alle durch das Vertauschen von zwei Jobs in dieser Reihenfolge erreichbar. Um aus einer Jobreihenfolge einen Plan zu generieren, kann man allgemein aus vielen Möglichkeiten wählen, die auch oft für Eröffnungsverfahren verwendet werden. Hier muss man auch die gegebenen Vorgänger-/Nachfolgerbeziehungen der Jobs berücksichtigen. Wir sind bisher mit den Ergebnissen sehr zufrieden, die sich ergeben, wenn man den nächsten Job, dessen Vorgänger bereits platziert sind, so einplant, dass er frühestmöglich endet (das legt Maschine und Startzeitpunkt fest).

Natürlichen müssen Eröffnungsverfahren und Verbesserungsstrategien immer abhängig von der Zielfunktion ausgewählt werden. Allerdings kann man für viele Anwendungen davon ausgehen, dass ein insgesamt kürzerer Plan auch lieber gesehen wird.

Weitere Vorhaben

Unser zweiter Lösungsansatz hat noch das Problem, dass die prinzipiell erreichbaren Pläne von der Methode abhängt, wie man Schedules aus den Jobreihenfolgen generiert. Insbesondere ist nicht gewährleistet, dass die optimale Lösung überhaupt gefunden werden kann. Hier wäre es interessant nachzuforschen, welche Strategien und welche Zielfunktionen die optimale Lösung abbilden können und ob man, falls das nicht möglich ist, zumindest eine Lösung mit Gütegarantie immer erreichen kann.

Desweiteren ist in allen verfolgten Ansätzen aufgefallen, dass die Algorithmen aus Komponenten bestehen, die nur eine bestimmte Aufgabe erfüllen und auf viele verschiedene Arten gelöst werden können. Zum Beispiel ist das Bauen eines Plans aus einer Jobreihenfolge eine solche Komponente. Oder natürlich auch die Eingangslösung und die Verbesserungsstrategien. Ein nächstes Ziel wäre es jetzt, einen Gesamtalgorithmus zu entwerfen, der abhängig von der zu lösenden Instanz des Problems die Umsetzung jeder Komponente intelligent aus einer Menge von vorab definierten Alternativen auswählt.