A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives for Rescheduling <s> This paperdescribes an algorithm designed to minimally reconfigure schedulesin response to a changing environment. External factors havecaused an existing schedule to become invalid, perhaps due tothe withdrawal of resources, or because of changes to the setof scheduled activities. The total shift in the start and endtimes of already scheduled activities should be kept to a minimum.This optimization requirement may be captured using a linearoptimization function over linear constraints. However, the disjunctivenature of the resource constraints impairs traditional mathematicalprogramming approaches. The unimodular probing algorithm interleavesconstraint programming and linear programming. The linear programmingsolver handles only a controlled subset of the problem constraints,to guarantee that the values returned are discrete. Using probebacktracking, a complete, repair-based method for search, thesevalues are simply integrated into constraint programming. Unimodularprobing is compared with alternatives on a set of dynamic schedulingbenchmarks, demonstrating its effectiveness.In the final discussion, we conjecture that analogous probebacktracking strategies may obtain performance improvements overconventional backtrack algorithms for a broad range of constraintsatisfaction and optimization problems. <s> BIB001 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives for Rescheduling <s> In this paper, we study the problem of how to react when an ongoing project is disrupted. The focus is on the resource-constrained project scheduling problem with finish–start precedence constraints. We begin by proposing a classification scheme for the different types of disruptions and then define the constraints and objectives that comprise what we call the recovery problem. The goal is to get back on track as soon as possible at minimum cost, where cost is now a function of the deviation from the original schedule. The problem is formulated as an integer linear program and solved with a hybrid mixed-inter programming/constraint programming procedure that exploits a number of special features in the constraints. The new model is significantly different from the original one due to the fact that a different set of feasibility conditions and performance requirements must be considered during the recovery process. The complexity of several special cases is analysed. To test the hybrid procedure, 554 20-activity instances were solved and the results compared with those obtained with CPLEX. Computational experiments were also conducted to determine the effects of different factors related to the recovery process. <s> BIB002
Rescheduling is necessary if the project is already in progress, but due to unexpected events (e.g., delays) the schedule that has been calculated before the start of the project is no longer valid. In such a situation, the problem's characteristics may have changed: Some activities might already be finished and can be ignored, some activities might be in progress and must be considered fixed (as long as no preemption is allowed), and the resource availability may have changed and might even have switched from time-independent to time-dependent. In contrast to proactive scheduling which anticipates disruptions by building robust schedules, we now consider the case that some disruption has occured and a new schedule has to be determined. This case is often referred to as reactive scheduling. Calhoun et al.  propose to minimize the perturbation of the original schedule by minimizing the number of activities that receive a different start time in the new schedule. Van de Vonder et al.  propose to reschedule the remaining activities such that the sum of deviations of the new finishing times from the original ones is minimized. They refer to a just in time problem developed by Vanhoucke et al.  where the weighted sum of earliness and tardiness of each activity is minized. They suggest to use the original finishing times as due dates in order to obtain a just-in-time problem. Sakkout and Wallace BIB001 measure the perturbation to be minimized as the sum of deviations of starting and finishing times of all activities. Zhu et al. BIB002 propose to penalize changes in resource utilization and in the selected modes in a multi-mode RCPSP. Moreover, it is considered to fix some activities by additional constraints. This can be useful if the activities have been scheduled that close to the current point of time that no change is possible, or if the schedule should catch up with the original one at a specific time in the future.