A survey of variants and extensions of the resource-constrained project scheduling problem <s> Introduction <s> A zero-one 0-1 linear programming formulation of multiproject and job-shop scheduling problems is presented that is more general and computationally tractable than other known formulations. It can accommodate a wide range of real-world situations including multiple resource constraints, due dates, job splitting, resource, substitutability, and concurrency and nonconcurrency of job performance requirements. Three possible objective functions are discussed; minimizing total throughput time for all projects: minimizing the time by which all projects are completed i.e., minimizing makespan; and minimizing total lateness or lateness penalty for all projects. <s> BIB001 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Introduction <s> Abstract In deterministic sequencing and scheduling problems, jobs are to be processed on machines of limited capacity. We consider an extension of this class of problems, in which the jobs require the use of additional scarce resources during their execution. A classification scheme for resource constraints is proposed and the computational complexity of the extended problem class is investigated in terms of this classification. Models involving parallel machines, unit-time jobs and the maximum completion time criterion are studied in detail; other models are briefly discussed. <s> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Introduction <s> 1 Basic Concepts.- 1.1 Directed Graphs and Project Networks.- 1.2 GERT Networks.- 1.3 Assumptions and Structural Problems.- 1.4 Complete and GERT Subnetworks.- 2 Temporal Analysis of GERT Networks.- 2.1 Activation Functions and Activation Distributions.- 2.2 Evaluation of Admissible GERT Networks.- 2.3 Computation of Some Quantities Important to Time Planning.- 2.4 Evaluation Methods for Admissible GERT Networks.- 3 STEOR Networks and EOR Networks.- 3.1 Markov Chains and Markov Renewal Processes.- 3.2 STEOR Networks and Markov Renewal Processes.- 3.3 Basic Properties of Admissible EOR Networks.- 3.4 Coverings of Admissible EOR Networks.- 3.5 Properties and Computation of Activation Functions and Activation Numbers.- 3.6 The MRP Method.- 4 Reducible GERT Networks.- 4.1 STEOR-Reducible Subnetworks.- 4.2 Cycle Reduction.- 4.3 Nodes Which Belong Together.- 4.4 Basic Element Structures.- 4.5 BES Networks.- 4.6 Evaluation Methods for BES Networks and General Admissible GERT Networks.- 5 Scheduling with GERT Precedence Constraints.- 5.1 Deterministic Single-Machine Scheduling.- 5.2 Stochastic Single-Machine Scheduling with GERT Precedence Constraints: Basic Concepts.- 5.3 Stochastic Single-Machine Scheduling with GERT Precedence Constraints: Optimality Criteria and Complexity.- 5.4 List Schedules and Sequences of Activity Executions.- 5.5 Minimum Flow-Time Scheduling in FOR Networks.- 5.6 A Flow-Time Scheduling Example.- 5.7 Minimizing the Maximum Expected Lateness in FOR Networks.- 5.8 Essential Histories and Scheduling Policies for Min-Sum Problems in General GERT Networks.- 5.9 Elements of Dynamic Programming.- 5.10 Determination of an Optimal Scheduling Policy for the General Min-Sum Problem.- 6 Cost Minimization for STEOR and FOR Networks.- 6.1 STEOR Networks with Time-Dependent Arc Weights.- 6.2 Cost Minimization in STEOR Networks: Basic Concepts.- 6.3 A Dynamic Programming Approach.- 6.4 The Value-Iteration and Policy-Iteration Techniques.- 7 Cost and Time Minimization for Decision Project Networks.- 7.1 Decision Project Networks.- 7.2 Cost Minimization.- 7.3 Randomized Actions.- 7.4 Multiple Executions of Projects.- 7.5 Time Minimization.- References. <s> BIB003 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Introduction <s> In this paper, research on the resource-constrained project scheduling problem is classified according to specified objectives and constraints. Each classified area is extensively surveyed, and special emphasis is given to trends in recent research. Specific papers involving nonrenewable resource constraints and time/cost-based objectives are discussed in detail because they present models that are close representations of real-world problems. The difficulty of solving such complex models by optimization techniques is noted. For the purposes of this survey, a set of 78 optimally solved test problems from the literature and a second set of 110 benchmark problems have been subjected to analysis with some well-known dispatching rules and a scheduling algorithm that consists of a decision-making process utilizing the problem constraints as a base of selection. The computational results are reported and discussed in the text. Constructive scheduling algorithms that are directly based on the problem constraints... <s> BIB004 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Introduction <s> Resource-constrained project scheduling involves the scheduling of project activities subject to precedence and resource constraints in order to meet the objective(s) in the best possible way. The area covers a wide variety of problem types. The objective of this paper is to provide a survey of what we believe are the important recent developments in the area. Our main focus will be on the recent progress made in and the encouraging computational experience gained with the use of optimal solution procedures for the basic resource-constrained project scheduling problem (RCPSP) and important extensions. We illustrate how the branching rules, dominance and bounding arguments of a new depth- first branch-and-bound procedure can be extended to a rich variety of related problems: the generalized resource-constrained project scheduling problem, the resource-constrained project scheduling problem with generalized precedence relations, the preemptive resource-constrained project scheduling problem, the resource availability cost problem, and the resource-constrained project scheduling problem with various time/resource(cost) trade-offs and discounted cash flows. <s> BIB005 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Introduction <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> BIB006 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Introduction <s> Abstract We consider heuristic algorithms for the resource-constrained project scheduling problem. Starting with a literature survey, we summarize the basic components of heuristic approaches. We briefly describe so-called X -pass methods which are based on priority rules as well as metaheuristic algorithms. Subsequently, we present the results of our in-depth computational study. Here, we evaluate the performance of several state-of-the-art heuristics from the literature on the basis of a standard set of test instances and point out to the most promising procedures. Moreover, we analyze the behavior of the heuristics with respect to their components such as priority rules and metaheuristic strategy. Finally, we examine the impact of problem characteristics such as project size and resource scarceness on the performance. <s> BIB007 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Introduction <s> There have been many survey papers in the area of project scheduling in recent years. These papers have primarily emphasized modeling and algorithmic contributions for specific classes of project scheduling problems, such as net present value (NPV) maximization and makespan minimization, with and without resource constraints. Paralleling these developments has been the research in the area of project scheduling decision support, with its emphasis on data sets, data generation methods, and so on, that are essential to benchmark, evaluate, and compare the new models, algorithms and heuristic techniques. These investigations have extended the frontiers of research and application in all areas of project scheduling and management. In this paper, we survey the vast literature in this area with a perspective that integrates models, data, and optimal and heuristic algorithms, for the major classes of project scheduling problems. We also include recent surveys that have compared commercial project scheduling systems. Finally, we present an overview of web-based decision support systems and discuss the potential of this technology in enabling and facilitating researchers and practitioners in identifying new areas of inquiry and application. <s> BIB008 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Introduction <s> The resource-constrained project-scheduling problem (RCPSP) and some of its generalizations are defined. Furthermore, constraint propagation techniques for these problems and related machine scheduling problems are introduced and possible applications of these techniques in connection with lower bound calculations, branch-and-bound methods, and heuristics are discussed. <s> BIB009 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Introduction <s> Abstract Project Management is a professional domain receiving growing attention during the last decades and now it is considered a key concept by Management Sciences to understand and to develop organizations. Operational Research has given essential scientific contributions to the success of Project Management not just through multiple models to understand and to represent projects but also by the development of algorithms and aids to support the decisional role of project manager. In this paper, the major contributions of OR are presented and discussed. <s> BIB010 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Introduction <s> This paper considers heuristics for the well‐known resource‐constrained project scheduling problem (RCPSP). It provides an update of our survey which was published in 2000. We summarize and categorize a large number of heuristics that have recently been proposed in the literature. Most of these heuristics are then evaluated in a computational study and compared on the basis of our standardized experimental design. Based on the computational results we discuss features of good heuristics. The paper closes with some remarks on our test design and a summary of the recent developments in research on heuristics for the RCPSP. <s> BIB011 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Introduction <s> The vast majority of the research efforts in project scheduling assume complete information about the scheduling problem to be solved and a static deterministic environment within which the pre-computed baseline schedule will be executed. However, in the real world, project activities are subject to considerable uncertainty, which is gradually resolved during project execution. In this survey we review the fundamental approaches for scheduling under uncertainty: reactive scheduling, stochastic project scheduling, fuzzy project scheduling, robust (proactive) scheduling and sensitivity analysis. We discuss the potentials of these approaches for scheduling under uncertainty projects with deterministic network evolution structure. <s> BIB012 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Introduction <s> The project scheduling problem involves the scheduling of project activities subject to precedence and/or resource constraints. Of obvious practical importance, it has been the subject of intensive research since the late fifties. A wide variety of commercialized project management software packages have been put to practical use. Despite all these efforts, numerous reports reveal that many projects escalate in time and budget and that many project scheduling procedures have not yet found their way to practical use. The objective of this paper is to confront project scheduling theory with project scheduling practice. We provide a generic hierarchical project planning and control framework that serves to position the various project planning procedures and discuss important research opportunities, the exploration of which may help to close the theory-practice gap. <s> BIB013
Project scheduling is an important task in project management. The presence of scarce resources as well as precedence relations between activities makes project scheduling a difficult task. In practice, specific software is used to support the scheduling process. The foundation of such software is a formal model that allows to describe the actual project by a set of scheduling constraints and an objective function. During the last decades, the resource-constrained project scheduling problem (RCPSP) has become a standard problem for project scheduling in the literature. It can be summarized as follows. The RCPSP considers a project with J activities which are labeled j = 1, . . . , J. The processing time (or duration) of an activity j is denoted as p j . Once started, an activity may not be interrupted, i.e., preemption is not allowed. Due to technological requirements, there are precedence relations between some of the activities. They are given by sets of immediate predecessors P j indicating that an activity j may not be started before each of its predecessors i ∈ P j is completed. The precedence relations can be represented by an activity-on-node network which is assumed to be acyclic. Each activity requires certain amounts of resources to be performed. The resources are called renewable because their full capacity is available in every period. We have K renewable resources labeled k = 1, . . . , K. For each resource k the per-period availability is assumed to be constant over time, it is given by R k . Activity j requires r jk units of resource k in each period it is in process. We consider two additional activities j = 0 and j = J + 1 representing the start and the completion of the project, respectively. Both are "dummy" activities with durations of 0 and no resource requests. All information is assumed to be deterministic and known in advance. The parameters are assumed to be nonnegative and integer valued. A schedule is an assignment of start times S j to the activities j = 0, 1, . . . , J + 1. The objective is to find a schedule which leads to the earliest possible end of the project, i.e., the minimal makespan. Blazewicz et al. BIB002 have shown that the RCPSP belongs to the class of the strongly NP-hard problems. A mathematical model for the RCPSP has been developed by Pritsker et al. BIB001 . Brucker et al. BIB006 have provided a notation to classify resource-constrained project scheduling problems. This notation follows the famous three field notation α|β|γ for machine scheduling problems introduced in Graham et al.  . In the context of project scheduling α specifies characteristics of the resources, β describes activities (and can be assigned more than one value), and γ denotes the problem's objective. The standard RCPSP is denoted by PS|prec|C max . While the RCPSP as given above is already a powerful model, it cannot cover all situations that occur in practice. Therefore, many researchers have developed more general project scheduling problems, often using the standard RCPSP as a starting point. Since the 1990s, several survey papers on project scheduling have been published. Those papers focus on methods for the RCPSP (see Hartmann and Kolisch BIB007 , Kolisch and Hartmann BIB011  ) and a few common variants (see Brucker BIB009 , Brucker et al. BIB006 , Herroelen et al. BIB005 , Herroelen BIB013 , Kolisch and Padman BIB008 ,Özdamar and Ulusoy BIB004 and Tavares BIB010 ). The purpose of this paper is to provide a broad overview over variants and extensions of the RCPSP that have been proposed in the literature. We restrict ourselves to deterministic approaches (for an introduction to stochastic problems, the reader is referred to Neumann BIB003 and Herroelen and Leus BIB012 ). Since a huge number of papers are available, we cannot give a fully exhaustive reference list, but we work out the diversity of problem settings currently available for project scheduling. If several papers are available for a concept, we focus on references from the last ten years. For those concepts presented here that are covered by the classification scheme of Brucker et al. BIB006 we point out to the related notation. Moreover, we propose extensions for some common concepts that are not yet covered by the existing classification scheme. The outline is as follows: Section 2 lists generalizations of the activity concept. Alternative precedence constraints and network characteristics are summarized in Section 3. Section 4 gives extensions of the resource concept. Different objectives are outlined in Section 5. Finally, Section 6 deals with the simultaneous consideration of multiple projects, and Section 7 briefly summarizes generators that have been developed to produce test instances for various project scheduling probems.