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.
Table of Contents:
Preface 13
Christian ARTIGUES, Sophie DEMASSEY and Emmanuel NÉRON
Part 1. Models and Algorithms for the Standard Resource-Constrained
Project Scheduling Problem 19
Chapter 1. The Resource-Constrained Project Scheduling Problem 21
Christian ARTIGUES
1.1. A combinatorial optimization problem 21
1.2. A simple resource-constrained project example 23
1.3. Computational complexity 23
1.4. Dominant and non-dominant schedule subsets 26
1.5. Order-based representation of schedules and related dominant schedule sets 28
1.6. Forbidden sets and resource flow network formulations of the RCPSP 31
1.7. A simple method for enumerating a dominant set of quasi-active schedules 34
Chapter 2. Resource and Precedence Constraint Relaxation 37
Emmanuel NÉRON
2.1. Relaxing resource constraints 38
2.2. Calculating the disjunctive subproblem 38
2.3. Deducing identical parallel machine problems 41
2.4. Single cumulative resource problem 45
2.5. Conclusion and perspectives 47
Chapter 3. Mathematical Programming Formulations and Lower Bounds 49
Sophie DEMASSEY
3.1. Sequence-based models 50
3.1.1. Minimal forbidden sets 51
3.1.2. Resource flow 52
3.2. Time-indexed formulations 53
3.2.1. Resource conflicts as linear constraints 54
3.2.2. Feasible configurations 56
3.2.2.1. Combinatorial relaxations 58
3.2.2.2. Column generation and further improvements 59
3.2.2.3. Cutting planes for the preemptive relaxation 60
3.3. Linear lower bounds and redundant resources 61
Chapter 4. Constraint Programming Formulations and Propagation Algorithms 63
Philippe LABORIE and Wim NUIJTEN
4.1. Constraint formulations 63
4.1.1. Constraint programming 63
4.1.2. Constraint-based scheduling 64
4.2. Constraint propagation algorithms 65
4.2.1. Temporal constraints 65
4.2.2. Timetabling 66
4.2.3. Disjunctive reasoning 67
4.2.4. Edge-finding 67
4.2.5. Energy reasoning 68
4.2.6. Precedence graph 70
4.2.7. Energy precedence 70
4.2.8. Balance constraint 71
4.3. Conclusion 72
Chapter 5. Branching Schemes for Branch-and-Bound 73
Emmanuel NÉRON
5.1. Chronological branching scheme 75
5.1.1. Adding one activity to a partial solution 75
5.1.1.1. Considering all relevant activities 75
5.1.1.2. Delaying one activity 77
5.1.2. Dominance rule: left shift and global left shift 78
5.1.3. Adding a subset of activities to a partial solution 79
5.1.3.1. Delaying alternatives 79
5.1.3.2. Building a solution using blocks 80
5.1.4. Dominance rule: cut-set 81
5.2. Specific branching schemes 82
5.2.1. Fixing disjunction and parallel relationship 82
5.2.2. Reducing time-windows of activities 83
5.2.3. Resolving forbidden sets 84
5.3. Conclusion and perspectives 85
Chapter 6. Heuristics 87
Christian ARTIGUES and David RIVREAU
6.1. Schedule representation schemes 87
6.1.1.Natural date variables 87
6.1.2. List schedule generation scheme representations 88
6.1.3. Set-based representations 88
6.1.4.Resource flow network representation 89
6.2. Constructive heuristics 89
6.2.1. Standard list schedule generation scheme heuristics 89
6.2.2. A generic insertion-based list schedule generation scheme 91
6.2.3. Set schedule generation scheme heuristics 93
6.2.4. (Double-) justification-based methods 94
6.3. Local search neighborhoods 94
6.3.1. List-based neighborhoods 95
6.3.2. Set-based neighborhoods 95
6.3.3. Resource flow-based neighborhoods 96
6.3.4. Extended neighborhood for natural date variables 96
6.4. Metaheuristics 97
6.4.1. Simulated annealing 97
6.4.2. Tabu search 97
6.4.3. Population-based metaheuristics 98
6.4.4. Additional methods 99
6.5. Conclusion 100
6.6. Appendix 101
6.6.1. Serial list schedule generation revisited 101
6.6.2. Parallel list schedule generation revisited 104
Chapter 7. Benchmark Instance Indicators and Computational Comparison of Methods 107
Christian ARTIGUES, Oumar KONÉ, Pierre LOPEZ, Marcel MONGEAU, Emmanuel NÉRON and David RIVREAU
7.1. Introduction 107
7.2. Standard instance indicators 108
7.3. New instance indicators 112
7.4. State-of-the-art benchmark instances 114
7.5. A critical analysis of the instance indicators 118
7.5.1. Indicator comparison between trivial and non-trivial instances 118
7.5.2. Indicator stability and correlation 120
7.6. Comparison of solution methods 124
7.6.1. Selected methods and experimental framework 124
7.6.2. Results on the KSD30 instances 129
7.6.3. Results on the BL instances 131
7.6.4. Results on the KSD60 instances 132
7.6.5. Results on the Pack instances 134
7.7. Conclusion 135
Part 2. Variants and Extensions 137
Chapter 8. Preemptive Activities 139
Jean DAMAY
8.1. Preemption in scheduling 139
8.2. State of the art 140
8.2.1. Integral preemption for the RCPSP 140
8.2.2. Rational preemption for parallel machine scheduling problems 141
8.3. Recent LP-based methods 142
8.3.1. Reformulation 142
8.3.2. A specific neighborhood search algorithm 144
8.3.2.1. Descent approach 144
8.3.2.2. Diversification techniques 145
8.3.2.3. Experimental results 145
8.3.3. Exact methods 146
8.3.3.1. Branch-and-bound 146
8.3.3.2. Branch and cut and price 147
8.4. Conclusion 147
Chapter 9. Multi-Mode and Multi-Skill Project Scheduling Problem 149
Odile BELLENGUEZ-MORINEAU and Emmanuel NÉRON
9.1. Introduction 149
9.2. Multi-Mode RCPSP 150
9.2.1. Problem presentation 150
9.2.2. Branching schemes for solving multi-mode RCPSP 152
9.2.3. Dominance rules 153
9.3. Multi-Skill Project Scheduling Problem 154
9.3.1. Problem presentation 154
9.3.2. Branching scheme based on time-windows reduction 157
9.3.3. Lower bounds and time-bound adjustments 158
9.3.4. Dominance rule 159
9.4. Conclusion and research directions 160
Chapter 10. Project Scheduling with Production and Consumption of Resources: How to Build Schedules 161
Jacques CARLIER, AzizMOUKRIM and Huang XU
10.1. Introduction 161
10.2. The precedence-constrained project scheduling problem 162
10.2.1. Traditional precedence constraints 162
10.2.2. AND/OR precedence constraints 163
10.3. The resource-constrained project scheduling problem 164
10.3.1. Graph representation 164
10.3.2. The strict order algorithm 164
10.4. Scheduling problems with production and consumption of a non-renewable resource 166
10.5. Discussion 170
Chapter 11. Activity Insertion Problem in a RCPSP with Minimum and Maximum Time Lags 171
Christian ARTIGUES and Cyril BRIAND
11.1. Introduction 171
11.2. Problem statement 172
11.3. Insertion positions 176
11.4. Feasibility conditions under a makespan upper bound 176
11.5. Computational complexity of the insertion problem with minimum and maximum time lags 178
11.6. A polynomial algorithm for the insertion problem with minimum time lags only 181
11.7. Conclusion 190
Chapter 12. Reactive Approaches 191
Christelle GUÉRET and Narendra JUSSIEN
12.1. Dynamic project scheduling 191
12.2. Explanations and constraint programming for solving dynamic problems 192
12.2.1. Dynamic problems and constraint programming 192
12.2.2. Explanation-based constraint programming 193
12.3. An explanation-based approach for solving dynamic project scheduling 194
12.3.1. The tree search to solve static instances 195
12.3.2. Incrementally handling unexpected events 196
12.4. Experimental results 197
12.4.1. Stability measures 197
12.4.2. Test set 197
12.4.3. Computational results 198
12.4.3.1. Analysis of the results in terms of cpu time 199
12.4.3.2. Analysis of the stability 200
12.5. Conclusion 201
Chapter 13. Proactive-reactive Project Scheduling 203
Erik DEMEULEMEESTER, Willy HERROELEN and Roel LEUS
13.1. Introduction 203
13.2. Solution robust scheduling under activity duration uncertainty 204
13.2.1. The proactive/reactive scheduling problem 204
13.2.2. Proactive scheduling 205
13.2.2.1.Robust resource allocation 205
13.2.2.2. Buffer insertion 206
13.2.3. Reactive scheduling 207
13.3. Solution robust scheduling under resource availability uncertainty 209
13.3.1. The problem 209
13.3.1.1. Proactive strategy 209
13.3.1.2. Reactive strategy 210
13.4. Conclusions and suggestions for further research 210
13.5. Acknowledgements 211
Chapter 14. RCPSP with Financial Costs 213
Laure-Emmanuelle DREZET
14.1. Problem presentation and context 213
14.2. Definitions and notations 214
14.2.1. Definitions 214
14.2.2. Notations 215
14.2.3. Classification 216
14.3. NPV maximization 217
14.3.1. Unconstrained resources: MAXNPV and PSP 217
14.3.2. Constrained resources: RCPSPDC, CCPSP and PSP 219
14.4. Resource-related costs 221
14.4.1. Resource Leveling Problem 221
14.4.2. Resource Investment Problem (RIP) and Resource Renting Problem (RRP) 223
14.5. Conclusion 225
Part 3. Industrial Applications 227
Chapter 15. Assembly Shop Scheduling 229
Michel GOURGAND, Nathalie GRANGEON and Sylvie NORRE
15.1. The assembly shop scheduling problem 229
15.1.1. Mono shop problem 230
15.1.1.1. Physical subsystem 230
15.1.1.2. Logical subsystem 230
15.1.1.3. Decisional subsystem 231
15.1.2. Multi shop problem 232
15.2. Link with the RCPSP 233
15.3. Proposition of extensions 234
15.3.1. RCPSP with variable demand profile 235
15.3.2. RCPSP with resource individualization 237
15.4. Proposition of solution methods 239
15.5. Some results 240
15.6. Conclusion 242
Chapter 16. Employee Scheduling in an IT Company 243
Laure-Emmanuelle DREZET and Jean-Charles BILLAUT
16.1. Introduction 243
16.2. Problem presentation and context 244
16.3. Real life example 247
16.4. Predictive phase 250
16.4.1. Greedy algorithms 250
16.4.2. Tabu search algorithm 251
16.5. Proactive phase 251
16.6. Reactive phase 252
16.7. Computational experiments 253
16.7.1. Predictive and proactive algorithms 253
16.7.2. Reactive algorithm 254
16.8. Conclusion 254
Chapter 17. Rolling Ingots Production Scheduling 257
Christoph SCHWINDT and Norbert TRAUTMANN
17.1. Introduction 257
17.2. Project scheduling model 259
17.2.1. Activities and temporal constraints 259
17.2.2. Resource constraints 261
17.2.3. Production scheduling problem 264
17.3. Solution method 264
17.4. Conclusions 266
Chapter 18. Resource-Constrained Modulo Scheduling 267
Benoît DUPONT DE DINECHIN, Christian ARTIGUES and Sadia AZEM
18.1. Introduction 267
18.2. The resource-constrained modulo scheduling problem 268
18.2.1. The resource-constrained cyclic scheduling problem 268
18.2.2. The resource-constrained modulo scheduling problem 269
18.2.3. From modulo scheduling to software pipelining 270
18.3. Integer linear programming formulations 273
18.3.1. The RCMSP formulations by Eichenberger et al 273
18.3.2. A new time-indexed RCMSP formulation 274
18.4. Solving the RCMSP formulations 275
18.4.1. Reducing the size of the RCMSP formulations 275
18.4.2. A large neighborhood search for the RCMSP 275
18.4.3. Implementation and experiments 276
18.5. Summary and conclusions 277
Bibliography 279
List of Authors 303
Index 307
About the Author :
Christian Artigues is a researcher at the Laboratory for Analysis and
Architecture of Systems (LAAS) of the French National Institute for
Scientific Research (CNRS).
Sophie Demassey is an Assistant Professor at the School of Mining Engineering (EMN), Nantes, France.
Emmanuel Néron is Assistant Professor at the Computer Science Department of Polytech'Tours, France, and is a member of the Computer Science Laboratory of the University of Tours, France.
