Job-Shop-Probleme mit Zusatzbeschränkungen

Man betrachtet n Fertigungsaufträge und m Arbeitssysteme. Die Aufgabenstellung der Termin- und Reihenfolgeplanung beruht auf den folgenden Voraussetzungen:

  1. Jeder Fertigungsauftrag hat eine Reihe von bestimmten Arbeitssystemen durchzulaufen, deren Folge im voraus bekannt ist. Diese aus technologischen Gründen hervorgehende Reihenfolge kann für jeden Auftrag anders ausfallen.

  2. Kein Fertigungsauftrag kann gleichzeitig in mehr als einem Arbeitssystem ausgeführt werden. Kein Arbeitssystem kann gleichzeitig mehrere Aufträge ausführen.

  3. Der komplexe Fertigungsauftrag kann in einzelne aufeinander folgende Arbeitsvorgänge eindeutig zerlegt werden. Die Bearbeitungszeit jedes Arbeitsvorganges sei bekannt und von anderen Bearbeitungsfaktoren unabhängig. Keine Arbeitsvorgänge dürfen unterbrochen werden.

  4. Jedem Fertigungsauftrag kann ein Beginn- und ein Abschlusstermin eindeutig zugeordnet werden. Diese Zeittermine sollen als Ungleichungsrestriktionen streng eingehalten werden.

Die Aufgabe der Termin- und Reihenfolgeplanung besteht nun darin, einen zulässigen Ablaufplan für die durchzuführenden Arbeitsvorgänge zu erstellen, der bezüglich mindestens einer vordefinierten Zielgröße optimal ist.

Im klassischen Job-Shop-Problem (vgl. Brucker, 1995) werden nur Annahmen (i-iii) durchgeführt. Voraussetzung (iv) kann deshalb als Beispiel einer Zusatzbeschränkung betrachtet werden, welche allein die Struktur jedoch nicht unbedingt die Komplexität des Originalproblems verschlechtert. Es ist bekannt (s. Garey, Johnson und Sethi, 1976), dass klassische Job-Shop-Probleme (vom Typ J | | Cmax) NP-vollständig im strengen Sinne sind.

Wie auch immer in solchen Fällen existierten weltbekannte Benchmarks, die seit Jahren nicht gelöst werden konnten, sowie geniale Algorithmen, welche diese Monstren als erste erledigten. Die bekannteste Benchmark FT10x10 (mit 10 Fertigungsaufträgen und 10 Arbeitssystemen) wurde im Jahre 1963 von Fisher und Thompson vorgeschlagen und galt damals als äußerst komplexe, praktisch unlösbare Aufgabe, welche man nur mit heuristischen (d. h. unexakten) Verfahren behandelte. Erst im Jahre 1989 wurde diese Benchmark mit einem Branch and Bound Algorithmus von Carlier und Pinson zum ersten Mal genau gelöst, mit Nachweis der Globalität des gefundenen Optimums. Es war eine Sensation!..

Dennoch nicht weniger sensationell klingt der nun wohl belegte Fakt, dass es noch 11 Jahre zuvor ein anderer Lösungsalgorithmus existierte, der das Monstrum von Fisher und Thompson ohne jegliche Schwierigkeiten schlug. Dieser Algorithmus stützte sich schon damals auf einige Ideen von modernen Constraint Propagation Techniques und war deshalb noch in der Lage, das durch die Zusatzbeschränkungen strukturell gestörte Job-Shop-Problem genau so gut zu verdauern. Der erste Artikel mit der Beschreibung des Algorithmus

[1] Yu. Zack. Certain properties of scheduling theory problems. Automation and Remote Control 39, 99-107, 1978.

enthielt leider keine Rechenteste, die seine praktische Effektivität demonstrieren könnten. Dies führte wahrscheinlich dazu, dass man ihn damals nur wenig beachtete und sehr bald völlig vergessen hatte. Die neusten Untersuchungen haben aber nachträglich gezeigt, dass das in [1] erläuterte Suchverfahren, mit ein paar unbedeutenden Nachbesserungen, die berühmte Benchmark FT10x10 (anhand moderner Personalcomputer) nur in wenigen Sekunden löst. Dies hat einen neuen ausführlicheren Artikel erfordert, der hiermit im Internet veröffentlicht wird:

[2] Yu. Zack, S. Rotin. Mathematisches Modell und Algorithmen der Termin- und Reihenfolgeplanung. Manuskript in Deutsch, Aachen, 2003.

Auf der Basis der alten Idee ist jetzt ein neues Programmpaket entstanden, das von Monat zu Monat weiter entwickelt wird. Bereits die erste Version des Lösungsprogramms zeigt recht gute Voraussetzungen für praktische Anwendungen und wird deshalb hierdurch auf den Software-Markt gebracht.

Freie Distribution unseres Programmprodukts kann man nach der Ausfüllung folgenden Formulars erhalten. In der Benutzeranleitung zu dieser Distribution ist unter anderem eine statische C-Bibliothek J_II_Cmax.lib beschrieben, deren Erwerb allerdings kostenpflichtig ist. Um weitere Angaben darüber zu bekommen, schreiben Sie uns bitte per e-Mail an!

Dr.-Ing. Yu. A. Zack
Dr. rer. nat. S. Rotin


Die mit Verfahren [1-2] erhaltene exakte Lösung zur Benchmark FT10x10 wird hiermit anhand Gantt-Diagramme veranschaulicht.

FT10x10.eps            FT10x10.pdf            FT10x10.jpg

© 2003-2004 Yuriy Zack