A survey of variants and extensions of the resource-constrained project scheduling problem
---
paper_title: Scheduling subject to resource constraints: classification and complexity

paper_content:

Abstract In deterministic sequencing and scheduling problems, jobs are to be processed on machines of limited capacity. We consider an extension of this class of problems, in which the jobs require the use of additional scarce resources during their execution. A classification scheme for resource constraints is proposed and the computational complexity of the extended problem class is investigated in terms of this classification. Models involving parallel machines, unit-time jobs and the maximum completion time criterion are studied in detail; other models are briefly discussed.
---
paper_title: Experimental Investigation of Heuristics for Resource-Constrained Project Scheduling: An Update

paper_content:

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.
---
paper_title: Project scheduling - Theory and practice

paper_content:

The project scheduling problem involves the scheduling of project activities subject to precedence and/or resource constraints. Of obvious practical importance, it has been the subject of intensive research since the late fifties. A wide variety of commercialized project management software packages have been put to practical use. Despite all these efforts, numerous reports reveal that many projects escalate in time and budget and that many project scheduling procedures have not yet found their way to practical use. The objective of this paper is to confront project scheduling theory with project scheduling practice. We provide a generic hierarchical project planning and control framework that serves to position the various project planning procedures and discuss important research opportunities, the exploration of which may help to close the theory-practice gap.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: Scheduling and constraint propagation

paper_content:

The resource-constrained project-scheduling problem (RCPSP) and some of its generalizations are defined. Furthermore, constraint propagation techniques for these problems and related machine scheduling problems are introduced and possible applications of these techniques in connection with lower bound calculations, branch-and-bound methods, and heuristics are discussed.
---
paper_title: A review of the contribution of Operational Research to Project Management

paper_content:

Abstract Project Management is a professional domain receiving growing attention during the last decades and now it is considered a key concept by Management Sciences to understand and to develop organizations. Operational Research has given essential scientific contributions to the success of Project Management not just through multiple models to understand and to represent projects but also by the development of algorithms and aids to support the decisional role of project manager. In this paper, the major contributions of OR are presented and discussed.
---
paper_title: Multiproject Scheduling with Limited Resources: A Zero-One Programming Approach

paper_content:

A zero-one 0-1 linear programming formulation of multiproject and job-shop scheduling problems is presented that is more general and computationally tractable than other known formulations. It can accommodate a wide range of real-world situations including multiple resource constraints, due dates, job splitting, resource, substitutability, and concurrency and nonconcurrency of job performance requirements. Three possible objective functions are discussed; minimizing total throughput time for all projects: minimizing the time by which all projects are completed i.e., minimizing makespan; and minimizing total lateness or lateness penalty for all projects.
---
paper_title: Resource-constrained project scheduling - A survey of recent developments

paper_content:

Resource-constrained project scheduling involves the scheduling of project activities subject to precedence and resource constraints in order to meet the objective(s) in the best possible way. The area covers a wide variety of problem types. The objective of this paper is to provide a survey of what we believe are the important recent developments in the area. Our main focus will be on the recent progress made in and the encouraging computational experience gained with the use of optimal solution procedures for the basic resource-constrained project scheduling problem (RCPSP) and important extensions. We illustrate how the branching rules, dominance and bounding arguments of a new depth- first branch-and-bound procedure can be extended to a rich variety of related problems: the generalized resource-constrained project scheduling problem, the resource-constrained project scheduling problem with generalized precedence relations, the preemptive resource-constrained project scheduling problem, the resource availability cost problem, and the resource-constrained project scheduling problem with various time/resource(cost) trade-offs and discounted cash flows.
---
paper_title: Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem

paper_content:

Abstract We consider heuristic algorithms for the resource-constrained project scheduling problem. Starting with a literature survey, we summarize the basic components of heuristic approaches. We briefly describe so-called X -pass methods which are based on priority rules as well as metaheuristic algorithms. Subsequently, we present the results of our in-depth computational study. Here, we evaluate the performance of several state-of-the-art heuristics from the literature on the basis of a standard set of test instances and point out to the most promising procedures. Moreover, we analyze the behavior of the heuristics with respect to their components such as priority rules and metaheuristic strategy. Finally, we examine the impact of problem characteristics such as project size and resource scarceness on the performance.
---
paper_title: Stochastic Project Networks: Temporal Analysis, Scheduling and Cost Minimization

paper_content:

1 Basic Concepts.- 1.1 Directed Graphs and Project Networks.- 1.2 GERT Networks.- 1.3 Assumptions and Structural Problems.- 1.4 Complete and GERT Subnetworks.- 2 Temporal Analysis of GERT Networks.- 2.1 Activation Functions and Activation Distributions.- 2.2 Evaluation of Admissible GERT Networks.- 2.3 Computation of Some Quantities Important to Time Planning.- 2.4 Evaluation Methods for Admissible GERT Networks.- 3 STEOR Networks and EOR Networks.- 3.1 Markov Chains and Markov Renewal Processes.- 3.2 STEOR Networks and Markov Renewal Processes.- 3.3 Basic Properties of Admissible EOR Networks.- 3.4 Coverings of Admissible EOR Networks.- 3.5 Properties and Computation of Activation Functions and Activation Numbers.- 3.6 The MRP Method.- 4 Reducible GERT Networks.- 4.1 STEOR-Reducible Subnetworks.- 4.2 Cycle Reduction.- 4.3 Nodes Which Belong Together.- 4.4 Basic Element Structures.- 4.5 BES Networks.- 4.6 Evaluation Methods for BES Networks and General Admissible GERT Networks.- 5 Scheduling with GERT Precedence Constraints.- 5.1 Deterministic Single-Machine Scheduling.- 5.2 Stochastic Single-Machine Scheduling with GERT Precedence Constraints: Basic Concepts.- 5.3 Stochastic Single-Machine Scheduling with GERT Precedence Constraints: Optimality Criteria and Complexity.- 5.4 List Schedules and Sequences of Activity Executions.- 5.5 Minimum Flow-Time Scheduling in FOR Networks.- 5.6 A Flow-Time Scheduling Example.- 5.7 Minimizing the Maximum Expected Lateness in FOR Networks.- 5.8 Essential Histories and Scheduling Policies for Min-Sum Problems in General GERT Networks.- 5.9 Elements of Dynamic Programming.- 5.10 Determination of an Optimal Scheduling Policy for the General Min-Sum Problem.- 6 Cost Minimization for STEOR and FOR Networks.- 6.1 STEOR Networks with Time-Dependent Arc Weights.- 6.2 Cost Minimization in STEOR Networks: Basic Concepts.- 6.3 A Dynamic Programming Approach.- 6.4 The Value-Iteration and Policy-Iteration Techniques.- 7 Cost and Time Minimization for Decision Project Networks.- 7.1 Decision Project Networks.- 7.2 Cost Minimization.- 7.3 Randomized Actions.- 7.4 Multiple Executions of Projects.- 7.5 Time Minimization.- References.
---
paper_title: A survey on the resource-constrained project scheduling problem

paper_content:

In this paper, research on the resource-constrained project scheduling problem is classified according to specified objectives and constraints. Each classified area is extensively surveyed, and special emphasis is given to trends in recent research. Specific papers involving nonrenewable resource constraints and time/cost-based objectives are discussed in detail because they present models that are close representations of real-world problems. The difficulty of solving such complex models by optimization techniques is noted. For the purposes of this survey, a set of 78 optimally solved test problems from the literature and a second set of 110 benchmark problems have been subjected to analysis with some well-known dispatching rules and a scheduling algorithm that consists of a decision-making process utilizing the problem constraints as a base of selection. The computational results are reported and discussed in the text. Constructive scheduling algorithms that are directly based on the problem constraints...
---
paper_title: An integrated survey of deterministic project scheduling

paper_content:

There have been many survey papers in the area of project scheduling in recent years. These papers have primarily emphasized modeling and algorithmic contributions for specific classes of project scheduling problems, such as net present value (NPV) maximization and makespan minimization, with and without resource constraints. Paralleling these developments has been the research in the area of project scheduling decision support, with its emphasis on data sets, data generation methods, and so on, that are essential to benchmark, evaluate, and compare the new models, algorithms and heuristic techniques. These investigations have extended the frontiers of research and application in all areas of project scheduling and management. In this paper, we survey the vast literature in this area with a perspective that integrates models, data, and optimal and heuristic algorithms, for the major classes of project scheduling problems. We also include recent surveys that have compared commercial project scheduling systems. Finally, we present an overview of web-based decision support systems and discuss the potential of this technology in enabling and facilitating researchers and practitioners in identifying new areas of inquiry and application.
---
paper_title: Project scheduling under uncertainty: Survey and research potentials

paper_content:

The vast majority of the research efforts in project scheduling assume complete information about the scheduling problem to be solved and a static deterministic environment within which the pre-computed baseline schedule will be executed. However, in the real world, project activities are subject to considerable uncertainty, which is gradually resolved during project execution. In this survey we review the fundamental approaches for scheduling under uncertainty: reactive scheduling, stochastic project scheduling, fuzzy project scheduling, robust (proactive) scheduling and sensitivity analysis. We discuss the potentials of these approaches for scheduling under uncertainty projects with deterministic network evolution structure.
---
paper_title: Priority rule-based heuristic for multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting

paper_content:

This paper presents a priority rule-based heuristic for the multi-mode resource-constrained project scheduling problem with the splitting of activities around unavailable resources allowed. All resources considered are renewable and each resource unit may not be available at all times due to resource vacations, which are known in advance. A new concept called moving resource strength is developed to help identify project situations where activity splitting is likely to be beneficial during scheduling. The moving resource strength concept is implemented in priority rule-based heuristics to control activity splitting when scheduling. Multiple comparisons of the performance of combination of activity–mode priority rules used in the heuristics are provided. Computational experiments demonstrate the effectiveness of the heuristic in reducing project makespan, and minimizing activity splitting.
---
paper_title: Linear programming based algorithms for preemptive and non-preemptive RCPSP

paper_content:

Abstract In this paper, the RCPSP (resource constrained project scheduling problem) is solved using a linear programming model. Each activity may or may not be preemptive. Each variable is associated to a subset of independent activities (antichains). The properties of the model are first investigated. In particular, conditions are given that allow a solution of the linear program to be a feasible schedule. From these properties, an algorithm based on neighbourhood search is derived. One neighbour solution is obtained through one Simplex pivoting, if this pivoting preserves feasibility. Methods to get out of local minima are provided. The solving methods are tested on the PSPLIB instances in a preemptive setting and prove efficient. They are used when preemption is forbidden with less success, and this difference is discussed.
---
paper_title: An efficient optimal solution procedure for the preemptive resource-constrained project scheduling problem

paper_content:

Abstract In this paper a branch-and-bound procedure is described for scheduling project activities subject to precedence and resource constraints, where activities can be preempted at any discrete time instant and where the objective is to minimize the project duration. The procedure is based on a depth-first solution strategy in which nodes in the solution tree represent resource and precedence feasible partial schedules. Branches emanating from a parent node correspond to exhaustive and minimal combinations of activities, the delay of which resolves resource conflicts at each parent node. A precedence based lower bound and several dominance rules are introduced in order to restrict the growth of the solutions tree. The solution procedure has been programmed in the C language and extensive computational experience is reported.
---
paper_title: Solving a Preemptive Project Scheduling Problem with Coloring Techniques

paper_content:

In this paper we describe an exact algorithm to solve a preemptive project scheduling problem with scarce resources. As most of the scheduling problems also the studied one is NP-hard. Many different approaches, such as mathematical programming, heuristics, simulating annealing, etc., have been presented to solve this class of intractable problems. In our approach we consider a graph-theoretical method based on new coloring techniques. In particular, given a disjunctive graph we examine the correspondences between an assignment of time windows (i.e. activities starting time and finishing time) and an assignment of colors to the activities of a project, defining when an exact weighted coloring is an optimal preemptive schedule. We present computational results on randomly generated test problems of the branch and bound algorithm proposed. From the results obtained emerges that the possibility to manage hard problems using new coloring techniques seems to be more efficient than others, referring in particular to the performances of the algorithm proposed.
---
paper_title: Properties of multi-mode resource-constrained project scheduling problems with resource vacations and activity splitting

paper_content:

This paper presents results from an extensive computational study of the multi-mode resource-constrained project scheduling problem when activities can be split during scheduling under situations where resources may be temporarily not available. All resources considered are renewable and each resource unit may not be available at all times due to resource vacations, which are known in advance, and assignment to other finite duration activities. A designed experiment is conducted that investigates project makespan improvement when activity splitting is permitted in various project scenarios, where different project scenarios are defined by parameters that have been used in the research literature. A branch-and-bound procedure is applied to solve a number of small project scheduling problems with and without activity splitting. The results show that, in the presence of resource vacations and temporary resource unavailability, activity splitting can significantly improve the optimal project makespan in many scenarios, and that the makespan improvement is primarily dependent on those parameters that impact resource utilization.
---
paper_title: Project scheduling with calendars

paper_content:

For many applications of project scheduling to real-life problems, it is necessary to take into account calendars specifying time intervals during which some resources such as manpower or machines are not available. Whereas the execution of certain activities like packaging may be suspended during breaks, other activities cannot be interrupted due to technical reasons. Minimum and maximum time lags between activities may depend on calendars, too. In this paper, we address the problem of scheduling the activities of a project subject to calendar constraints. We devise efficient algorithms for computing earliest and latest start and completion times of activities. Moreover, we sketch how to use these algorithms for developing priority-rule methods coping with renewable-resource constraints and calendars.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: Resource-constrained project scheduling and timetabling

paper_content:

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.
---
paper_title: Resource-constrained project scheduling with renewable and non-renewable resources and time-resource tradeoffs

paper_content:

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.
---
paper_title: Batch scheduling in process industries: an application of resource-constrained project scheduling

paper_content:

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.
---
paper_title: Scheduling Projects with Labor Constraints

paper_content:

In this paper we consider a labor constrained scheduling problem (LCSP) which is a simplification of a practical problem arising in industry. Jobs are subject to precedence constraints and have specified processing times. Moreover, for each job the labor requirement varies as the job is processed. Given the amount of labor available in each period, the problem is to finish all the jobs as soon as possible, that is, to minimize makespan, subject to the precedence and labor constraints. Several Integer Programming (IP) formulations for this problem are discussed and valid inequalities for these different models are introduced. It turns out that a major drawback in using the IP approach is the weakness of the lower bound relaxations. However, we report computational experiments showing how the solution of the linear relaxation of the IP models can be used to provide good schedules. Solutions arising from these LP-based heuristics are considerably improved by local search procedures. We further exploit the capabilities of local search for LCSP by designing a Tabu Search algorithm. The computational experiments on a benchmark data set show that the Tabu algorithm generates the best known upper bounds for almost all these instances. We also show how IP can be used to provide reasonably good lower bounds for LCSP when the makespan is replaced by suitably modified objective functions. Finally some directions for further investigations which may turn IP techniques into a more interesting tool for solving such a problem are suggested.
---
paper_title: Scheduling project networks with resource constraints and time windows

paper_content:

Project networks with time windows are generalizations of the well-known CPM and MPM networks that allow for the introduction of arbitrary minimal and maximal time lags between the starting and completion times of any pair of activities.
---
paper_title: A project scheduling problem with labour constraints and time-dependent activities requirements

paper_content:

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.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: Formulation and Tabu Search Algorithm for the Resource Constrained Project Scheduling Problem

paper_content:

The resource constrained project scheduling problem (RCPSP) can formulate many scheduling problems including jobshop and flowshop scheduling problems. In this paper, we extend the definition of RCPSP further so that various complicated constraints and objective functions arising in practice can be handled; for example, each activity can be processed in one of the selectable modes, the available amounts of renewable resources may vary depending on the periods, setup activities can be dealt with, and complex objective functions can be handled. Then, we develop a tabu search based heuristic algorithm, which contains elaborations in representing solutions and in constructing neighborhood. Our code was tested for many benchmarks of RCPSP, and also for some problems from real applications. For a number of RCPSP instances, we found better solutions than the best ones found so far. These computational results indicate the effectiveness and usefulness of our approach.
---
paper_title: Modelling Setup Times in Project Scheduling

paper_content:

In this chapter project scheduling problems with setup times are considered. Some practical applications justifying considering setups separately from activities are described. An extensive classification of setup times adapted from machine scheduling is proposed, including activity vs. class setup, separable vs. inseparable setup, as well as sequence-independent and sequence-dependent setup times. A new category of setup times - schedule-dependent ones - is discussed. The main part of the paper shows how to model setup times in the presence of particular project components, such as: precedence constraints, resource availability constraints, multiple resource units requests, multiple resources, etc. Some possible extensions of the presented models are given.
---
paper_title: ProGen/πx – An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions

