Artigues C., Demassey S., Néron E. (eds.) Resource-Constrained Project Scheduling Models, Algorithms, Extensions and Applications

ISTE / John Wiley, 2008. — 293 p.Nowadays, material and human resource management is an increasingly important issue for organizations. Thus, a careful management of projects is an absolute necessity to preserve the competitiveness of companies. Scheduling plays a major part in project management. Indeed, the scheduling process amounts to deciding when the project activities will start and how they will use the available resources. Such decisions can be expected to have a large impact on the total project duration (makespan), which is the main performance criterion we consider in this book. Note that establishing a good schedule is necessary but not sufficient for actual project makespan minimization. As a comprehensive counter-example, let us consider the project that consisted of writing the present book. We expected a one year total duration but we must admit that the realized makespan exceeded two years. In this case, the makespan increase was clearly caused by an over-optimistic estimation of activity durations and resource availabilities while the schedule was correct.
Nevertheless, we focus in this book on the deterministic resource-constrained project scheduling problem (RCPSP). The standard RCPSP can be defined as a combinatorial optimization problem, i.e. in terms of decision variables, constraints and objective functions, as follows. A set of activities and a set of resources of known characteristics (activity durations, activity resource demands, resource availabilities, precedence restrictions) are given. The decision variables are the activity start times defined on integer time periods. The objective function which has to be minimized is the makespan, i.e. the largest activity completion time, assuming the project starts at time 0. There are two types of constraints. The precedence constraints prevent each activity from starting before the completion of its predecessors. The resource constraints ensure that, at each time period and for each resource, the total activity demand does not exceed the resource availability. Once started, an activity cannot be interrupted.
Despite the simplicity of its definition, the RCPSP belongs to the class of NP-hard optimization problems and is actually one of the most intractable classical problems in practice. In the publicly available PSPLIB library, the optimal makespan of randomly generated problems with 60 activities and 4 resources is still unknown. For both its industrial relevance and its challenging difficulty, solving the RCPSP has become a flourishing research theme. This becomes clear when observing the significant number of books that were published on this subject. One might even legitimately ask why yet another book on the RCPSP is needed.
The aim of this book is to present the latest results in the field, not as a collection of independent articles, but as a whole, in an integrated manner. Thus, it provides a state-of-the-art of the solution approaches for the standard RCPSP (Part 1) and for several of its variants (Part 2) and industrial applications (Part 3). The developments on each approach type are investigated from the fundamentals to the most recent – even current – studies.Part 1 Models and Algorithms for the Standard Resource-Constrained Project Scheduling Problem
The Resource-Constrained Project Scheduling Problem
Resource and Precedence Constraint Relaxation
Mathematical Programming Formulations and Lower Bounds
Constraint Programming Formulations and Propagation Algorithms
Branching Schemes for Branch-and-Bound
Heuristics
Benchmark Instance Indicators and Computational Comparison of Methods
Part 2 Variants and Extensions
Preemptive Activities
Multi-Mode and Multi-Skill Project Scheduling Problem
Project Scheduling with Production and Consumption of Resources: How to Build Schedules
Activity Insertion Problem in a RCPSP with Minimum and Maximum Time Lags
Reactive Approaches
Proactive-reactive Project Scheduling
RCPSP with Financial Costs
Part 3 Industrial Applications
Assembly Shop Scheduling
Employee Scheduling in an IT Company
Rolling Ingots Production Scheduling
Resource-Constrained Modulo Scheduling