Project Scheduling with Activity Exchange

Abstract

Motivated by a practice in aircraft maintenance, in this thesis we study models of project scheduling with exchange operations between activities. Here the idea is to move work content within the project network which admits to move work from critical positions to less critical ones. This admits reducing project duration and meeting due dates. The first paper adresses questions of complexity and identifies NP-hard as well as tractable cases. In the second paper a model is studied where this exchange procedure is fully implemented and a branch-and-bound approach is developed to solve this problem exactly. Within a computational study the performance of this procedure is demonstrated. The third paper adresses the aspect of uncertainty which occurs very naturally in a maintenance context. Since the stochastic nature also increases complexity we develop a heuristic approach and study its behaviour in a comprehensive computational study. In a broader setting this work can be also considered as a contribution to the growing field of flexible project scheduling, for which the classical assumption of a fixed project structure is relaxed in a novel way.

Motiviert durch eine Praxis aus der Instandsetzung von Flugzeugen, befasst sich diese Arbeit mit Projekt-Scheduling-Modellen mit Austauschoperationen für Aktivitäten. Die Idee hierbei ist es, Arbeitsaufwände innerhalb des Projektnetzwerks zu verlagern und somit Arbeitsinhalte von zeitkritischen hin zu weniger zeitkritischen Stellen zu verschieben. Dadurch kann die Projektdauer reduziert und Zeitvorgaben können eingehalten werden. Das erste Paper beschäftigt sich mit Fragen der Komplexität und identifiziert NP-schwere sowie in Polynomialzeit lösbare Fälle. Im zweiten Paper wird ein Modell untersucht bei dem die Austauschoption weitergehend umgesetzt wird und ein Branch-and-Bound-Ansatz entwickelt wird um das Problem exakt zu lösen. Im Rahmen einer Rechenstudie wird die Leistungsfähigkeit des Verfahrens nachgewiesen. Das dritte Paper greift den Aspekt der Unsicherheit auf wie er ganz natürlich im Instandsetzungskontext auftritt. Da die stochastische Natur aber auch die Komplexität des Problems erhöht, wird ein heuristischer Lösungsansatz entwickelt, dessen Lösungsverhalten im Rahmen einer umfangreichen Rechenstudie untersucht wird. In einem umfassenderen Kontext kann die Arbeit auch als Beitrag zum wachsenden Forschungsfeld des Schedulings von flexiblen Projekten betrachtet werden, wofür die klassische Annahme einer festen Projektstruktur auf eine neuartige Weise relaxiert wird.