paper_content:

Abstract Project scheduling has long been an area of intensive research, but until recently most efforts have been dedicated to developing solution procedures and generalizing models, with little work done on generating problem instances. Additionally, if labor time regulations have to be taken into consideration, the classical resource-constrained project scheduling problem (RCPSP) cannot be used for many problems in manpower scheduling. This paper introduces several extensions to the RCPSP aimed at modeling such problems, and a problem instance generator based on the project generator ProGen incorporating these extensions. Thus, it becomes possible to thoroughly test solution procedures for, e.g., audit-staff scheduling, crew scheduling and timetabling problems. Preliminary computational results are given that were obtained with a greedy randomized solution method using priority rules specifically tailored to the generalized model.
---
paper_title: Setup times and fast tracking in resource-constrained project scheduling

paper_content:

Resource-constrained project scheduling with activity pre-emption assumes that activities are allowed to be interrupted and restarted later in the schedule at no extra cost. In the current paper, we extend this pre-emptive scheduling problem with setup times between activity interruptions and the possibility to schedule pre-emptive sub-parts of activities in parallel. The contribution of the paper is twofold. First, we briefly show that an efficient exact branch-and-bound procedure from the literature to solve the resource-constrained project scheduling problem can be easily adapted to cope with our problem extensions. Second, we extensively test the impact of these pre-emptive extensions to the quality of the schedule from a makespan point-of-view.
---
paper_title: Tabu search for multi-mode resource-constrained project scheduling with schedule-dependent setup times

paper_content:

Abstract In this paper, a multi-mode resource-constrained project scheduling problem with schedule-dependent setup times is considered. A schedule-dependent setup time is defined as a setup time dependent on the assignment of resources to activities over time, when resources are, e.g., placed in different locations. In such a case, the time necessary to prepare the required resource for processing an activity depends not only on the sequence of activities but, more generally, on the locations in which successive activities are executed. Activities are non-preemptable, resources are renewable, and the objective is to minimize the project duration. A local search metaheuristic—tabu search is proposed to solve this strongly NP-hard problem, and it is compared with the multi-start iterative improvement method as well as with random sampling. A computational experiment is described, performed on a set of instances based on standard test problems constructed by the ProGen project generator. The algorithms are computationally compared, the results are analyzed and discussed, and some conclusions are given.
---
paper_title: Batch scheduling in process industries: an application of resource-constrained project scheduling

paper_content:

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.
---
paper_title: A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems

paper_content:

The particle swarm optimization (PSO) has been widely used to solve continuous problems. The discrete problems have just begun to be also solved by the discrete PSO. However, the combinatorial problems remain a prohibitive area to the PSO mainly in case of integer values. In this paper, we propose a combinatorial PSO (CPSO) algorithm that we take up challenge to use in order to solve a multi-mode resource-constrained project scheduling problem (MRCPSP). The results that have been obtained using a standard set of instances, after extensive experiments, prove to be very competitive in terms of number of problems solved to optimality. By comparing average deviations and percentages of optima found, our CPSO algorithm outperforms the simulated annealing algorithm and it is close to the PSO algorithm.
---
paper_title: Resource---constrained project scheduling: a heuristic for the multi---mode case

paper_content:

This paper presents a heuristic solution procedure for a very general resource---constrained project scheduling problem. Here, multiple execution modes are available for the individual activities of the project. In addition, minimum as well as maximum time lags between different activities may be given. The objective is to determine a mode and a start time for each activity such that the temporal and resource constraints are met and the project duration is minimized. Project scheduling problems of this type occur e.g. in process industries. The heuristic is a multi---pass priority---rule method with backplanning which is based on an integration approach and embedded in random sampling. Its performance is evaluated within an experimental performance analysis for problem instances of real---life size with 100 activities and up to 5 modes per activity.
---
paper_title: Scheduling projects with heterogeneous resources to meet time and quality objectives

paper_content:

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.
---
paper_title: A solution procedure for the discrete time, cost and quality tradeoff problem using electromagnetic scatter search

paper_content:

Abstract Decisions concerning a project’s expedition, traditionally involved considerations regarding time and cost tradeoff. It was recently suggested that the quality of a project should also be taken into considerations. In this paper, we propose a meta-heuristic solution procedure for the discrete time, cost and quality tradeoff problem. This problem involves the scheduling of project activities in order to minimize the total cost of the project while maximizing the quality of the project and also meeting a given deadline. We apply a so called electromagnetic scatter search to solve this problem. In this process, we initially generate a population of feasible solutions. In so doing, we use frequency memory to well sample the feasible region. A number of these solutions are then selected and improved locally. The improved solutions are then combined to generate new set of solutions. The combination process utilizes attraction–repulsion mechanisms borrowed from the electromagnetism theory. The whole process is stopped when no significant improvement in the set of solutions are observed. The validity of the proposed solution procedure is demonstrated, and its applicability is tested on a randomly generated large and complex problem having 19,900 activities.
---
paper_title: Project Scheduling under Resource and Mode Identity Constraints. Model, Complexity, Methods, and Application

paper_content:

Abstract A recurring problem in project management involves the allocation of scarce resources to the individual jobs comprising the project. In many situations such as audit-staff scheduling, timetabling, and course scheduling, the resources correspond to individuals (skilled labour). This naturally leads to an assignment-type project scheduling problem, i.e. a project has to be performed by assigning one or more of several individuals (resources) to each job. In this paper we consider the nonpreemptive variant of a resource-constrained project scheduling problem with mode identity. Mode identity refers to a generalization of the multi-mode case where the set of all jobs is partitioned into disjoint subsets while all jobs forming one subset have to be processed in the same mode. Both time and cost incurred by processing a subset of jobs depend on the resources assigned to it. This problem is a substantial and nontrivial generalization of the well-known multi-mode case. Regarding precedence and temporal relations as well as release dates and deadlines, the question arises to which jobs resources should be assigned in order to minimize overall costs. For solving this time-resource-cost-tradeoff problem we present a tailored parallel randomized solution approach called ramses into which both static and dynamic priority rules can be incorporated. The results of an extensive computational study on a practical application from the field of audit-staff scheduling indicate that ramses is capable of producing “good” solutions in neglectable amounts of time.
---
paper_title: Lower Bounds in Different Problem Classes of Project Schedules with Resource Constraints

paper_content:

The worldwide opening of the markets, hence the continuously increasing number of competitors, the higher customers standards and shorter product innovation cycles require a cost- or time-minimizing manufacturing of customer orders or projects, preferably just in time, under limited availability of resources. Manufacturing planning can no longer be the result of experience.
---
paper_title: A genetic algorithm approach to a general category project scheduling problem

paper_content:

A genetic algorithm (GA) approach is proposed for the general resource-constrained project scheduling model, in which activities may be executed in more than one operating mode, and renewable as well as nonrenewable resource constraints exist. Each activity's operation mode has a different duration and requires different amounts of renewable and nonrenewable resources. The objective is the minimization of the project duration or makespan. The problem under consideration is known to be one of the most difficult scheduling problems, and it is hard to find a feasible solution for such a problem, let alone the optimal one. The GA approach described in this paper incorporates problem-specific scheduling knowledge by an indirect chromosome encoding that consists of selected activity operating modes and an ordered set of scheduling rules. The scheduling rules in the chromosome are used in an iterative scheduling algorithm that constructs the schedule resulting from the chromosome. The proposed GA is denoted a hybrid GA (HGA) approach, since it is integrated with traditional scheduling tools and expertise specifically developed for the general resource-constrained project scheduling problem. The results demonstrate that HGA approach produces near-optimal solutions within a reasonable amount of computation time.
---
paper_title: A mathematical model for the multi-mode resource-constrained project scheduling problem with mode dependent time lags

paper_content:

This paper presents an exact model for the multi-mode resource-constrained project scheduling problem with generalized precedence relations in which the minimal or maximal time lags between a pair of activities may vary depending on the chosen modes. All resources considered are renewable. The objective is to determine a mode and a start time for each activity so that all constraints are obeyed and the project duration is minimized. Project scheduling of this type occurs in many fields, for instance, construction industries. The proposed model has been inspired by the rectangle packing problems. In spite of the fact that it needs a feasible solution to start for conventional models, the new model has no need for a feasible solution to start. Computational results with a set of 60 test problems have been reported and the efficiency of the proposed model has been analyzed.
---
paper_title: A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags

paper_content:

Abstract The paper presents an exact procedure for a general resource-constrained project scheduling problem where multiple modes are available for the performance of the individual activities and minimum as well as maximum time lags between the different activities may be given. The objective is to determine a mode and a start time for each activity such that all constraints are observed and the project duration is minimized. Project scheduling problems of this type occur, e.g. in process industries. The solution method is a depth-first search based branch-and-bound procedure. It makes use of a branching strategy where the branching rule is selected dynamically. The solution approach is an integration approach where the modes and start times are determined simultaneously. Within an experimental performance analysis this procedure is compared with existing solution procedures.
---
paper_title: A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version

paper_content:

This paper describes new simulated annealing (SA) algorithms for the resource-constrained project scheduling problem (RCPSP) and its multiple mode version (MRCPSP). The objective function considered is minimisation of the makespan. The conventional SA search scheme is replaced by a new design that takes into account the specificity of the solution space of project scheduling problems. For RCPSP, the search was based on an alternated activity and time incrementing process, and all parameters were set after preliminary statistical experiments done on test instances. For MRCPSP, we introduced an original approach using two embedded search loops alternating activity and mode neighbourhood exploration. The performance evaluation done on the benchmark instances available in the literature proved the efficiency of both adaptations that are currently among the most competitive algorithms for these problems.
---
paper_title: Simulated Annealing for Multi-Mode Resource-Constrained Project Scheduling

paper_content:

In this paper the resource-constrained project scheduling problem with multiple execution modes for each activity and the makespan as the minimization criterion is considered. A simulated annealing approach to solve this problem is presented. The feasible solution representation is based on a precedence feasible list of activities and a mode assignment. A comprehensive computational experiment is described, performed on a set of standard test problems constructed by the ProGen project generator. The results are analyzed and discussed and some final remarks are included. Copyright Kluwer Academic Publishers 2001
---
paper_title: The resource constrained project scheduling problem with multiple crashable modes: An exact solution method

paper_content:

We introduce a formulation and an exact solution method for a nonpreemptive resource constrained project scheduling problem in which the duration/cost of an activity is determined by the mode selection and the duration reduction (crashing) within the mode. This problem is a natural combination of the time/cost tradeoff problem and the resource constrained project scheduling problem. It involves the determination, for each activity, of its resource requirements, the extent of crashing, and its start time so that the total project cost is minimized. We present a branch and bound procedure and report computational results with a set of 160 problems. Computational results demonstrate the effectiveness of our procedure. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 107–127, 2001
---
paper_title: Lagrangian heuristics for scheduling new product development projects in the pharmaceutical industry

paper_content:

To stay ahead of their competition, pharmaceutical firms must make effective use of their new product development (NPD) capabilities by efficiently allocating its analytical, clinical testing and manufacturing resources across various drug development projects. The resulting project scheduling problems involve coordinating hundreds of testing and manufacturing activities over a period of several quarters. Most conventional integer programming approaches are computationally impractical for problems of this size, while priority rule-driven heuristics seldom provide consistent solution quality. We propose a Lagrangian decomposition (LD) heuristic that exploits the special structure of these problems. Some resources (typically manpower) are shared across all on-going projects while others (typically equipment) are specific to individual project categories. Our objective function is a weighted discounted cost expressed in terms of activity completion times. The LD heuristics were subjected to a comprehensive experimental study based on typical operational instances. While the conventional "Reward---Risk" priority rule heuristic generates duality gaps between 47---58%, the best LD heuristic achieves duality gaps between 10---20%. The LD heuristics also yield makespan reductions of over 30% over the Reward---Risk priority rule.
---
paper_title: A Branch-and-Cut Procedure for the Multimode Resource-Constrained Project-Scheduling Problem

paper_content:

This paper considers the multimode resource-constrained project-scheduling problem (MRCPSP) with a minimum-makespan objective. An exact branch and cut algorithm is presented based on the integer linear programming (ILP) formulation of the problem. In the preprocessing stage, lower bounds on the distance between each pair of precedence-constrained activities are derived. These bounds are used to reduce the number of variables in the model and to generate cuts that tighten the linear programming relaxation. The solution process is accelerated by an adaptive branching scheme in conjunction with a bound-tightening scheme that is called iteratively after branching. To find good feasible solutions in the early stages of the computations, a high-level neighborhood search strategy known as local branching is included. Here, a neighborhood of a feasible solution is defined by the linear inequalities in the ILP model and is searched first. As implemented, the full algorithm is exact rather than heuristic in nature. Numerical results are reported for 20- and 30-activity benchmark problems. These are the largest instances available and are generally viewed to be notoriously difficult. Up until now, there were no confirmed optimal solutions for any of the 552 30-activity instances. We were able to find several better solutions and to show that at least 506 are optimal.
---
paper_title: Lower bounds for the Multi-Skill Project Scheduling Problem with hierarchical levels of skills

paper_content:

In this paper, we introduce an extension of the classical Resource-Constrained Project Scheduling Problem: the Multi-skill Project Scheduling Problem. We consider a project made up of activities that must be implemented by a staff: every member of this staff masters one or more skill(s). An activity needs a given amount of each skill with a fixed minimum level of mastering. For each unit of a skill needed, we have to assign an employee who masters the required level of this skill during the whole processing time of the activity. The objective is to minimize the duration of the project, i.e. the makespan. We introduce here two lower bounds used to evaluate the minimum duration.
---
paper_title: Project scheduling with multiple modes: a genetic algorithm

paper_content:

In this paper we consider the resource-constrained project scheduling problem with multiple execution modes for each activity and makespan minimization as objective. We present a new genetic algorithm approach to solve this problem. The genetic encoding is based on a precedence feasible list of activities and a mode assignment. After defining the related crossover, mutation, and selection operators, we describe a local search extension which is employed to improve the schedules found by the basic genetic algorithm. Finally, we present the results of our thorough computational study. We determine the best among several different variants of our genetic algorithm and compare it to four other heuristics that have recently been proposed in the literature. The results that have been obtained using a standard set of instances show that the new genetic algorithm outperforms the other heuristic procedures with regard to a lower average deviation from the optimal makespan.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: The multi-mode resource-constrained project scheduling problem with generalized precedence relations

paper_content:

Abstract In this paper, we tackle the challenging problem of scheduling activities to minimize the project duration, in which the activities (a) are subject to generalized precedence relations, (b) require units of multiple renewable, non-renewable and doubly constrained resources for which a limited availability is imposed, and (c) can be performed in one of several different ways, reflected in multiple activity scenarios or modes. These multiple modes give rise to several kinds of trade-offs (time/resource, time/cost and resource/resource trade-offs) which allow for a more efficient allocation and use of resources. We present a local search-based solution methodology which is able to handle many real-life project scheduling characteristics such as time-varying resource requirements and availabilities, activity ready times, due dates and deadlines, activity overlaps, activity start time constraints and other types of temporal constraints.
---
paper_title: Formulation and Tabu Search Algorithm for the Resource Constrained Project Scheduling Problem

paper_content:

The resource constrained project scheduling problem (RCPSP) can formulate many scheduling problems including jobshop and flowshop scheduling problems. In this paper, we extend the definition of RCPSP further so that various complicated constraints and objective functions arising in practice can be handled; for example, each activity can be processed in one of the selectable modes, the available amounts of renewable resources may vary depending on the periods, setup activities can be dealt with, and complex objective functions can be handled. Then, we develop a tabu search based heuristic algorithm, which contains elaborations in representing solutions and in constructing neighborhood. Our code was tested for many benchmarks of RCPSP, and also for some problems from real applications. For a number of RCPSP instances, we found better solutions than the best ones found so far. These computational results indicate the effectiveness and usefulness of our approach.
---
paper_title: Resource-constrained project scheduling and timetabling

paper_content:

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.
---
paper_title: Local Search for Nonpreemptive Multi-Mode Resource-Constrained Project Scheduling

paper_content:

