Resource-Constrained Project Scheduling

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.

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