A survey of variants and extensions of the resource-constrained project scheduling problem <s> Partially 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> BIB001 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Partially Renewable Resources <s> We consider a generalization of the classical resource constrained project scheduling problem. We introduce so-called partially reiiewable resources by assuming for each resource a capacity on subsets of periods. The concept of partially renewable resources is a fundamental tool in order to make e.g. timetabling and shift scheduling aspects amenable to project scheduling. In addition, partially renewable resources serve to model complicated labor regulations. Furthermore, they cover traditional renewable and nonre-newable resource constraints as special cases. We consider makespan minimization as objective. For the exact Solution of the problem we employ a basic enumeration scheme. In order to speed up convergence, we formulate bounds which take into account future resource consumption of partially renewable resources. Moreover, we generalize the serial scheduling scheme in order to get fast approximation methods. A rigorous assessment of the procedures is provided by solving Pro Gen instances generated under a full factorial test design. Besides the well-known problem parameters we employ additionally three parameters which control the generation of partially renewable resources. <s> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Partially 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> BIB003 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Partially Renewable Resources <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> BIB004 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Partially Renewable Resources <s> In this paper we develop a heuristic algorithm, based on Scatter Search, for project scheduling problems under partially renewable resources. This new type of resource can be viewed as a generalization of renewable and non-renewable resources, and is very helpful in modelling conditions that do no fit into classical models, but which appear in real timetabling and labor scheduling problems. The Scatter Search algorithm is tested on existing test instances and obtains the best results known so far. <s> BIB005 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Partially Renewable Resources <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> BIB006 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Partially Renewable Resources <s> Recently, in the field of project scheduling problems the concept of partially renewable resources has been introduced. Theoretically, it is a generalization of both renewable and non-renewable resources. From an applied point of view, partially renewable resources allow us to model a large variety of situations that do not fit into classical models, but can be found in real problems in timetabling and labor scheduling. In this paper, we develop some preprocessing techniques and several heuristic algorithms for the problem. Preprocessing significantly reduces the dimension of the problems, therefore improving the efficiency of solution procedures. Heuristic algorithms based on GRASP and Path relinking are then developed and tested on existing test instances, obtaining excellent results. <s> BIB007
Partially renewable resources (which generalize both renewable and nonrenewable resources) have been introduced by Böttcher et al. BIB002 ; see also Alvarez-Valdes et al. BIB005 BIB007 , Drexl et al.  BIB004 and Schirmer and Drexl  . For each partially renewable resource k, we have a set Π k of socalled period subsets. Resource k has a total availability of R π k (Q ki ) during the time given by period subset Q ki ⊆ {1, . . . , T }, where Q ki ∈ Π k and T is the planning horizon. The request of activity j for partially renewable resource k is again denoted as r jk . In an equivalent normalized formulation, a separate partially renewable resource is defined for each period subset. Considering the notation of Brucker et al. BIB003 , we propose to use α = PS; PR to reflect project scheduling with partially renewable resources. For illustration of this concept, consider an employee who may work on every day from Monday through Friday and either on Saturday or on Sunday but not both. Obviously, each day (Mon-day through Sunday) would be one period. A partially renewable resource would then be defined as follows: Each day from Monday through Friday makes up one separate period subset with an associated availability of 1. The weekend restriction is imposed by defining another period subset containing both Saturday and Sunday with a capacity of 1. Zhu et al. BIB006 integrate partially renewable resources into the multi-mode RCPSP. Nudtasomboon and Randhawa BIB001 