This paper addresses a general class of nonpreemptive resource-constrained project scheduling problems in which activity durations are discrete functions of committed renewable and nonrenewabe resources. We provide a 0-1 problem formulation and stress the importance of the outlined model by giving applications within production and operations management. Furthermore, we prove that even the problem to derive a feasible solution is NP-complete. As a consequence, solution procedures proposed so far suffer from severe drawbacks: Exact procedures can only solve very small instances to optimality, while heuristic solution approaches fail to generate feasible solutions when problems become highly resource-constrained. Hence, we propose a new local search methodology which first tries to find a feasible solution and second performs a single-neighbourhood search on the set of feasible mode-assignments. In order to evaluate the new procedura we perform a rigorous computational study on the ProGen benchmark-set which is available in the open literature. The experiment includes a comparison of our procedure with other recently proposed heuristics.
---
paper_title: Modeling the supply chain configuration problem with resource constraints

paper_content:

Abstract In this paper, we study the supply chain configuration problem (SCCP) under resource constraints. We present a new modeling framework based on multi-mode resource-constrained project scheduling (MRCPSP) for configuring the supply chain subject to explicit resource constraints. It establishes a bridge between the areas of project scheduling and supply chain design. Our model is also able to handle additional practical issues such as quality level requirements and general temporal constraints , which are often encountered in the real world. A constraint programming (CP) based solution approach is proposed and implemented in our case study. Conclusions and future research directions are discussed.
---
paper_title: ProGen/πx – An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions

paper_content:

Abstract Project scheduling has long been an area of intensive research, but until recently most efforts have been dedicated to developing solution procedures and generalizing models, with little work done on generating problem instances. Additionally, if labor time regulations have to be taken into consideration, the classical resource-constrained project scheduling problem (RCPSP) cannot be used for many problems in manpower scheduling. This paper introduces several extensions to the RCPSP aimed at modeling such problems, and a problem instance generator based on the project generator ProGen incorporating these extensions. Thus, it becomes possible to thoroughly test solution procedures for, e.g., audit-staff scheduling, crew scheduling and timetabling problems. Preliminary computational results are given that were obtained with a greedy randomized solution method using priority rules specifically tailored to the generalized model.
---
paper_title: Resource-constrained project scheduling with renewable and non-renewable resources and time-resource tradeoffs

paper_content:

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.
---
paper_title: Environment-oriented project scheduling for the dismantling of buildings

paper_content:

This paper presents a case study for the environment-friendly dismantling and recycling of buildings. Based on material-flow management it is shown how the dismantling on the construction site can be improved using resource-constrained project scheduling. Computational results show that strict environmental requirements like high recycling quotas and the reduction of harmful substances in recycling materials can be satisfied. Moreover, a comparison with results in practice indicates that project scheduling helps to achieve economic advantages for environment-friendly dismantling and recycling strategies.
---
paper_title: Network decomposition-based benchmark results for the discrete time-cost tradeoff problem

paper_content:

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.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: The discrete time/resource trade-off problem in project networks: a branch-and-bound approach

paper_content:

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.
---
paper_title: New computational results on the discrete time/cost trade-off problem in project networks

paper_content:

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.
---
paper_title: A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling

paper_content:

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.
---
paper_title: Nonlinear time/cost tradeoff models in project management

paper_content:

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.
---
paper_title: Solving the discrete time/resource trade-off problem in project scheduling with genetic algorithms

paper_content:

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.
---
paper_title: Solving the resource constrained project scheduling problem with optimization subroutine library

paper_content:

In this paper we present three new models for the resource constrained project scheduling problem, using two objective functions: minimizing the makespan and maximizing the net present value of the cash flows of the activities. In these models, compared to the models in the literature, we relax one of the most constraining assumptions about the integrality of the activity durations and the project time line. Furthermore resources are assumed to be partially-renewable. These models have multiple uses in Operations Management in that they can be used to solve resource constrained MRP problems. The models are found to be amenable to solution using the Optimization Subroutine Library (OSL). Extensive computational experiments with OSL on a total of 1400 problems with different parameter settings are reported. Detailed analysis is done to determine the factors that affect the computational efficiency of the code and the models. In general, results demonstrate that OSL is a powerful tool for solving the models with either objective function. Optimal solutions are obtained with reasonable computational effort. A discussion of the application of several special features of OSL is also given.
---
paper_title: MRP in a job shop environment using a resource constrained project scheduling model

paper_content:

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.
---
paper_title: ProGen/πx – An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions

paper_content:

Abstract Project scheduling has long been an area of intensive research, but until recently most efforts have been dedicated to developing solution procedures and generalizing models, with little work done on generating problem instances. Additionally, if labor time regulations have to be taken into consideration, the classical resource-constrained project scheduling problem (RCPSP) cannot be used for many problems in manpower scheduling. This paper introduces several extensions to the RCPSP aimed at modeling such problems, and a problem instance generator based on the project generator ProGen incorporating these extensions. Thus, it becomes possible to thoroughly test solution procedures for, e.g., audit-staff scheduling, crew scheduling and timetabling problems. Preliminary computational results are given that were obtained with a greedy randomized solution method using priority rules specifically tailored to the generalized model.
---
paper_title: WORK CONTINUITY CONSTRAINTS IN PROJECT SCHEDULING

paper_content:

Repetitive projects involve the repetition of activities along the stages of the project. Since the resources required to perform these activities move from one stage to the other, a main objective of scheduling these projects is to maintain the continuity of work of these resources so as to minimize the idle time of resources. This requirement, often referred to as work continuity constraints, involves a tradeoff between total project duration and the resource idle time. The contribution of this paper is threefold. First, we provide an extensive literature summary of the topic under study. Although most research papers deal with the scheduling of construction projects, we show that this can be extended to many other environments. Second, we propose an exact search procedure for scheduling repetitive projects with work continuity constraints. This algorithm iteratively shifts repeating activities further in time in order to decrease the resource idle time. We have embedded this recursive search procedure in a horizon-varying algorithm in order to detect the complete tradeoff profile between resource idle time and project duration. The procedure has been coded in Visual C++ and has been validated on a randomly generated problem set. Finally, we illustrate the concepts on three examples. First, the use of our new algorithm is illustrated on a small fictive problem example from literature. In a second example, we show that work continuity constraints involve a tradeoff between total project duration and the resource idle time. A last example describes the scheduling of a well-known real-life project that aims at the construction of a tunnel at the Westerschelde in The Netherlands.
---
paper_title: Integrated Scheduling, Assembly Area- and Part-Assignment for Large Scale, Make-to-Order Assemblies

paper_content:

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.
---
paper_title: Scheduling project networks with resource constraints and time windows

paper_content:

Project networks with time windows are generalizations of the well-known CPM and MPM networks that allow for the introduction of arbitrary minimal and maximal time lags between the starting and completion times of any pair of activities.
---
paper_title: Modelling setup times, process batches and transfer batches using activity network logic

paper_content:

Abstract The objective of this paper is to demonstrate how modelling ideas and solution procedures, borrowed from the field of generalized resource-constrained project scheduling, can be used to formulate and solve several types of production scheduling problems involving sequence-independent setup times as well as process and transfer batches. The computational results provide useful insight in the trade-offs that do exist between the computational effort required and the size of the process and transfer batches used.
---
paper_title: Computing lower bounds by destructive improvement - an application to resource-constrained project scheduling

paper_content:

In this paper, two meta-strategies for computing lower bounds (for minimization problems) are described. Constructive (direct) methods directly calculate a bound value by relaxing a problem and solving this relaxation. Destructive improvement techniques restrict a problem by setting a maximal objective function value F and try to contradict (destruct) the feasibility of this reduced problem. In case of success, F or even F + 1 is a valid lower bound value. The fundamental properties and differences of both meta-strategies are explained by applying them to the well-known resource-constrained project scheduling problem (RCPSP). For this problem, only a few constructive bound arguments are available in the literature. We present a number of extensions and new methods as well as techniques for reducing problem data which can be exploited within the destructive improvement framework. Comprehensive numerical experiments show that the new constructive bound arguments clearly provide better bounds than the former ones and that further really significant improvements are obtained through an appropriate application of destructive improvement.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: Time-Cost Optimization of Construction Projects with Generalized Activity Constraints

paper_content:

Time-cost analysis is an important element of project scheduling, especially for lengthy and costly construction projects, as it evaluates alternative schedules and establishes an optimum one considering any project completion deadline. Existing methods for time-cost analysis have not adequately considered typical activity and project characteristics, such as generalized precedence relationships between activities, external time constraints, activity planning constraints, and bonuses/penalties for early/delayed project completion that would provide a more realistic representation of actual construction projects. The present work aims to incorporate such characteristics in the analysis and has developed two solution methods, an exact and an approximate one. The exact method utilizes a linear/integer programming model to provide the optimal project time-cost curve and the minimum cost schedule considering all activity time-cost alternatives together. The approximate method performs a progressive project length reduction providing a near-optimal project time-cost curve but it is faster than the exact method as it examines only certain activities at each stage. In addition, it can be easily incorporated in project scheduling software. Evaluation results indicate that both methods can effectively simulate the structure of construction projects, and their application is expected to provide time and cost savings.
---
paper_title: PROGRESS: Optimally solving the generalized resource-constrained project scheduling problem

paper_content:

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.
---
paper_title: ProGen/πx – An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions

paper_content:

Abstract Project scheduling has long been an area of intensive research, but until recently most efforts have been dedicated to developing solution procedures and generalizing models, with little work done on generating problem instances. Additionally, if labor time regulations have to be taken into consideration, the classical resource-constrained project scheduling problem (RCPSP) cannot be used for many problems in manpower scheduling. This paper introduces several extensions to the RCPSP aimed at modeling such problems, and a problem instance generator based on the project generator ProGen incorporating these extensions. Thus, it becomes possible to thoroughly test solution procedures for, e.g., audit-staff scheduling, crew scheduling and timetabling problems. Preliminary computational results are given that were obtained with a greedy randomized solution method using priority rules specifically tailored to the generalized model.
---
paper_title: Resource---constrained project scheduling: a heuristic for the multi---mode case

paper_content:

This paper presents a heuristic solution procedure for a very general resource---constrained project scheduling problem. Here, multiple execution modes are available for the individual activities of the project. In addition, minimum as well as maximum time lags between different activities may be given. The objective is to determine a mode and a start time for each activity such that the temporal and resource constraints are met and the project duration is minimized. Project scheduling problems of this type occur e.g. in process industries. The heuristic is a multi---pass priority---rule method with backplanning which is based on an integration approach and embedded in random sampling. Its performance is evaluated within an experimental performance analysis for problem instances of real---life size with 100 activities and up to 5 modes per activity.
---
paper_title: A constraint-based method for project scheduling with time windows

paper_content:

This paper presents a heuristic algorithm for solving RCPSP/max, the resource constrained project scheduling problem with generalized precedence relations. The algorithm relies, at its core, on a constraint satisfaction problem solving (CSP) search procedure, which generates a consistent set of activity start times by incrementally removing resource conflicts from an otherwise temporally feasible solution. Key to the effectiveness of the CSP search procedure is its heuristic strategy for conflict selection. A conflict sampling method biased toward selection of minimal conflict sets that involve activities with higher-capacity requests is introduced, and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This CSP search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically on a large set of previously studied RCPSP/max benchmark problems.
---
paper_title: A mathematical model for the multi-mode resource-constrained project scheduling problem with mode dependent time lags

paper_content:

This paper presents an exact model for the multi-mode resource-constrained project scheduling problem with generalized precedence relations in which the minimal or maximal time lags between a pair of activities may vary depending on the chosen modes. All resources considered are renewable. The objective is to determine a mode and a start time for each activity so that all constraints are obeyed and the project duration is minimized. Project scheduling of this type occurs in many fields, for instance, construction industries. The proposed model has been inspired by the rectangle packing problems. In spite of the fact that it needs a feasible solution to start for conventional models, the new model has no need for a feasible solution to start. Computational results with a set of 60 test problems have been reported and the efficiency of the proposed model has been analyzed.
---
paper_title: A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags

paper_content:

Abstract The paper presents an exact procedure for a general resource-constrained project scheduling problem where multiple modes are available for the performance of the individual activities and minimum as well as maximum time lags between the different activities may be given. The objective is to determine a mode and a start time for each activity such that all constraints are observed and the project duration is minimized. Project scheduling problems of this type occur, e.g. in process industries. The solution method is a depth-first search based branch-and-bound procedure. It makes use of a branching strategy where the branching rule is selected dynamically. The solution approach is an integration approach where the modes and start times are determined simultaneously. Within an experimental performance analysis this procedure is compared with existing solution procedures.
---
paper_title: Scheduling project networks with resource constraints and time windows

paper_content:

Project networks with time windows are generalizations of the well-known CPM and MPM networks that allow for the introduction of arbitrary minimal and maximal time lags between the starting and completion times of any pair of activities.
---
paper_title: Methods for Resource-Constrained Project Scheduling with Regular and Nonregular Objective Functions and Schedule-Dependent Time Windows

paper_content:

Projects with minimum and maximum time lags between the start of different activities (i.e. there are schedule-dependent time windows) play an important role in practice. Unfortunately, maximum time lags have been discussed in literature very rarely and only recently. However, maximum time lags (in addition to minimum ones) are needed to model a variety of practical requirements such as deadlines for subprojects or individual activities, simultaneous or non-delay execution of several activities, time-varying resource requirements, time windows for resources, scheduling of make-to-order production, and resource allocation in process-determined industry (cf. Neumann and Schwindt 1995, 1997).
---
paper_title: Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints

paper_content:

Abstract This paper deals with resource-constrained project scheduling problems with nonregular objective functions where general temporal constraints given by minimum and maximum time lags between activities are prescribed. In particular, resource leveling and net present value problems are studied. We present different heuristic and exact procedures for (approximately) solving those problems. A detailed experimental performance analysis shows that these procedures also solve large problem instances in reasonable computing time.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: The multi-mode resource-constrained project scheduling problem with generalized precedence relations

paper_content:

Abstract In this paper, we tackle the challenging problem of scheduling activities to minimize the project duration, in which the activities (a) are subject to generalized precedence relations, (b) require units of multiple renewable, non-renewable and doubly constrained resources for which a limited availability is imposed, and (c) can be performed in one of several different ways, reflected in multiple activity scenarios or modes. These multiple modes give rise to several kinds of trade-offs (time/resource, time/cost and resource/resource trade-offs) which allow for a more efficient allocation and use of resources. We present a local search-based solution methodology which is able to handle many real-life project scheduling characteristics such as time-varying resource requirements and availabilities, activity ready times, due dates and deadlines, activity overlaps, activity start time constraints and other types of temporal constraints.
---
paper_title: Resource-constrained project scheduling and timetabling

paper_content:

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.
---
paper_title: Batch scheduling in process industries: an application of resource-constrained project scheduling

paper_content:

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.
---
paper_title: Due Dates and RCPSP

paper_content:

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.
---
paper_title: Satisfiability Tests and Time-Bound Adjustments for Cumulative Scheduling Problems

paper_content:

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
---
paper_title: Two approaches to the problem of sharing delay costs in joint projects

paper_content:

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.)
---
paper_title: An efficient search procedure for the resource-constrained multi-project scheduling problem with discounted cash flows

paper_content:

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.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: A branch-and-cut algorithm for scheduling of projects with variable-intensity activities

paper_content:

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.
---
paper_title: A project scheduling problem with labour constraints and time-dependent activities requirements

paper_content:

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.
---
paper_title: PROGRESS: Optimally solving the generalized resource-constrained project scheduling problem

paper_content:

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.
---
paper_title: RCPS with variable intensity activities and feeding precedence constraints

paper_content:

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.
---
paper_title: A heuristic treatment of tardiness and net present value criteria in resource constrained project scheduling

paper_content:

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.
---
paper_title: Discrete Time/Cost Trade-offs in Project Scheduling with Time-switch Constraints

paper_content:

The discrete time-cost trade-offs problem(DTCTP,for short) is a most widely concerned with bi-criteria optimization model in project scheduling literatures,which has been studied under three possible objectives.(1)P1:the so-called deadline problem involves the scheduling of project activities in order to minimize the total cost of the project while meeting a given deadline.(2)P2:the budget problem aims at minimizing the project duration without exceeding a given budget.(3)P3: the time/cost profile problem involves the generation of the complete efficient time-cost profile over the set of feasible project durations.However,the literature on the DTCTP with time-switch constraints are sparsely paid attention.In this paper,we firstly introduce the problem description of time-switch constraints,and then build the arithmetic model of the DTCTPTSC_-P2;From the point view of practicality,a genetic algorithm is developed to solve the model.Finally,a project example based on real-life situation is used to validate the model and the algorithm.At the same time,the results show that the model plays an instructional role for contractor to more closely control the project's scheduling.
---
paper_title: Resource-constrained project scheduling and timetabling

