Resource-Constrained Project Scheduling E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 528

Veröffentlichungsjahr: 2013

Beschreibung

This title presents a large variety of models and algorithms dedicated to the resource-constrained project scheduling problem (RCPSP), which aims at scheduling at minimal duration a set of activities subject to precedence constraints and limited resource availabilities. In the first part, the standard variant of RCPSP is presented and analyzed as a combinatorial optimization problem. Constraint programming and integer linear programming formulations are given. Relaxations based on these formulations and also on related scheduling problems are presented. Exact methods and heuristics are surveyed. Computational experiments, aiming at providing an empirical insight on the difficulty of the problem, are provided. The second part of the book focuses on several other variants of the RCPSP and on their solution methods. Each variant takes account of real-life characteristics which are not considered in the standard version, such as possible interruptions of activities, production and consumption of resources, cost-based approaches and uncertainty considerations. The last part presents industrial case studies where the RCPSP plays a central part. Applications are presented in various domains such as assembly shop and rolling ingots production scheduling, project management in information technology companies and instruction scheduling for VLIW processor architectures.

Leseprobe

Table of Contents

Preface

Part 1: Models and Algorithms for the Standard Resource-Constrained Project Scheduling Problem

Chapter 1: The Resource-Constrained Project Scheduling Problem

1.1. A combinatorial optimization problem

1.2. A simple resource-constrained project example

1.3. Computational complexity

1.4. Dominant and non-dominant schedule subsets

1.5. Order-based representation of schedules and related dominant schedule sets

1.6. Forbidden sets and resource flow network formulations of the RCPSP

1.7. A simple method for enumerating a dominant set of quasi-active schedules

Chapter 2: Resource and Precedence Constraint Relaxation

2.1. Relaxing resource constraints

2.2. Calculating the disjunctive subproblem

2.3. Deducing identical parallel machine problems

2.4. Single cumulative resource problem

2.5. Conclusion and perspectives

Chapter 3: Mathematical Programming Formulations and Lower Bounds

3.1. Sequence-based models

3.2. Time-indexed formulations

3.3. Linear lower bounds and redundant resources

Chapter 4: Constraint Programming Formulations and Propagation Algorithms

4.1. Constraint formulations

4.2. Constraint propagation algorithms

4.3. Conclusion

Chapter 5: Branching Schemes for Branch-and-Bound

5.1. Chronological branching scheme

5.2. Specific branching schemes

5.3. Conclusion and perspectives

Chapter 6: Heuristics

6.1. Schedule representation schemes

6.2. Constructive heuristics

6.3. Local search neighborhoods

6.4. Metaheuristics

6.5. Conclusion

6.6. Appendix

Chapter 7: Benchmark Instance Indicators and Computational Comparison of Methods

7.1. Introduction

7.2. Standard instance indicators

7.3. New instance indicators

7.4. State-of-the-art benchmark instances

7.5. A critical analysis of the instance indicators

7.6. Comparison of solution methods

7.7. Conclusion

Part 2: Variants and Extensions

Chapter 8: Preemptive Activities

8.1. Preemption in scheduling

8.2. State of the art

8.3. Recent LP-based methods

8.4. Conclusion

Chapter 9: Multi-Mode and Multi-Skill Project Scheduling Problem

9.1. Introduction

9.2. Multi-Mode RCPSP

9.3. Multi-Skill Project Scheduling Problem

9.4. Conclusion and research directions

Chapter 10: Project Scheduling with Production and Consumption of Resources: How to Build Schedules

10.1. Introduction

10.2. The precedence-constrained project scheduling problem

10.3. The resource-constrained project scheduling problem

10.4. Scheduling problems with production and consumption of a non-renewable resource

10.5. Discussion

Chapter 11: Activity Insertion Problem in a RCPSP with Minimum and Maximum Time Lags

11.1. Introduction

11.2. Problem statement

11.3. Insertion positions

11.4. Feasibility conditions under a makespan upper bound

11.5. Computational complexity of the insertion problem with minimum and maximum time lags

11.6. A polynomial algorithm for the insertion problem with minimum time lags only

11.7. Conclusion

Chapter 12: Reactive Approaches

12.1. Dynamic project scheduling

12.2. Explanations and constraint programming for solving dynamic problems

12.3. An explanation-based approach for solving dynamic project scheduling

12.4. Experimental results

12.5. Conclusion

Chapter 13: Proactive-reactive Project Scheduling

13.1. Introduction

13.2. Solution robust scheduling under activity duration uncertainty

13.3. Solution robust scheduling under resource availability uncertainty

13.4. Conclusions and suggestions for further research

13.5. Acknowledgements

Chapter 14: RCPSP with Financial Costs

14.1. Problem presentation and context

14.2. Definitions and notations

14.3. NPV maximization

14.4. Resource-related costs

