A survey of variants and extensions of the resource-constrained project scheduling problem <s> Maximal 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> Maximal 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> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Maximal Time Lags <s> Abstract In this paper, we tackle the challenging problem of scheduling activities to minimize the project duration, in which the activities (a) are subject to generalized precedence relations, (b) require units of multiple renewable, non-renewable and doubly constrained resources for which a limited availability is imposed, and (c) can be performed in one of several different ways, reflected in multiple activity scenarios or modes. These multiple modes give rise to several kinds of trade-offs (time/resource, time/cost and resource/resource trade-offs) which allow for a more efficient allocation and use of resources. We present a local search-based solution methodology which is able to handle many real-life project scheduling characteristics such as time-varying resource requirements and availabilities, activity ready times, due dates and deadlines, activity overlaps, activity start time constraints and other types of temporal constraints. <s> BIB003 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Maximal Time Lags <s> Projects with minimum and maximum time lags between the start of different activities (i.e. there are schedule-dependent time windows) play an important role in practice. Unfortunately, maximum time lags have been discussed in literature very rarely and only recently. However, maximum time lags (in addition to minimum ones) are needed to model a variety of practical requirements such as deadlines for subprojects or individual activities, simultaneous or non-delay execution of several activities, time-varying resource requirements, time windows for resources, scheduling of make-to-order production, and resource allocation in process-determined industry (cf. Neumann and Schwindt 1995, 1997). <s> BIB004 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Maximal Time Lags <s> Abstract This paper deals with resource-constrained project scheduling problems with nonregular objective functions where general temporal constraints given by minimum and maximum time lags between activities are prescribed. In particular, resource leveling and net present value problems are studied. We present different heuristic and exact procedures for (approximately) solving those problems. A detailed experimental performance analysis shows that these procedures also solve large problem instances in reasonable computing time. <s> BIB005 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Maximal Time Lags <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> Maximal Time Lags <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> BIB007 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Maximal Time Lags <s> This paper presents a heuristic solution procedure for a very general resource---constrained project scheduling problem. Here, multiple execution modes are available for the individual activities of the project. In addition, minimum as well as maximum time lags between different activities may be given. The objective is to determine a mode and a start time for each activity such that the temporal and resource constraints are met and the project duration is minimized. Project scheduling problems of this type occur e.g. in process industries. The heuristic is a multi---pass priority---rule method with backplanning which is based on an integration approach and embedded in random sampling. Its performance is evaluated within an experimental performance analysis for problem instances of real---life size with 100 activities and up to 5 modes per activity. <s> BIB008 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Maximal Time Lags <s> This paper presents a heuristic algorithm for solving RCPSP/max, the resource constrained project scheduling problem with generalized precedence relations. The algorithm relies, at its core, on a constraint satisfaction problem solving (CSP) search procedure, which generates a consistent set of activity start times by incrementally removing resource conflicts from an otherwise temporally feasible solution. Key to the effectiveness of the CSP search procedure is its heuristic strategy for conflict selection. A conflict sampling method biased toward selection of minimal conflict sets that involve activities with higher-capacity requests is introduced, and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This CSP search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically on a large set of previously studied RCPSP/max benchmark problems. <s> BIB009 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Maximal Time Lags <s> Abstract The paper presents an exact procedure for a general resource-constrained project scheduling problem where multiple modes are available for the performance of the individual activities and minimum as well as maximum time lags between the different activities may be given. The objective is to determine a mode and a start time for each activity such that all constraints are observed and the project duration is minimized. Project scheduling problems of this type occur, e.g. in process industries. The solution method is a depth-first search based branch-and-bound procedure. It makes use of a branching strategy where the branching rule is selected dynamically. The solution approach is an integration approach where the modes and start times are determined simultaneously. Within an experimental performance analysis this procedure is compared with existing solution procedures. <s> BIB010 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Maximal Time Lags <s> This paper presents an exact model for the multi-mode resource-constrained project scheduling problem with generalized precedence relations in which the minimal or maximal time lags between a pair of activities may vary depending on the chosen modes. All resources considered are renewable. The objective is to determine a mode and a start time for each activity so that all constraints are obeyed and the project duration is minimized. Project scheduling of this type occurs in many fields, for instance, construction industries. The proposed model has been inspired by the rectangle packing problems. In spite of the fact that it needs a feasible solution to start for conventional models, the new model has no need for a feasible solution to start. Computational results with a set of 60 test problems have been reported and the efficiency of the proposed model has been analyzed. <s> BIB011
Similarly to minimal time lags, we denote a maximal time lag between the completion time of activity i and the start time of successsor activity j asd FS i j , which means that C i +d FS i j ≥ S j must hold. In other words, activity j may not start later thand FS i j periods after the completion time of activity i. Analogously, maximal start-start, start-finish, and finish-finish time lags can be given. The RCPSP with minimal and maximal time lags is often referred to as RCPSP/max. Note that maximal time lags might lead to infeasible project instances, and the associated feasibility problem is NP-complete. Like minimal time lags, maximal time lags are covered by temp for β in the classification scheme of Brucker et al. BIB002 . Problems with minimal and maximal time lags have been discussed by, e.g., Bartusch et al. BIB001 , Cesta et al. BIB009 , Dorndorf et al.  , Neumann and Zimmermann  BIB005 , Neumann et al.  , Schwindt  , and Schwindt and Trautmann BIB006 ). The concepts of minimal and maximal time lags has also been considered within the multi-mode RCPSP, see Barrios et al.  , Brucker and Knust BIB007 , Heilmann BIB008 BIB010 , de Reyck and Herroelen BIB003 and Calhoun et al.  . Sabzehparvar and Seyed-Hosseini BIB011 consider minimal and maximal mode-dependent time lags, i.e. any time lag between two activities i and j depends on the modes m i and m j (thus, a maximal finish-start time lag can be written asd FS im i jm j ). It should be noted that maximal time lags typically lead to cyclic network structures, see Franck and Neumann  for a discussion of this issue. A survey of exact and heuristic algorithms for problems with maximal time lags has been given by Neumann and Zimmermann BIB004 .