Handbook on Project Management and Scheduling Vol.1

Schedule generation schemes are the backbone of heuristics to solve project scheduling problems. In this chapter we introduce the two schedule generation schemes for the classical resource constrained project scheduling problem, the serial and the parallel schedule generation scheme. We characterize them according to the types of schedule they generate and discuss variants of the schedule generation schemes in order to deal with extensions such as general precedence constraints and stochastic activity durations.

In this chapter, (mixed-)integer linear programming formulations of the resource-constrained project scheduling problem are presented. Standard formulations from the literature and newly proposed formulations are classified according to their size in function of the input data. According to this classification, compact models (of polynomial size), pseudo-polynomial sized models, and formulations of exponential size are presented. A theoretical and experimental comparison of these formulations is then given. The complementarity of the formulations for different usages is finally discussed and directions for future work, such as hybridization with other methods, are given.

In this chapter methods to calculate lower bounds on the minimum project duration (i.e. the makespan C _max ) of the basic resource-constrained project scheduling problem \(\mathit{PS}\,\mid \,\mathit{prec}\,\mid \,C_{\mathit{max}}\) are presented. We distinguish between constructive and destructive lower bounds.

Given the \(\mathcal{N}\!\mathcal{P}\)-hard nature of the Resource Constrained Project Scheduling Problem (RCPSP), obtaining an optimal solution for larger instances of the problem becomes computationally intractable. Metaheuristic approaches are therefore commonly used to provide near-optimal solutions for larger instances of the problem. Over the past two decades, a number of different metaheuristic approaches have been proposed and developed for combinatorial optimization problems in general and for the RCPSP in particular. In this chapter, we review the various metaheuristic approaches such as genetic algorithms, simulated annealing, tabu search, scatter search, ant colonies, the bees algorithm, neural networks etc., that have been applied to the RCPSP. One metaheuristic approach called the NeuroGenetic approach is described in more detail. The NeuroGenetic approach is a hybrid of a neural-network based approach and the genetic algorithms approach. We summarize the best results in the literature for the various metaheuristic approaches on the standard benchmark problems J30, J60, J90, and J120 from PSPLIB (Kolisch and Sprecher, Eur J Oper Res 96:205–216, 1996).

Generalized precedence relations are temporal constraints in which the starting/finishing times of a pair of activities have to be separated by at least or at most an amount of time denoted as time lag (minimum time lag and maximum time lag, respectively). This chapter is devoted to project scheduling with generalized precedence relations with and without resource constraints. Attention is focused on lower bounds and exact algorithms. In presenting existing results on these topics, we concentrate on recent results obtained by ourselves. The mathematical models and the algorithms presented here are supported by extensive computational results.

Boolean satisfiability solving is a powerful approach for testing the feasibility of propositional logic formulae in conjunctive normal form. Nowadays, Boolean satisfiability solvers efficiently handle problems with millions of clauses and hundreds of thousands of Boolean variables. But still many combinatorial problems such as resource-constrained project scheduling are beyond their capabilities. However, hybrid solution approaches have recently been proposed for resource-constrained project scheduling with generalized precedence constraints (PS | temp | C _max ) that incorporate advanced Boolean satisfiability technology such as nogood learning and conflict-driven search. In this chapter, we present a generic exact method for PS | temp | C _max using one of the most successful hybrid approaches called lazy clause generation. This approach combines constraint programming solving with Boolean satisfiability solving.

This contribution discusses an extension of the classical resource-constrained project scheduling problem (RCPSP) in which the resource requests of the activities and the resource capacities may change over time. We present relationships to other variants of the RCPSP as well as some applications of this problem setting. Subsequently, we analyze the applicability of heuristics which were originally developed for the standard RCPSP and adapt one of them, a genetic algorithm, to this extension. The chapter closes with a few computational results and some remarks on research perspectives.

This chapter looks at project scheduling problems with storage resources. Activities can produce or consume resources at their start or at their completion. We consider projects composed of events subject to precedence constraints and resource constraints. We describe briefly the exact methods of Neumann and Schwindt and of Laborie, which solve the problem when stocks of resources have to be between minimum and maximum levels. We then suppose that there are no maximum stocks. We report the shifting algorithm which solves in polynomial time the financing problem where resources are produced at given dates. We also explain how an earliest schedule corresponding to a linear order of consumption events can be built. The enumeration of linear orders then becomes sufficient for building an exact method.

