A survey of variants and extensions of the resource-constrained project scheduling problem <s> Setup Times <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> BIB001 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Setup Times <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> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Setup Times <s> Abstract Project scheduling has long been an area of intensive research, but until recently most efforts have been dedicated to developing solution procedures and generalizing models, with little work done on generating problem instances. Additionally, if labor time regulations have to be taken into consideration, the classical resource-constrained project scheduling problem (RCPSP) cannot be used for many problems in manpower scheduling. This paper introduces several extensions to the RCPSP aimed at modeling such problems, and a problem instance generator based on the project generator ProGen incorporating these extensions. Thus, it becomes possible to thoroughly test solution procedures for, e.g., audit-staff scheduling, crew scheduling and timetabling problems. Preliminary computational results are given that were obtained with a greedy randomized solution method using priority rules specifically tailored to the generalized model. <s> BIB003 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Setup Times <s> The resource constrained project scheduling problem (RCPSP) can formulate many scheduling problems including jobshop and flowshop scheduling problems. In this paper, we extend the definition of RCPSP further so that various complicated constraints and objective functions arising in practice can be handled; for example, each activity can be processed in one of the selectable modes, the available amounts of renewable resources may vary depending on the periods, setup activities can be dealt with, and complex objective functions can be handled. Then, we develop a tabu search based heuristic algorithm, which contains elaborations in representing solutions and in constructing neighborhood. Our code was tested for many benchmarks of RCPSP, and also for some problems from real applications. For a number of RCPSP instances, we found better solutions than the best ones found so far. These computational results indicate the effectiveness and usefulness of our approach. <s> BIB004 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Setup Times <s> In this chapter project scheduling problems with setup times are considered. Some practical applications justifying considering setups separately from activities are described. An extensive classification of setup times adapted from machine scheduling is proposed, including activity vs. class setup, separable vs. inseparable setup, as well as sequence-independent and sequence-dependent setup times. A new category of setup times - schedule-dependent ones - is discussed. The main part of the paper shows how to model setup times in the presence of particular project components, such as: precedence constraints, resource availability constraints, multiple resource units requests, multiple resources, etc. Some possible extensions of the presented models are given. <s> BIB005 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Setup Times <s> Abstract In this paper, a multi-mode resource-constrained project scheduling problem with schedule-dependent setup times is considered. A schedule-dependent setup time is defined as a setup time dependent on the assignment of resources to activities over time, when resources are, e.g., placed in different locations. In such a case, the time necessary to prepare the required resource for processing an activity depends not only on the sequence of activities but, more generally, on the locations in which successive activities are executed. Activities are non-preemptable, resources are renewable, and the objective is to minimize the project duration. A local search metaheuristic—tabu search is proposed to solve this strongly NP-hard problem, and it is compared with the multi-start iterative improvement method as well as with random sampling. A computational experiment is described, performed on a set of instances based on standard test problems constructed by the ProGen project generator. The algorithms are computationally compared, the results are analyzed and discussed, and some conclusions are given. <s> BIB006 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Setup Times <s> Resource-constrained project scheduling with activity pre-emption assumes that activities are allowed to be interrupted and restarted later in the schedule at no extra cost. In the current paper, we extend this pre-emptive scheduling problem with setup times between activity interruptions and the possibility to schedule pre-emptive sub-parts of activities in parallel. The contribution of the paper is twofold. First, we briefly show that an efficient exact branch-and-bound procedure from the literature to solve the resource-constrained project scheduling problem can be easily adapted to cope with our problem extensions. Second, we extensively test the impact of these pre-emptive extensions to the quality of the schedule from a makespan point-of-view. <s> BIB007
In some cases, it may be required that a resource (e.g., a machine) must be prepared before a certain activity can be started. The time needed for such a preparation is called setup time. Mika et al. BIB006 consider three types of setup times. Sequence-independent setup times depend only on the activity and the resource on which the activity will be performed. Sequencedependent setup times additionally depend on the sequence of the activities, i.e., on the previous activity executed on the same resource. Finally, schedule-dependent setup times depend on the occupation of resources by activities over time, that is, the setup time related to the processing of activity j depends on the resources the direct predecessors of j are processed on. These concepts are embedded into an RCPSP with multiple modes (see Section 2.4). The authors note that schedule-dependent setup times could be captured by adding activities with specific modes, although this would lead to a huge number of additional activities and modes. In the notation of Brucker et al. BIB001 , s j and s i j as values of β can be used to represent sequence-independent and sequence-dependent setup times, respectively. Mika et al. BIB005 discuss many further aspects of setup times. They consider setup times between single activities as well as between families of activities. Moreover, they distinguish between inseparable setups which must be executed immediately before an activity starts and separable activities which may also start earlier. A setup may be executed either after the predecessors are finished or independently from the predecessors, or it may overlap with the predecessor for a given time. The setups of several resources may be required to be synchronous or not. Finally, so-called removal times are analogous to setup times but occur after an activity is finished. Vanhoucke BIB007 incorporates sequence-independent setup times into an RCPSP with preemption and fast tracking (see Section 2.1). Each time an activity is resumed after having been interrupted, the setup time occurs. Schwindt and Trautmann BIB002 incorporate sequence-dependent setup times into an RCPSP with various extensions. Their goal is to capture a scheduling problem that arises in batch production. Drexl et al. BIB003 employ sequence-dependent setup times (which are called changeover times here) into a multi-mode RCPSP (see Section 2.4). The setup time of activity j performed in mode m j depends on the previous activity i and its mode m i . Nonobe and Ibaraki BIB004 model setup times as additional activities that have to be completed before the activity which requires the setup is started.