14.5. Conclusion

Part 3: Industrial Applications

Chapter 15: Assembly Shop Scheduling

15.1. The assembly shop scheduling problem

15.2. Link with the RCPSP

15.3. Proposition of extensions

15.4. Proposition of solution methods

15.5. Some results

15.6. Conclusion

Chapter 16: Employee Scheduling in an IT Company

16.1. Introduction

16.2. Problem presentation and context

16.3. Real life example

16.4. Predictive phase

16.5. Proactive phase

16.6. Reactive phase

16.7. Computational experiments

16.8. Conclusion

Chapter 17: Rolling Ingots Production Scheduling

17.1. Introduction

17.2. Project scheduling model

17.3. Solution method

17.4. Conclusions

Chapter 18: Resource-Constrained Modulo Scheduling

18.1. Introduction

18.2. The resource-constrained modulo scheduling problem

18.3. Integer linear programming formulations

18.4. Solving the RCMSP formulations

18.5. Summary and conclusions

Bibliography

List of Authors

Index

First published in Great Britain and the United States in 2008 by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd6 Fitzroy SquareLondon W1T 5DXUKJohn Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USAwww.iste.co.ukwww.wiley.com

© ISTE Ltd, 2008

The rights of Christian Artigues, Sophie Demassey and Emmanuel Néron to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Artigues, Christian.

Resource-constrained project scheduling: models, algorithms, extensions and applications / edited by Christian Artigues, Sophie Demassey, Emmanuel Néron.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-84821-034-9

1. Production scheduling. I. Demassey, Sophie. II. Néron, Emmanuel. III. Title.

TS157.5.A77 2008

658.5'3--dc22

2007043947

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN: 978-1-84821-034-9

Preface

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 [BLA 83] and is actually one of the most intractable classical problems in practice. In the publicly available PSPLIB library [PSPib], 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 [SLO 89, KOL 95a, JOZ 98, WEG 98, HAR 99, KLE 01, DOR 02, DEM 02c, NEU 03, BRU 06]. 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.

This book contains 18 chapters written by 28 authors who are all active researchers in the area. We describe hereafter the contents of the book, underlining the original aspects for each chapter.

There are three parts. The first part is devoted to the standard RCPSP as stated above and the various methods that have been proposed to solve it. More precisely, each chapter of this part focuses on a particular aspect of the solution process. Chapter 1, written by Christian Artigues, focuses on the models and describes the RCPSP as a combinatorial optimization problem. Different combinatorial models of the resource constraints and characterizations of dominant schedule sets are given. In particular, the properties of the order-based representation are studied. Chapter 2, written by Emmanuel Néron, considers the scheduling standard subproblems obtained by various relaxations. Solving these subproblems using specific scheduling methods generally yields quickly computable lower bounds. However, extraction of a relevant subproblem may be a complex task. The chapter describes innovative concepts of redundant resources and redundant functions, designed with this aim in mind. Chapter 3, written by Sophie Demassey, is devoted to mathematical programming formulations of the RCPSP and to lower bounds resulting from their relaxations. Besides recalling the main sequence-based and time-indexed integer linear programming formulations, it describes the recent cutting-plane and column generation techniques making it possible to obtain tight lower bounds when used in conjunction with constraint programming. A promising formulation based on the redundant resource concept and linear lower bounds is also introduced. Chapter 4, written by Philippe Laborie and Wim Nuijten, is devoted to constraint programming approaches for scheduling and describes the existing propagation algorithms relevant for the RCPSP. The by-now standard disjunctive, edge-finding and energy reasoning rules are recalled. The original balance and energy-precedence propagation algorithms are presented. Chapter 5, written by Emmanuel Néron, presents the main branching schemes and associated dominance rules used to solve the RCPSP via exact methods. Indeed, a multitude of branchand-bound methods can be derived by combining the presented branching schemes with the lower bounds and constraint propagation algorithms presented in Chapters 2, 3 and 4. Chapter 6, written by Christian Artigues and David Rivreau, describes the main heuristics and metaheuristics that were proposed to approximate the RCPSP. The chapter reviews the literature and proposes a unifying framework based on the concepts of events and resource flows for the two main constructive algorithms: the parallel and the serial scheduling schemes. Chapter 7, written by Christian Artigues, Oumar Koné, Pierre Lopez, Marcel Mongeau, Emmanuel Néron and David Rivreau, is devoted to extensive computational experiments. Its objective is twofold. First, a selection of representative exact and heuristic methods among those presented in the previous chapters are tested and compared under a common experimental framework on four different instance sets. Second, classical and new instance difficulty indicators are evaluated through experiments and their discriminating power is discussed.