In this chapter project scheduling under an additional continuous resource is considered. In particular, we deal with discrete-continuous project scheduling problems to minimize the project duration. These problems are characterized by the fact that activities of a project simultaneously require discrete and continuous resources for their execution. A class of the problems is considered, where the number of discrete resources is arbitrary, and there is one continuous, renewable resource, whose total amount available at a time is limited. Activities are nonpreemptable, and the processing rate of an activity is a continuous, increasing function of the amount of the continuous resource allotted to the activity at a time. Theoretical results for the cases of convex and concave processing rate functions of activities are presented, and the methodology developed for solving the problems with concave functions is described in detail. Some conclusions and final remarks are given.

In recent years, in the field of project scheduling 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 chapter we define this type of resource, describe an integer linear formulation and present some examples of conditions appearing in real problems which can be modeled using partially renewable resources. Then we introduce some preprocessing procedures to identify infeasible instances and to reduce the size of the feasible ones. Some exact, heuristic, and metaheuristic algorithms are also described and tested.

A fundamental assumption in the basic RCPSP is that activities in progress are non-preemptable. Some papers reveal the potential benefits of allowing activity interruptions in the schedule when the objective is the makespan minimization. In this chapter we consider the Maxnint_PRCPSP in which it is assumed that activities can be interrupted at any integer time instant with no cost incurred, that each activity can be split into a maximum number of parts, and that each part has a minimum duration established. We show how some procedures developed for the RCPSP can be adapted to work with the Maxnint_PRCPSP and we introduce some procedures specifically designed for this problem. Furthermore, precedence relationships between activities can refer to portions of work content or periods of time. In single-modal project scheduling when interruption is not allowed, both are equivalent but not when preemption is considered. We present a study of generalized work and time precedence relationships and all conversions amongst them.

In this chapter we are concerned with project scheduling problems involving preemption of activities at arbitrary points in time. We survey the literature on preemptive project scheduling and propose a classification scheme for these problems. We then consider a project scheduling problem under continuous preemption, flexible resource allocation, and generalized feeding precedence relations between the activities. After providing a formal problem statement we reduce the problem to a canonical form only containing nonpositive completion-to-start time lags and investigate structural issues like necessary feasibility conditions and preemption gains. Next, we develop an MILP formulation that encodes a schedule as a sequence of slices containing sets of activities that are simultaneously in progress. Moreover, feasibility tests, preprocessing methods, and a column-generated based lower bound on the minimum project duration are presented. Finally, we report on the results of an experimental performance analysis of the MILP model for the project duration problem.

An important variant of the resource-constrained project scheduling problem is to maximise the net present value. Significant progress has been made recently on this problem for both exact and inexact methods. The lazy clause generation based constraint programming approach is the state of the art among the exact methods and is briefly discussed. The performance of the Lagrangian relaxation based decomposition method is greatly improved when the forward-backward improvement heuristic is employed. A novel decomposition approach is designed for very large industrial problems which can make full use of the parallel computing capability of modern personal computers. Computational results are also presented to compare different approaches on both difficult benchmark problems and large industrial applications.

In this chapter, an exact method for the RACP problem is built from a combination of an RCPSP exact solver and RCPSP heuristic. In the RACP, the objective is to find the resource values that yield the least cost while finishing the project before the deadline. In the present method, the project feasibility is assessed by fixing the RACP resources and solving the underlying RCPSP with an exact algorithm. The idea is to reduce the number of RCPSP subproblems to be solved by sweeping the search space with a branching strategy that generates good bounds along the search. This approach is called the modified minimum bounding algorithm (MMBA). In the algorithm, we also employ a heuristic method in order to find an upper bound for the project cost. We fully describe the MMBA including possible alternative implementations. We also include an integer programming formulation of the RACP to be used directly or in subproblem solvers.

In this chapter, an Invasive Weed Optimization (IWO) algorithm for the resource availability cost problem is presented, in which the total cost of the (unlimited) renewable resources required to complete the project by a prespecified project deadline should be minimized. The IWO algorithm is a new search strategy, which makes use of mechanisms inspired by the natural behavior of weeds in colonizing and finding a suitable place for growth and reproduction. All algorithmic components are explained in detail and computational results for the RACP are presented. The procedure is also executed to solve the RACP with tardiness (RACPT), in which lateness of the project is permitted with a predefined penalty.

Resource leveling problems arise whenever it is expedient to reduce the fluctuations in resource utilization over time, while maintaining a prescribed project completion deadline. Several resource leveling objective functions may be defined, whose consideration results in resource profiles with desired properties, e.g., well-balanced resource profiles or profiles with a minimum number of jump discontinuities. In this chapter, we concentrate on three resource leveling problems that are known from the literature. In order to solve medium-scale instances of the considered problems, an enumeration scheme that uses problem structures is presented. Furthermore, mixed-integer (linear) programming models are introduced, and resource leveling instances are solved using CPLEX 12. In a comprehensive computational study, the performance of the described methods is analyzed.

