Scheduling projects with limited number of preemptions

A recent paper (Ballestín F, Valls V, Quintanilla S. Preemption in resource-constrained project scheduling. European Journal of Operational Research 2008;189:1136–152) revealed the potential benefits of allowing one interruption when scheduling activities in a resource-constrained project. This paper further investigates the effect of interruption on project length in more general cases. To achieve this, a new model that covers most practical applications of discrete activity preemption is proposed and a metaheuristic algorithm for the problem is developed. Computational experiments on the standard j120 and j30 sets generated using ProGen study the difference in makespan between allowing mm interruptions per activity, m=0,1,2,…m=0,1,2,… . In the second part of the paper the usefulness of preemption in the presence of due dates is analysed.