A survey of variants and extensions of the resource-constrained project scheduling problem <s> Tradeoff Problems <s> Abstract In this paper we develop a series of nonlinear time/cost tradeoff models for project management. A base model with quadratic cost relations is developed and then extended to include other operational considerations. The use of nonlinear functions to describe time/cost relationships in project scheduling environments permits a more accurate representation of the operational setting than is possible with linear or piecewise linear approximations. Examples of the models presented are solved directly with commercially available nonlinear programming codes. <s> BIB001 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Tradeoff Problems <s> We describe a new exact procedure for the discrete time/cost trade-off problem in deterministic activity-on-the-arc networks of the CPM type, where the duration of each activity is a discrete, nonincreasing function of the amount of a single resource (money) committed to it. The objective is to construct the complete and efficient time/cost profile over the set of feasible project durations. The procedure uses a horizon-varying approach based on the iterative optimal solution of the problem of minimising the sum of the resource use over all activities subject to the activity precedence constraints and a project deadline. This optimal solution is derived using a branch-and-bound procedure which computes lower bounds by making convex piecewise linear underestimations of the discrete time/cost trade-off curves of the activities to be used as input for an adapted version of the Fulkerson labelling algorithm for the linear time/cost trade-off problem. Branching involves the selection of an activity in order to partition its set of execution modes into two subsets which are used to derive improved convex piecewise linear underestimations. The procedure has been programmed in Visual C ++ under Windows NT and has been validated using a factorial experiment on a large set of randomly generated problem instances. <s> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Tradeoff Problems <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> Tradeoff Problems <s> In many solution methods for resource-constrained project scheduling, it is assumed that both the duration of each activity and its resource requirements are known and fixed. In real-life projects, however, it often occurs that only one renewable bottleneck resource is available and that the activities have a total work content which indicates how much work (expressed in man-periods) has to be performed. The objective then is to schedule each activity in one of its possible execution modes, subject to the precedence and resource constraints, in order to minimize the project makespan. We present a branch-and-bound procedure and report computational results, obtained using a full factorial experiment on a randomly generated problem set. <s> BIB004 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Tradeoff Problems <s> In project management, the project duration can often be compressed by accelerating some of its activities at an additional expense. This is the so-called time–cost tradeoff problem which has been extensively studied in the past. However, the discrete version of the problem which is of great practical relevance, did not receive much attention so far. Given a set of modes (time–cost pairs) for each activity, the objective of the discrete time–cost tradeoff problem is to select a mode for each activity so that the total cost is minimized while meeting a given project deadline. ::: ::: The discrete time–cost tradeoff problem is a strongly -hard optimization problem for general activity networks. In terms of what current state-of-art algorithms can do, instances with (depending on the structure of the network and the number of processing alternatives per activity) no more than 20–50 activities can be solved to optimality in reasonable amount of time. Hence, heuristics must be employed to solve larger instances. To evaluate such heuristics, lower bounds are needed. This paper provides lower and upper bounds using column generation techniques based on “network decomposition”. Furthermore, a computational study is provided to demonstrate that the presented bounds are tight and that large and hard instances can be solved in short run-time. <s> BIB005 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Tradeoff Problems <s> In this paper, we develop a metaheuristic procedure for solving the discrete time/resource trade-off problem in the field of project scheduling. In this problem, a project contains activities interrelated by finish-start-type precedence constraints with a time lag of zero, which require a single constrained renewable resource. Each activity has a specified work content and can be performed in different modes, i.e. with different durations and resource requirements; as long as the required work content is met. The objective is to schedule each activity in one of its modes in order to minimize the project makespan. To tackle this problem, we use a genetic algorithm in which a new method based on the resource utilization ratio is developed for generation of crossover points and also a local search method is incorporated with the algorithm. Comparative computational results reveal that this procedure outperforms the best available results in the literature. <s> BIB006 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Tradeoff Problems <s> We develop a heuristic procedure for solving the discrete time/resource trade-off problem in the field of project scheduling. In this problem, a project contains activities interrelated by finish-start-type precedence constraints with a time lag of zero, which require one or more constrained renewable resources. Each activity has a specified work content and can be performed in different modes, i.e. with different durations and resource requirements, as long as the required work content is met. The objective is to schedule each activity in one of its modes in order to minimize the project makespan. We use a scatter search algorithm to tackle this problem, using path relinking methodology as a solution combination method. Computational results on randomly generated problem sets are compared with the best available results indicating the efficiency of the proposed algorithm. <s> BIB007
In the discrete time-resource tradeoff problem, the workload ψ j for each activity j with regard to a single renewable resource k = 1 is given. Activity j can be performed in each discrete combination of processing time p j and resource request r jk that allows to reach the workload, that is, p j · r jk ≥ ψ j . Note that a combination of p j and r jk must be considered only if it is efficient, that is, (p j − 1) · r jk < ψ j and p j · (r jk − 1) < ψ j . This problem setting has been discussed by Demeulemeester et al. BIB004 and Ranjbar and Kianfar BIB006 . Ranjbar et al. BIB007 consider the case of multiple renewable resources. The discrete time-cost tradeoff problem includes one nonrenewable resource (which is interpreted as the budget of the project) and no renewable resource; for a description of nonrenewable resources refer to Section 4.1. Demeulemeester et al. BIB002 consider this problem setting with makespan minimization as objective, and they also discuss a "dual" version with a deadline and a resource-based objective (see Section 5.4). A further approach to the discrete time-cost tradeoff problem has been presented by Akkan et al. BIB005 . Note that these two discrete tradeoff problems are special cases of the multi-mode RCPSP and, thus, are covered by MPS|prec|C max employing the notation of Brucker et al. BIB003 . A mode can be defined for each efficient combination of processing time and resource request that covers the workload. The difference is that tradeoff problems usually specify the workload whereas multimode problems list every possible mode explicitly. Due to this difference, we propose to use α = T tr PS and α = T tc PS to specify the discrete time-resource and the discrete time-cost tradeoff problem, respectively, considering the notation of Brucker et al. BIB003 . Deckro et al. BIB001 consider the continuous version of the time-cost tradeoff problem where activity durations are not limited to discrete values. A deadline is imposed, and the cost function is quadratic and increases with an increasing deviation of the actual duration from the given normal duration. Extensions include a budget contraint and bonus or penalty payments in case of early or late project completion, respectively.