New Challenges in Scheduling Theory

October 21 - 27, 2012 --- Centre CNRS "La Villa Clythia", Frejus, France

The preemptive project scheduling problem with generalized precedence relationships

SpeakerChristoph Schwindt

We study a resource-constrained project scheduling problem where the activities can be interrupted at any point in time during their execution and generalized precedence relationships between the activities have to be taken into account. The precedence relationships define minimum and maximum time lags between points in time when given parts of the activities have been executed. After providing a formal problem statement, we reduce the problem to a canonical form only containing nonpositive completion-to-start minimum time lags. Next, we develop an MILP formulation that encodes a schedule as a sequence of time slices with associated sets of activities that are in progress during the respective slice. Moreover, we establish an upper bound on the number of slices needed to represent an optimal schedule. Finally, we report on the results of an experimental performance analysis comparing upper bounds obtained with the MILP model and a large neighborhood descent procedure and lower bounds that arise from solving a linear programming relaxation of the problem via column generation.