Job Shop Scheduling mit Lagrangescher Relaxation

Die industrielle Produktion benötigt für die Fertigungsplanung und -steuerung Dispositionsverfahren, die die vorhandenen Ressourcen optimal nutzen. Diese Verfahren müssen bei Störungen flexibel darauf reagieren und die Produktion auch im eingeschränkten Betrieb weiterführen. Heuristiken und stochastische Verfahren lassen im allgemeinen keine Aussage über die Güte der erzielten Lösung zu, wenn man das Optimum nicht kennt. Die bekannten exakten Verfahren, die das Optimum sicher finden, benötigen einen Rechenaufwand, der exponentiell mit der Problemgröße wächst. In der vorliegenden Arbeit wurde daher ein Verfahren entwickelt, das einen fast-optimalen Plan mit garantierten Fehlerschranken und vertretbarem Rechenaufwand bestimmt. Die vorgegebene Kostenfunktion wurde so gewählt, daß die Endtermine der eingeplanten Aufträge möglichst eingehalten werden, da das heute dominierende Ziel ist, Kundenaufträge termingerecht abzuliefern. Es handelt sich um ein Iterationsverfahren, bei dem von Anfang an eine Lösung vorliegt, die verbessert wird. Falls erforderlich oder die Lösung gut genug ist, kann das Verfahren abgebrochen werden. Das Lagrange-Verfahren wurde zunächst für den Fall von gleich effizienten parallelen Maschinen für die einzelnen Operationen eines Auftrags entwickelt. Dafür wurde ein effizienter Algorithmus gefunden, dessen Rechenaufwand linear anstelle exponentiell mit der Anzahl der Operationen pro Auftrag wächst. Wird das Verfahren für das Job Shop-Scheduling-Problem mit unterschiedlich effizienten Maschinen für die einzelnen Operationen eines Auftrags verallgemeinert, hängt die Bearbeitungsdauer von der gewählten Maschine ab. Als kompliziertester Fall wird die simultane Planung weiterer Ressourcen und Betriebsmittel-Restriktionen für eine Operation erstmals in einem einstufigen Verfahren realisiert.