A novel resource-leveling algorithm is presented based on entropy concepts, restating the resource-leveling heuristic known as the “Minimum Moment Method”, as an “Entropy Maximization Method” and improving on its efficiency. The proposed resource-leveling algorithm makes use of the general theory of entropy and two of its principal properties (subadditivity and maximality) to restate resource leveling as a process of maximizing the entropy found in a project’s resource histogram. Entropy in this resource-centric problem domain is defined as the ratio of allocated daily resource units over the total number of resource units to complete the project. Entropy’s subadditivity and maximality properties state that if a system consists of two subdomains having n and m components respectively, then the total system entropy is less than or equal to the sum of the subdomains’ entropy, and that the entropy is maximum when all admissible outcomes have equal probabilities of occurrence (maximal uncertainty is reached for the equiprobability distribution of possible outcomes).

Project managers carry out a project with several objectives in mind. They want to finish the project as soon as possible, with the minimum cost, the maximum quality, etc. This chapter studies project scheduling problems when several goals are sought, that is, multi-objective project scheduling problems (MOPSPs) and multi-objective resource-constrained project scheduling problems (MORCPSPs). We will discuss some of the most important issues that have to be taken into account when dealing with these problems. We will also prove some useful results that can help researchers create algorithms for some of these problems.

The aim of this chapter is to present a simplified formulation of multi-objective resource-constrained project scheduling problem based on a goal programming model. Three objectives will be explained and formulated in the context of project management, namely: the project duration, the project cost, and the quantity of the allocated resources. These objectives are incommensurable and conflicting. The proposed model will provide the baseline schedule of the best compromise based on the project manager’s preference structure.

In this chapter we present a state-of-the-art in the area of multi-mode project scheduling problems. These problems are characterized by the fact that each activity of a project can be executed in one of several modes, representing a relation between the resource requirements of the activity and its duration. In the overview we present the models and solution approaches that have been proposed in the literature across the class of multi-mode project scheduling problems up to now. Firstly we deal with the basic multi-mode resource-constrained project scheduling problems with the objective to minimize the project duration. We present the mixed-integer linear programming formulations of the problem, describe the exact approaches, the existing methods for lower bounds calculation, as well as heuristic approaches to solve the problem. Secondly, we also discuss special cases and extensions of the basic problem. Finally, we analyze multi-mode problems with other objectives, distinguishing between financial and resource-based objectives.

This chapter reports on a new solution approach for the multi-mode resource-constrained project scheduling problem (MRCPSP, MPS | prec | C _max ). This problem type aims at the selection of a single activity mode from a set of available modes in order to construct a precedence and a (renewable and nonrenewable) resource-feasible project schedule with a minimal makespan. The problem type is known to be \(\mathcal{N}\mathcal{P}\)-hard and has been solved using various exact as well as (meta-)heuristic procedures. The new algorithm splits the problem type into a mode assignment and a single mode project scheduling step. The mode assignment step is solved by a satisfiability (SAT) problem solver and returns a feasible mode selection to the project scheduling step. The project scheduling step is solved using an efficient meta-heuristic procedure from literature to solve the resource-constrained project scheduling problem (RCPSP). However, unlike many traditional meta-heuristic methods in literature to solve the MRCPSP, the new approach executes these two steps in one run, relying on a single priority list. Straightforward adaptations to the pure SAT solver by using pseudo boolean nonrenewable resource constraints has led to a high quality solution approach in a reasonable computational time. Computational results show that the procedure can report similar or sometimes even better solutions than found by other procedures in literature, although it often requires a higher CPU time.

This chapter deals with a special resource-constrained multi-mode net present value problem, i.e., the capital-constrained multi-mode project payment scheduling problem where the objective is to assign activity modes and payments so as to maximize the net present value (NPV) of the contractor under the capital constraint. With the different payment patterns adopted, four optimization models are constructed using the event-based method. Metaheuristics, including tabu search and simulated annealing, are developed and compared with other two simple heuristics based on a computational experiment performed on a data set generated randomly. The results indicate that the loop nested tabu search is the most promising procedure for the problem studied. Moreover, the effects of key parameters on the NPV are studied and the following conclusions are drawn: The NPV rises with the increase of the initial capital availability, the payment number, the payment proportion, or the project deadline; the marginal return decreases as the initial capital availability goes up; the NPVs under the milestone event based payment pattern are not less than those under the other three payment patterns.

