Scheduling in Netzwerken

Aufgrund des anhaltenden Fortschritts in der elektronischen Datenverarbeitung konnten mathematische Methoden in den letzten Jahrzehnten Einzug in die Produktionsplanung halten. So werden heute komplexe Planungsaufgaben in allen Industriebereichen mithilfe mathematischer Modelle bewältigt. In diesen Kontext lässt sich die Problemstellung dieser Arbeit einordnen. Deren Ziel besteht in der Herleitung eines Ablaufplans, der die Verarbeitung von Rohstahl auf mehreren parallelen Sequenzen von Maschinenanlagen optimal regelt. Um dieses Problem zu lösen, werden in dieser Arbeit klassische Flow-Shop-Modelle durch die Verwendung eines Scheduling-Netzwerkes erweitert. Die primäre Zielsetzung besteht dabei in der Entwicklung neuer Modellierungsansätze, die eine effiziente Ermittlung von Lösungen für praktisch relevante Probleminstanzen gewährleisten. Dazu werden zunächst die notwendigen Grundlagen der Schedulingtheorie sowie der kombinatorischen Optimierung vermittelt. Im nächsten Teil wird die Komplexität der erweiterten Flow-Shop-Probleme näher untersucht. Anschließend wird ein Approximationsverfahren vorgestellt und es werden spezielle Scheduling-Netzwerke analysiert. Abschließend werden gemischt-ganzzahlige Programme als effiziente Lösungsverfahren für beliebige Scheduling-Netzwerke hergeleitet.