Title (eng)
An application of constraint programming and Boolean satisfiability solving techniques to variants of the resource-constrained project scheduling problem
Parallel title (deu)
Über die Anwendung von Techniken aus der Constraintprogrammierung und aus dem SAT-Solving zur Lösung von ressourcenbeschränkten Projektplanungsproblemen
Author
Alexander Schnell
Advisor
Richard Hartl
Assessor
Walter Gutjahr
Christian Artigues
Abstract (deu)
In der Praxis sind Projekt Manager oft mit dem Problem konfrontiert, den in Zusammenhang stehenden Meilensteinen eines Projekts (auch Vorgänge genannt), Startzeitpunkte zuzuweisen, sodass eine termingerechte Fertigstellung des Projekts gewährleistet ist. Wenn die verfügbaren Ressourcen beschränkt sind und das Projekt aus einer großen Anzahl von Vorgängen besteht, ist dies eine schwierige Aufgabe. In der wissenschaftlichen Literatur wird diese Planungsaufgabe das ressourcenbeschränkte Projektplanungsproblem (RCPSP) genannt. Eine Vielzahl von Varianten des RCPSPs mit unterschiedlichen Problemcharakteristiken und Optimierungszielen wurde bereits von Forschern betrachtet.
In dieser Dissertation geht es hauptsächlich um eine Untersuchung von neuen exakten Algorithmen für das RCPSP mit einer und mehreren Ausführungsalternativen (SRCPSP und MRCPSP), und mit Vorrangbeziehungen und allgemeinen Zeitbeziehungen. Erst kürzlich hat sich herausgestellt, dass Branch and Bound-Verfahren, die Prinzipien aus der Constraintprogrammierung (CP) und dem SAT-Solving integrieren, sehr gute Ergebnisse bei der Lösung von Varianten des SRCPSP erzielen. Der hauptsächliche Forschungsbeitrag dieser Dissertation besteht in der
Anwendung und Erweiterung der bestehenden CP-SAT Verfahren, sodass Instanzen des MRCPSP mit Vorrangbeziehungen und allgemeinen Zeitbeziehungen in effizienter Weise exakt gelöst werden können. Für spezielle Instanzen des MRCPSP mit Vorrangbeziehungen und allgemeinen Zeitbeziehungen aus der Literatur erzielen wir mit unseren besten Modellen und zugehörigen Lösungsverfahren bessere Ergebnisse als die besten bekannten exakten Verfahren für diese Problemstellungen. Außerdem können wir insgesamt 613 offene Instanzen des MRCPSP mit Vorrangbeziehungen und allgemeinen Zeitbeziehungen schließen sowie die beste bekannte Gesamtprojektdauer für 447 Instanzen verbessern. Zum Abschluss der Dissertation liefern wir eine Vielzahl von Vorschlägen für zukünftige Forschungsthemen im Bereich von CP-SAT Ansätzen für Projektplanungsprobleme.
Abstract (eng)
In practice, project managers are confronted with the problem of assigning starting times to a number of precedence-related project milestones (activities), so that a
certain project deadline is respected. When the amount of available resources is limited and the number of activities is large, this is a highly complex task. In the scientific literature, this issue is known as the resource-constraint project scheduling problem (RCPSP). Many variants of the RCPSP introducing various problem characteristics and optimization goals have been considered in the literature. In this dissertation, the main research topic is the analysis of new exact solution approaches for the single-mode RCPSP (SRCPSP) and the multi-mode RCPSP (MRCPSP)
with standard precedence relations (SPRs) and generalized precedence relations (GPRs). Recently, Branch and Bound (BaB) algorithms combining Constraint Programming (CP)
and Boolean Satisfiability (SAT) Solving techniques have been highly successful for variants of the SRCPSP.
The major contribution of this dissertation is the introduction of various extensions of the CP-SAT approaches for the SRCPSP to the MRCPSP with SPRs and GPRs. Extensive computational studies show the quality of these generalizations. Our best performing solution approaches significantly outperform the state-of-the-art exact algorithms for the considered MRCPSP classes on certain benchmark sets from the literature. Furthermore, in total, we close (find the optimal solution and prove its optimality for) 613 open instances of the MRCPSP with SPRs and GPRs.
In addition, we improve the best known makespan for 447 instances. The dissertation ends with a proposal of future research directions in the area of CP-SAT approaches for scheduling problems.
Keywords (eng)
Resource-Constrained Project SchedulingExact AlgorithmsConstraint ProgrammingBoolean Satisfiability Solving
Keywords (deu)
Ressourcenbeschränkte ProjektplanungExakte AlgorithmenConstraintprogrammierungSAT Solving
Subject (deu)
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1318211
rdau:P60550 (deu)
VII, 126 S. : graph. Darst.
Number of pages
140
Association (deu)
Title (eng)
An application of constraint programming and Boolean satisfiability solving techniques to variants of the resource-constrained project scheduling problem
Parallel title (deu)
Über die Anwendung von Techniken aus der Constraintprogrammierung und aus dem SAT-Solving zur Lösung von ressourcenbeschränkten Projektplanungsproblemen
Author
Alexander Schnell
Abstract (deu)
In der Praxis sind Projekt Manager oft mit dem Problem konfrontiert, den in Zusammenhang stehenden Meilensteinen eines Projekts (auch Vorgänge genannt), Startzeitpunkte zuzuweisen, sodass eine termingerechte Fertigstellung des Projekts gewährleistet ist. Wenn die verfügbaren Ressourcen beschränkt sind und das Projekt aus einer großen Anzahl von Vorgängen besteht, ist dies eine schwierige Aufgabe. In der wissenschaftlichen Literatur wird diese Planungsaufgabe das ressourcenbeschränkte Projektplanungsproblem (RCPSP) genannt. Eine Vielzahl von Varianten des RCPSPs mit unterschiedlichen Problemcharakteristiken und Optimierungszielen wurde bereits von Forschern betrachtet.
In dieser Dissertation geht es hauptsächlich um eine Untersuchung von neuen exakten Algorithmen für das RCPSP mit einer und mehreren Ausführungsalternativen (SRCPSP und MRCPSP), und mit Vorrangbeziehungen und allgemeinen Zeitbeziehungen. Erst kürzlich hat sich herausgestellt, dass Branch and Bound-Verfahren, die Prinzipien aus der Constraintprogrammierung (CP) und dem SAT-Solving integrieren, sehr gute Ergebnisse bei der Lösung von Varianten des SRCPSP erzielen. Der hauptsächliche Forschungsbeitrag dieser Dissertation besteht in der
Anwendung und Erweiterung der bestehenden CP-SAT Verfahren, sodass Instanzen des MRCPSP mit Vorrangbeziehungen und allgemeinen Zeitbeziehungen in effizienter Weise exakt gelöst werden können. Für spezielle Instanzen des MRCPSP mit Vorrangbeziehungen und allgemeinen Zeitbeziehungen aus der Literatur erzielen wir mit unseren besten Modellen und zugehörigen Lösungsverfahren bessere Ergebnisse als die besten bekannten exakten Verfahren für diese Problemstellungen. Außerdem können wir insgesamt 613 offene Instanzen des MRCPSP mit Vorrangbeziehungen und allgemeinen Zeitbeziehungen schließen sowie die beste bekannte Gesamtprojektdauer für 447 Instanzen verbessern. Zum Abschluss der Dissertation liefern wir eine Vielzahl von Vorschlägen für zukünftige Forschungsthemen im Bereich von CP-SAT Ansätzen für Projektplanungsprobleme.
Abstract (eng)
In practice, project managers are confronted with the problem of assigning starting times to a number of precedence-related project milestones (activities), so that a
certain project deadline is respected. When the amount of available resources is limited and the number of activities is large, this is a highly complex task. In the scientific literature, this issue is known as the resource-constraint project scheduling problem (RCPSP). Many variants of the RCPSP introducing various problem characteristics and optimization goals have been considered in the literature. In this dissertation, the main research topic is the analysis of new exact solution approaches for the single-mode RCPSP (SRCPSP) and the multi-mode RCPSP (MRCPSP)
with standard precedence relations (SPRs) and generalized precedence relations (GPRs). Recently, Branch and Bound (BaB) algorithms combining Constraint Programming (CP)
and Boolean Satisfiability (SAT) Solving techniques have been highly successful for variants of the SRCPSP.
The major contribution of this dissertation is the introduction of various extensions of the CP-SAT approaches for the SRCPSP to the MRCPSP with SPRs and GPRs. Extensive computational studies show the quality of these generalizations. Our best performing solution approaches significantly outperform the state-of-the-art exact algorithms for the considered MRCPSP classes on certain benchmark sets from the literature. Furthermore, in total, we close (find the optimal solution and prove its optimality for) 613 open instances of the MRCPSP with SPRs and GPRs.
In addition, we improve the best known makespan for 447 instances. The dissertation ends with a proposal of future research directions in the area of CP-SAT approaches for scheduling problems.
Keywords (eng)
Resource-Constrained Project SchedulingExact AlgorithmsConstraint ProgrammingBoolean Satisfiability Solving
Keywords (deu)
Ressourcenbeschränkte ProjektplanungExakte AlgorithmenConstraintprogrammierungSAT Solving
Subject (deu)
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1318212
Number of pages
140
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0