paper_content:

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.
---
paper_title: Managing and modelling general resource transfers in ( multi-) project scheduling

paper_content:

Most approaches to multi-project scheduling are based on the assumption that resources can be transferred between projects without any expense in time and cost. As this assumption often is not realistic, we generalise the multi-project scheduling problem (RCMPSP) by additionally including transfer times and cost. To integrate this aspect, in a first step, we develop a framework for considering resource transfers in single and multi-project environments. It includes managerial approaches to handle resource transfers, a classification of resource transfer types and new roles that resources can take in these transfers. Afterwards, we define the multi-project scheduling problem with transfer times (RCMPSPTT) and formulate it in a basic and an extended version as integer linear programmes. Eventually, it is supplemented for the first time by cost considerations and introduced as resource constrained multi-project scheduling problem with transfer times and cost (RCMPSPTTC). Computational experiments compare the presented managerial approaches and prove the necessity of explicitly considering transfer times in project scheduling. Moreover, the experiments evaluate the presented MIP models and show that specialised solution procedures are vital.
---
paper_title: RCPS with variable intensity activities and feeding precedence constraints

paper_content:

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.
---
paper_title: Formulation and Tabu Search Algorithm for the Resource Constrained Project Scheduling Problem

paper_content:

The resource constrained project scheduling problem (RCPSP) can formulate many scheduling problems including jobshop and flowshop scheduling problems. In this paper, we extend the definition of RCPSP further so that various complicated constraints and objective functions arising in practice can be handled; for example, each activity can be processed in one of the selectable modes, the available amounts of renewable resources may vary depending on the periods, setup activities can be dealt with, and complex objective functions can be handled. Then, we develop a tabu search based heuristic algorithm, which contains elaborations in representing solutions and in constructing neighborhood. Our code was tested for many benchmarks of RCPSP, and also for some problems from real applications. For a number of RCPSP instances, we found better solutions than the best ones found so far. These computational results indicate the effectiveness and usefulness of our approach.
---
paper_title: Resource-constrained project scheduling and timetabling

paper_content:

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.
---
paper_title: A model, heuristic procedure and decision support system for solving the movie shoot scheduling problem

paper_content:

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.
---
paper_title: Handling Airport Ground Processes based on Resource-Constrained Project Scheduling

paper_content:

This paper describes how the Resource-Constrained Project Scheduling Problem (RCPSP) can be used as a basis for real-time decision support in the disruption management of the aircraft turnaround, the most typical airport ground process. For this purpose, the RCPSP is extended by the possibility to describe alternative activities, which can be used to model potential process modifications. An evolutionary approach is presented for solving this generalized problem, considering both basic rescheduling possibilities as well as the option of exchanging activities. The work presented in this paper is based on the results of a study conducted in collaboration with Deutsche Lufthansa AG, concerned with the analysis of the elementary requirements of decision support systems for turnaround process management.
---
paper_title: Resource constrained scheduling of hierarchically structured design activity networks

paper_content:

In this paper, a new approach to the problem of scheduling of design activities with precedence and multiple resource constraints is proposed. In addition to the AND type relationship, OR and EXCLUSIVE OR relationships may also exist between design activities. In order to handle these logical relationships, IDEF3 is used for network representation. A large network of design activities can be arranged in different levels of abstraction. A procedure is proposed to transform an IDEF3 model into a set of alternative precedence networks. In the networks selected, the activities that are resource independent are grouped with a partitioning procedure. In order to increase the efficiency of the search for the best schedule, a procedure based on the Christofides et al. (1987) reduction procedure is introduced to determine a lower bound on the completion time of the hierarchically structured design activity network. >
---
paper_title: Stochastic Project Networks: Temporal Analysis, Scheduling and Cost Minimization

paper_content:

1 Basic Concepts.- 1.1 Directed Graphs and Project Networks.- 1.2 GERT Networks.- 1.3 Assumptions and Structural Problems.- 1.4 Complete and GERT Subnetworks.- 2 Temporal Analysis of GERT Networks.- 2.1 Activation Functions and Activation Distributions.- 2.2 Evaluation of Admissible GERT Networks.- 2.3 Computation of Some Quantities Important to Time Planning.- 2.4 Evaluation Methods for Admissible GERT Networks.- 3 STEOR Networks and EOR Networks.- 3.1 Markov Chains and Markov Renewal Processes.- 3.2 STEOR Networks and Markov Renewal Processes.- 3.3 Basic Properties of Admissible EOR Networks.- 3.4 Coverings of Admissible EOR Networks.- 3.5 Properties and Computation of Activation Functions and Activation Numbers.- 3.6 The MRP Method.- 4 Reducible GERT Networks.- 4.1 STEOR-Reducible Subnetworks.- 4.2 Cycle Reduction.- 4.3 Nodes Which Belong Together.- 4.4 Basic Element Structures.- 4.5 BES Networks.- 4.6 Evaluation Methods for BES Networks and General Admissible GERT Networks.- 5 Scheduling with GERT Precedence Constraints.- 5.1 Deterministic Single-Machine Scheduling.- 5.2 Stochastic Single-Machine Scheduling with GERT Precedence Constraints: Basic Concepts.- 5.3 Stochastic Single-Machine Scheduling with GERT Precedence Constraints: Optimality Criteria and Complexity.- 5.4 List Schedules and Sequences of Activity Executions.- 5.5 Minimum Flow-Time Scheduling in FOR Networks.- 5.6 A Flow-Time Scheduling Example.- 5.7 Minimizing the Maximum Expected Lateness in FOR Networks.- 5.8 Essential Histories and Scheduling Policies for Min-Sum Problems in General GERT Networks.- 5.9 Elements of Dynamic Programming.- 5.10 Determination of an Optimal Scheduling Policy for the General Min-Sum Problem.- 6 Cost Minimization for STEOR and FOR Networks.- 6.1 STEOR Networks with Time-Dependent Arc Weights.- 6.2 Cost Minimization in STEOR Networks: Basic Concepts.- 6.3 A Dynamic Programming Approach.- 6.4 The Value-Iteration and Policy-Iteration Techniques.- 7 Cost and Time Minimization for Decision Project Networks.- 7.1 Decision Project Networks.- 7.2 Cost Minimization.- 7.3 Randomized Actions.- 7.4 Multiple Executions of Projects.- 7.5 Time Minimization.- References.
---
paper_title: Heuristic scheduling of capital constrained projects

paper_content:

Abstract The movement to product and process development projects that involve joint ventures among strategic partners, as well as the increasing prevalence of projects within organizations has led to increased implementation of project scheduling methods. It is frequently the case that a capital constraint is placed on a project, thus limiting the number and value of activities that can be scheduled to occur simultaneously. However, the quantity of capital available to schedule activities can increase as additional cash is received as progress payments for completed activities. Since the project manager'so objective is to maximize project Net Present Value (NPV), it is important for the manager to develop a schedule that balances the early receipt of progress payments (which improve NPV and increase the capital balance available), with the delay of particularly large expenditures. Due to the intractability of optimal methods, the use of heuristic methods is required to solve problems of practical size. This paper presents the first test of heuristic methods for solving this problem. We use information from a relaxed optimization-guided model that employs information from the unconstrained NPV-optimal problem in heuristic procedure for solving the capital constrained problem. An experimental design is employed to test the heuristics that includes multiple factor levels for a number of project characteristics, including capital utilization, frequency of progress payments, and project network structure. The results indicate very good relative performance for the optimization-guided procedures as compared to two benchmark heuristics.
---
paper_title: A solution procedure for the discrete time, cost and quality tradeoff problem using electromagnetic scatter search

paper_content:

Abstract Decisions concerning a project’s expedition, traditionally involved considerations regarding time and cost tradeoff. It was recently suggested that the quality of a project should also be taken into considerations. In this paper, we propose a meta-heuristic solution procedure for the discrete time, cost and quality tradeoff problem. This problem involves the scheduling of project activities in order to minimize the total cost of the project while maximizing the quality of the project and also meeting a given deadline. We apply a so called electromagnetic scatter search to solve this problem. In this process, we initially generate a population of feasible solutions. In so doing, we use frequency memory to well sample the feasible region. A number of these solutions are then selected and improved locally. The improved solutions are then combined to generate new set of solutions. The combination process utilizes attraction–repulsion mechanisms borrowed from the electromagnetism theory. The whole process is stopped when no significant improvement in the set of solutions are observed. The validity of the proposed solution procedure is demonstrated, and its applicability is tested on a randomly generated large and complex problem having 19,900 activities.
---
paper_title: Project Scheduling under Time Dependent Costs – A Branch and Bound Algorithm

paper_content:

In a given project network, execution of each activity in normal duration requires utilization of certain resources. If faster execution of an activity is desired then additional resources at extra cost would be required. Given a project network, the cost structure for each activity and a planning horizon, the project compression problem is concerned with the determination of optimal schedule (duration) of performing each activity while satisfying given restrictions and minimizing the total cost of project execution. This paper considers the project compression problem with time dependent cost structure for each activity. The planning horizon is divided into several regular time intervals over which the cost structure of an activity may vary. But the cost structure of the activities remains the same (constant) within a time interval. Key events of the project attract penalty for finishing earlier or later than the corresponding target times. The objective is to find an optimal project schedule minimizing the total project cost. We present a mathematical model for this problem, develop some heuristics and an exact branch and bound algorithm. Using simulated problems we provide an insight into the computational performances of heuristics and the branch and bound algorithm.
---
paper_title: Two approaches to the problem of sharing delay costs in joint projects

paper_content:

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.)
---
paper_title: An integrated survey of deterministic project scheduling

paper_content:

There have been many survey papers in the area of project scheduling in recent years. These papers have primarily emphasized modeling and algorithmic contributions for specific classes of project scheduling problems, such as net present value (NPV) maximization and makespan minimization, with and without resource constraints. Paralleling these developments has been the research in the area of project scheduling decision support, with its emphasis on data sets, data generation methods, and so on, that are essential to benchmark, evaluate, and compare the new models, algorithms and heuristic techniques. These investigations have extended the frontiers of research and application in all areas of project scheduling and management. In this paper, we survey the vast literature in this area with a perspective that integrates models, data, and optimal and heuristic algorithms, for the major classes of project scheduling problems. We also include recent surveys that have compared commercial project scheduling systems. Finally, we present an overview of web-based decision support systems and discuss the potential of this technology in enabling and facilitating researchers and practitioners in identifying new areas of inquiry and application.
---
paper_title: On Certain Models of Resource Allocation Problems

paper_content:

This paper presents a general model of resource allocation problems based on the concept of the system of the complex of operations type. Using the terminology of this model, a classification of particular allocation problems has been made and examples of an exact formulation of new problems have been given. Attention has been paid to the practical interpretation of assumptions and results. Some desired directions of further development in the theory and application of the considered problems have been indicated.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: Multiobjective network scheduling with efficient use of renewable and nonrenewable resources

paper_content:

Abstract The paper deals with the allocation of different categories of resources in a network project under multiple conflicting criteria including project duration or maximum lateness, and several cost criteria. The resource requirements of the splittable activities are assumed to be discrete, i.e., assuming arbitrary values from given finite sets for particular resource types and categories. Two approaches for solving the problem, using multiobjective linear programming in specific ways, are described. Reduction of the number of activity preemptions, as a secondary project performance measure, is considered.
---
paper_title: GRASP and Path Relinking for Project Scheduling under Partially Renewable Resources

paper_content:

Recently, in the field of project scheduling problems the concept of partially renewable resources has been introduced. Theoretically, it is a generalization of both renewable and non-renewable resources. From an applied point of view, partially renewable resources allow us to model a large variety of situations that do not fit into classical models, but can be found in real problems in timetabling and labor scheduling. In this paper, we develop some preprocessing techniques and several heuristic algorithms for the problem. Preprocessing significantly reduces the dimension of the problems, therefore improving the efficiency of solution procedures. Heuristic algorithms based on GRASP and Path relinking are then developed and tested on existing test instances, obtaining excellent results.
---
paper_title: Project scheduling under partially renewable resource constraints

paper_content:

We consider a generalization of the classical resource constrained project scheduling problem. We introduce so-called partially reiiewable resources by assuming for each resource a capacity on subsets of periods. The concept of partially renewable resources is a fundamental tool in order to make e.g. timetabling and shift scheduling aspects amenable to project scheduling. In addition, partially renewable resources serve to model complicated labor regulations. Furthermore, they cover traditional renewable and nonre-newable resource constraints as special cases. We consider makespan minimization as objective. For the exact Solution of the problem we employ a basic enumeration scheme. In order to speed up convergence, we formulate bounds which take into account future resource consumption of partially renewable resources. Moreover, we generalize the serial scheduling scheme in order to get fast approximation methods. A rigorous assessment of the procedures is provided by solving Pro Gen instances generated under a full factorial test design. Besides the well-known problem parameters we employ additionally three parameters which control the generation of partially renewable resources.
---
paper_title: A Branch-and-Cut Procedure for the Multimode Resource-Constrained Project-Scheduling Problem

paper_content:

This paper considers the multimode resource-constrained project-scheduling problem (MRCPSP) with a minimum-makespan objective. An exact branch and cut algorithm is presented based on the integer linear programming (ILP) formulation of the problem. In the preprocessing stage, lower bounds on the distance between each pair of precedence-constrained activities are derived. These bounds are used to reduce the number of variables in the model and to generate cuts that tighten the linear programming relaxation. The solution process is accelerated by an adaptive branching scheme in conjunction with a bound-tightening scheme that is called iteratively after branching. To find good feasible solutions in the early stages of the computations, a high-level neighborhood search strategy known as local branching is included. Here, a neighborhood of a feasible solution is defined by the linear inequalities in the ILP model and is searched first. As implemented, the full algorithm is exact rather than heuristic in nature. Numerical results are reported for 20- and 30-activity benchmark problems. These are the largest instances available and are generally viewed to be notoriously difficult. Up until now, there were no confirmed optimal solutions for any of the 552 30-activity instances. We were able to find several better solutions and to show that at least 506 are optimal.
---
paper_title: A Scatter Search Algorithm for Project Scheduling under Partially Renewable Resources

paper_content:

In this paper we develop a heuristic algorithm, based on Scatter Search, for project scheduling problems under partially renewable resources. This new type of resource can be viewed as a generalization of renewable and non-renewable resources, and is very helpful in modelling conditions that do no fit into classical models, but which appear in real timetabling and labor scheduling problems. The Scatter Search algorithm is tested on existing test instances and obtains the best results known so far.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: ProGen/πx – An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions

paper_content:

Abstract Project scheduling has long been an area of intensive research, but until recently most efforts have been dedicated to developing solution procedures and generalizing models, with little work done on generating problem instances. Additionally, if labor time regulations have to be taken into consideration, the classical resource-constrained project scheduling problem (RCPSP) cannot be used for many problems in manpower scheduling. This paper introduces several extensions to the RCPSP aimed at modeling such problems, and a problem instance generator based on the project generator ProGen incorporating these extensions. Thus, it becomes possible to thoroughly test solution procedures for, e.g., audit-staff scheduling, crew scheduling and timetabling problems. Preliminary computational results are given that were obtained with a greedy randomized solution method using priority rules specifically tailored to the generalized model.
---
paper_title: Resource-constrained project scheduling with renewable and non-renewable resources and time-resource tradeoffs

paper_content:

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.
---
paper_title: Scheduling of continuous and discontinuous material flows with intermediate storage restrictions

paper_content:

This paper deals with scheduling batch (i.e., discontinuous), continuous, and semicontinuous production in process industries (e.g., chemical, pharmaceutical, or metal casting industries) where intermediate storage facilities and renewable resources (processing units and manpower) of limited capacity have to be observed. First, different storage configurations typical of process industries are discussed. Second, a basic scheduling problem covering the three above production modes is presented. Third, (exact and truncated) branch-and-bound methods for the basic scheduling problem and the special case of batch scheduling are proposed and subjected to an experimental performance analysis. The solution approach presented is flexible and in principle simple, and it can (approximately) solve relatively large problem instances with sufficient accuracy.
---
paper_title: Project scheduling with inventory constraints

paper_content:

Inventory constraints refer to so-called cumulative resources, which can store a single or several different products and have a prescribed minimum and maximum inventory, where the inventory is depleted and replenished over time. Some additional applications of cumulative resources, e.g. to investment projects, are also discussed in this paper.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: Batch scheduling in process industries: an application of resource-constrained project scheduling