For executing the activities of a project, one or several resources are required, which are in general scarce. Many resource-allocation methods assume that the usage of these resources by an activity is constant during execution; in practice, however, the project manager may vary resource usage by individual activities over time within prescribed bounds. This variation gives rise to the project scheduling problem which consists in allocating the scarce resources to the project activities over time such that the project duration is minimized, the total number of resource units allocated equals the prescribed work content of each activity, and precedence and various work-content-related constraints are met.

This chapter compares a priority-rule based method known from the literature against a recent MILP formulation on a benchmark test set of small-sized problem instances. Our computational results indicate that the priority-rule based method derives feasible solutions to all instances of the test set. The MILP formulation provides feasible solutions to a surprisingly large number of instances; most of these solutions are optimal or near-optimal, and on these instances the MILP formulation outperforms the priority-rule based method.

This chapter addresses modeling issues associated with project staffing and scheduling problems. Emphasis is given to mixed-integer linear programming formulations. The need for such formulations is motivated and a general modeling framework is introduced, which captures many features that have been considered in the literature on project staffing and scheduling problems. The use of the general framework is then exemplified using two problems that have been addressed in the literature. Several model enhancements and preprocessing procedures are discussed.

This chapter introduces a procedure to solve the Multi-Skill Project Scheduling Problem. The problem combines both the classical Resource-Constrained Project Scheduling Problem and the multi-purpose machine model. The aim is to find a schedule that minimizes the completion time (makespan) of a project composed of a set of activities. Precedence relations and resources constraints are considered. In this problem, resources are staff members that master several skills. Thus, a given number of workers must be assigned to perform each skill required by an activity. Practical applications include the construction of buildings, as well as production and software development planning. We present an approach that integrates the utilization of Lagrangian relaxation and column generation for obtaining strong makespan lower bounds. Finally, we present the corresponding obtained results.

Staffing projects often requires both assignment and scheduling decisions to be made, which leads to a computationally demanding large-scale optimization problem. In this chapter, we show that a general class of assignment-type resource-constrained project scheduling problems (RCPSPs) can be handled by a hybrid Benders decomposition (HBD) approach. Our HBD framework extends the classical Benders decomposition method (Benders, Numer Math 4:238–252, 1962) by integrating solution techniques in math programming and constraint programming (CP). Effective cut generation schemes are devised to improve the algorithm performance. Performance of our HBD is demonstrated on a project scheduling problem with multi-skilled workforce. Extensions to the basic HBD framework are discussed.

This chapter presents a generic model for an industrial project scheduling problem. The problem addressed here is an extension of the Resource-Constrained Project Scheduling Problem (RCPSP) and the Multi-Skill Project Scheduling Problem (MSPSP). The main specificities of this problem are the following: We considered both preemptive activities and non-preemptive activities, resource requirements of activities are given in terms of skills, and different durations exist in terms of both activities and skills. This model and its resolution methods are to be used in the Apache Open For Business (OFBiz) open source Enterprise Resource Planning (ERP) system, and must therefore satisfy some industrial constraints. We first propose a general model for this problem. Then, we propose a Mixed Integer Linear Program (MIP) formulation and a heuristic algorithm based on priority rules. The originality of the model lies in the fact that it simultaneously considers skill synchronization, preemption and precedence relationships. Experimental results performed on adapted instances from the PSPLIB benchmark are provided.

In this chapter we review the literature on the discrete time-cost tradeoff problem (DTCTP). We then present the four integer programming formulations of a version of DTCTP with irregular starting time costs from Szmerekovsky and Venkateshan (Comp and Oper Res 39(7):1402–1410, 2012). Specifically, the problem is an irregular costs project scheduling problem with time-cost tradeoffs. The empirical tests performed in Szmerekovsky and Venkateshan (Comp and Oper Res 39(7):1402–1410, 2012) are updated using the current version of CPLEX and similar results are found being driven by a reduced number of binary variables, a tighter linear programming relaxation, and the sparsity and embedded network structure of the constraint matrix.

Time-cost tradeoffs have been extensively studied in the literature since the development of the critical path method. Recently, the discrete version of the problem formulation has been extended to various practical assumptions, and solved with both exact and heuristic optimisation procedures, as described in Vanhoucke and Debels (J Sched 10:311–326, 2007).In this chapter, an overview is given of four variants of the discrete time-cost tradeoff problem and a newly developed electromagnetic meta-heuristic (EM) algorithm to solve these problems is presented. We extend the standard electromagnetic meta-heuristic with problem specific features and investigate the influence of various EM parameters on the solution quality. We test the new meta-heuristic on a benchmark set from the literature and present extensive computational results.