A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> This paper addresses a general class of nonpreemptive resource-constrained project scheduling problems in which activity durations are discrete functions of committed renewable and nonrenewabe resources. We provide a 0-1 problem formulation and stress the importance of the outlined model by giving applications within production and operations management. Furthermore, we prove that even the problem to derive a feasible solution is NP-complete. As a consequence, solution procedures proposed so far suffer from severe drawbacks: Exact procedures can only solve very small instances to optimality, while heuristic solution approaches fail to generate feasible solutions when problems become highly resource-constrained. Hence, we propose a new local search methodology which first tries to find a feasible solution and second performs a single-neighbourhood search on the set of feasible mode-assignments. In order to evaluate the new procedura we perform a rigorous computational study on the ProGen benchmark-set which is available in the open literature. The experiment includes a comparison of our procedure with other recently proposed heuristics. <s> BIB001 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> In this paper we consider the resource-constrained project scheduling problem with multiple execution modes for each activity and makespan minimization as objective. We present a new genetic algorithm approach to solve this problem. The genetic encoding is based on a precedence feasible list of activities and a mode assignment. After defining the related crossover, mutation, and selection operators, we describe a local search extension which is employed to improve the schedules found by the basic genetic algorithm. Finally, we present the results of our thorough computational study. We determine the best among several different variants of our genetic algorithm and compare it to four other heuristics that have recently been proposed in the literature. The results that have been obtained using a standard set of instances show that the new genetic algorithm outperforms the other heuristic procedures with regard to a lower average deviation from the optimal makespan. <s> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <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> BIB003 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> Abstract A recurring problem in project management involves the allocation of scarce resources to the individual jobs comprising the project. In many situations such as audit-staff scheduling, timetabling, and course scheduling, the resources correspond to individuals (skilled labour). This naturally leads to an assignment-type project scheduling problem, i.e. a project has to be performed by assigning one or more of several individuals (resources) to each job. In this paper we consider the nonpreemptive variant of a resource-constrained project scheduling problem with mode identity. Mode identity refers to a generalization of the multi-mode case where the set of all jobs is partitioned into disjoint subsets while all jobs forming one subset have to be processed in the same mode. Both time and cost incurred by processing a subset of jobs depend on the resources assigned to it. This problem is a substantial and nontrivial generalization of the well-known multi-mode case. Regarding precedence and temporal relations as well as release dates and deadlines, the question arises to which jobs resources should be assigned in order to minimize overall costs. For solving this time-resource-cost-tradeoff problem we present a tailored parallel randomized solution approach called ramses into which both static and dynamic priority rules can be incorporated. The results of an extensive computational study on a practical application from the field of audit-staff scheduling indicate that ramses is capable of producing “good” solutions in neglectable amounts of time. <s> BIB004 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <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> BIB005 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> A genetic algorithm (GA) approach is proposed for the general resource-constrained project scheduling model, in which activities may be executed in more than one operating mode, and renewable as well as nonrenewable resource constraints exist. Each activity's operation mode has a different duration and requires different amounts of renewable and nonrenewable resources. The objective is the minimization of the project duration or makespan. The problem under consideration is known to be one of the most difficult scheduling problems, and it is hard to find a feasible solution for such a problem, let alone the optimal one. The GA approach described in this paper incorporates problem-specific scheduling knowledge by an indirect chromosome encoding that consists of selected activity operating modes and an ordered set of scheduling rules. The scheduling rules in the chromosome are used in an iterative scheduling algorithm that constructs the schedule resulting from the chromosome. The proposed GA is denoted a hybrid GA (HGA) approach, since it is integrated with traditional scheduling tools and expertise specifically developed for the general resource-constrained project scheduling problem. The results demonstrate that HGA approach produces near-optimal solutions within a reasonable amount of computation time. <s> BIB006 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> The worldwide opening of the markets, hence the continuously increasing number of competitors, the higher customers standards and shorter product innovation cycles require a cost- or time-minimizing manufacturing of customer orders or projects, preferably just in time, under limited availability of resources. Manufacturing planning can no longer be the result of experience. <s> BIB007 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <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> BIB008 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <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> BIB009 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <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> BIB010 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> In this paper the resource-constrained project scheduling problem with multiple execution modes for each activity and the makespan as the minimization criterion is considered. A simulated annealing approach to solve this problem is presented. The feasible solution representation is based on a precedence feasible list of activities and a mode assignment. A comprehensive computational experiment is described, performed on a set of standard test problems constructed by the ProGen project generator. The results are analyzed and discussed and some final remarks are included. Copyright Kluwer Academic Publishers 2001 <s> BIB011 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <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> BIB012 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> We introduce a formulation and an exact solution method for a nonpreemptive resource constrained project scheduling problem in which the duration/cost of an activity is determined by the mode selection and the duration reduction (crashing) within the mode. This problem is a natural combination of the time/cost tradeoff problem and the resource constrained project scheduling problem. It involves the determination, for each activity, of its resource requirements, the extent of crashing, and its start time so that the total project cost is minimized. We present a branch and bound procedure and report computational results with a set of 160 problems. Computational results demonstrate the effectiveness of our procedure. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 107–127, 2001 <s> BIB013 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> This paper presents a case study for the environment-friendly dismantling and recycling of buildings. Based on material-flow management it is shown how the dismantling on the construction site can be improved using resource-constrained project scheduling. Computational results show that strict environmental requirements like high recycling quotas and the reduction of harmful substances in recycling materials can be satisfied. Moreover, a comparison with results in practice indicates that project scheduling helps to achieve economic advantages for environment-friendly dismantling and recycling strategies. <s> BIB014 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <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> BIB015 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> This paper describes new simulated annealing (SA) algorithms for the resource-constrained project scheduling problem (RCPSP) and its multiple mode version (MRCPSP). The objective function considered is minimisation of the makespan. The conventional SA search scheme is replaced by a new design that takes into account the specificity of the solution space of project scheduling problems. For RCPSP, the search was based on an alternated activity and time incrementing process, and all parameters were set after preliminary statistical experiments done on test instances. For MRCPSP, we introduced an original approach using two embedded search loops alternating activity and mode neighbourhood exploration. The performance evaluation done on the benchmark instances available in the literature proved the efficiency of both adaptations that are currently among the most competitive algorithms for these problems. <s> BIB016 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <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> BIB017 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> In this paper, we introduce an extension of the classical Resource-Constrained Project Scheduling Problem: the Multi-skill Project Scheduling Problem. We consider a project made up of activities that must be implemented by a staff: every member of this staff masters one or more skill(s). An activity needs a given amount of each skill with a fixed minimum level of mastering. For each unit of a skill needed, we have to assign an employee who masters the required level of this skill during the whole processing time of the activity. The objective is to minimize the duration of the project, i.e. the makespan. We introduce here two lower bounds used to evaluate the minimum duration. <s> BIB018 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> This paper considers the multimode resource-constrained project-scheduling problem (MRCPSP) with a minimum-makespan objective. An exact branch and cut algorithm is presented based on the integer linear programming (ILP) formulation of the problem. In the preprocessing stage, lower bounds on the distance between each pair of precedence-constrained activities are derived. These bounds are used to reduce the number of variables in the model and to generate cuts that tighten the linear programming relaxation. The solution process is accelerated by an adaptive branching scheme in conjunction with a bound-tightening scheme that is called iteratively after branching. To find good feasible solutions in the early stages of the computations, a high-level neighborhood search strategy known as local branching is included. Here, a neighborhood of a feasible solution is defined by the linear inequalities in the ILP model and is searched first. As implemented, the full algorithm is exact rather than heuristic in nature. Numerical results are reported for 20- and 30-activity benchmark problems. These are the largest instances available and are generally viewed to be notoriously difficult. Up until now, there were no confirmed optimal solutions for any of the 552 30-activity instances. We were able to find several better solutions and to show that at least 506 are optimal. <s> BIB019 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> To stay ahead of their competition, pharmaceutical firms must make effective use of their new product development (NPD) capabilities by efficiently allocating its analytical, clinical testing and manufacturing resources across various drug development projects. The resulting project scheduling problems involve coordinating hundreds of testing and manufacturing activities over a period of several quarters. Most conventional integer programming approaches are computationally impractical for problems of this size, while priority rule-driven heuristics seldom provide consistent solution quality. We propose a Lagrangian decomposition (LD) heuristic that exploits the special structure of these problems. Some resources (typically manpower) are shared across all on-going projects while others (typically equipment) are specific to individual project categories. Our objective function is a weighted discounted cost expressed in terms of activity completion times. The LD heuristics were subjected to a comprehensive experimental study based on typical operational instances. While the conventional "Reward---Risk" priority rule heuristic generates duality gaps between 47---58%, the best LD heuristic achieves duality gaps between 10---20%. The LD heuristics also yield makespan reductions of over 30% over the Reward---Risk priority rule. <s> BIB020 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <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> BIB021 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> Abstract Decisions concerning a project’s expedition, traditionally involved considerations regarding time and cost tradeoff. It was recently suggested that the quality of a project should also be taken into considerations. In this paper, we propose a meta-heuristic solution procedure for the discrete time, cost and quality tradeoff problem. This problem involves the scheduling of project activities in order to minimize the total cost of the project while maximizing the quality of the project and also meeting a given deadline. We apply a so called electromagnetic scatter search to solve this problem. In this process, we initially generate a population of feasible solutions. In so doing, we use frequency memory to well sample the feasible region. A number of these solutions are then selected and improved locally. The improved solutions are then combined to generate new set of solutions. The combination process utilizes attraction–repulsion mechanisms borrowed from the electromagnetism theory. The whole process is stopped when no significant improvement in the set of solutions are observed. The validity of the proposed solution procedure is demonstrated, and its applicability is tested on a randomly generated large and complex problem having 19,900 activities. <s> BIB022 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> The particle swarm optimization (PSO) has been widely used to solve continuous problems. The discrete problems have just begun to be also solved by the discrete PSO. However, the combinatorial problems remain a prohibitive area to the PSO mainly in case of integer values. In this paper, we propose a combinatorial PSO (CPSO) algorithm that we take up challenge to use in order to solve a multi-mode resource-constrained project scheduling problem (MRCPSP). The results that have been obtained using a standard set of instances, after extensive experiments, prove to be very competitive in terms of number of problems solved to optimality. By comparing average deviations and percentages of optima found, our CPSO algorithm outperforms the simulated annealing algorithm and it is close to the PSO algorithm. <s> BIB023 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> Abstract In this paper, we study the supply chain configuration problem (SCCP) under resource constraints. We present a new modeling framework based on multi-mode resource-constrained project scheduling (MRCPSP) for configuring the supply chain subject to explicit resource constraints. It establishes a bridge between the areas of project scheduling and supply chain design. Our model is also able to handle additional practical issues such as quality level requirements and general temporal constraints , which are often encountered in the real world. A constraint programming (CP) based solution approach is proposed and implemented in our case study. Conclusions and future research directions are discussed. <s> BIB024 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Modes <s> In service organizations, heterogeneity in workforce skills can lead to variation in end-product/service quality. The multi-mode, resource-constrained, project scheduling problem (MRCPSP), which assumes similar skills among resources in a given resource pool, accounts for differences in quality levels of individuals by assigning different activity durations depending on the skill level used. This approach is often inadequate to model the problem type investigated here. Using typical projects from the customer training division of a large telecommunications company (which motivated this research), a labor assignment problem using a successive work-time concept is formulated and solved using integer programming optimization procedures. The setting represents a multiple-project environment where projects are separate and independent, but require the same renewable resource mix for their completion. The paper demonstrates how the output of the model can be used to identify bottlenecks (or critical resource skills), and also demonstrates how cross-training the appropriately skilled groups or individuals can increase throughput. The approach guides decision-making concerning which workers to cross-train in order to extract the greatest benefits from worker-flexibility. <s> BIB025
The standard RCPSP assumes that an activity can only be executed in a single way which is determined by a fixed duration and fixed resource requirements. Starting with the work of Elmaghraby  , the activity concept as given in the standard RCPSP has been extended by allowing several alternatives or modes in which an activity can be performed. Each mode reflects a feasible way to combine a duration and resource requests that allow to accomplish the underlying activity. The assumptions of the multi-mode RCPSP can be summarized as follows. An activity j must be performed in one of its modes which are labelled 1, . . . , M j with M j being the number of modes. Once started in one of its modes, an activity must be completed in that mode; mode changes and preemption are not permitted. The processing time of activity j being executed in mode m is given by p jm . The request of activity j being executed in mode m for resource k is r jmk . In addition to renewable resources, often also nonrenewable resources are considered in multi-mode models, see Section 4.1. A schedule for the multi-mode RCPSP assigns a start time S j and a mode m j to each activity j. The most popular objective in the literature is the minimization of the makespan. The multi-mode RCPSP is often referred to as MRCPSP. Clearly, if only one mode per activity and no nonrenewable resources are given, we obtain the standard RCPSP. Note that there might not be a feasible schedule if a nonrenewable resources is given, and as shown by Kolisch and Drexl BIB001 the related feasibility problem (i.e., the problem to determine whether there is a feasible schedule) is NP-complete if at least two nonrenewable resources are present. To capture multiple modes for activities in the notation of Brucker et al. BIB005 , α is set to MPS. Recent papers on this problem class include Alcaraz et al.  , Bouleimen and Lecocq BIB016 , Hartmann BIB002 , Jarboui et al. BIB023 , Józefowska et al. BIB011 ,Özdamar BIB006 and Pesch BIB007 while Varma et al. BIB020 discuss a multi-mode problems without nonrenewable resources. Multi-mode problems with generalized precedence constraints have been considered by Barrios et al.  , Brucker and Knust BIB009 , Calhoun et al.  , de Reyck and Herroelen BIB008 , Drexl et al. BIB010 , Heilmann BIB012 BIB017 , Nonobe and Ibaraki BIB015 , and Sabzehparvar and Seyed-Hosseini BIB021 (see also Section 3). Zhu et al. BIB019 employ a multi-mode problem with generalized resource constraints (see also Section 4). Erenguc et al. BIB013 introduce so-called crashable modes. The duration of a mode can be shortened at the expense of additional costs, which is essentially a special case of the mode concept described above. Bellenguez and Néron BIB018 consider activities which require staff members with certain skill levels. This can be seen as a special case of the mode concept where each mode corresponds to a feasible subset of staff members that can carry out the activity with regard to the required skill levels. Li and Womer BIB024 employ the mode concept to take quality considerations into account. Each mode m of an activity j is associated with a quality γ jm . The sum of the qualities related to the actual modes in the schedule must be at least Γ. The authors use the resulting multi-mode RCPSP to capture the configuration of a supply chain, where the quality represents the reliability of a node in the supply chain. Tareghian and Taheri BIB022 follow a similar approach. Their objective is to maximize the quality while the project's deadline and budget (nonrenewable resource capacity) must be observed. Tiwari et al. BIB025 also consider quality. In their problem setting, an activity may be started in a mode that does not allow to complete the activity at a required quality level. Processing in such a mode then has to be followed by a rework mode that completes the activity. Their approach was motivated by customer training projects in a telecommunication firm. There, an activity may be started by a less skilled employee who is available and then completed by an employee with the required skills. Nudtasomboon and Randhawa BIB003 allow preemption of activities in a multi-mode RCPSP. When an activity is resumed, the mode may not change. Various alternative objectives are included (see Section 5). Salewski et al. BIB004 and Drexl et al. BIB010 extend the multi-mode RCPSP by introducing socalled mode identity constraints. The motivation for this is that there may be several activities that should be performed in the same way, e.g., by allocating the same resources to them. To cover this, the set of all activities is partitioned into sets of activities H u , u = 1, . . . ,U. The activities of each set H u must be performed in the same mode. That is, m i = m j is must hold for all activities i, j ∈ H u (note that this requires M i = M j ). Schultmann and Rentz BIB014 present a case study that demonstrates how the multi-mode RCPSP can be applied to projects which consist of the dismantling of buildings.