A survey of variants and extensions of the resource-constrained project scheduling problem <s> Preemptive Scheduling <s> Abstract In this paper a branch-and-bound procedure is described for scheduling project activities subject to precedence and resource constraints, where activities can be preempted at any discrete time instant and where the objective is to minimize the project duration. The procedure is based on a depth-first solution strategy in which nodes in the solution tree represent resource and precedence feasible partial schedules. Branches emanating from a parent node correspond to exhaustive and minimal combinations of activities, the delay of which resolves resource conflicts at each parent node. A precedence based lower bound and several dominance rules are introduced in order to restrict the growth of the solutions tree. The solution procedure has been programmed in the C language and extensive computational experience is reported. <s> BIB001 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Preemptive Scheduling <s> The resource-constraint project scheduling problem is modeled as a zero-one integer programming model. The model considers many important characteristics of project scheduling including activity preemption, renewable and non-renewable resources, time-resource tradeoffs, and multiple objectives. Solution algorithms are developed for three single objective problems (time minimization, cost minimization, and resource leveling) and for the preemptive goal programming model that includes time, cost and resource leveling objectives. <s> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Preemptive Scheduling <s> In this paper we describe an exact algorithm to solve a preemptive project scheduling problem with scarce resources. As most of the scheduling problems also the studied one is NP-hard. Many different approaches, such as mathematical programming, heuristics, simulating annealing, etc., have been presented to solve this class of intractable problems. In our approach we consider a graph-theoretical method based on new coloring techniques. In particular, given a disjunctive graph we examine the correspondences between an assignment of time windows (i.e. activities starting time and finishing time) and an assignment of colors to the activities of a project, defining when an exact weighted coloring is an optimal preemptive schedule. We present computational results on randomly generated test problems of the branch and bound algorithm proposed. From the results obtained emerges that the possibility to manage hard problems using new coloring techniques seems to be more efficient than others, referring in particular to the performances of the algorithm proposed. <s> BIB003 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Preemptive Scheduling <s> Abstract Project scheduling is concerned with single-item or small batch production where scarce resources have to be allocated to dependent activities over time. Applications can be found in diverse industries such as construction engineering, software development, etc. Also, project scheduling is increasingly important for make-to-order companies where the capacities have been cut down in order to meet lean management concepts. Likewise, project scheduling is very attractive for researchers, because the models in this area are rich and, hence, difficult to solve. For instance, the resource-constrained project scheduling problem contains the job shop scheduling problem as a special case. So far, no classification scheme exists which is compatible with what is commonly accepted in machine scheduling. Also, a variety of symbols are used by project scheduling researchers in order to denote one and the same subject. Hence, there is a gap between machine scheduling on the one hand and project scheduling on the other with respect to both, viz. a common notation and a classification scheme. As a matter of fact, in project scheduling, an ever growing number of papers is going to be published and it becomes more and more difficult for the scientific community to keep track of what is really new and relevant. One purpose of our paper is to close this gap. That is, we provide a classification scheme, i.e. a description of the resource environment, the activity characteristics, and the objective function, respectively, which is compatible with machine scheduling and which allows to classify the most important models dealt with so far. Also, we propose a unifying notation. The second purpose of this paper is to review some of the recent developments. More specifically, we review exact and heuristic algorithms for the single-mode and the multi-mode case, for the time–cost tradeoff problem, for problems with minimum and maximum time lags, for problems with other objectives than makespan minimization and, last but not least, for problems with stochastic activity durations. <s> BIB004 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Preemptive Scheduling <s> Crew or staff scheduling is a complex combinatorial problem. It consists of assigning tasks to persons which have to perform these task and to schedule the performance of the tasks. Railway and airline crew scheduling problems, audit scheduling problems, school and university course scheduling and staff scheduling in hospitals are typical examples of such combinatorial problems. <s> BIB005 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Preemptive Scheduling <s> The paper deals with batch scheduling problems in process industries where final products arise from several successive chemical or physical transformations of raw materials using multi–purpose equipment. In batch production mode, the total requirements of intermediate and final products are partitioned into batches. The production start of a batch at a given level requires the availability of all input products. We consider the problem of scheduling the production of given batches such that the makespan is minimized. Constraints like minimum and maximum time lags between successive production levels, sequence–dependent facility setup times, finite intermediate storages, production breaks, and time–varying manpower contribute to the complexity of this problem. We propose a new solution approach using models and methods of resource–constrained project scheduling, which (approximately) solves problems of industrial size within a reasonable amount of time. <s> BIB006 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Preemptive Scheduling <s> For many applications of project scheduling to real-life problems, it is necessary to take into account calendars specifying time intervals during which some resources such as manpower or machines are not available. Whereas the execution of certain activities like packaging may be suspended during breaks, other activities cannot be interrupted due to technical reasons. Minimum and maximum time lags between activities may depend on calendars, too. In this paper, we address the problem of scheduling the activities of a project subject to calendar constraints. We devise efficient algorithms for computing earliest and latest start and completion times of activities. Moreover, we sketch how to use these algorithms for developing priority-rule methods coping with renewable-resource constraints and calendars. <s> BIB007 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Preemptive Scheduling <s> This paper presents results from an extensive computational study of the multi-mode resource-constrained project scheduling problem when activities can be split during scheduling under situations where resources may be temporarily not available. All resources considered are renewable and each resource unit may not be available at all times due to resource vacations, which are known in advance, and assignment to other finite duration activities. A designed experiment is conducted that investigates project makespan improvement when activity splitting is permitted in various project scenarios, where different project scenarios are defined by parameters that have been used in the research literature. A branch-and-bound procedure is applied to solve a number of small project scheduling problems with and without activity splitting. The results show that, in the presence of resource vacations and temporary resource unavailability, activity splitting can significantly improve the optimal project makespan in many scenarios, and that the makespan improvement is primarily dependent on those parameters that impact resource utilization. <s> BIB008 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Preemptive Scheduling <s> This paper presents a priority rule-based heuristic for the multi-mode resource-constrained project scheduling problem with the splitting of activities around unavailable resources allowed. All resources considered are renewable and each resource unit may not be available at all times due to resource vacations, which are known in advance. A new concept called moving resource strength is developed to help identify project situations where activity splitting is likely to be beneficial during scheduling. The moving resource strength concept is implemented in priority rule-based heuristics to control activity splitting when scheduling. Multiple comparisons of the performance of combination of activity–mode priority rules used in the heuristics are provided. Computational experiments demonstrate the effectiveness of the heuristic in reducing project makespan, and minimizing activity splitting. <s> BIB009 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Preemptive Scheduling <s> Abstract In this paper, the RCPSP (resource constrained project scheduling problem) is solved using a linear programming model. Each activity may or may not be preemptive. Each variable is associated to a subset of independent activities (antichains). The properties of the model are first investigated. In particular, conditions are given that allow a solution of the linear program to be a feasible schedule. From these properties, an algorithm based on neighbourhood search is derived. One neighbour solution is obtained through one Simplex pivoting, if this pivoting preserves feasibility. Methods to get out of local minima are provided. The solving methods are tested on the PSPLIB instances in a preemptive setting and prove efficient. They are used when preemption is forbidden with less success, and this difference is discussed. <s> BIB010
The basic RCPSP assumes that an activity cannot be interrupted once it has been started. Bianco et al. BIB003 , Brucker and Knust BIB005 , Debels and Vanhoucke  , Demeulemeester and Herroelen BIB001 and Nudtasomboon and Randhawa BIB002 allow activity preemption at discrete points in time, that is, an activity can be interrupted after each integer unit of its processing time. In the α|β|γ notation of Brucker et al. BIB004 , preemption is represented by adding the value prmt to β. Ballestin et al.  consider a variant in which an activity may be interrupted at most m times; their focus is on the case m = 1. Debels and Vanhoucke  extend the concept of preemption by a so-called fast tracking option: The parts of an activity that result from preemption need not to be processed in sequence, i.e. they can also be carried out in parallel. Franck et al. BIB007 propose a calendar concept for project scheduling which includes preemptive scheduling. A calendar is defined as a binary function that determines for each period whether activity execution is possible or a break occurs during which an activity may not be started or continued. (Note that there is an analogy between the calendar concept and resource capacities varying with time, cf. Section 4.6.) Activities are allowed to be interrupted but only due to calendar breaks (a similar concept is considered in Schwindt and Trautmann BIB006 ). Moreover, each activity j has a minimum processing time ε j during which it may not be interrupted. Buddhakulsomsiria and Kim BIB008 BIB009 follow a similar approach. Their approach permits activity splitting due to resource vacations (i.e., resource capacities varying with time). This concept is embedded into a multi-mode RCPSP with renewable resources only (cf. Section 2.4). Damay et al. BIB010 consider two types of activities. An activity of the first type may not be interrupted. An activity of the second type may be interrupted at arbitrary (not necessarily integer) points in time.