Detailansicht
Heuristische Optimierung des multi-modalen RCPSP mit stochastischen Bearbeitungsdauern
Bernhard Hrobath
Art der Arbeit
Magisterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Magisterstudium Statistik
Betreuer*in
Walter Gutjahr
DOI
10.25365/thesis.48518
URN
urn:nbn:at:at-ubw:1-11571.58712.574263-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Ziel der Arbeit ist es, zwei heuristische Optimierungsmethoden für das multi-modale Resource-Constrained Project Scheduling Problem (RCPSP) zu erstellen und zu evaluieren. Dabei werden die Bearbeitungszeiten der Aktivitäten stochastisch (d.h. als Zufallsvariablen) angenommen und drei Modellierungen konstruiert. Als Basismodelle werden Gleichverteilung, Dreiecksverteilung und eine verschobene Weibull-Verteilung herangezogen.
Als Heuristiken werden dabei die variable neighborhood search (VNS) sowie ein genetischer Algorithmus (GA) verwendet. Diese Algorithmen müssen auf die besondere Problemstruktur, die stochastischen Bearbeitungszeiten sowie die in dieser Arbeit verwendete spezielle Zielfunktion – dem average value at risk zum Niveau α (AVaRα) der makespan maßgeschneidert konstruiert werden. Die Evaluierung erfolgt für insgesamt 90 Projekte der Benchmark-Datenbank PSPLIB. Die Projekte sind dabei von unterschiedlicher Größenordnung und Schwierigkeit. Aufgrund der stochastischen Modellierung der Bearbeitungszeiten ist eine Erweiterung der aus der Datenbank entnommenen Projekte durch die Konstruktion von Szenarien auf Basis der Modellierungen der stochastischen Bearbeitungszeiten nötig.
Der Vergleich der Algorithmen zeigt, dass der VNS-Algorithmus in der hier verwendeten Umsetzung häufig besser abschneidet als der GA. Es werden mit der VNS im Großteil der betrachteten Problemstellungen bessere Lösungen gefunden. Die Komplexität der Problemstellung und der Modellierung birgt einige Hürden, die bei der Umsetzung der Algorithmen beachtet werden müssen. Insofern ergibt sich noch Verbesserungspotenzial um die Performanz der Algorithmen zu steigern.
Die stochastische Modellierung der Bearbeitungszeiten ist zwar praxisrelevant, erfordert jedoch eine höhere Komplexität der Algorithmen, beispielsweise durch die aufwändigere Berechnung der Zielfunktion. Im Vergleich mit einer deterministischen Variante der Algorithmen erweisen sich die stochastischen Modellierungen jedoch als vorteilhaft. Dieser Vorteil zeigt sich insbesondere dann, wenn Zufallsmodelle zu Grunde liegen, in denen der Zusammenhang zwischen AVaRα und Modalwert (bzw. Erwartungswert) nicht mehr stark ausgeprägt ist.
Schlagwörter
Schlagwörter
(Deutsch)
heuristische Optimierung genetischer Algorithmus VNS RCPSP
Autor*innen
Bernhard Hrobath
Haupttitel (Deutsch)
Heuristische Optimierung des multi-modalen RCPSP mit stochastischen Bearbeitungsdauern
Publikationsjahr
2017
Umfangsangabe
81 Seiten : Diagramme
Sprache
Deutsch
Beurteiler*in
Walter Gutjahr
Klassifikationen
31 Mathematik > 31.99 Mathematik: Sonstiges ,
54 Informatik > 54.50 Programmierung: Allgemeines
AC Nummer
AC14488480
Utheses ID
42871
Studienkennzahl
UA | 066 | 951 | |