paper_content:

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.
---
paper_title: Solving the discrete-continuous project scheduling problem via its discretization

paper_content:

Abstract. In this paper a discrete-continuous project scheduling problem is considered. In this problem activities simultaneously require discrete and continuous resources. The processing rate of each activity depends on the amount of the continuous resource allotted to this activity at a time. All the resources are renewable ones. The activities are nonpreemtable and the objective is to minimize the makespan. Discretization of this problem leading to a classical (i.e. discrete) project scheduling problem in the multi-mode version is presented. A simulated annealing (SA) approach to solving this problem is described and tested computationally in two versions: with and without finding an optimal continuous resource allocation for the final schedule. In the former case a nonlinear solver is used for solving a corresponding convex programming problem. The results are compared with the results obtained using SA for the discrete-continuous project scheduling problem where the nonlinear solver is used for exact solving the continuous part in each iteration. The results of a computational experiment are analyzed and some conclusions are included.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: A branch-and-cut algorithm for scheduling of projects with variable-intensity activities

paper_content:

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.
---
paper_title: RCPS with variable intensity activities and feeding precedence constraints

paper_content:

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.
---
paper_title: Discrete-continuous project scheduling with discounted cash flows-A tabu search approach

paper_content:

In this paper discrete-continuous project scheduling problems with discounted cash flows are considered. In discrete-continuous project scheduling activities require for their processing discrete and continuous resources. The processing rate of an activity depends on the amount of the continuous resource allotted to this activity at a time. A positive cash flow is associated with each activity. Two common payment models-lump-sum payment and payments at activities' completion times-are considered. The objective is the maximization of the net present value of all cash flows of the project. Some properties of optimal schedules are discussed, and the formulation of a mathematical programming problem for an optimal continuous resource allocation is presented. Applications of a local search metaheuristic-tabu search, as well as simple search methods-multi-start iterative improvement and random sampling are described. The algorithms are compared on the basis of a computational experiment, the results are analyzed and discussed. Some conclusions as well as directions for further research are given.
---
paper_title: A Survey of Interval Capacity Consistency Tests for Time- and Resource-Constrained Scheduling

paper_content:

Interval capacity consistency tests consider the resource capacities available and required within certain time intervals. The goal of the tests is to draw conclusions that allow to rule out inadmissible activity start times or sequences. The tests can be effectively used to reduce the search space of difficult time- and resource-constrained scheduling problems. They have successfully been applied in algorithms for solving idealised problems such as the classical job shop scheduling problem (JSP) or the resource-constrained project scheduling problem (RCPSP) as well as for solving industrial scheduling problems. For instance, it seems fair to say that the advances in modern branch and bound algorithms for the JSP that have been made in the last decade can to a large extent be attributed to the effect of interval consistency tests, some of which are also known under the names of immediate selection, edge finding, and energetic reasoning. The tests can also serve to derive tight lower bounds for makespan minimisation problems.
---
paper_title: Solving a Preemptive Project Scheduling Problem with Coloring Techniques

paper_content:

In this paper we describe an exact algorithm to solve a preemptive project scheduling problem with scarce resources. As most of the scheduling problems also the studied one is NP-hard. Many different approaches, such as mathematical programming, heuristics, simulating annealing, etc., have been presented to solve this class of intractable problems. In our approach we consider a graph-theoretical method based on new coloring techniques. In particular, given a disjunctive graph we examine the correspondences between an assignment of time windows (i.e. activities starting time and finishing time) and an assignment of colors to the activities of a project, defining when an exact weighted coloring is an optimal preemptive schedule. We present computational results on randomly generated test problems of the branch and bound algorithm proposed. From the results obtained emerges that the possibility to manage hard problems using new coloring techniques seems to be more efficient than others, referring in particular to the performances of the algorithm proposed.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: Heuristics for multimode scheduling problems with dedicated resources

paper_content:

We study scheduling problems with multiple modes and dedicated resources arising in production and project management, which constitute a special class of the general multimode resource-constrained project scheduling problem. A task may require simultaneously a set of discrete, renewable resources to be processed and the processing can be performed in different modes, that is with different resource sets, processing times, or costs. Precedence constraints can exist among tasks. The total budget that can be allocated to the project can be limited. The problem consists of identifying a mode for each task and a starting time for its processing respecting precedence, resource, and budget constraints. A graph model and an iterative solution scheme are presented. Specific heuristic algorithms for the cases with and without budget constraints are given and computational results are discussed.
---
paper_title: Solving the resource constrained project scheduling problem with optimization subroutine library

paper_content:

In this paper we present three new models for the resource constrained project scheduling problem, using two objective functions: minimizing the makespan and maximizing the net present value of the cash flows of the activities. In these models, compared to the models in the literature, we relax one of the most constraining assumptions about the integrality of the activity durations and the project time line. Furthermore resources are assumed to be partially-renewable. These models have multiple uses in Operations Management in that they can be used to solve resource constrained MRP problems. The models are found to be amenable to solution using the Optimization Subroutine Library (OSL). Extensive computational experiments with OSL on a total of 1400 problems with different parameter settings are reported. Detailed analysis is done to determine the factors that affect the computational efficiency of the code and the models. In general, results demonstrate that OSL is a powerful tool for solving the models with either objective function. Optimal solutions are obtained with reasonable computational effort. A discussion of the application of several special features of OSL is also given.
---
paper_title: Scheduling project networks with resource constraints and time windows

paper_content:

Project networks with time windows are generalizations of the well-known CPM and MPM networks that allow for the introduction of arbitrary minimal and maximal time lags between the starting and completion times of any pair of activities.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: Resource-constrained project scheduling and timetabling

paper_content:

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.
---
paper_title: Batch scheduling in process industries: an application of resource-constrained project scheduling

paper_content:

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.
---
paper_title: Due Dates and RCPSP

paper_content:

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.
---
paper_title: Integrated Scheduling, Assembly Area- and Part-Assignment for Large Scale, Make-to-Order Assemblies

paper_content:

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.
---
paper_title: Experimental Investigation of Heuristics for Resource-Constrained Project Scheduling: An Update

paper_content:

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.
---
paper_title: The multiple resource constrained project scheduling problem: A breadth-first approach

paper_content:

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.
---
paper_title: MRP in a job shop environment using a resource constrained project scheduling model

paper_content:

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.
---
paper_title: Scheduling an r&d project with quality-dependent time slots

paper_content:

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.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: Using metaheuristics in multiobjective resource constrained project scheduling

paper_content:

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.
---
paper_title: Resource-constrained project scheduling with renewable and non-renewable resources and time-resource tradeoffs

paper_content:

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.
---
paper_title: Bi-objective resource-constrained project scheduling with robustness and makespan criteria

paper_content:

Resource-constrained project scheduling problem (RCPSP) is one of the most important problems in the context of project scheduling. Considering a single objective, such as makespan minimization, net present value minimization or cost minimization has been the cornerstone of most studies done so far. At the other hand, taking this problem into account as a multi objective one has not been well studied. In this paper, a bi-objective model of RCPSP is presented. The first objective is makespan to be minimized, and the second one, a recently developed measure, is robustness maximization aimed at floating time maximization to make scheduling more reliable. The problem formed in this way is an NP-hard one forcing us to use simulated annealing algorithm to obtain a global optimum solution or at least a satisfying one. Finally, we have illustrated our new algorithm using a numerical example with different weights for robustness. (As an example, when robustness weight is zero, the problem will be solved as a makespan objective.)
---
paper_title: Ensuring quality in resource constrained project scheduling

paper_content:

This study constitutes an initial effort for modeling and solving resource constrained project scheduling problems with the objective of maximizing quality. Two mixed integer formulations of the problem are introduced. The first formulation assumes integral activity durations and completion times. These assumptions are relaxed in the second formulation. In both formulations the quality of a project is measured by the amount of rework required and the corresponding additional cost incurred. These quality measures are expressed in a common unit of measure and incorporated into the objective function. The second mixed integer formulation is found to be more efficient and thus computational results are reported based on that model. A set of resource constrained scheduling problems are solved using the quality objective and traditional objective functions from the literature. In general it is found that the schedules obtained when maximizing quality outperform the schedules obtained with minimizing makespan or maximizing the net present value of project cash flows objectives in terms of makespan, cost and computational times.
---
paper_title: A note on the paper by M. A. Al-Fawzan and M. Haouari about a bi-objective problem for robust resource-constrained project scheduling

paper_content:

Abstract The project schedule robustness measure proposed by Al-Fawzan and Haouari is considered. The deficiency of this criterion is proven. Two new criteria are proposed.
---
paper_title: A bi-objective model for robust resource-constrained project scheduling

paper_content:

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.
---
paper_title: Disruption management for resource-constrained project scheduling

paper_content:

In this paper, we study the problem of how to react when an ongoing project is disrupted. The focus is on the resource-constrained project scheduling problem with finish–start precedence constraints. We begin by proposing a classification scheme for the different types of disruptions and then define the constraints and objectives that comprise what we call the recovery problem. The goal is to get back on track as soon as possible at minimum cost, where cost is now a function of the deviation from the original schedule. The problem is formulated as an integer linear program and solved with a hybrid mixed-inter programming/constraint programming procedure that exploits a number of special features in the constraints. The new model is significantly different from the original one due to the fact that a different set of feasibility conditions and performance requirements must be considered during the recovery process. The complexity of several special cases is analysed. To test the hybrid procedure, 554 20-activity instances were solved and the results compared with those obtained with CPLEX. Computational experiments were also conducted to determine the effects of different factors related to the recovery process.
---
paper_title: Probe Backtrack Search for Minimal Perturbation in Dynamic Scheduling

paper_content:

This paperdescribes an algorithm designed to minimally reconfigure schedulesin response to a changing environment. External factors havecaused an existing schedule to become invalid, perhaps due tothe withdrawal of resources, or because of changes to the setof scheduled activities. The total shift in the start and endtimes of already scheduled activities should be kept to a minimum.This optimization requirement may be captured using a linearoptimization function over linear constraints. However, the disjunctivenature of the resource constraints impairs traditional mathematicalprogramming approaches. The unimodular probing algorithm interleavesconstraint programming and linear programming. The linear programmingsolver handles only a controlled subset of the problem constraints,to guarantee that the values returned are discrete. Using probebacktracking, a complete, repair-based method for search, thesevalues are simply integrated into constraint programming. Unimodularprobing is compared with alternatives on a set of dynamic schedulingbenchmarks, demonstrating its effectiveness.In the final discussion, we conjecture that analogous probebacktracking strategies may obtain performance improvements overconventional backtrack algorithms for a broad range of constraintsatisfaction and optimization problems.
---
paper_title: Robust optimization models for project scheduling with resource availability cost

paper_content:

We address a project scheduling problem with resource availability cost for which the activity durations are uncertain. The problem is formulated within the robust optimization framework, where uncertainty is modeled via a set of scenarios. The proposed solution method is based on the scatter search methodology and employs advanced strategies, such as dynamic updating of the reference set, a frequency-based memory mechanism, and path relinking. A multistart heuristic was also developed and comparative results are reported. The tradeoffs for risk-averse decision makers are discussed.
---
paper_title: Solving the resource availability cost problem in project scheduling by path relinking and genetic algorithm

paper_content:

This paper considers a project scheduling problem with the objective of minimizing resource availability costs required to execute the activities in a project by a given project deadline. The project contains activities interrelated by finish-start-type precedence relations with a time lag of zero, which require a set of renewable resources. Two metaheuristics, path relinking and genetic algorithm, are developed to tackle this problem in which a schedule is created with a precedence feasible priority list given to the schedule generation scheme. In these procedures, each new generation of solutions are created using the combination of current solutions. Comparative computational results reveal that path relinking is a very effective metaheuristic and dominates genetic algorithm.
---
paper_title: Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints

paper_content:

Abstract This paper deals with resource-constrained project scheduling problems with nonregular objective functions where general temporal constraints given by minimum and maximum time lags between activities are prescribed. In particular, resource leveling and net present value problems are studied. We present different heuristic and exact procedures for (approximately) solving those problems. A detailed experimental performance analysis shows that these procedures also solve large problem instances in reasonable computing time.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: A branch-and-cut algorithm for scheduling of projects with variable-intensity activities

paper_content:

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.
---
paper_title: Resource constrained project scheduling with multiple objectives: a decision support approach

paper_content:

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.
---
paper_title: Optimization guided lower and upper bounds for the resource investment problem

paper_content:

The resource investment problem deals with the issue of providing resources to a project such that a given deadline can be met. The objective is to make the resources available in the cheapest possible way. For each resource, expenses depend on the maximum amount required during the course of the project. In this paper we develop two lower bounds for this NP-hard problem using Lagrangean relaxation and column generation techniques, respectively. Both procedures are capable of yielding feasible solutions as well. Hence, we also have two optimization guided heuristics. A computational study consisting of a set of 3210 instances compares both approaches and allows insight into the performance.
---
paper_title: The resource renting problem subject to temporal constraints

paper_content:

We introduce a project scheduling problem subject to temporal constraints where the resource availability costs have to be minimized. As an extension of known project scheduling problems which consider only time-independent costs, this problem includes both time-independent procurement costs and time-dependent renting costs for the resources. Consequently, in addition to projects where all resources are bought, we can deal with projects where resources are rented. Based on the enumeration of a finite set of schedules which is proved to contain an optimal schedule, we develop a depth-first branch-and-bound procedure. Computational experience with a randomly generated test set containing 10800 problem instances is reported.
---
paper_title: A genetic algorithm for the resource renting problem with minimum and maximum time lags

paper_content:

We work with a project scheduling problem subject to temporal constraints where the resource availability costs have to be minimised. As an extension of the more well known Resource Investment Problem, which considers only time-independent costs, this problem includes both time-independent fixed costs and time-dependent variable renting costs for the resources. Consequently, in addition to projects where all resources are bought, we can deal with projects where resources are rented. Based on a new codification of a solution for project scheduling, we develop a Genetic Algorithm capable of outperforming a branch-and-bound procedure that exists for the problem.
---
paper_title: Using metaheuristics in multiobjective resource constrained project scheduling

paper_content:

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.
---
paper_title: A model, heuristic procedure and decision support system for solving the movie shoot scheduling problem

paper_content:

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.
---
paper_title: Resource-constrained project scheduling with renewable and non-renewable resources and time-resource tradeoffs

paper_content:

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.
---
paper_title: A genetic algorithm for resource investment project scheduling problem, tardiness permitted with penalty

paper_content:

Abstract In this paper a genetic algorithm for solving a class of project scheduling problems, called Resource Investment Problem, is presented. Tardiness of project is permitted with defined penalty. Elements of algorithm such as chromosome structure, unfitness function, crossover, mutation, immigration and local search operations are explained. The performance of this genetic algorithm is compared with the performance of other published algorithms for Resource Investment Problem. Also 690 problems are solved and their optimal solutions are used for the performance tests of the genetic algorithm. The tests results are quite satisfactory.
---
paper_title: Optimal resource leveling using non-serial dyanamic programming

paper_content:

Abstract A recurring problem in managing project activities is to minimize the deviation between the resource requirements and stated desirable levels. This paper presents a new optimizing approach for resource leveling based on non-serial dynamic programming. This approach permits a marked reduction of the complexity of the problem as it checks for only the feasible time subsets which are far less numerous than feasible sequences. The model, which is applied to an activity-on-node network, requires as input the scheduling results provided by the critical path method (CPM). Applications of the model to two opposite cases are also described and the solutions compared with the ones achieved by the Burges and Killebrew heuristic. Computational results indicate that the procedure provides exact solutions for small to medium size problems, requiring only modest computing facilities.
---
paper_title: Network decomposition-based benchmark results for the discrete time-cost tradeoff problem

paper_content:

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.
---
paper_title: A solution procedure for the discrete time, cost and quality tradeoff problem using electromagnetic scatter search

paper_content:

Abstract Decisions concerning a project’s expedition, traditionally involved considerations regarding time and cost tradeoff. It was recently suggested that the quality of a project should also be taken into considerations. In this paper, we propose a meta-heuristic solution procedure for the discrete time, cost and quality tradeoff problem. This problem involves the scheduling of project activities in order to minimize the total cost of the project while maximizing the quality of the project and also meeting a given deadline. We apply a so called electromagnetic scatter search to solve this problem. In this process, we initially generate a population of feasible solutions. In so doing, we use frequency memory to well sample the feasible region. A number of these solutions are then selected and improved locally. The improved solutions are then combined to generate new set of solutions. The combination process utilizes attraction–repulsion mechanisms borrowed from the electromagnetism theory. The whole process is stopped when no significant improvement in the set of solutions are observed. The validity of the proposed solution procedure is demonstrated, and its applicability is tested on a randomly generated large and complex problem having 19,900 activities.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: New computational results on the discrete time/cost trade-off problem in project networks

