TY - BOOK

T1 - Heuristiken für die gewinnorientierte Planung ressourcenbeschränkter Projekte mit erweiterbaren Kapazitäten

AU - Schnabel, André

N1 - Dissertation

PY - 2020/10/31

Y1 - 2020/10/31

N2 - Das ressourcenbeschränkte Projektplanungsproblem (RCPSP) ist eine in der Fachliteratur ausgiebig untersuchte Problemstellung. Die Kapazitäten der erneuerbaren Ressourcen im RCPSP sind über den Planungshorizont hinweg konstant verfügbar. Diese Annahme ist jedoch in der praktischen Anwendung in vielen Situationen nicht zutreffend. Exogen vorgegebene schwankende Ressourcenprofile wurden bereits in der Literatur betrachtet. Alternativ können die zeitabhängigen Kapazitäten der erneuerbaren Ressourcen endogen fest- gelegt werden, indem mit Kosten behaftete Zusatzkapazitäten in begrenztem Umfang hinzugenommen werden. Die Zahlungsbereitschaft eines Kunden sinkt typischerweise, wenn die Gesamtdauer des Projekts aufgrund von Verspätungen steigt. Der erzielte Deckungsbeitrag berechnet sich aus der Differenz zwischen Kundenerlös, welcher von der Projektdauer abhängt, und den variablen Kosten für Zusatzkapazität, welche durch den Ablaufplan hervorgerufen werden. Der Trade-off zwischen der Maximierung der Erlöse auf der einen Seite und einer Minimierung der variablen Kosten für Zusatzkapazität auf der anderen Seite führt zu einer neuartigen Problemstellung, welche das RCPSP generalisiert und als ressourcenbeschränkte Projektplanung mit projektdauerabhängigen Erlösen und Zusatzkapazitätskosten (engl. resource-constrained project scheduling problem with revenues and overcapacity costs, RCPSP-ROC) bezeichnet wird.Das RCPSP-ROC ist ebenfalls NP-schwer, da es das bereits NP-schwere RCPSP um zusätzliche Aspekte erweitert. Daher wurden in dieser Schrift heuristische Lösungsverfahren für das neuartige Problem entworfen und implementiert. Die Verfahren finden gute Lösungen für Probleminstanzen mit praxisnaher Größe in annehmbarer Zeit.In der Literatur werden mehrere effiziente heuristische Lösungsverfahren für das RCPSP vorgestellt. Diese planen Arbeitsgänge so früh wie möglich ein. Im Gegensatz zum RCPSP, welches als Zielstellung die Projektdauer minimiert, maximiert das RCPSP-ROC den Deckungsbeitrag. Der Deckungsbeitrag wird aus einem regulären Erlös-Term und einem nicht-regulären Kosten-Term berechnet. Es kann allerdings sinnvoll sein, Arbeitsgänge bewusst verzögert zu starten, da Kosten entstehen, wenn zusätzliche Kapazität benötigt wird. Die Menge der aktiven Pläne (bezogen auf die maximal erlaubte Zusatzkapazität) enthält folglich nicht zwangsläufig eine optimale Lösung für dieses Problem. Es wurden daher neue Algorithmen entworfen und evaluiert, um Ablaufpläne für das RCPSP-ROC zu erzeugen. Die Lösungsverfahren verbinden Ansätze von sowohl zeit- als auch kostenorientierten Zielfunktionen aus der Literatur zur Projektplanung.Diese Arbeit beschreibt das RCPSP-ROC in Form eines gemischt-ganzzahligen linearen Optimierungsmodells und untersucht strukturelle Eigenschaften des Problems im Rahmen einer fiktiven Fallstudie. Damit das NP-schwere RCPSP-ROC effizient gelöst werden kann, werden verschiedene heuristische Verfahren vorgestellt. Die Verfahren werden auf Basis einer neu entworfenen Problem- bibliothek miteinander verglichen. Diese Problembibliothek basiert auf den RCPSP-Testinstanzen aus der PSPLIB. Es wird gezeigt, dass maßgeschneiderte Genetische Algorithmen generische Blackbox-Heuristiken in den meisten Fällen dominieren. Die Blackbox-Heuristiken liefern wiederum bessere Ergebnisse für Instanzen des RCPSP-ROC als exakte Solver für gemischt-ganzzahlige lineare Optimierungsmodelle. Insgesamt heben die Ergebnisse die zentralen Charakteristika dieser Problemstellung hervor und zeigen, dass diverse Ansätze zur Planung von Projekten mit beschränkten Ressourcen aus der Literatur auf- gegriffen und angepasst werden können, um das RCPSP-ROC zu lösen.

