A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Renewable Resources <s> Abstract Over the past 30 years, various formulations of the project scheduling problem have been proposed. Traditionally, the managerial focus of most project scheduling formulations has been on the single objective of minimizing project completion time. Other relevant factors which legitimately should be included as an objective, such as physical, financial, and human resources, have either been assumed to be available in plentiful quantities, or have been accounted for in the form of rigid resource constraints. In this paper, an interactive decision support approach is introduced for explicitly considering multiple factors, simultaneously, in a multiobjective decision making framework. The approach enhances the traditional project scheduling framework in that it allows the decision maker to examine the minimization of project completion time as well as the balancing of available resurces. The approach thus makes the decision process for the project scheduling problem more flexible because various tradeoffs between project completion time and resource requirements can be evaluated. The decision support framework employs an interactive procedure based on vector maximization. Use of the method is illustrated with an example, and results from the example are compared with traditional single objective mathematical programming, preemptive goal programming, and Archemedian goal programming. <s> BIB001 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Renewable Resources <s> Abstract A recurring problem in managing project activities is to minimize the deviation between the resource requirements and stated desirable levels. This paper presents a new optimizing approach for resource leveling based on non-serial dynamic programming. This approach permits a marked reduction of the complexity of the problem as it checks for only the feasible time subsets which are far less numerous than feasible sequences. The model, which is applied to an activity-on-node network, requires as input the scheduling results provided by the critical path method (CPM). Applications of the model to two opposite cases are also described and the solutions compared with the ones achieved by the Burges and Killebrew heuristic. Computational results indicate that the procedure provides exact solutions for small to medium size problems, requiring only modest computing facilities. <s> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Renewable Resources <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> Objectives Based on Renewable Resources <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> Objectives Based on Renewable Resources <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> Objectives Based on Renewable Resources <s> Although single objective metaheuristics are widely spread and applied in many combinatorial optimisation problems, only very recently have multiobjective metaheuristics (MOMH) been designed and used in practice. They aim at obtaining good approximations of the set of nondominated solutions of a problem, in an efficient way. In this work, we have applied multiobjective versions of simulated annealing and taboo search to the resource constrained project scheduling problem (RCPSP), in order to minimise the makespan, the “weighted” lateness of activities and the violation of resource constraints. Computational experience performed on randomly generated instances shows that this general approach is flexible, effective and able to deal with multiple objectives and with variations in the problem structure. <s> BIB006 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Renewable Resources <s> The resource investment problem deals with the issue of providing resources to a project such that a given deadline can be met. The objective is to make the resources available in the cheapest possible way. For each resource, expenses depend on the maximum amount required during the course of the project. In this paper we develop two lower bounds for this NP-hard problem using Lagrangean relaxation and column generation techniques, respectively. Both procedures are capable of yielding feasible solutions as well. Hence, we also have two optimization guided heuristics. A computational study consisting of a set of 3210 instances compares both approaches and allows insight into the performance. <s> BIB007 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Renewable Resources <s> We introduce a project scheduling problem subject to temporal constraints where the resource availability costs have to be minimized. As an extension of known project scheduling problems which consider only time-independent costs, this problem includes both time-independent procurement costs and time-dependent renting costs for the resources. Consequently, in addition to projects where all resources are bought, we can deal with projects where resources are rented. Based on the enumeration of a finite set of schedules which is proved to contain an optimal schedule, we develop a depth-first branch-and-bound procedure. Computational experience with a randomly generated test set containing 10800 problem instances is reported. <s> BIB008 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Renewable Resources <s> In this paper we study a resource constrained project scheduling problem in which the resource usage of each activity may vary over time proportionally to its varying intensity. We formalize the problem by means of a mixed integer-linear program, prove that feasible solution existence is NP-complete in the strong sense and propose a branch-and-cut algorithm for finding optimal solutions. To this end, we provide a complete description of the polytope of feasible intensity assignments to two variable-intensity activities connected by a precedence constraint along with a fast separation algorithm. A computational evaluation confirms the effectiveness of our method on various benchmark instances. <s> BIB009 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Renewable Resources <s> We address a project scheduling problem with resource availability cost for which the activity durations are uncertain. The problem is formulated within the robust optimization framework, where uncertainty is modeled via a set of scenarios. The proposed solution method is based on the scatter search methodology and employs advanced strategies, such as dynamic updating of the reference set, a frequency-based memory mechanism, and path relinking. A multistart heuristic was also developed and comparative results are reported. The tradeoffs for risk-averse decision makers are discussed. <s> BIB010 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Renewable Resources <s> Abstract In this paper a genetic algorithm for solving a class of project scheduling problems, called Resource Investment Problem, is presented. Tardiness of project is permitted with defined penalty. Elements of algorithm such as chromosome structure, unfitness function, crossover, mutation, immigration and local search operations are explained. The performance of this genetic algorithm is compared with the performance of other published algorithms for Resource Investment Problem. Also 690 problems are solved and their optimal solutions are used for the performance tests of the genetic algorithm. The tests results are quite satisfactory. <s> BIB011 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Renewable Resources <s> We work with a project scheduling problem subject to temporal constraints where the resource availability costs have to be minimised. As an extension of the more well known Resource Investment Problem, which considers only time-independent costs, this problem includes both time-independent fixed costs and time-dependent variable renting costs for the resources. Consequently, in addition to projects where all resources are bought, we can deal with projects where resources are rented. Based on a new codification of a solution for project scheduling, we develop a Genetic Algorithm capable of outperforming a branch-and-bound procedure that exists for the problem. <s> BIB012 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Renewable Resources <s> This paper considers a project scheduling problem with the objective of minimizing resource availability costs required to execute the activities in a project by a given project deadline. The project contains activities interrelated by finish-start-type precedence relations with a time lag of zero, which require a set of renewable resources. Two metaheuristics, path relinking and genetic algorithm, are developed to tackle this problem in which a schedule is created with a precedence feasible priority list given to the schedule generation scheme. In these procedures, each new generation of solutions are created using the combination of current solutions. Comparative computational results reveal that path relinking is a very effective metaheuristic and dominates genetic algorithm. <s> BIB013 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Objectives Based on Renewable Resources <s> Creating a movie shoot schedule is an important part of the movie production process. Even for a small movie project already 50 activities requiring 130 resources such as different actors, director, team, special effects and locations etc. have to be scheduled respecting complex constraints which may be imposed on single resources as well as on every activity. In this paper, we present the movie shoot scheduling problem and formulate a conceptual model. We present a metaheuristic approach for generating operational schedules, outline the modules of the decision support system Schedule This which we have developed and finally we shortly report practical experiences. Our experience from using the DSS in real movie shooting projects shows significant improvements with respect to faster and better scheduling as well as ad hoc re-scheduling. <s> BIB014
Various objectives related to renewable resources have been discussed in the literature. A comprehensive overview is provided by Neumann et al.  . In the basic RCPSP, the makespan is to be minimized while a given capacity level of each renewable resource has to be observed. A "dual" version of this is the resource investment problem where the costs for providing a certain capacity level are to be minimized while a deadline for the project has to be observed. The objective is to minimize the sum of availability costs of all resources, i.e. ∑ k C k (R k ), where C k is a discrete non-decreasing cost function of resource k and the capacity levels R k are variables. A special case is obtained from the linear cost function C k (R k ) = c k · R k , where c k is the per-unit cost of resource k. The resource investment problem has recently been tackled by Drexl and Kimms BIB007 , Neumann and Zimmermann BIB005 , Neumann et al.  , Ranjbar et al. BIB013 , and Yamashita et al. BIB010 . Shadrokh and Kianfar BIB011 present an extension of the resource investment problem. Instead of a deadline, a due date is used, i.e., delayed completion of the project is allowed. The objective is to minimize the sum of resource availability costs and tardiness penalty. The latter results from a constant cost factor for each period the project is delayed. Nübel BIB008 suggests the resource renting problem in which the renewable resources have to be rented. Renting resource k is associated with fixed costs c f k per unit and variable costs c v k per unit and period. Thus renting a units of resource k over t periods leads to costs of a · (c The fixed costs could be the delivery costs of the resource to the project's location while the variable costs represent the actual rent. The objective is to minimize the total renting costs. Observe that c v k = 0 leads to the resource investment problem. The resource renting problem has been picked up by Ballestín BIB012 . Another resource-based objective is to achieve a smooth resource profile, which leads to the resource leveling problem. The objective there is to minimize the changes in the level of resource usage from period to period in the schedule while a deadline has to be observed. This might be measured as the maximum change or the sum of all changes, see Neumann and Zimmermann BIB005 , Neumann et al.  and Nudtasomboon and Randhawa BIB003 . Bandelloni et al. BIB002 propose to minimize the sum of all squared changes. Davis et al. BIB001 , Neumann and Zimmermann BIB005 and Viana and de Sousa BIB006 propose to minimize the utilized renewable resource units of each resource that exceed a given level. Nudtasomboon and Randhawa BIB003 minimize the cumulated deviations of the resource utilization from a given level, i.e., they consider both over-and underutilization. Bomsdorf and Derigs BIB014 discuss the minimization of both the number and the length of gaps in the resource profile. Kis BIB009 distinguishes between internal and external capacities of the renewable resources. The objective is to minimize the expenses for using external capacities. In the notation of Brucker et al. BIB004 , these objectives are represented by ∑ c k f (r k (S,t)) in the γ field. Here c k represent the cost per unit of resource k and f is a function of resource utilization profile r k (S,t). Note that the resource investment problem is obtained by setting f = max.