A survey of variants and extensions of the resource-constrained project scheduling problem <s> Minimal Time Lags <s> Project networks with time windows are generalizations of the well-known CPM and MPM networks that allow for the introduction of arbitrary minimal and maximal time lags between the starting and completion times of any pair of activities. <s> BIB001 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Minimal Time Lags <s> Abstract The objective of this paper is to demonstrate how modelling ideas and solution procedures, borrowed from the field of generalized resource-constrained project scheduling, can be used to formulate and solve several types of production scheduling problems involving sequence-independent setup times as well as process and transfer batches. The computational results provide useful insight in the trade-offs that do exist between the computational effort required and the size of the process and transfer batches used. <s> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Minimal Time Lags <s> Abstract The problem of scheduling multiple, large-scale, make-to-order assemblies is considered. Beside `classical’ precedence and resource constraints as known from resource-constrained project scheduling we take spatial resource and part availability constraints into account. The objective is to minimize the sum of the weighted tardiness. We propose a MIP-model of the problem which is a generalization of three allocation problems. Since the problem is NP -hard, a list-scheduling heuristic is proposed and evaluated on a set of benchmark instances. <s> BIB003 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Minimal Time Lags <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> Minimal Time Lags <s> In this paper, two meta-strategies for computing lower bounds (for minimization problems) are described. Constructive (direct) methods directly calculate a bound value by relaxing a problem and solving this relaxation. Destructive improvement techniques restrict a problem by setting a maximal objective function value F and try to contradict (destruct) the feasibility of this reduced problem. In case of success, F or even F + 1 is a valid lower bound value. The fundamental properties and differences of both meta-strategies are explained by applying them to the well-known resource-constrained project scheduling problem (RCPSP). For this problem, only a few constructive bound arguments are available in the literature. We present a number of extensions and new methods as well as techniques for reducing problem data which can be exploited within the destructive improvement framework. Comprehensive numerical experiments show that the new constructive bound arguments clearly provide better bounds than the former ones and that further really significant improvements are obtained through an appropriate application of destructive improvement. <s> BIB005 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Minimal Time Lags <s> Abstract. This paper deals with the generalized resource-constrained project scheduling problem (GRCPSP) which extends the well-known resource-constrained project scheduling problem (RCPSP) by considering job specific release and due dates, non-negative minimum start-to-start time lags as well as time-varying resource availabilities. The structure of the project is represented by an acyclic network diagram. Though the extensions are of high practical importance, only a few exact solution procedures have been presented in the literature so far. Therefore, a new exact procedure PROGRESS is developed which includes new dominance rules as well as enhancements of existing ones. For evaluating the efficiency experimentally, new GRCPSP instances with 30 and 60 jobs are considered which extend the standard benchmark sets for the RCPSP generated by ProGen. PROGRESS shows superior performance when applied to the GRCPSP and is also very competitive in comparison to approaches proposed for the RCPSP. <s> BIB006 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Minimal Time Lags <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> BIB007 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Minimal Time Lags <s> Time-cost analysis is an important element of project scheduling, especially for lengthy and costly construction projects, as it evaluates alternative schedules and establishes an optimum one considering any project completion deadline. Existing methods for time-cost analysis have not adequately considered typical activity and project characteristics, such as generalized precedence relationships between activities, external time constraints, activity planning constraints, and bonuses/penalties for early/delayed project completion that would provide a more realistic representation of actual construction projects. The present work aims to incorporate such characteristics in the analysis and has developed two solution methods, an exact and an approximate one. The exact method utilizes a linear/integer programming model to provide the optimal project time-cost curve and the minimum cost schedule considering all activity time-cost alternatives together. The approximate method performs a progressive project length reduction providing a near-optimal project time-cost curve but it is faster than the exact method as it examines only certain activities at each stage. In addition, it can be easily incorporated in project scheduling software. Evaluation results indicate that both methods can effectively simulate the structure of construction projects, and their application is expected to provide time and cost savings. <s> BIB008 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Minimal Time Lags <s> Repetitive projects involve the repetition of activities along the stages of the project. Since the resources required to perform these activities move from one stage to the other, a main objective of scheduling these projects is to maintain the continuity of work of these resources so as to minimize the idle time of resources. This requirement, often referred to as work continuity constraints, involves a tradeoff between total project duration and the resource idle time. The contribution of this paper is threefold. First, we provide an extensive literature summary of the topic under study. Although most research papers deal with the scheduling of construction projects, we show that this can be extended to many other environments. Second, we propose an exact search procedure for scheduling repetitive projects with work continuity constraints. This algorithm iteratively shifts repeating activities further in time in order to decrease the resource idle time. We have embedded this recursive search procedure in a horizon-varying algorithm in order to detect the complete tradeoff profile between resource idle time and project duration. The procedure has been coded in Visual C++ and has been validated on a randomly generated problem set. Finally, we illustrate the concepts on three examples. First, the use of our new algorithm is illustrated on a small fictive problem example from literature. In a second example, we show that work continuity constraints involve a tradeoff between total project duration and the resource idle time. A last example describes the scheduling of a well-known real-life project that aims at the construction of a tunnel at the Westerschelde in The Netherlands. <s> BIB009
In the classical RCPSP, an activity must have finished before any of its successors can be started. This basic precedence concept can be extended by so-called minimal time lags d FS i j between the completion time C i of an activity i and the start time S j of successor activity j, which leads to constraints C i + d FS i j ≤ S j (note that we always have d FS i j = 0 in the standard RCPSP). Allowing negative minimal time lags implies that the corresponding activities may overlap. Minimal time lags are captured by the value temp for β in the α|β|γ notation of Brucker et al. BIB004 . Minimal time-lags have recently been considered by, e.g., Chassiakos and Sakellaropoulos BIB008 , Klein BIB005  , Klein and Scholl  BIB006 , Kolisch BIB003 , and Vanhoucke BIB009 . Demeulemeester and Herroelen BIB002 show how minimal time-lags can be used to capture sequenceindependent setup times as well as batches in production projects. Drexl et al. BIB007 consider a multi-mode problem with minimum time-lags that depend on the modes. In addition to a minimal time lag between the completion time of activity i and the start time of activity j, we may also consider minimal time lags between the start time of i and the start time of j, between the start time of i and the completion time of j, and between the finish time of i and the completion time of j. Note that these four types of minimal time-lags can all be transformed into each other such that one type is sufficient to obtain the full expressive power of minimal time lags. We omit further details here and refer to the transformation rules provided in Bartusch et al. BIB001 . It should be mentioned, however, that these transformations are not applicable if a multi-mode problem is considered.