Part 2 of the book presents variants and extensions of the RCPSP. Clearly, the standard model does not allow for modeling all the practical situations accurately. Each chapter of this part focuses on a particular variant or extension and presents the latest advances made to tackle it. Most chapters present new and original methods. Chapter 8, written by Jean Damay, presents LP-based neighborhood search and exact methods for the rational preemptive variant of the RCPSP. This variant has never been considered before despite its practical interest. It considers the case where activities can be interrupted at any, not necessarily integer, time. Chapter 9, written by Odile Bellenguez-Morineau and Emmanuel Néron, is devoted to the multi-mode RCPSP and the multi-skill RCPSP. The chapter reviews branching schemes and dominance rules for the multi-mode RCPSP. This extension introduces alternative activity execution modes, differing by the resource requirements and the durations. The multi-skill RCPSP is a variant for which the modes are implicitly defined using the intermediate concept of required and available skills. This model makes it possible to efficiently represent the practical case of human resources while there would be an explosion of the number of modes in the multi-mode model. An exact method is proposed to solve the problem. Chapter 10, written by Jacques Carlier, Aziz Moukrim and Huang Xu, considers a RCPSP with renewable (as in the standard case) and non-renewable resources. Some activities consume a non-renewable resources while others produce it. They propose an enumeration method based on the concept of arbitrage and on the strict order algorithm. They also show how AND/OR precedence constraints can be used to compute solutions. Chapter 11, written by Christian Artigues and Cyril Briand, considers the RCPSP with minimum and maximum time lags. They focus on the problem of activity insertion in a schedule represented by a resource flow, which can occur in reactive scheduling (next chapter) or as a component of a local search method. They show the problem is NP-hard and propose a polynomial algorithm when only minimum time lags are considered. Chapter 12, written by Christelle Guéret and Narendra Jussien, proposes a reactive approach to solve a dynamic project scheduling problem, i.e. one that may change over time through unexpected events. Their method can tackle various events including the insertion of a new activity as in the previous chapter. They make use of explanation-based constraint programming, where explanations allow for schedule repairing through the tree-search after each disruption. Chapter 13, written by Erik Demeulemeester, Willy Herroelen and Roel Leus, makes a step further in tackling project scheduling under uncertainty using proactive/reactive procedures. Uncertainty may affect activity durations and resource availabilities. Proactive scheduling methods aiming at anticipating disruptions through robust resource allocation and buffer insertion in a precomputed schedule are presented. Reactive strategies are carried out when the proactive schedule cannot absorb the disruptions. The objective is to minimize an instability function measuring the distance between the precomputed schedule and the realized schedule. While the previous chapters mainly consider makespan minimization, Chapter 14, written by Laure-Emmanuelle Drezet, introduces several other objective functions dealing with financial aspects. The chapter reviews and classifies the existing work carried out on net present value maximization and resource-related costs such as resource leveling and resource investment.

Part 3 of the book is devoted to industrial applications involving the RCPSP or its variants and extensions. Thereby, the reader may verify how the different models and methods presented in this book are actually applied in various and perhaps surprising situations. Chapter 15, written by Michel Gourgand, Nathalie Grangeon and Sylvie Norre, considers an assembly shop problem in an automotive company. Special attention is paid to the modeling process which exhibits a RCPSP with variable resource profile and resource individualization, linked with the multimode aspects described in Chapter 9. The problem is solved by neighborhood search heuristics. Chapter 16, written by Laure-Emmanuelle Drezet and Jean-Charles Billaut, describes an employee scheduling problem in a IT company. The problem is modeled as a mixed project scheduling and workforce assignment problem. It follows that work regulation constraints are added to the standard RCPSP model. Since the considered projects (software developments) are highly likely to be disrupted, a proactive/reactive method (see Chapter 13) is proposed. Chapter 17, written by Christoph Schwindt and Norbert Trautmann, considers a rolling ingots production scheduling problem in the aluminium industry. This industrial context gives rise to a complex multi-mode RCPSP with minimum and maximum time lags, batching machines and sequence-dependent changeover times. A filtered beam search version of a branch-and-bound method is proposed to solve the problem. Chapter 18, written by Benoit Dupont de Dinechin, Christian Artigues and Sadia Azem, presents an unusual application of the RCPSP, namely an instruction scheduling problem for very long instruction word processors. The specific characteristics of these processors and the cyclic nature of the problem yields a modulo RCPSP with minimum and maximum time lags. New integer linear programming formulations are proposed and an efficient large neighborhood search technique is used to solve near-optimally large industrial problems in a few minutes.

We wish to warmly thank all the colleagues who kindly accepted to review one or several chapters of the book: Philippe Baptiste, Rainer Kolisch, Philippe Lacomme, Francis Sourd and Mario Vanhoucke.

Christian ARTIGUES, SOPHIE DEMASSEY and Emmanuel NÉRON

Part 1

Models and Algorithms for the Standard Resource-Constrained Project Scheduling Problem