| Ressourcenbeschränkte Projektplanung mit stochastischen Vorgangsdauern |
Schlüsselwörter:
Stochastic Scheduling, AND/OR Precedence Constraints, Branch-and-Bound
Stochastisches Scheduling, AND/OR Precedence Constraints, Branch-and-Bound
Sachgruppe der DNBAbstract
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.
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.
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.
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äselektive 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.
| Betreuer | Möhring, Rolf H.; Prof. Dr. |
| Gutachter | Möhring, Rolf H.; Prof. Dr. |
| Gutachter | Brucker, Peter; Prof. Dr. |
| Upload: | 2001-07-24 |
| URL of Theses: | http://edocs.tu-berlin.de/diss/2001/stork_frederik.pdf |