A survey of variants and extensions of the resource-constrained project scheduling problem <s> Release Dates and Deadlines <s> This paper presents a set of satisfiability tests and time‐bound adjustmentalgorithms that can be applied to cumulative scheduling problems. An instance of thecumulative scheduling problem (CuSP) consists of (1) one resource witha given capacity, and (2) a set of activities, each having a release date, adeadline, a processing time and a resource capacityrequirement. The problem is to decide whether there exists a start time assignment to allactivities such that at no point in time the capacity of the resource is exceeded and alltiming constraints are satisfied. The cumulative scheduling problem can be seen as a relaxationof the decision variant of the resource‐constrained project scheduling problem.We present three necessary conditions for the existence of a feasible schedule. Two ofthem are obtained by polynomial relaxations of the CuSP. The third is based on energeticreasoning. We show that the second condition is closely related to the subset bound, awell‐known lower bound of the m‐machine problem. We also present three algorithms,based on the previously mentioned necessary conditions, to adjust release dates anddeadlines of activities. These algorithms extend the time‐bound adjustment techniquesdeveloped for the one‐machine problem. They have been incorporated in a branch andbound procedure to solve the resource‐constrained project scheduling problem.Computational results are reported. Copyright Kluwer Academic Publishers 1999 <s> BIB001 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Release Dates and Deadlines <s> Considers the resource‐constrained project scheduling problem where cash inflows and outflows are tied to the occurrence of events. The objective is the maximization of the project net present value (NPV) as well as the minimization of project tardiness in the presence of a project due date. Develops hybrid scheduling rules with both NPV and tardiness considerations to enhance both objectives. Experiments extensively with a set of benchmark problems originally designed for the objective of minimizing the project duration. Demonstrates that thje hybrid rules developed here are superior in performance with respect to both objectives when compared with well known rules which are developed for the two objective of minimizing the project duration. Demonstrates that the hybrid rules developed here are superior in performance with respect to both objectives when compared with well‐known rules which are developed for the two objectives taken individually. Furthermore, the iterative algorithm improves the performance of all tested rules significantly. <s> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Release Dates and Deadlines <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> Release Dates and Deadlines <s> Abstract. This paper deals with the generalized resource-constrained project scheduling problem (GRCPSP) which extends the well-known resource-constrained project scheduling problem (RCPSP) by considering job specific release and due dates, non-negative minimum start-to-start time lags as well as time-varying resource availabilities. The structure of the project is represented by an acyclic network diagram. Though the extensions are of high practical importance, only a few exact solution procedures have been presented in the literature so far. Therefore, a new exact procedure PROGRESS is developed which includes new dominance rules as well as enhancements of existing ones. For evaluating the efficiency experimentally, new GRCPSP instances with 30 and 60 jobs are considered which extend the standard benchmark sets for the RCPSP generated by ProGen. PROGRESS shows superior performance when applied to the GRCPSP and is also very competitive in comparison to approaches proposed for the RCPSP. <s> BIB004 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Release Dates and Deadlines <s> This paper concentrates on cost sharing situations which arise when delayed joint projects involve joint delay costs. The problem here is to determine “fair” shares for each of the agents who contribute to the delay of the project such that the total delay cost is cleared. We focus on the evaluation of the responsibility of each agent in delaying the project based on the activity graph representation of the project and then on solving the important problem of the delay cost sharing among the agents involved. Two approaches, both rooted in cooperative game theory methods are presented as possible solutions. In the first approach delay cost sharing rules are introduced which are based on the delay of the project and on the individual delays of the agents who perform activities. This approach is inspired by the bankruptcy and taxation literature and leads to five rules: the (truncated) proportional rule, the (truncated) constrained equal reduction rule and the constrained equal contribution rule. By introducing two coalitional games related to delay cost sharing problems, which we call the pessimistic delay game and the optimistic delay game, also game theoretical solutions as the Shapley value, the nucleolus and the τ-value generate delay cost sharing rules. In the second approach the delays of the relevant paths in the activity graph together with the delay of the project play a role. A two-stage solution is proposed. The first stage can be seen as a game between paths, where the delay cost of the project has to be allocated to the paths. Here serial cost sharing methods play a role. In the second stage the allocated costs of each path are divided proportionally to the individual delays among the activities in the path. Copyright Kluwer Academic Publishers 2002(This abstract was borrowed from another version of this item.) <s> BIB005 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Release Dates and Deadlines <s> The main purposes of this study are to incorporate both the project delay penalty and early completion bonus into the objective function of the resource-constrained multi-project scheduling problem with discounted cash flows (RCMPSP-DCF) and to develop an efficient heuristic search scheduling rule. The effectiveness of the proposed heuristic rule is evaluated by comparing it with the optimal solution obtained by the optimal model for 42 small-scale problems. The result indicates that the solution obtained using the proposed heuristic rule is very close to the optimal solution, and that the proposed heuristic rule provides significant savings in computation time. Moreover, the proposed heuristic rule is also compared with four existing heuristic rules based on an experiment involving the single-project and multi-project scheduling problems. The results indicate that the proposed heuristic rule is superior to the four existing rules under the performance criteria of the average total project net present value and the average total project delay. In addition, the number of times that the proposed heuristic rule can obtain the best solution is also far more than that of any other rule considered in this paper under the two aforementioned performance criteria. Furthermore, this study has found that the performance of a heuristic scheduling rule is significantly affected by the number of projects. A rule that can lower the total project delay to the minimum is also able to maxi5 mize the total project net present value. <s> BIB006 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Release Dates and Deadlines <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> BIB007 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Release Dates and Deadlines <s> This paper presents a branch-and-cut based exact solution algorithm for scheduling of projects with variable intensity activities connected by feeding precedence constraints the objective being to minimize the violation of resource constraints. Feeding precedence constraints allow some overlap in the execution of the connected activities and capture the flow of material or information between them. New polyhedral results are obtained and computational results are summarized. <s> BIB008 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Release Dates and Deadlines <s> Due dates are an essential feature of real projects, but little effort has been made in studying the RCPSP with due dates in the activities. This paper tries to bridge this gap by studying two problems: the TardinessRCPSP, in which the objective is total tardiness minimization and the DeadlineRCPSP, in which the due dates are strict (deadlines) and the objective is makespan minimization. The first problem is NP-hard and the second is much harder, since finding a feasible solution is already NP-hard. This paper has three objectives: Firstly to compare the performance on both problems of well-known RCPSP heuristics - priority rules, sampling procedures and metaheuristics - with new versions we have developed that take due dates into consideration. Secondly, to present an instance generator that can generate instances with loose, medium, and tight due dates for computational study. And, finally, to adapt the technique of justification to deal with due dates and deadlines and to show its profitability. <s> BIB009 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Release Dates and Deadlines <s> We consider in this paper a project scheduling problem where resources are employees and activity requirements are time-dependent. Furthermore, employees have different skills and legal constraints dictated by the French workforce legislation have to be respected. The project has to be scheduled and employees have to be assigned to activities, so that most of the constraints are respected and the maximal lateness is minimized. We first give a linear programming formulation of the problem. Then, greedy algorithms are proposed to give an approximate solution to the problem. These methods give an initial solution to a Tabu search algorithm. Finally, computational experiments are conducted and results are discussed. <s> BIB010
A release date r j is the earliest time at which activity j may be started. Likewise, a deadline d j denotes the latest time instant at which activity j must be finished. In the notation of Brucker et al. BIB003 , release dates and due dates are represented in the β field by r j and d j , respectively. Recent problems with release dates and deadlines include Drezet and Billaut BIB010 , Kis BIB007 BIB008 , and Klein and Scholl  BIB004 . Baptiste et al. BIB001 consider what they call the cumulative scheduling problem which is an RCPSP with a single renewable resource and without precedence relations, but with release dates and deadlines for the activities (the objective is to find a feasible schedule). Note that a release date r j is equivalent to a minimal finish-start time lag between the dummy source activity and activity j. Analogously, a deadline d j can be imposed by a maximal finishfinish time lag between the dummy source activity and activity j. Whereas a deadline as defined above may not be violated, Ballestín et al. BIB009 , Brânzei et al. BIB005 , Chiu and Tsai BIB006 , Neumann et al.  , andÖzdamar et al. BIB002 consider due dates which can be exceeded at some penalty cost. Objective functions considering due dates are discussed in Section 5.1. Due dates are also important when multiple projects are planned simultaneously, see Section 6.2.