Loading…
Stochastic resource-constrained project scheduling
Stork, Frederik
In der ressourcenbeschränkten Projektplanung müssen Vorgänge unter Berücksichtigung von Reihenfolgebeziehungen und Kapazitätsrestriktionen zeitlich so eingeplant werden, dass eine gegebene Kostenfunktion minimiert wird. In der vorliegenden Arbeit wird zusätzlich davon ausgegangen, dass die Dauer der einzelnen Vorgänge nicht zu Beginn der Planung bekannt, sondern durch je eine Zufallsvariable gegeben ist. Auf diese Weise ist es möglich, unvorhersehbare Ereignisse wie zum Beispiel Wetterbedingungen, Krankheit von Mitarbeitern, Rechtsfragen oder Genehmigungsverfahren in die Planung eines Projekts mit einzubeziehen. Als Konsequenz hieraus kann das Risiko von Projekt-Verzögerungen und damit verbundenen Kostensteigerungen (von denen im Rahmen von umfangreichen Projekten häufig berichtet wird) reduziert werden. Ziel der vorliegenden Arbeit ist es, Algorithmen zu entwickeln, die die Berechnung guter Lösungen in akzeptabler Rechenzeit ermöglichen. Eine Lösung ist hier eine so genannte Politik, eine Planungsvorschrift, die zu jedem möglichen Entscheidungszeitpunkt t während der Umsetzung des Projekts eine Menge von Vorgängen definiert, deren Durchführung zum Zeitpunkt t begonnen werden soll. Basierend auf der Beobachtung, dass die häufig angewendeten Prioritäts-Politiken nicht für eine "robuste" Planung geeignet sind, liegt der Schwerpunkt der Untersuchungen auf der strukturell sehr attraktiven Klasse der präselektiven Politiken. Solche Politiken selektieren für jede minimal verbotene Menge F von Vorgängen einen Vorgang aus F, dessen Durchführung erst dann begonnen wird, wenn mindestens ein anderer Vorgang aus F beendet ist. (Eine minimal verbotene Menge ist eine minimale Teilmenge von Vorgängen, zwischen denen keine Reihenfolgebeziehungen vorliegen, die jedoch aufgrund der Ressourcen-Beschränkungen nicht zur gleichen Zeit in Betrieb sein können.) Um ein bestmögliches Verständnis von präselektiven Politiken zu erzielen, betrachten wir im ersten Teil der vorliegenden Arbeit eine Verallgemeinerung klassischer Reihenfolgebeziehungen zwischen Vorgängen, die so genannten AND/OR Reihenfolgebeziehungen. Diese finden zum Beispiel im Rahmen von Montage- oder Demontage-Prozessen Anwendung; der Zusammenhang zu dem oben beschriebenen ressourcenbeschränkten Scheduling-Modell besteht in der Tatsache, dass präselektive Politiken durch eine Menge von AND/OR Reihenfolgebeziehungen repräsentiert werden können. Es werden Resultate im Zusammenhang mit der Verallgemeinerung von Begriffen wie transitive Hülle und transitive Reduktion erzielt. Darüber hinaus werden für gegebene zeitliche Abstände zwischen den Vorgängen Algorithmen zur Berechnung frühster Startzeiten von Vorgängen entwickelt. Basierend auf den beschriebenen Ergebnissen werden Dominanzresultate für präselektive Politiken abgeleitet, sowie zwei Teilklassen der präselektiven Politiken definiert und untersucht, die vom algorithmischen Standpunkt gesehen bessere Eigenschaften als präselektive Politiken besitzen. Für diese Klassen von Politiken (und eine weitere, aus der Literatur bekannte Klasse) werden insgesamt fünf verschiedene Branch-and-Bound Verfahren entwickelt und implementiert sowie auf Basis von 1440 Instanzen getestet und miteinander verglichen. Die empirischen Ergebnisse zeigen, dass die entwickelten Resultate auf dem Gebiet der AND/OR Reihenfolgebeziehungen die Leistung der Branch-and-Bound Verfahren deutlich steigern und dass die vorgeschlagenen Teilklassen der präselektiven Politiken gute Ausgangspunkte für den algorithmischen Zugang zur heuristischen Lösung von Real-Life Instanzen darstellen.
In resource-constrained project scheduling, jobs (activities) have to be planned over time subject to precedence and resource constraints with the intention to minimize some objective function. In addition, we assume that the processing time of each job is uncertain and follows a given probability distribution. This extension of classical deterministic resource-constrained project scheduling is motivated by uncertain events that usually appear within the execution of projects. Weather conditions, unavailability of resources, and authorization processes are only some examples. The purpose of this thesis is to develop and implement algorithms to find solutions (so-called policies) of good quality within moderate computation times. A policy may be seen as a dynamic decision process that defines which jobs are started at certain decision times t, based on the observed past up to t. We study the class of preselective policies as well as different subclasses thereof. A preselective policy defines for each minimal forbidden set F a preselected job from F which is postponed until at least one other job from F has been completed. (A minimal forbidden set F is an inclusion-minimal set of jobs without any precedence constraints among them and the total resource consumption of the jobs in F exceeds the resource availability.) To obtain results on the combinatorial structure of preselective policies we study the concept of so-called AND/OR precedence constraints which are a generalization of traditional precedence constraints. AND/OR precedence constraints are of relevance in its own due to their appearance within, e.g., assembly or disassembly processes. We propose a new field of application which is based on the fact that any preselective policy can be expressed as a set of such constraints. To this end, we develop a number of basic algorithms for scheduling jobs subject to AND/OR precedence constraints. For example, we give two different polynomial time algorithms to compute earliest job start times as well as a linear time algorithm to detect 'transitive' AND/OR precedence constraints. The results obtained for AND/OR precedence constraints give also rise to consider particular subclasses of preselective policies. These classes differ with respect to both their computational tractability and the optimum expected objective function value that can be achieved within the respective class. We collect some of the structural and algorithmic properties of these classes of policies and use them to develop in total five branch-and-bound algorithms. Enhanced with many additional ingredients to speed up the computations, the algorithms are rigorously tested on 1440 instances created by the widely accepted instance generator ProGen. In particular, for each of the considered classes of policies, we establish results on the trade-off between computational efficiency on the one hand and solution quality on the other hand. The experiments reveal that the considered subclasses of preselective policies are a good starting point to develop heuristic approaches to solve large-scale stochastic resource-constrained project scheduling problems.
