Stochastic resource-constrained project scheduling

Abstract

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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 146 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.