Optimierungsverfahren für die Personaleinsatz- und Ablaufplanung in chemischen Produktionsprozessen

Ziele und Methoden

Die Aufgabe besteht letztlich darin, jeder einzelnen Task eine zulässige Startzeit sowie die entsprechend qualifizierten Mitarbeiter zuzuweisen. Im Rahmen des Projektes wird zu diesem Zweck ein Programmpaket erstellt, das dem Planer ermöglichen soll, je nach Rechenzeit einen Produktionsplan mit Gütegarantie von 10% bis hin zur Optimalität aufzustellen. Bislang wird in der Praxis nur heuristisch, also ohne Kontrolle über die Güte geplant.

Ausgangspunkt ist ein in M. Bartusch, R. H. Möhring und F. J. Radermacher, Scheduling Project Networks with Resource Constraints and Time Windows [1] vorgestellter Branch-and-Bound Ansatz für Probleme mit Zeitfensterbedingungen bei knappen Ressourcen. Aufbauend auf diesem Ansatz konnten durch neue Branching Strategien mittlerweile erhebliche Verbesserungen erzielt werden [4].

Branch-and-Bound bezeichnet die rekursive Auffächerung des Gesamtproblems in kleinere Teilprobleme (branching), die mit Knoten im Branch-and-Bound Baum identifiziert werden. Durch verschiedene Techniken versucht man Teilprobleme zu identifizieren, die nicht weiter untersucht werden müssen. Dies geschieht einerseits in jedem Knoten durch den Vergleich einer unteren Schranke für den Zielfunktionswert des Knotens mit der besten bis dato bekannten Lösung (bounding). Andererseits können irrelevante Teilprobleme auch durch sogenannte Dominanzregeln identifiziert werden, indem verschiedene Knoten des Baumes miteinander verglichen werden.

Gute untere und obere Schranken sind stets entscheidend für den Erfolg der Methode. Sie bestimmen letztlich die Größe des Branch-and-Bound Baumes und damit das Laufzeitverhalten des Algorithmus; sie sind ferner wichtig zur Beurteilung der Güte bislang ermittelter Lösungen. Zur Ermittlung besserer unterer Schranken werden verschiedene Relaxierungen des Problems untersucht.

Speziell wird ferner an einem Branch-and-Cut Verfahren gearbeitet, welches unter anderem auf neuen Erkenntnissen über Intervallordnungs-Polytope [2] basiert.

Im Hinblick auf obere Schranken kommt erschwerend hinzu, daß die Ermittlung eines zulässigen Produktionsplans i. a.bereits ein NP-schweres Problem ist, für das im allgemeinen kein effizienter Algorithmus existiert.

Um letztendlich trotzdem eine exakte Lösung des BASF Problems in akzeptabler Zeit garantieren zu können, wird daher eine Kombination verschiedener mathematischer Verfahren entwickelt. In den äußeren Rahmen von Branch-and-Bound Verfahren werden die folgenden Ansätze eingebunden:

Polyedrische Untersuchungen von Planungsproblemen: Modellierung durch Intervallordnungs-Polytope, neue Ungleichungen für Intervallordnungs-Polytope, Berücksichtigung von Zeitfenstern, Branch and Cut Verfahren

Untere Schranken: LP und Lagrange Relaxierungen[5]

Obere Schranken: LP-basierte Heuristiken zur Erzeugung zulässiger Lösungen für das BASF-Problem

Dominanzregeln und starke kombinatorische Schranken zur Identifikation irrelevanter Teilprobleme im Branch and Bound Baum