paper_content:

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.
---
paper_title: Using metaheuristics in multiobjective resource constrained project scheduling

paper_content:

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.
---
paper_title: Resource-constrained project scheduling with renewable and non-renewable resources and time-resource tradeoffs

paper_content:

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.
---
paper_title: On project scheduling with irregular starting time costs

paper_content:

Maniezzo and Mingozzi (Oper. Res. Lett. 25 (1999) 175-182) study a project scheduling problem with irregular starting time costs. Starting from the assumption that its computational complexity status is open, they develop a branch-and-bound procedure and they identify special cases that are solvable in polynomial time. In this note, we present a collection of previously established results which show that the general problem is solvable in polynomial time. This collection may serve as a useful guide to the literature, since this polynomial-time solvability has been rediscovered in different contexts or using different methods. In addition, we briefly review some related results for specializations and generalizations of the problem.
---
paper_title: The project scheduling problem with irregular starting time costs

paper_content:

We consider the problem of scheduling a set of activities satisfying precedence constraints in order to minimize the sum of the costs associated with the starting times of the activities. We consider the case in which the activity starting time cost functions are irregular functions. This problem can be solved in polynomial time either when the precedence graph has a special structure or when the starting time cost function of each activity is monotonic. A (0-1) integer programming formulation of this problem is presented and used to derive valid lower bounds to the optimal solution cost. An exact branch-and-bound algorithm is described. Computational results show the effectiveness of the proposed exact algorithm in solving problems up to 100 activities.
---
paper_title: Solving Project Scheduling Problems by Minimum Cut Computations

paper_content:

In project scheduling, a set of precedence-constrained jobs has to be scheduled so as to minimize a given objective. In resource-constrained project scheduling, the jobs additionally compete for scarce resources. Due to its universality, the latter problem has a variety of applications in manufacturing, production planning, project management, and elsewhere. It is one of the most intractable problems in operations research, and has therefore become a popular playground for the latest optimization techniques, including virtually all local search paradigms. We show that a somewhat more classical mathematical programming approach leads to both competitive feasible solutions and strong lower bounds, within reasonable computation times. The basic ingredients of our approach are the Lagrangian relaxation of a time-indexed integer programming formulation and relaxation-based list scheduling, enriched with a useful idea from recent approximation algorithms for machine scheduling problems. The efficiency of the algorithm results from the insight that the relaxed problem can be solved by computing a minimum cut in an appropriately defined directed graph. Our computational study covers different types of resource-constrained project scheduling problems, based on several notoriously hard test sets, including practical problem instances from chemical production planning.
---
paper_title: Project Scheduling under Time Dependent Costs – A Branch and Bound Algorithm

paper_content:

In a given project network, execution of each activity in normal duration requires utilization of certain resources. If faster execution of an activity is desired then additional resources at extra cost would be required. Given a project network, the cost structure for each activity and a planning horizon, the project compression problem is concerned with the determination of optimal schedule (duration) of performing each activity while satisfying given restrictions and minimizing the total cost of project execution. This paper considers the project compression problem with time dependent cost structure for each activity. The planning horizon is divided into several regular time intervals over which the cost structure of an activity may vary. But the cost structure of the activities remains the same (constant) within a time interval. Key events of the project attract penalty for finishing earlier or later than the corresponding target times. The objective is to find an optimal project schedule minimizing the total project cost. We present a mathematical model for this problem, develop some heuristics and an exact branch and bound algorithm. Using simulated problems we provide an insight into the computational performances of heuristics and the branch and bound algorithm.
---
paper_title: A Metaheuristic Approach to the Resource Constrained Project Scheduling with Variable Activity Durations and Convex Cost Functions

paper_content:

We introduce a generalized model of the resource constrained project scheduling problem (RCPSP). It features that (i) the duration of an activity is not constant, but can vary in a specified range, and (ii) the objective is to minimize a convex function of time-lag costs, where a time-lag cost is charged according to the difference between the start/completion times of activities. These features achieve the flexibility of the model. It is known that, in the RCPSP, resource constraints can be replaced by some precedence constraints appropriately defined between the activities that require a common scarce resource. If we remove resource constraints by precedence constraints, our problem can be formulated as the dual problem of a minimum cost flow problem, and thus can be solved efficiently. Exploiting this property, we design a heuristic algorithm based on local search. We conducted computational experiments with benchmark instances to minimize the weighted earliness-tardiness costs, as well as instances in which activity-crashing or relaxation of temporal constraints are allowed. These results indicate the usefulness of our generalized RCPSP model and the proposed algorithm.
---
paper_title: Integrated project scheduling and material planning with variable activity duration and rewards

paper_content:

Integrating project scheduling and material ordering adds more realism to project scheduling and considers additional trade-offs that could lead to reductions in the overall project cost. In this paper we review the evolution of the integrated problem, and investigate the impact of treating the activity duration as a decision variable on the activities schedule and materials plan. The effects of introducing rewards (penalties) for early (late) completion as well as materials quantity discounts on the project schedule and cost are also considered- These additions provide scheduling flexibility that might lead to further reduction in the project's total cost or makespan. Considering the various project costs, we found that there exists an optimal schedule that either starts as early as possible (ai time zero) or completes as late as possible. We also show that if the project starts at time zero, then its duration cannot be longer than that for the case where the schedule ends as late as possible. Ft is also shown that the material ordering policy does not follow the Wagner and Whitin model when activity duration is variable or in the presence of quantity discounts. These results have led to modeling and solving the problem in a more efficient manner. Extensive computational work shows the validity of the model and the solution approach.
---
paper_title: Heuristic scheduling of capital constrained projects

paper_content:

Abstract The movement to product and process development projects that involve joint ventures among strategic partners, as well as the increasing prevalence of projects within organizations has led to increased implementation of project scheduling methods. It is frequently the case that a capital constraint is placed on a project, thus limiting the number and value of activities that can be scheduled to occur simultaneously. However, the quantity of capital available to schedule activities can increase as additional cash is received as progress payments for completed activities. Since the project manager'so objective is to maximize project Net Present Value (NPV), it is important for the manager to develop a schedule that balances the early receipt of progress payments (which improve NPV and increase the capital balance available), with the delay of particularly large expenditures. Due to the intractability of optimal methods, the use of heuristic methods is required to solve problems of practical size. This paper presents the first test of heuristic methods for solving this problem. We use information from a relaxed optimization-guided model that employs information from the unconstrained NPV-optimal problem in heuristic procedure for solving the capital constrained problem. An experimental design is employed to test the heuristics that includes multiple factor levels for a number of project characteristics, including capital utilization, frequency of progress payments, and project network structure. The results indicate very good relative performance for the optimization-guided procedures as compared to two benchmark heuristics.
---
paper_title: Solving the resource constrained project scheduling problem with optimization subroutine library

paper_content:

In this paper we present three new models for the resource constrained project scheduling problem, using two objective functions: minimizing the makespan and maximizing the net present value of the cash flows of the activities. In these models, compared to the models in the literature, we relax one of the most constraining assumptions about the integrality of the activity durations and the project time line. Furthermore resources are assumed to be partially-renewable. These models have multiple uses in Operations Management in that they can be used to solve resource constrained MRP problems. The models are found to be amenable to solution using the Optimization Subroutine Library (OSL). Extensive computational experiments with OSL on a total of 1400 problems with different parameter settings are reported. Detailed analysis is done to determine the factors that affect the computational efficiency of the code and the models. In general, results demonstrate that OSL is a powerful tool for solving the models with either objective function. Optimal solutions are obtained with reasonable computational effort. A discussion of the application of several special features of OSL is also given.
---
paper_title: A project activity scheduling problem with net present value measure

paper_content:

This paper considers an activity scheduling problem for a project where cash inflows and outflows are given and availability restrictions are imposed on capital and renewable resources. The objective of the problem is to maximize the net present value of the project. Resource-duration interactions are considered in analyzing the problem. A two-phase heuristic solution algorithm is exploited and tested with various numerical problems for its effectiveness and efficiency.
---
paper_title: Project network models with discounted cash flows a guided tour through recent developments

paper_content:

Abstract The vast majority of the project scheduling methodologies presented in the literature have been developed with the objective of minimizing the project duration subject to precedence and other constraints. In doing so, the financial aspects of project management are largely ignored. Recent efforts have taken into account discounted cash flows and have focused on the maximization of the net present value ( npv ) of the project as the more appropriate objective. In this paper we offer a guided tour through the important recent developments in the expanding field of research on deterministic and stochastic project network models with discounted cash flows. Subsequent to a close examination of the rationale behind the npv objective, we offer a taxonomy of the problems studied in the literature and critically review the major contributions. Proper attention is given to npv maximization models for the unconstrained scheduling problem with known cash flows, optimal and suboptimal scheduling procedures with various types of resource constraints, and the problem of determining both the timing and amount of payments.
---
paper_title: An equitable approach to the payment scheduling problem in project management

paper_content:

Abstract This study reports on a new approach to the payment scheduling problem. In this approach, the amount and timing of the payments made by the client and received by the contractor are determined so as to achieve an equitable solution. An equitable solution is defined as one where both the contractor and the client deviate from their respective ideal solutions by an equal percentage. The ideal solutions for the contractor and the client result from having a lump sum payment at the start and end of the project, respectively. A double-loop genetic algorithm (GA) is proposed to solve for an equitable solution. The outer loop represents the client and the inner loop the contractor. The inner loop corresponds to a multi-mode resource-constrained project scheduling problem (RCPSP) with the objective of maximizing the contractor's net present value (NPV) for a given payment distribution. When searching for an equitable solution, information flows between the outer and inner loops regarding the payment distribution over the event nodes and the timing of these payments. An example problem is solved and analyzed. A set of 93 problems from the literature are solved and some computational results are reported.
---
paper_title: Maximizing the Net Present Value of a Project Under Resource Constraints Using a Lagrangian Relaxation Based Heuristic with Tight Upper Bounds

paper_content:

Resource-constrained project scheduling under a net present value objective attracts growing interest. Because this is an NP-hard problem, it is unlikely that optimum solutions can be computed for large instances within reasonable computation time. Thus, heuristics have become a popular research field. Up to now, however, upper bounds are not well researched. Therefore, most researchers evaluate their heuristics on the basis of a best known lower bound, but it is unclear how good the performance really is. With this contribution we close this gap and derive tight upper bounds on the basis of a Lagrangian relaxation of the resource constraints. We also use this approach as a basis for a heuristic and show that our heuristic as well as the cash flow weight heuristic proposed by Baroum and Patterson yield solutions very close to the optimum result. Furthermore, we discuss the proper choice of a test-bed and emphasize that discount rates must be carefully chosen to give realistic instances.
---
paper_title: On Maximizing the Net Present Value of a Project Under Renewable Resource Constraints

paper_content:

In this paper we study the resource-constrained project-scheduling problem with discounted cash flows. Each activity of this resource-constrained project-scheduling problem has certain resource requirements and a known deterministic cash flow that can be either positive or negative. Deterministic cash flows are assumed to occur over the duration of the activities. Progress payments and cash outflows occur at the completion of activities. The objective is to schedule the activities subject to a fixed deadline to maximize the net present value subject to the precedence and resource constraints. With these features the financial aspects of project management are taken into account.We introduce a depth-first branch-and-bound algorithm that makes use of extra precedence relations to resolve a number of resource conflicts and a fast recursive search algorithm for the max- npv problem to compute upper bounds. The recursive search algorithm exploits the idea that positive cash flows should be scheduled as early as possible while negative cash flows should be scheduled as late as possible within the precedence constraints. The procedure has been coded in Visual C++, Version 4.0 under Windows NT, and has been validated on two problem sets.
---
paper_title: Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints

paper_content:

Abstract This paper deals with resource-constrained project scheduling problems with nonregular objective functions where general temporal constraints given by minimum and maximum time lags between activities are prescribed. In particular, resource leveling and net present value problems are studied. We present different heuristic and exact procedures for (approximately) solving those problems. A detailed experimental performance analysis shows that these procedures also solve large problem instances in reasonable computing time.
---
paper_title: Knowledge integration using problem spaces: A study in resource-constrained project scheduling

paper_content:

The need to develop schedules for projects with resource constraints and cash flows arises in organizational settings ranging from construction planning to research and development. Given the intractable nature of the problem, a variety of knowledge sources relevant to the project scheduling task have been identified in the Operations Management literature. These include a large number of heuristic procedures that can be used to generate feasible project schedules as well as recent neural network-based approaches that can select appropriate heuristic procedures to apply to a specific instance of the project scheduling problem. While integrated application of these knowledge sources is required to effectively support scheduling, previous work has focussed on developing and implementing them in isolation. The problem space computational model presented in this paper addresses this shortcoming by integrating these various knowledge sources, thus enabling the development of decision support systems for resource constrained project scheduling. More generally, the modeling approach used in this paper can be applied to create systems to assist knowledge intensive tasks that arise in many organizational settings.
---
paper_title: Lagrangian heuristics for scheduling new product development projects in the pharmaceutical industry

paper_content:

To stay ahead of their competition, pharmaceutical firms must make effective use of their new product development (NPD) capabilities by efficiently allocating its analytical, clinical testing and manufacturing resources across various drug development projects. The resulting project scheduling problems involve coordinating hundreds of testing and manufacturing activities over a period of several quarters. Most conventional integer programming approaches are computationally impractical for problems of this size, while priority rule-driven heuristics seldom provide consistent solution quality. We propose a Lagrangian decomposition (LD) heuristic that exploits the special structure of these problems. Some resources (typically manpower) are shared across all on-going projects while others (typically equipment) are specific to individual project categories. Our objective function is a weighted discounted cost expressed in terms of activity completion times. The LD heuristics were subjected to a comprehensive experimental study based on typical operational instances. While the conventional "Reward---Risk" priority rule heuristic generates duality gaps between 47---58%, the best LD heuristic achieves duality gaps between 10---20%. The LD heuristics also yield makespan reductions of over 30% over the Reward---Risk priority rule.
---
paper_title: Scheduling a Project to Maximize Its Present Value: A Zero-One Programming Approach

paper_content:

A zero-one integer programming formulation of the project scheduling problem is reported which maximizes the discounted value of cash flows in a project when progress payments and cash outflows are made upon the completion of certain activities. While this problem has been treated previously, it has not been addressed in a manner which allows for the type of constraints treated in this paper. And while cash can be treated as any other resource in the noncash flow, resource-constrained version of this problem, the effects of cash inflows and outflows and the time sequencing alternatives for them allow for a different treatment of cash resources than has been previously reported.
---
paper_title: The resource constrained time/cost tradeoff project scheduling problem with discounted cash flows

paper_content:

Many of the recent studies on Project Scheduling focus on maximizing the Net Present Value (NPV) of cash flows that occur during the implementation of a project in the presence of precedence and resource constraints. The literature contains several integer programming formulations, heuristic procedures and their implementations. In most of these formulations, activity durations are assumed to be fixed. In this paper, we study a practical extension of the problem where the activity durations can be reduced from their normal durations by allocating more resources. Costs associated with such reductions are referred to as crashing costs. The problem under consideration involves determining the timing and duration of activities such that the NPV of all cash flows is maximized in the presence of precedence and resource constraints. We suggest a heuristic procedure for obtaining “good” feasible solutions. We compare the performance of three priority rules embedded in the proposed procedure. Two of these priority rules have been shown to be the most effective in the literature, the third is a new rule developed in this paper. Extensive computational experiments with the heuristic procedure on a total of 380 test problems are reported. The heuristic solutions are compared to benchmark solutions obtained from the best of 50-randomly generated solutions for each test problem. In addition, upper bounds on the optimal values are obtained by performing Subgradient optimization on a Lagrangian Relaxation of the problem. These upper bounds are used to assess the quality of the heuristic solutions. In general, none of the priority rules produced consistently better results for all the test problems. However, all three priority rules provide “good” quality solutions with modest computational effort. The Lagrangian approach is found to provide tight bounds on the optimal values.
---
paper_title: Scheduling projects to maximize net present value -- the case of time-dependent, contingent cash flows

paper_content:

