Algorithmen zur Planung von Produktions-Transport-Systemen

Der Begriff Supply Chain (Lieferkette) in der Produktionsindustrie 
bedeutet die Verkettung von Lieferanten, Produzenten und Endkunden mit dem
Ziel der Kostensenkung, Produktivitätssteigerung, Senkung der 
Durchlaufzeiten, usw. Das heisst, nicht die einzelnen Abläufe, sondern die 
gesamte "Kette" wird bei der Optimierung betrachtet. Nehmen wir als Beispiel 
die Automobilindustrie: Die Autoteile kommen von unterschiedlichen 
Lieferanten, werden dann zu einem Auto zusammengebaut, die Autos müssen dann
an Kunden in der ganzen Welt ausgeliefert werden. Dabei müssen viele 
Bedingungen wie z.B. die Reihenfolge der einzelnen Aufgaben, Kapazität der 
Transportmittel und nicht zuletzt Termineinhaltung berücksichtigt werden.

Das Ziel dieser Diplomarbeit ist es, Algorithmen zur Transportplanung in 
einer Lieferkette zu entwickeln. Dabei beschränken wir uns auf ein 
zweistufiges Modell, d.h. n Jobs müssen eine Kette bestehend aus zwei 
Prozessen (Maschinen), einer Produktionsmaschine und einer darauffolgenden 
Transportmaschine durchlaufen. Das Ziel ist es, die n Jobs möglichst pünktlich 
fertig zu stellen. Folgende Bedingungen müssen dabei berücksichtigt werden:
Auf der Produktionsmaschine kann nur ein Job gleichzeitig bearbeitet werden, 
die Berbeitungszeit ist dabei jobabhängig, auf der Transportmaschine dagegen 
können mehrere Jobs zu einem Batch mit beschränkter Kapazität und konstanter 
Bearbeitungszeit zusammengefasst werden. Ein Job kann erst dann auf der 
Transportmaschine starten, wenn er auf der Produktionsmaschine fertiggestellt 
wurde. Weiterhin sind unterschiedliche Releasedates auf der 
Produktionsmaschine und Duedates für die gesamte Bearbeitungskette zu beachten.
(Releasedates sind Zeitpuntkte, zu denen die Jobs für die Bearbeitung auf 
der Maschine bereit sind, Duedates sind die spätesten 
Fertigstellungszeitpunkte der Jobs.)

Das Problem ist als NP-vollständig bekannt und wird zuerst als ein 
gemischt-ganzzahliges lineares Programm modelliert. Danach werden Lokale 
Suchverfahren zur Lösung des Problems eingesetzt. Die zentrale Rolle spielt 
dabei der sog. ``Barrieralgorithmus'', mit dem man das Batchingproblem 
(das Einplanen der Jobs auf der Transportmaschine unter Berücksichtigung 
von Release- und Duedates) polynomiell lösen kann.