AB - Das ressourcenbeschränkte Projektplanungsproblem (RCPSP) ist eine in der Fachliteratur ausgiebig untersuchte Problemstellung. Die Kapazitäten der erneuerbaren Ressourcen im RCPSP sind über den Planungshorizont hinweg konstant verfügbar. Diese Annahme ist jedoch in der praktischen Anwendung in vielen Situationen nicht zutreffend. Exogen vorgegebene schwankende Ressourcenprofile wurden bereits in der Literatur betrachtet. Alternativ können die zeitabhängigen Kapazitäten der erneuerbaren Ressourcen endogen fest- gelegt werden, indem mit Kosten behaftete Zusatzkapazitäten in begrenztem Umfang hinzugenommen werden. Die Zahlungsbereitschaft eines Kunden sinkt typischerweise, wenn die Gesamtdauer des Projekts aufgrund von Verspätungen steigt. Der erzielte Deckungsbeitrag berechnet sich aus der Differenz zwischen Kundenerlös, welcher von der Projektdauer abhängt, und den variablen Kosten für Zusatzkapazität, welche durch den Ablaufplan hervorgerufen werden. Der Trade-off zwischen der Maximierung der Erlöse auf der einen Seite und einer Minimierung der variablen Kosten für Zusatzkapazität auf der anderen Seite führt zu einer neuartigen Problemstellung, welche das RCPSP generalisiert und als ressourcenbeschränkte Projektplanung mit projektdauerabhängigen Erlösen und Zusatzkapazitätskosten (engl. resource-constrained project scheduling problem with revenues and overcapacity costs, RCPSP-ROC) bezeichnet wird.Das RCPSP-ROC ist ebenfalls NP-schwer, da es das bereits NP-schwere RCPSP um zusätzliche Aspekte erweitert. Daher wurden in dieser Schrift heuristische Lösungsverfahren für das neuartige Problem entworfen und implementiert. Die Verfahren finden gute Lösungen für Probleminstanzen mit praxisnaher Größe in annehmbarer Zeit.In der Literatur werden mehrere effiziente heuristische Lösungsverfahren für das RCPSP vorgestellt. Diese planen Arbeitsgänge so früh wie möglich ein. Im Gegensatz zum RCPSP, welches als Zielstellung die Projektdauer minimiert, maximiert das RCPSP-ROC den Deckungsbeitrag. Der Deckungsbeitrag wird aus einem regulären Erlös-Term und einem nicht-regulären Kosten-Term berechnet. Es kann allerdings sinnvoll sein, Arbeitsgänge bewusst verzögert zu starten, da Kosten entstehen, wenn zusätzliche Kapazität benötigt wird. Die Menge der aktiven Pläne (bezogen auf die maximal erlaubte Zusatzkapazität) enthält folglich nicht zwangsläufig eine optimale Lösung für dieses Problem. Es wurden daher neue Algorithmen entworfen und evaluiert, um Ablaufpläne für das RCPSP-ROC zu erzeugen. Die Lösungsverfahren verbinden Ansätze von sowohl zeit- als auch kostenorientierten Zielfunktionen aus der Literatur zur Projektplanung.Diese Arbeit beschreibt das RCPSP-ROC in Form eines gemischt-ganzzahligen linearen Optimierungsmodells und untersucht strukturelle Eigenschaften des Problems im Rahmen einer fiktiven Fallstudie. Damit das NP-schwere RCPSP-ROC effizient gelöst werden kann, werden verschiedene heuristische Verfahren vorgestellt. Die Verfahren werden auf Basis einer neu entworfenen Problem- bibliothek miteinander verglichen. Diese Problembibliothek basiert auf den RCPSP-Testinstanzen aus der PSPLIB. Es wird gezeigt, dass maßgeschneiderte Genetische Algorithmen generische Blackbox-Heuristiken in den meisten Fällen dominieren. Die Blackbox-Heuristiken liefern wiederum bessere Ergebnisse für Instanzen des RCPSP-ROC als exakte Solver für gemischt-ganzzahlige lineare Optimierungsmodelle. Insgesamt heben die Ergebnisse die zentralen Charakteristika dieser Problemstellung hervor und zeigen, dass diverse Ansätze zur Planung von Projekten mit beschränkten Ressourcen aus der Literatur auf- gegriffen und angepasst werden können, um das RCPSP-ROC zu lösen.

KW - Ressourcenbeschränkte Projektplanung

KW - Flexible Kapazitäten

KW - Überstunden

KW - Zusatzkapazität

KW - Genetische Algorithmen

KW - Lokale Suche

M3 - Dissertation

SN - 978-3-658-31609-9

T3 - Produktion und Logistik

PB - Springer Gabler

CY - Wiesbaden

ER -