A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Objectives <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> Multiple Objectives <s> The paper presents a decision support system (DSS) for multiobjective project scheduling under multiple-category resource constraints. It handles quite a general class of nonpreemptive scheduling problems with renewable, nonrenewable and doubly-constrained resources, multiple performing modes of activities, precedence constraints in the form of an activity network and multiple project performance criteria of time and cost type. The DSS is based on three kinds of heuristics: parallel priority rules, simulated annealing and branch-and-bound. The last algorithm can even yield exact solutions when sufficient processing time is available. Some parts of the system are interactive, in particular, the search for the best compromise schedule. Graphical facilities enable a thorough evaluation of feasible schedules. Methodological foundations of the system and the algorithms used in the calculation phase are first explained. Then, a functional description of the system is made. The last part presents results of three test problems, in particular, an agricultural problem including 30 activities, multiple objectives and multiple-category resources. <s> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple 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> BIB003 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Objectives <s> Abstract The paper considers an interactive search over a non-dominated solution space of a multiple-criteria project scheduling problem. The approach described handles quite a general class of non-preemptive project scheduling problems with renewable, non-renewable and doubly constrained resources, multiple performing modes of activities, precedence constraints in the form of an activity network and multiple project performance criteria of time and cost type. The approach consists of two stages. In the first stage, a large representative sample of approximately non-dominated schedules is generated by the Pareto Simulated Annealing (PSA) metaheuristic method. Then, in the second stage, an interactive search over the sample is organized by the `Light Beam Search' (LBS) procedure in its discrete version. <s> BIB004 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple 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> BIB005 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Objectives <s> Multiobjective Project Scheduling Problems (MPS) have arisen in organizational settings ranging from construction planning to Research and Development. To date several papers have been published on this subject. In Slowinski, Soniewicki and Weglarz (1994) the Decision Support System (DSS) for the MPS was considered. In this system a set of heuristically generated, nondominated schedules was considered by the decision maker (DM) using an interactive procedure finding compromise schedules. Although pretty efficient, it was not satisfactory for one reason — the scheduling process often entails decisions that cannot be integrated into a mathematical model. <s> BIB006 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple 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> BIB007 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Objectives <s> Abstract A common problem which arises in project management is the fact that the planned schedule is often disrupted by several uncontrollable factors like additional time that might be required for rework and correction of detected defects. As a result, project managers are often unable to meet the promised completion dates. It is therefore vital to take into account such possible disruptions and their potential negative consequences at the project schedule design stage. In this paper, we address the issue of designing a project schedule which is not only short in time, but also less vulnerable to disruptions due to reworks and other undesirable conditions. To that aim, we introduce the concept of schedule robustness and we develop a bi-objective resource-constrained project scheduling model. We consider the objectives of robustness maximization along with makespan minimization. We develop a tabu search algorithm in order to generate an approximate set of efficient solutions. Several variants of the algorithm are tested and compared on a large set of benchmark problems. <s> BIB008 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Objectives <s> Abstract We consider a real-world multi-mode multi-project scheduling problem in which the resources form a hybrid flow shop consisting of 16 production stages. Furthermore, sequence-dependent setup states arise at two production stages leading to a batching problem. The objective is to minimize the weighted tardiness. A mathematical model based on the well-known resource constrained project scheduling problem is presented to provide a formal description of the problem. As problem instances consist of about 30,000 jobs a heuristic solution procedure using dispatching rules is applied. We describe how these rules are modified in order to form batches. <s> BIB009 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Objectives <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> BIB010 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Multiple Objectives <s> Many project tasks and manufacturing processes consist of interdependent time-related activities that can be represented as networks. Deciding which of these sub-processes should receive extra resources to speed up the whole network (i.e., where activity crashing should be applied) usually involves the pursuit of multiple objectives amid a lack of a priori preference information. A common decision support approach lies in first determining efficient combinations of activity crashing measures and then pursuing an interactive exploration of this space. As it is impossible to exactly solve the underlying multiobjective combinatorial optimization problem within a reasonable computation time for real-world problems, we have developed proper solution procedures based on three major (nature-inspired) metaheuristics. This paper describes these implementations, discusses their strengths, and provides results from computational experiments. <s> BIB011
The problems discussed above have a single objective function (e.g., makespan minimization) while all other properties of a schedule are controlled by means of constraints (e.g., resource usages and costs). However, several authors have employed multiple performance measures into their project scheduling problems. A widely used approach to cope with multiple objectives is to define one overall objective as the weighted sum of all performance measures considered. This is done by Nudtasomboon and Randhawa BIB003 who include various objectives into the multi-mode RCPSP such as makespan, weighted tardiness, resource leveling and nonrenewable resource consumption. Voß and Witt BIB009 employ the multi-mode RCPSP with an objective that contains makespan, weighted tardiness and setup costs. The inclusion of setup costs supports batching of activities. The problem setting is motivated by a production planning problem at a steel manufacturer. Bomsdorf and Derigs BIB010 employ an objective for movie shooting projects that consists of several components which are allowed to be squared. The components include specific criteria such as the minimization of location changes over time (each activity is associated with a location). Al-Fawzan and Haouari BIB008 combine makespan minimization and maximization of total free slack into one objective. Another way to deal with multiple objectives is the generation of Pareto-optimal schedules. This approach is followed by several authors. Davis et al. BIB001 minimize the makespan as well as the overutilization of each renewable resource. Viana and de Sousa BIB007 add to these the minimization of overutilization of each nonrenewable resource and the mean weighted tardiness. Hapke et al. BIB004 propose a multi-criteria approach which allows to simultaneously consider several objectives, namely time based, resource based, and financial ones. Słowiński et al. BIB002 consider the multi-mode RCPSP with various objectives including makespan, mean weighted lateness, total number of tardy activities, smoothness of the resource profile, total and weighted resource consumption and net present value. Dörner et al. BIB011 employ three objectives within a variant of the time-cost tradeoff problem. The first objective is a function of the project makespan, while the second and the third are functions of the monetary and nonmonetary costs for crashing the activities, respectively. The case of Pareto-optimal schedules can be represented in the classification scheme of Brucker et al. BIB005 by setting γ to a vector containing all symbols of the objectives under consideration. Nabrzynski and Wȩglarz BIB006 present a knowledge-based approach to a project scheduling problem with multiple modes and a set of time and cost criteria. The latter includes the makespan, the smoothness of the resource profile, mean weighted lateness, mean weighted flow time, total and weighted resource consumption as well as the net present value. 6 Multiple Projects