Abstract The problem of scheduling activities in a project to maximize its Net Present Value (NPV) has been solved for the case where net cash flow magnitudes are independent of the time of realization. This paper models a more realistic version of this problem — because of incentive payments and penalties for early and late event occurrences, respectively, and because of changing costs of resources over time, net cash flow magnitudes are dependent on the time of realization. We formulate an optimization program for this more general problem and present a simulated annealing solution approach. We test different implementation strategies for this algorithm and suggest a method for choosing neighborhood moves. We compare the NPVs of the solutions obtained from our formulation with the NPVs of early start schedules and with late start schedules for 168 different problems. These computational results show that the simulated annealing approach consistently produces substantially better solutions than the early start or late start schedules. Even poor simulated annealing neighborhood moves give improved solutions for most problems studied.
---
paper_title: An efficient search procedure for the resource-constrained multi-project scheduling problem with discounted cash flows

paper_content:

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.
---
paper_title: A genetic algorithm for resource investment problem with discounted cash flows

paper_content:

A resource investment problem with discounted cash flows is a project scheduling problem in which the availability levels of the resources are considered decision variables and the goal is to find a schedule and resource requirement levels such that the net present value of the project cash flows optimizes. In this paper, we present a genetic algorithm to solve this problem. We explain the elements of the algorithm such as chromosome structure, fitness function, crossover, mutation, and local improvement operations and solve more than 220 problems with known optimal solutions to evaluate the performance of the proposed algorithm. The results of the experimentation are quite satisfactory.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: Simulated annealing and tabu search for multi-mode resource-constrained project scheduling with positive discounted cash flows and different payment models

paper_content:

In this paper the multi-mode resource-constrained project scheduling problem with discounted cash flows is considered. A project is represented by an activity-on-node (AoN) network. A positive cash flow is associated with each activity. Four different payment models are considered: lump-sum payment at the completion of the project, payments at activities' completion times, payments at equal time intervals and progress payments. The objective is to maximize the net present value of all cash flows of the project. Local search metaheuristics: simulated annealing and tabu search are proposed to solve this strongly NP-hard problem. A comprehensive computational experiment is described, performed on a set of instances based on standard test problems constructed by the ProGen project generator, where, additionally, the activities' cash flows are generated randomly with the uniform distribution. The metaheuristics are computationally compared, the results are analyzed and discussed and some conclusions are given.
---
paper_title: Maximizing the net present value of a project with linear time-dependent cash flows

paper_content:

The paper studies the unconstrained project-scheduling problem with discounted cash flows where the cash flow functions are assumed to be linear-dependent on the completion times of the corresponding activities. Each activity of this unconstrained project-scheduling problem has a known deterministic cash flow function that is linear and non-increasing in time. Progress payments and cash outflows occur at the completion times of activities. The objective is to schedule the activities in order to maximize the net present value (npv) subject to the precedence constraints and a fixed deadline. Despite the growing amount of research concerning the financial aspects in project scheduling, little research has been done on the problem with time-dependent cash flow functions. Nevertheless, this problem gives an incentive to solve more realistic versions of project-scheduling problems with financial objectives. We introduce an extension of an exact recursive algorithm that has been used in solving the max-npv probl...
---
paper_title: Discrete-continuous project scheduling with discounted cash flows-A tabu search approach

paper_content:

In this paper discrete-continuous project scheduling problems with discounted cash flows are considered. In discrete-continuous project scheduling activities require for their processing discrete and continuous resources. The processing rate of an activity depends on the amount of the continuous resource allotted to this activity at a time. A positive cash flow is associated with each activity. Two common payment models-lump-sum payment and payments at activities' completion times-are considered. The objective is the maximization of the net present value of all cash flows of the project. Some properties of optimal schedules are discussed, and the formulation of a mathematical programming problem for an optimal continuous resource allocation is presented. Applications of a local search metaheuristic-tabu search, as well as simple search methods-multi-start iterative improvement and random sampling are described. The algorithms are compared on the basis of a computational experiment, the results are analyzed and discussed. Some conclusions as well as directions for further research are given.
---
paper_title: A Branch and Bound Procedure for the Resource Constrained Project Scheduling Problem with Discounted Cash Flows

paper_content:

Management of projects is complicated by the scarcity of resources required to execute them. Limited resources usually extend the project completion times beyond those determined by CPM/PERT. Several solution procedures have been developed for solving the resource constrained project scheduling problem. One objective commonly used for these problems is to complete the project as early as possible (minimize makespan). The problem considered in this paper is a resource constrained project scheduling problem, with the added features that there are cash flows associated with the project activities, and the objective is to schedule the project activities in such a way that the net present value of cash flows is maximized. With these features the problem becomes financially motivated and more realistic. We introduce a branch and bound procedure to solve the resource constrained project scheduling problem with discounted cash flows. Our procedure exploits the known fact that potential resource violations can be eliminated by introducing additional precedence relations between certain project activities. Specifically, we use the "minimal delaying alternatives" concept to resolve resource conflicts. The bounds in the branch and bound procedure are computed by solving Payment Scheduling Problems, which can be formulated as linear programs and by that are well-solvable. We test our procedure computationally on a set of 90 test problems from the literature and compare it with the only other exact procedure we know of.
---
paper_title: On modelling payments in projects

paper_content:

Projects are often evaluated on financial performance. The net present value (NPV) has long been established as a highly relevant criterion in the management and control of projects. Research in this area has emphasised scheduling of activities in projects to maximise the contractor's NPV assuming that cash flows (both positive and negative) that occur over the duration of the project are known. In practice, however, the contractor usually knows the expenses associated with project activities. He can use this information combined with the knowledge of other project parameters such as activity durations to negotiate the payments received for completed work so that the project achieves the maximum level of financial returns. Extending previous research, this paper examines the problem of simultaneously determining the amount, location and timing of progress payments. We present several models and their solutions for an example problem. Based on the assumptions made, the models are applicable in different project environments. The problem and models presented here can be used by the contractor and client for managing cash flows, setting milestones, and negotiating critical contract parameters, in addition to identifying the location, timing, and amount of progress payments. They also contribute to the body of research on formulating and solving difficult combinatorial optimisation problems.
---
paper_title: A heuristic treatment of tardiness and net present value criteria in resource constrained project scheduling

paper_content:

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.
---
paper_title: Progress payments in project scheduling problems

paper_content:

Abstract In this paper we study the unconstrained project scheduling problem with discounted cash flows where the net cash flows are assumed to be dependent on the completion times of the corresponding activities. Cash outflows occur when an activity is completed whereas cash inflows are incurred as progress payments at the end of some time period. The objective is to schedule the activities in order to maximize the net present value of the project subject to the precedence constraints and a fixed deadline. This paper extends the ever-growing amount of research concerning the financial aspects in project scheduling in which cash flows are time-dependent. We introduce a branch-and-bound algorithm which computes upper bounds by making piecewise linear overestimations. In doing so, the algorithm transforms the problem into a weighted earliness–tardiness project scheduling problem. The algorithm is extended with two new rules in order to reduce the size of the branch-and-bound tree. Computational results are reported.
---
paper_title: Hybrid flow shop scheduling as a multi-mode multi-project scheduling problem with batching requirements: A real-world application

paper_content:

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.
---
paper_title: Interactive analysis of multiple-criteria project scheduling problems

paper_content:

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.
---
paper_title: Knowledge-based Multiobjective Project Scheduling Problems

paper_content:

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.
---
paper_title: DSS for multiobjective project scheduling

paper_content:

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.
---
paper_title: Nature-inspired metaheuristics for multiobjective activity crashing

paper_content:

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.
---
paper_title: Resource-constrained project scheduling : Notation, classification, models, and methods

paper_content:

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.
---
paper_title: Resource constrained project scheduling with multiple objectives: a decision support approach

paper_content:

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.
---
paper_title: Using metaheuristics in multiobjective resource constrained project scheduling

paper_content:

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.
---
paper_title: A model, heuristic procedure and decision support system for solving the movie shoot scheduling problem

paper_content:

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.
---
paper_title: Resource-constrained project scheduling with renewable and non-renewable resources and time-resource tradeoffs

paper_content:

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.
---
paper_title: A bi-objective model for robust resource-constrained project scheduling

paper_content:

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.
---
paper_title: Multi-project scheduling using an heuristic and a genetic algorithm

paper_content:

Managing multiple projects is a complex task. It involves the integration of varieties of resources and schedules. The researchers have proposed many tools and techniques for single project scheduling. Mathematical programming and heuristics are limited in application. In recent years non-traditional techniques are attempted for scheduling. This paper proposes the use of a heuristic and a genetic algorithm for scheduling a multi-project environment with an objective to minimize the makespan of the projects. The proposed method is validated with numerical examples and is found competent.
---
paper_title: Managing and modelling general resource transfers in ( multi-) project scheduling

paper_content:

Most approaches to multi-project scheduling are based on the assumption that resources can be transferred between projects without any expense in time and cost. As this assumption often is not realistic, we generalise the multi-project scheduling problem (RCMPSP) by additionally including transfer times and cost. To integrate this aspect, in a first step, we develop a framework for considering resource transfers in single and multi-project environments. It includes managerial approaches to handle resource transfers, a classification of resource transfer types and new roles that resources can take in these transfers. Afterwards, we define the multi-project scheduling problem with transfer times (RCMPSPTT) and formulate it in a basic and an extended version as integer linear programmes. Eventually, it is supplemented for the first time by cost considerations and introduced as resource constrained multi-project scheduling problem with transfer times and cost (RCMPSPTTC). Computational experiments compare the presented managerial approaches and prove the necessity of explicitly considering transfer times in project scheduling. Moreover, the experiments evaluate the presented MIP models and show that specialised solution procedures are vital.
---
paper_title: Project scheduling - Theory and practice

paper_content:

The project scheduling problem involves the scheduling of project activities subject to precedence and/or resource constraints. Of obvious practical importance, it has been the subject of intensive research since the late fifties. A wide variety of commercialized project management software packages have been put to practical use. Despite all these efforts, numerous reports reveal that many projects escalate in time and budget and that many project scheduling procedures have not yet found their way to practical use. The objective of this paper is to confront project scheduling theory with project scheduling practice. We provide a generic hierarchical project planning and control framework that serves to position the various project planning procedures and discuss important research opportunities, the exploration of which may help to close the theory-practice gap.
---
paper_title: A market-based multi-agent system model for decentralized multi-project scheduling

paper_content:

We consider a multi-project scheduling problem, where each project is composed of a set of activities, with precedence relations, requiring specific amounts of local and shared (among projects) resources. The aim is to complete all the project activities, satisfying precedence and resource constraints, and minimizing each project schedule length. The decision making process is supposed to be decentralized, with as many local decision makers as the projects. A multi-agent system model, and an iterative combinatorial auction mechanism for the agent coordination are proposed. We provide a dynamic programming formulation for the combinatorial auction problem, and heuristic algorithms for both the combinatorial auction and the bidding process. An experimental analysis on the whole multi-agent system model is discussed.
---
paper_title: Multiproject Scheduling with Limited Resources: A Zero-One Programming Approach

paper_content:

A zero-one 0-1 linear programming formulation of multiproject and job-shop scheduling problems is presented that is more general and computationally tractable than other known formulations. It can accommodate a wide range of real-world situations including multiple resource constraints, due dates, job splitting, resource, substitutability, and concurrency and nonconcurrency of job performance requirements. Three possible objective functions are discussed; minimizing total throughput time for all projects: minimizing the time by which all projects are completed i.e., minimizing makespan; and minimizing total lateness or lateness penalty for all projects.
---
paper_title: A MULTICRITERIA HEURISTIC METHOD TO IMPROVE RESOURCE ALLOCATION IN MULTIPROJECT SCHEDULING

paper_content:

Abstract Many works published in the area of project management make reference to the scheduling of single projects and time objectives like minimising project duration. Nevertheless, frequently companies manage various projects which share a pool of constrained resources, taking into account other objectives in addition to time. In order to add flexibility in using project scheduling tools, we have developed a multicriteria heuristic that improves lexicographicly two criteria: one time type – mean project delay or multiproject duration increase – and one no time type – project splitting, in-process inventory, resource levelling or idle resources – that can be chosen by the user. The multicriteria heuristic algorithm consists of several algorithms based on the improvement of multiproject feasible schedules. Through an extensive computational study, we have shown that this method improves the feasible multiproject schedule obtained from heuristic methods based on the priority rules coded Maximum Total Work Content (MAXTWK) and Minimum Latest Finish Time (MINLFT) as well as project management software – Microsoft Project, CA-SuperProject, Time Line and Project Scheduler.
---
paper_title: Multi-Project Scheduling: Categorization of Heuristic Rules Performance

paper_content:

Application of heuristic solution procedures to the practical problem of project scheduling has previously been studied by numerous researchers. However, there is little consensus about their findings, and the practicing manager is currently at a loss as to which scheduling rule to use. Furthermore, since no categorization process was developed, it is assumed that once a rule is selected it must be used throughout the whole project. This research breaks away from this tradition by providing a categorization process based on two powerful project summary measures. The first measure identifies the location of the peak of total resource requirements and the second measure identifies the rate of utilization of each resource type. The performance of the rules are classified according to values of these two measures, and it is shown that a rule introduced by this research performs significantly better on most categories of projects.
---
paper_title: An efficient search procedure for the resource-constrained multi-project scheduling problem with discounted cash flows

paper_content:

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.
---
paper_title: A multi‐agent system for the decentralized resource‐constrained multi‐project scheduling problem

paper_content:

A restart evolution strategy (RES) for the resource-constrained project scheduling problem (RCPSP), as well as its integration in a multi-agent system (MAS) for solving the decentralized resource-constrained multi-project scheduling problem (DRCMPSP) will be presented. To evaluate the developed approach, problem instances of the RCPSP taken from the literature with up to 300 activities are used, as well as 80 generated instances of the DRCMPSP, with up to 20 projects and with up to 120 activities each. For 73 instances of the RCPSP, the RES found better solutions than the best ones found so far. In addition, the MAS is suitable for solving large multi-project instances decentrally. The results for the DRCMPSP instances show that the presented decentralized MAS is competitive with a central solution approach.
---
paper_title: Multiproject scheduling: Analysis of scheduling strategies under unequal delay penalties

paper_content:

Abstract The multiproject scheduling problem is investigated under the assumption that delays corresponding to different projects carry different penalties. Five penalty functions are introduced that simulate typical business behavior. These are: 1) assigning the highest penalty to the project requiring the greatest amount of resources; 2) assigning the highest priority to the longest project; 3) assigning the highest priority to the project requiring the least amount of resources; 4) assigning the highest priority to the shortest project; and 5) random assignment. Justification for each case is provided. Two powerful project summary measures were used to generate the test problems. The first measure, average resource load factor (ARLF), identifies whether the location of the peak requirement of all (i.e., combined) resources is in the first or second half of the project's critical path. If each resource is expressed in terms of dollars, then ARLF identifies the location of the peak cash requirement. Since in practice the choice of the scheduling strategy is influenced by the location of the peak cash requirement, performance of the scheduling strategies is analyzed with respect to values of this measure. The second measure, average utilization factor (AUF), calculates the ratio of resource requirements to availabilities. It is shown that problems tested must have different AUF values in order to be classified different for purposes of experimental design. Thus a factorial model of the form, y = Strategy + Penalty + ARLF + AUF + ϵ was used to generate 385 problems, each requiring 2 to 4 resources, containing 3 to 5 projects and 34 to 63 activities. The computer program used in the study is based on a parallel method of scheduling in which priorities of the activities are determined when the activity is considered for scheduling. Ten scheduling strategies are tested. Some important ones are: 1) to schedule the shortest activity first; 2) to schedule the activity with minimum slack first; 3) to schedule the activity with maximum work content first (i.e., from the project with highest work content); 4) to schedule the shortest activity from the shortest project first; and 5) to schedule the activity with maximum penalty first. Shortest activity first and minimum slack first are popular strategies introduced by other researchers. Using number of times ranked first as our criterion, scheduling the activity with maximum penalty first provides the best results followed by the strategy of scheduling the activity with maximum work content. But when these results are analyzed with respect to existence of a very expensive project (i.e., dominance) in the problem, performance of the maximum penalty strategy improves. When the overall results are analyzed with respect to values of ARLF, a different picture emerges. Then the strategy of scheduling the activity with the highest penalty first provides the best results if the peak requirement is early. When the peak requirement is toward the middle of a project's unconstrained critical path, scheduling the activity with the highest work content provides the best results. When the peak requirement is late in a project's life, scheduling the shortest activity from the shortest project is the best strategy to adopt. These findings were tested for statistical significance by using nonparametric testing procedures and were found to be significant.
---
paper_title: Resource-Constrained Multi-Project Scheduling: Priority Rule Performance Revisited

