A survey of variants and extensions of the resource-constrained project scheduling problem <s> Time-Based Objectives <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> Time-Based Objectives <s> Abstract The problem of scheduling multiple, large-scale, make-to-order assemblies is considered. Beside `classical’ precedence and resource constraints as known from resource-constrained project scheduling we take spatial resource and part availability constraints into account. The objective is to minimize the sum of the weighted tardiness. We propose a MIP-model of the problem which is a generalization of three allocation problems. Since the problem is NP -hard, a list-scheduling heuristic is proposed and evaluated on a set of benchmark instances. <s> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Time-Based Objectives <s> We describe a simple breadth-first tree search scheme for minimizing the makespan of a project consisting of a partially ordered network of activities under multiple resource constraints. The method compares quite favourably with existing techniques that employ depth-first or best-first search; in particular, it is able to solve optimally on a Pentium PC running SCO UNIX the entire set of 680 benchmark problems (First Lot: 480, Second Lot: 200) generated by Kolisch et al., 1995. The new algorithm has also been checked out experimentally on additional random test problems at graded levels of difficulty that were generated using two parameters: the threshold, which determined the predecessors of an activity, and the total resource availability of each resource type. The breadth-first scheme can be modified quite readily to do best-first search or to minimize measures other than makespan such as mean flow time and maximum tardiness. <s> BIB003 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Time-Based Objectives <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> Time-Based Objectives <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> BIB005 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Time-Based Objectives <s> One of the most difficult tasks in a job shop manufacturing environment is to balance schedule and capacity in an ongoing basis. MRP systems are commonly used for scheduling, although their inability to deal with capacity constraints adequately is a severe drawback. In this study, we show that material requirements planning can be done more effectively in a job shop environment using a resource constrained project scheduling model. The proposed model augments MRP models by incorporating capacity constraints and using variable lead time lengths. The efficacy of this approach is tested on MRP systems by comparing the inventory carrying costs and resource allocation of the solutions obtained by the proposed model to those obtained by using a traditional MRP model. In general, it is concluded that the proposed model provides improved schedules with considerable reductions in inventory carrying costs. <s> BIB006 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Time-Based Objectives <s> This paper considers heuristics for the well‐known resource‐constrained project scheduling problem (RCPSP). It provides an update of our survey which was published in 2000. We summarize and categorize a large number of heuristics that have recently been proposed in the literature. Most of these heuristics are then evaluated in a computational study and compared on the basis of our standardized experimental design. Based on the computational results we discuss features of good heuristics. The paper closes with some remarks on our test design and a summary of the recent developments in research on heuristics for the RCPSP. <s> BIB007 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Time-Based Objectives <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> BIB008 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Time-Based Objectives <s> In this paper we introduce the concept of quality-dependent time slots in the project scheduling literature. Quality-dependent time slots refer to pre-defined time windows where certain activities can be executed under ideal circumstances (optimal level of quality). Outside these time windows, there is a loss of quality due to detrimental effects. The purpose is to select a quality-dependent time slot for each activity, resulting in a minimal loss of quality. The contribution of this paper is threefold. First, we show that an R&D project from the bio-technology sector can be transformed to a resource-constrained project scheduling problem (RCPSP). Secondly, we propose an exact search procedure for scheduling this project with the aforementioned quality restrictions. Finally, we test the performance of our procedure on a randomly generated problem set. <s> BIB009
While the minimization of the makespan is among the most popular objectives (see, e.g., the references in Kolisch and Hartmann BIB007 ), there are various other time-based objectives. Objectives based on lateness, tardiness, and earliness are of particular importance. The lateness L j of an activity j is the deviation of the completion time C j from a given due date d j , hence L j = C j − d j . The tardiness T j is similar but it cannot be negative; it is defined as T j = max{0,C j − d j }. The earliness E j is defined analogously as E j = max{0, d j −C j }. Ballestín et al. BIB008 , Kolisch BIB002 , Nudtasomboon and Randhawa BIB001 , and Viana and de Sousa BIB005 consider the minimization of the weighted tardiness. Note that this generalizes the makespan objective. Neumann et al.  describe the minimization of the maximum lateness and of the weighted total tardiness. Vanhoucke et al.  discuss a just-in-time objective which is achieved by minimizing the weighted sum of all earliness and tardiness values. Franck and Schwindt  mention a multi-mode RCPSP with the objective to minimize the sum of the earliness and tardiness values. An alternative objective minimizes the maximum value of all earliness and tardiness values. Lorenzoni et al.  propose a variant where earliness and tardiness are measured w.r.t. a given time window in which an activity should be carried out. Vanhoucke BIB009 defines a set of time windows for each activity. Carrying out an activity within one of its time windows is desired due to quality considerations. The objective function minimizes penalties that are caused by executing activities outside their time windows. The approach is motivated by a bio-technology project. Vanhoucke BIB009 notes that this concept is similar to the time-switch constraints (see Section 3.4) where time windows are reflected by hard constraints. Nudtasomboon and Randhawa BIB001 propose to minimize the sum of all activity completion times, while Rom et al. BIB006 minimize the weighted sum of the completion times. Similarly, Nazareth et al. BIB003 suggest to minimize the mean flow time, which is the average of all activity completion times. Note that minimization of total completion time and minimization of average completion time is equivalent. In the α|β|γ notation of Brucker et al. BIB004 , these objectives can be captured in the γ field by symbols that are well known from machine scheduling: We can use γ = C max for the makespan, γ = L max for the maximal lateness, γ = ∑ w j C j for total weighted completion time, γ = ∑ w j T j for total weighted tardiness, γ = ∑ w j U j for weighted number of tardy jobs, or γ = ∑(w e j E j + w t j T j ) for sum of total weighted earliness and total weighted tardiness (w j is the weight of activity j in the objective and U j ∈ {0, 1} indicates whether activity j is late or not).