Tobias Paetz

Preemptive Resource-Constrained Project Scheduling Under Generalized Precedence Relations

PhD studentTobias Paetz
Research areaResource-Constrained Scheduling


Standard DIN-69901-5:2009 defines a project to be an endeavor which is essentially characterised by the uniqueness of its conditions in totality. Given the reduction of product life cycles and the customization of services, according to the estimates of Deutsche Bank Research, about 15% of value added world wide will be generated in projects by the year 2020. Resource-constrained project planning is concerned with the specification of execution time intervals for the activities involved in a project. When scheduling the activities, the limited availability of resources like staff, facilities, input materials, and liquid assets deployed in the execution of project activities have to be taken into account.

In the literature it is commonly assumed that the activities of a project cannot be interrupted during their execution. In the case of the aggregate rough-cut planning of projects and for many project planning applications in production planning, this assumption is, however, not fulfilled. In this doctoral project we are developing models and methods for resource-constrained project planning problems with interruptible activities between which generalized precedence relations can be defined. The precedence relations are assumed to be specified in the shape of minimum and maximum time lags between completion and start times of the activities. The proposed models include mixed-integer linear programming formulations and continuous relaxations that are based on the antichains of the precedence order induced by the time lags. The latter model can be solved with the aid of column-generation techniques and provide tight lower bounds on the optimum objective function values. To strengthen the model formulations, various preprocessing methods are deployed, which yield additional minimum and maximum lags between the activities. Novel priority-rule based methods are being developed for large problem instances. These methods rely on the generation of extra decision points that are derived from tentative upper bounds for minimax objective functions.