The impact of the number of preemptions in resource-constrained project scheduling problems with time-varying resources: computational experiments and a case study

Abstract This paper addresses the preemptive version of the resource-constrained project scheduling problem (RCPSP), with the aim of assessing the impact of the number of preemptions on project makespan. In fact, preempting some activity can reduce the makespan, but it may have the undesired effect of requiring a surplus of coordination in the project team. Hence, we consider the bicriteria problem of minimizing makespan and number of preemptions, and using a suitable integer linear programming formulation we compute the Pareto front for a sample of 30-job benchmark instances. Resource availability can either remain constant or can vary over time (according to a known schedule), as typical of situations in which the same resources are shared among various projects. We perform a detailed analysis of the impact of preemptions on project makespan, and how it is related to structural parameters of RCPSP instances. Among other results, we find that most often very few preemptions are enough to achieve most of the benefit. Also, the utility in introducing preemptions is significantly higher when resources vary over time. The proposed solution approach is then applied to a case study in Information Technology (IT) project management, showing how preemptions and efficiency can be traded off in practice.