A survey of variants and extensions of the resource-constrained project scheduling problem <s> Conclusions <s> 1 The Model.- 1.1 Resource Categories.- 1.2 Problem Description.- 1.3 Critical Path Analysis.- 1.4 Mathematical Programming Formulation.- 2 Special Cases.- 2.1 Flow-Shop-Problem.- 2.2 Job-Shop-Problem.- 2.3 Open-Shop-Problem.- 2.4 Assembly Line Balancing.- 3 Variants and Extensions.- 3.1 Generalized Temporal Constraints.- 3.2 Resource Requirements Varying with Time.- 3.3 Further Regular Measures of Performance.- 4 Types of Schedules.- 4.1 Introduction.- 4.2 Definitions.- 4.3 Illustrations.- 5 A Branch and Bound Algorithm.- 5.1 The Precedence Tree.- 5.2 Minimizing the Projects Makespan.- 5.3 Optimizing any Regular Measure of Performance.- 5.4 Priority Rules and Heuristic Search Strategies.- 5.5 Acceleration Schemes.- 5.6 Limitations of the Branch and Bound Procedure.- 6 Generation of Instances by ProGen.- 6.1 Introduction.- 6.2 ProGen Specific Notation and Symbols.- 6.3 Project Generation.- 6.4 Resource Demand and Availability Generation.- 7 Computational Results.- 7.1 Exact Methods.- 7.2 Truncated Exact Methods.- 8 An Artificial Intelligence Approach.- 8.1 Model Reformulations.- 8.2 A PROLOG-Based Implementationll.- 8.3 Preliminary Computational Results.- 9 Applications.- 10 Conclusions.- List of Figures.- List of Tables. <s> BIB001 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Conclusions <s> This paper provides the following contributions: First, distribution requirements for lessons of different lengths are modelled in a novel way by the use of the so-called multiple mode concept with mode identity constraints. Second, we show that several types of constraints may be modelled using the unifying framework of partially renewable resources. Among these constraints are: No class, subject, room, and teacher overlaps; class, subject, room, and teacher unavailabilities; compactness constraints; preassignment constraints; lectures to be given simultaneously; lunch breaks, etc. Third, we present two-phase parallel greedy randomized and genetic methods. Fourth, we provide an instance generator for the generation of a representative set of instances. Fifth, the generator along with a statistical model is used for a thorough experimental evaluation of the methods. Computational results show that the methods solve the instances investigated close to optimality. <s> BIB002 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Conclusions <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> BIB003 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Conclusions <s> Abstract Lufthansa Technical Training GmbH (LTT) performs training courses for Lufthansa Technik AG as well as for several other international airlines. Courses of about 670 different types are offered of which several hundred take place each year. The course scheduling problem faced by LTT is to construct a yearly schedule which maximizes the profit margin incurred while meeting a variety of complex precedence, temporal, and resource-related constraints. A “good” operational schedule should also meet a number of additional subordinate objectives. We formalize the problem and develop a heuristic scheme along with several priority rules, as well as a local search algorithm to determine well-suited weights for weighted composite rules. The operational planning situation of 1996 served as our major test instance; additional test instances were constructed by modifying this data. Several computational experiments were carried out to evaluate the performance of the algorithms. It turned out that the best so-found schedule is substantially better in terms of the profit margin incurred than the solution manually constructed by LTT. <s> BIB004 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Conclusions <s> The paper deals with batch scheduling problems in process industries where final products arise from several successive chemical or physical transformations of raw materials using multi–purpose equipment. In batch production mode, the total requirements of intermediate and final products are partitioned into batches. The production start of a batch at a given level requires the availability of all input products. We consider the problem of scheduling the production of given batches such that the makespan is minimized. Constraints like minimum and maximum time lags between successive production levels, sequence–dependent facility setup times, finite intermediate storages, production breaks, and time–varying manpower contribute to the complexity of this problem. We propose a new solution approach using models and methods of resource–constrained project scheduling, which (approximately) solves problems of industrial size within a reasonable amount of time. <s> BIB005 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Conclusions <s> This paper considers two problem classes that are important to researchers as well as practitioners, namely packing and project scheduling problems. First, the two problem categories are described. This includes a classification of packing problems as well as of project scheduling concepts. While both problem classes are different with respect to their fields of application, similarities of their mathematical structures are examined. It is shown that all packing problems considered here are special cases of models for project scheduling. The aim is to indicate which project scheduling models can be used to capture the different types of packing problems. Finally, some implications for research on optimization algorithms for these two problem classes are discussed. <s> BIB006 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Conclusions <s> Crew or staff scheduling is a complex combinatorial problem. It consists of assigning tasks to persons which have to perform these task and to schedule the performance of the tasks. Railway and airline crew scheduling problems, audit scheduling problems, school and university course scheduling and staff scheduling in hospitals are typical examples of such combinatorial problems. <s> BIB007 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Conclusions <s> This paper deals with the lead optimization phase of pharmaceutical research where a number of leads (molecules as a basis for potential drugs) are processed by different departments in order to optimize their biochemical characteristics. We depict each lead as a project and model the problem as a static multi-project selection and scheduling problem under resource constraints with the objective to maximize the weighted work performed. For solving the problem we propose two heuristics. We assess their performance in a computational study and we point out one dominant method. Furthermore we show the impact of problem parameters such as the extend to which projects can be crashed. <s> BIB008 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Conclusions <s> Some well-known decision problems can be regarded as special cases of the resource-constrained project-scheduling problem (RCPSP) with respect to the structure of their mathematical models. These decision models include assembly line balancing, job shop scheduling and some packing problems. Here, the differences and similarities of mathematical models of the multilevel capacitated lot-sizing problem (MLCLSP) and the RCPSP are shown, and it is concluded that the RCPSP is a special case of the MLCLSP. This theoretical result is complemented by an integrated, general model formulation that allows one to coordinate customer-specific orders and make-to-stock (lot size) production at the master (production) planning level. <s> BIB009 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Conclusions <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> BIB010 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Conclusions <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> BIB011 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Conclusions <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> BIB012 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Conclusions <s> In service organizations, heterogeneity in workforce skills can lead to variation in end-product/service quality. The multi-mode, resource-constrained, project scheduling problem (MRCPSP), which assumes similar skills among resources in a given resource pool, accounts for differences in quality levels of individuals by assigning different activity durations depending on the skill level used. This approach is often inadequate to model the problem type investigated here. Using typical projects from the customer training division of a large telecommunications company (which motivated this research), a labor assignment problem using a successive work-time concept is formulated and solved using integer programming optimization procedures. The setting represents a multiple-project environment where projects are separate and independent, but require the same renewable resource mix for their completion. The paper demonstrates how the output of the model can be used to identify bottlenecks (or critical resource skills), and also demonstrates how cross-training the appropriately skilled groups or individuals can increase throughput. The approach guides decision-making concerning which workers to cross-train in order to extract the greatest benefits from worker-flexibility. <s> BIB013 </s> A survey of variants and extensions of the resource-constrained project scheduling problem <s> Conclusions <s> We consider the problem of simultaneously scheduling IT-projects and assigning multi-skilled internal and external human resources with resource-specific efficiencies to the project work. The objective is to minimize labor costs. The problem is modeled as a mixed-integer linear program (MIP) with a tight LP-bound. The performance of the model w.r.t. solution gap and computation time is assessed and managerial insight is given concerning different problem parameters such as the time window size of projects, the number of skills of human resources, and the workload. Furthermore, we show the benefit of applying the MIP compared to simple heuristics used in practice in terms of obtaining feasible and low-cost solutions. Finally, we provide insight into the benefit of applying the MIP in case of central compared to decentral planning. <s> BIB014
We have summarized and classified publications on various variants and generalizations of the well-known resource-constrained project scheduling problem (RCPSP). Among the most popular extensions are multiple modes, generalized time lags, and objectives based on the net present value. Beyond these well-researched areas, many other concepts have been developed in recent years. This paper can serve as a guide through these developments. Several recent problem settings have been motivated by specific industries. This includes production and engineering where Bartels and Zimmermann  consider the automotive industry, Schwindt and Trautmann BIB005 deal with the process industry, Kolisch BIB003 discusses the production of palletizing systems, and Voß and Witt BIB011 consider a steel manufacturer. Specific requirements of research projects have been discussed for medical research (Hartmann  ), pharmaceutical research (Kolisch and Meyer BIB008 ), and bio-technology (Vanhoucke BIB010 ). Further examples include training in the telecommunication industry (Tiwari et al. BIB013 ) and aviation industry (Haase et al. BIB004 ), arrivals of ships in ports (Lorenzoni et al.  ), IT projects (Heimerl and Kolisch BIB014 ) and movie projects (Bomsdorf and Derigs BIB012 ). Also note that some of the above papers consider ongoing processes rather than projects in the strict sense (i.e., a set of activities which are carried out to achieve a predefined goal). Apparently, project scheduling concepts are powerful enough to capture such problems as well. The field of project scheduling has also attracted researchers who examined the underlying mathematical structures and their relationships to other optimization problems. For example, Sprecher BIB001 shows that the flow shop, open shop, job shop, and assembly line balancing problems are special cases of project scheduling problems. Hartmann BIB006 outlines how bin packing, strip packing, and knapsack problems can be modeled as project scheduling problems. Stadtler BIB009 compares the multi-level capacitated lotsizing problem and the RCPSP and presents an integrated model. Brucker and Knust BIB007 and Drexl and Salewski BIB002 show how school and university timetabling problems can be captured as project scheduling problems. These studies show that the use of the RCPSP with all its extensions is not limited to applications in its original field, the scheduling of projects. The RCPSP and its generalizations are also perceived as a collection of powerful tools that allow to describe many highly complex optimization problems from other areas. If some problem is captured as a resource-constrained project scheduling problem, it is possible to employ the solution methods that have been developed for the project scheduling problem. Hence, algorithms originally designed for project scheduling can be transferred to problems from other fields. We believe that this underscores the importance of research on models and methods for project scheduling.