Resource-Constrained Project Scheduling: Models, Algorithms, Extensions and Applications

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