Exakte Methoden und Matheuristiken für das Multi-Mode Resource-Constrained Project Scheduling Problem

Die Projektplanung ist ein wichtiges und aktuelles Forschungsgebiet des Operations Research: Dies ist einerseits auf die hohe Praxisrelevanz und andererseits auf die Komplexität des Problems zurückzuführen. Diese Arbeit betrachtet ein spezielles Problem der Projektplanung, das Multi-Mode Resource-Constrained Project Scheduling Problem (MRCPSP). Bei diesem soll die Dauer des Projektes minimiert werden, unter Berücksichtigung von knappen Ressourcen sowie von Präzedenz-beziehungen der Aktivitäten. Hierbei können verschiedene Ausführungsmodi für die Aktivitäten ausgewählt werden, mit denen unterschiedliche Ressourcenverbräuche und Zeitdauern verbunden sind. In dieser Arbeit werden zunächst alternative Implementierungen des mathematischen MRCPSP-Modells von Talbot (1982) untersucht. Im Anschluss folgen die Vorstellung und Untersuchung von zwei hybriden Ansätzen, welche Elemente der mathematischen Programmierung mit heuristischen Ansätzen kombinieren. Diese Kombination wird Matheuristik genannt. Die erste Matheuristik verbindet Iterated Local Search mit der MIP-Implementierung des mathematischen Modells von Talbot. Der zweite hybride Ansatz nutzt eine Adaptive Large Neighborhood Search. Diese erzeugt Teilprobleme, die dann durch Adaptionen der MIP-Implementierung von Talbot gelöst werden. Alle Lösungsverfahren werden in einer detaillierten Untersuchung miteinander verglichen. Abschließend werden neue Verfahren zur Generierung von unteren Schranken für das MRCPSP vorgestellt. Alle Experimente in dieser Arbeit wurden mit den MMLIB-Datensätzen von Van Peteghem und Vanhoucke (2014) durchgeführt. Die experimentellen Untersuchungen verbesserten die besten bekannten Lösungen von insgesamt 610 MMLIB-Instanzen. Des Weiteren konnten die unteren Schrankenwerte von 50,65% der MMLIB-Instanzen verbessert werden.