Man betrachtet n Fertigungsaufträge und m Arbeitssysteme. Die
Aufgabenstellung der Termin- und Reihenfolgeplanung beruht auf den folgenden
Voraussetzungen:
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.
Kein Fertigungsauftrag kann gleichzeitig in mehr als einem Arbeitssystem
ausgeführt werden. Kein Arbeitssystem kann gleichzeitig mehrere Aufträge ausführen.
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.
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