paper_content:

Managers of multiple projects with overly constrained resources face difficult decisions in how to allocate resources to minimize the average delay per project or the time to complete the whole set of projects. We address the static resource-constrained multi-project scheduling problem (RCMPSP) with two lateness objectives, project lateness and portfolio lateness. In this context, past research has reported conflicting results on the performance of activity priority rule heuristics and does not provide managers with clear guidance on which rule to use in various situations. Using recently improved measures for RCMPSP characteristics, we conducted a comprehensive analysis of 20 priority rules on 12,320 test problems generated to the specifications of project-, activity-, and resource-related characteristics--including network complexity and resource distribution and contention. We found several situations in which widely advocated priority rules perform poorly. We also confirmed that portfolio managers and project managers will prefer different priority rules depending on their local or global objectives. We summarize our results in two decision tables, the practical use of which requires managers to do only a rough, qualitative characterization of their projects in terms of complexity, degree of resource contention, and resource distribution.
---
paper_title: A 0–1 goal programming model for scheduling multiple maintenance projects at a copper mine

paper_content:

Abstract This paper describes the application of 0–1 goal programming (GP) in multi-project resource-constrained scheduling for the maintenance of mineral-processing equipment at a copper mine in China. This involves four projects, 40 jobs and nine types of resources. We first develop a generalized 0–1 GP model. Because of the limited computing capacity at the mine, an effective two-phase hybrid solution approach is then proposed. In Phase I, under resource constraints, a feasible schedule is obtained by a heuristic. Based on this feasible schedule and a model-simplification procedure, many decision variables in the generalized model are eliminated and redundant constraints are removed. (Although this procedure is particularly designed for this mine, we also discuss its extension to general problems.) In Phase II, the streamlined model is solved by implicit enumeration. This approach eliminates 90% of the variables and 96% of the constraints in the problem we studied. We are thus able to solve a multi-project scheduling problem of medium size on a PC. In comparison with the heuristic method that the mine was using, our hybrid approach reduced project duration by 13%, total project cost by 30%, cost for the critical project by 15%, and overall workload by 59%.
---
paper_title: Resource-constrained multi-project scheduling with tardy costs: Comparing myopic, bottleneck, and resource pricing heuristics

paper_content:

Abstract This paper addresses the problem of scheduling multiple resource-constrained projects with the objective of minimizing weighted tardiness costs. Extending our earlier heuristic scheduling work for production shops, we develop an efficient and effective means of generating low cost schedules for multiple projects requiring multiple resources. A ‘cost-benefit’ scheduling policy with resource pricing is developed which balances the marginal cost of delaying the start of an eligible activity with the marginal benefit of such a delay. A central part of this policy is the heuristic estimation of implicit resource prices, which form the basis for calculating marginal delay costs. The resulting policies are tested against a number of dispatch scheduling rules taken from the project scheduling literature, and against several new scheduling rules, with encouraging results for both the weighted tardiness problem and for the special case of weighted project delay.
---
paper_title: Selection and Scheduling of Pharmaceutical Research Projects

paper_content:

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.
---
paper_title: Project selection, scheduling and resource allocation with time dependent returns

paper_content:

In this paper we formulate and analyze the joint problem of project selection and task scheduling. We study the situation where a manager has many alternative projects to pursue such as developing new product platforms or technologies, incremental product upgrades, or continuing education of human resources. Project return is assumed to be a known function of project completion time. Resources are limited and renewable. The objective is to maximize present worth of profit. A general mathematical formulation that can address several versions of the problem is presented. An implicit enumeration procedure is then developed and tested to provide good solutions based on project ordering and a prioritization rule for resource allocation. The algorithm uses an imbedded module for solving the resource-constrained project scheduling problem at each stage. The importance of integrating the impact of resource constraints into the selection of projects is demonstrated.
---
paper_title: WORK CONTINUITY CONSTRAINTS IN PROJECT SCHEDULING

paper_content:

Repetitive projects involve the repetition of activities along the stages of the project. Since the resources required to perform these activities move from one stage to the other, a main objective of scheduling these projects is to maintain the continuity of work of these resources so as to minimize the idle time of resources. This requirement, often referred to as work continuity constraints, involves a tradeoff between total project duration and the resource idle time. The contribution of this paper is threefold. First, we provide an extensive literature summary of the topic under study. Although most research papers deal with the scheduling of construction projects, we show that this can be extended to many other environments. Second, we propose an exact search procedure for scheduling repetitive projects with work continuity constraints. This algorithm iteratively shifts repeating activities further in time in order to decrease the resource idle time. We have embedded this recursive search procedure in a horizon-varying algorithm in order to detect the complete tradeoff profile between resource idle time and project duration. The procedure has been coded in Visual C++ and has been validated on a randomly generated problem set. Finally, we illustrate the concepts on three examples. First, the use of our new algorithm is illustrated on a small fictive problem example from literature. In a second example, we show that work continuity constraints involve a tradeoff between total project duration and the resource idle time. A last example describes the scheduling of a well-known real-life project that aims at the construction of a tunnel at the Westerschelde in The Netherlands.
---
paper_title: Integrated Scheduling, Assembly Area- and Part-Assignment for Large Scale, Make-to-Order Assemblies

paper_content:

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.
---
paper_title: Scheduling and staffing multiple projects with a multi-skilled workforce

paper_content:

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.
---
paper_title: Analysis of supplier buyer relationships using resource constrained project scheduling strategies

paper_content:

Abstract Many studies in the product development literature discuss the benefits of partnering with suppliers. In these partnership relations buyers and suppliers establish long term, co-operative relationships during Product Development Projects (PDP) in order to reduce product development time and improve project performance. Traditional contractual approaches, on the other hand, where buyers work independently of suppliers and lack control over suppliers' resources, are commonly blamed for delays in the development time. This study constitutes of an initial effort to model and investigate these relationships analytically. The impact of scheduling strategies, the number of suppliers, and resource availability on PDP completion time is evaluated under contractual or partnership arrangement. Contractual relationships seem to provide a good or even better development times than the ones provided by the partnership approach.
---
paper_title: Scheduling programs with repetitive projects: A comparison of a simulated annealing, a genetic and a pair-wise swap algorithm

paper_content:

Abstract We address the problem of scheduling in programs involving the production of multiple units of the same product. Our study was motivated by a construction program for fast naval patrol boats. Other applications of this problem include procurement of multiple copies of aircraft, spacecraft, and weapon systems. In this problem we must decide how many units of the product to assign to each of a number of available crews (individuals, teams, subcontractors, etc.). These types of problems are characterized by two potentially conflicting considerations: 1) the need to complete each unit by its contractual due date, and 2) learning effects. Because of the first consideration, there is a tendency to use multiple crews for simultaneous production, so that meeting due dates is assured. However, the second consideration encourages assigning many units to a single crew so that learning effects are maximized. We study this scheduling problem with two different penalty cost structures and develop models for both versions. The models trade-off the penalty associated with late deliveries and the savings due to learning (and possibly incentive payments for early completion). We discuss different heuristic algorithms — simulated annealing, a genetic algorithm, and a pair-wise swap heuristic — as well as an exhaustive search to determine a baseline for comparisons. Our computational results show that the pair-wise swap algorithm is the most efficient solution procedure for these models.
---
paper_title: An evaluation of the adequacy of project network generators with systematically sampled networks

paper_content:

This paper evaluates and compares different network generators to generate project scheduling problem instances based on indicators measuring the topological network structure. We review six topological network indicators in order to describe the detailed structure of a project network. These indicators were originally developed by [L.V. Tavares, J.A. Ferreira and J.S. Coelho, The risk of delay of a project in terms of the morphology of its network, European Journal of Operational Research 119 (1999), 510–537] and have been modified, or sometimes completely replaced, by alternative indicators to describe the network topology. The contribution of this paper is twofold. Firstly, we generate a large amount of different networks with four project network generators. Our general conclusions are that none of the network generators are able to capture the complete feasible domain of all networks. Additionally, each network generator covers its own network-specific domain and, consequently, contributes to the generation of data sets. Secondly, we perform computational results on the well-known resource-constrained project scheduling problem to prove that our indicators are reliable and have significant, predictive power to serve as complexity indicators.
---
paper_title: Benchmark Instances for Project Scheduling Problems

paper_content:

With the development of project scheduling models and methods arose the need for data instances in order to benchmark the solution procedures. Generally, benchmark instances can be distinguished by their origin into real world problems and artificial problems. The analysis of algorithmic performance on real world problem instances is of a high practical relevance, but at the same time it is only an analysis of individual cases. Consequently, general conclusions about the algorithms cannot be drawn. A solution procedure which shows very good performance on one real world instance might produce poor results on another. In order to allow a systematic evaluation of the performance of algorithms, characteristics of the projects have to be identified. The characteristics can then serve as the parameters for the systematic generation of artificial instances. The variation of the levels of these problem parameters in a full factorial design study allows to produce a set of well-balanced instances (cf. Montgomery 1976).
---
paper_title: ProGen/πx – An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions

paper_content:

Abstract Project scheduling has long been an area of intensive research, but until recently most efforts have been dedicated to developing solution procedures and generalizing models, with little work done on generating problem instances. Additionally, if labor time regulations have to be taken into consideration, the classical resource-constrained project scheduling problem (RCPSP) cannot be used for many problems in manpower scheduling. This paper introduces several extensions to the RCPSP aimed at modeling such problems, and a problem instance generator based on the project generator ProGen incorporating these extensions. Thus, it becomes possible to thoroughly test solution procedures for, e.g., audit-staff scheduling, crew scheduling and timetabling problems. Preliminary computational results are given that were obtained with a greedy randomized solution method using priority rules specifically tailored to the generalized model.
---
paper_title: dagen: A generator of testsets for project activity nets

paper_content:

Abstract We offer a methodology, and the relevant software, to generate source-terminal directed project nets of specified number of nodes, number of activities, complexity index, and ranges of costs and resources utilization.
---
paper_title: RanGen: A Random Network Generator for Activity-on-the-Node Networks

paper_content:

In this paper, we describe RanGen, a random network generator for generating activity-on-the-node networks and accompanying data for different classes of project scheduling problems. The objective is to construct random networks which satisfy preset values of the parameters used to control the hardness of a problem instance. Both parameters which are related to the network topology and resource-related parameters are implemented. The network generator meets the shortcomings of former network generators since it employs a wide range of different parameters which have been shown to serve as possible predictors of the hardness of different project scheduling problems. Some of them have been implemented in former network generators while others have not.
---
paper_title: Scheduling projects with heterogeneous resources to meet time and quality objectives

paper_content:

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.
---
paper_title: Integrated Scheduling, Assembly Area- and Part-Assignment for Large Scale, Make-to-Order Assemblies

paper_content:

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.
---
paper_title: Hybrid flow shop scheduling as a multi-mode multi-project scheduling problem with batching requirements: A real-world application

paper_content:

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.
---
paper_title: Selection and Scheduling of Pharmaceutical Research Projects

paper_content:

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.
---
paper_title: Scheduling and staffing multiple projects with a multi-skilled workforce

paper_content:

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.
---
paper_title: Multi-level capacitated lot-sizing and resource constrained project scheduling : an integrating perspective

paper_content:

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.
---
paper_title: The Course Scheduling Problem at Lufthansa Technical Training

paper_content:

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.
---
paper_title: Distribution requirements and compactness constraints in school timetabling

paper_content:

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.
---
paper_title: Scheduling an r&d project with quality-dependent time slots

paper_content:

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.
---
paper_title: Resource-Constrained Project Scheduling: Exact Methods for the Multi-Mode Case

paper_content:

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.
---
paper_title: Packing problems and project scheduling models: An integrated perspective

paper_content:

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.
---
paper_title: Resource-constrained project scheduling and timetabling

paper_content:

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.
---
paper_title: A model, heuristic procedure and decision support system for solving the movie shoot scheduling problem

paper_content:

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.
---
paper_title: Batch scheduling in process industries: an application of resource-constrained project scheduling

paper_content:

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.
---

Title: A survey of variants and extensions of the resource-constrained project scheduling problem

Section 1: Introduction
Description 1: Write an introduction to the RCPSP, including its importance, basic characteristics, and the need for variants and extensions.

Section 2: Preemptive Scheduling
Description 2: Discuss the concept of preemptive scheduling and its various forms, including activity interruption and fast tracking.

Section 3: Resource Requests Varying with Time
Description 3: Explain how resource requests can vary over time and the implications of time-dependent resource requests within RCPSP.

Section 4: Setup Times
Description 4: Describe different types of setup times required before an activity can start and their integration into RCPSP.

Section 5: Multiple Modes
Description 5: Elaborate on the multi-mode RCPSP where activities can be executed in several different modes, each with its own duration and resource requirements.

Section 6: Tradeoff Problems
Description 6: Detail tradeoff problems such as time-resource and time-cost tradeoffs in RCPSP.

Section 7: Further Activity Concepts
Description 7: Explore additional concepts related to activities in RCPSP, such as forbidden periods and continuous durations.

Section 8: Minimal Time Lags
Description 8: Discuss minimal time lags between activities and their extensions within the RCPSP framework.

Section 9: Maximal Time Lags
Description 9: Explain maximal time lags and their impact on project scheduling.

Section 10: Release Dates and Deadlines
Description 10: Review the implications of including release dates and deadlines for activities in RCPSP.

Section 11: Time-Switch Constraints
Description 11: Introduce time-switch constraints and their effect on project scheduling.

Section 12: Further Temporal Constraints
Description 12: Present additional temporal constraints such as parallelity constraints, bounding constraints, and feeding precedence constraints.

Section 13: Logical Dependencies
Description 13: Discuss logical dependencies between activities and their extensions to the precedence network concept.

Section 14: Network Representations
Description 14: Compare different ways of representing activities in network formulations, including activity-on-node and activity-on-arc networks.

Section 15: Nonrenewable and Doubly Constrained Resources
Description 15: Explain resource types like nonrenewable and doubly constrained resources within RCPSP.

Section 16: Partially Renewable Resources
Description 16: Describe partially renewable resources and their use in project scheduling.

Section 17: Cumulative Resources
Description 17: Outline the concept of cumulative resources and their applications in production scenarios.

Section 18: Continuous Resources
Description 18: Discuss the integration of continuously divisible resources into project scheduling problems.

Section 19: Dedicated Resources
Description 19: Define dedicated resources and explain their special case within RCPSP.

Section 20: Resource Capacities Varying with Time
Description 20: Present the concept of time-dependent resource capacities and their implications for RCPSP.

Section 21: Time-Based Objectives
Description 21: Review various time-based objectives in project scheduling, including makespan, lateness, tardiness, and earliness.

Section 22: Robustness-Based Objectives
Description 22: Explore objectives aimed at creating robust schedules that handle unforeseen delays.

Section 23: Objectives for Rescheduling
Description 23: Discuss objectives for rescheduling projects in response to disruptions.

Section 24: Objectives Based on Renewable Resources
Description 24: Explain objectives related to renewable resources, such as resource investment and resource leveling.

Section 25: Objectives Based on Nonrenewable Resources
Description 25: Detail objectives that minimize the consumption of nonrenewable resources.

Section 26: Objectives Based on Costs
Description 26: Review cost-based objectives including activity start-time costs and project completion costs.

Section 27: Objectives Based on the Net Present Value
Description 27: Discuss the maximization of the net present value (NPV) in project scheduling.

Section 28: Multiple Objectives
Description 28: Present multiple objectives cases, including weighted sum and Pareto-optimal schedules.

Section 29: Networks for Multiple Projects
Description 29: Describe the integration of multiple dependent projects into a single scheduling problem.

Section 30: Objectives for Multi-Project Scheduling
Description 30: Review different objectives for scheduling multiple projects, such as minimizing weighted tardiness and resource leveling.

Section 31: Project Selection and Scheduling
Description 31: Discuss problems that combine project selection with scheduling decisions.

Section 32: Further Specific Multi-Project Problems
Description 32: Outline specific multi-project scheduling problems, including fixed schedules and repeated projects.

Section 33: Test Instance Generators
Description 33: Summarize the development and use of test instance generators for various RCPSP variants.

Section 34: Conclusions
Description 34: Provide a comprehensive summary of the paper and highlight the significance of the research on RCPSP and its extensions.