Preface 13
Chapter 1. Introduction to Flexibility and Robustness in Scheduling 15
Jean-Charles BILLAUT, AzizMOUKRIM and Eric SANLAVILLE
1.1. Scheduling problems 15
1.1.1. Machine environments 16
1.1.2.Characteristics of tasks 17
1.1.3. Optimality criteria 18
1.2. Background to the study 19
1.3. Uncertainty management 20
1.3.1. Sources of uncertainty 21
1.3.2. Uncertainty of models 22
1.3.3. Possible methods for problem solving 23
1.3.3.1. Full solution process of a scheduling problem with uncertainties 23
1.3.3.2. Proactive approach 24
1.3.3.3. Proactive/reactive approach 24
1.3.3.4. Reactive approach 25
1.4. Flexibility 25
1.5. Robustness 26
1.5.1. Flexibility as a robustness indicator 27
1.5.2. Schedule stability (solution robustness) 28
1.5.3. Stability relatively to a performance criterion (quality robustness) 29
1.5.4. Respect of a fixed performance threshold 30
1.5.5. Deviation measures with respect to the optimum 30
1.5.6. Sensitivity and robustness 31
1.6. Bibliography 31
Chapter 2. Robustness in Operations Research and Decision Aiding 35
Bernard ROY
2.1. Overview 35
2.1.1. Robust in OR-DA with meaning? 36
2.1.2. Why the concern for robustness? 37
2.1.3. Plan of the chapter 38
2.2. Where do "vague approximations" and "zones of ignorance" come from? - the concept of version 38
2.2.1. Sources of inaccurate determination, uncertainty and imprecision 38
2.2.2. DAP formulation: the concept of version 40
2.3. Defining some currently used terms 41
2.3.1. Procedures, results and methods 41
2.3.2. Two types of procedures and methods 42
2.3.3. Conclusions relative to a set ¿R of results 43
2.4. How to take the robustness concern into consideration 43
2.4.1. What must be robust? 44
2.4.2. What are the conditions for validating robustness? 45
2.4.3. How can we define the set of pairs of procedures and versions to take into account? 46
2.5. Conclusion 47
2.6. Bibliography 47
Chapter 3. The Robustness of Multi-Purpose Machines Workshop Configuration 53
Marie-Laure ESPINOUSE, Mireille JACOMINO and André ROSSI
3.1. Introduction 53
3.2. Problem presentation 53
3.2.1. Modeling the workshop 54
3.2.1.1. Production resources 54
3.2.1.2. Modeling the workshop demand 55
3.2.2. Modeling disturbances on the data 55
3.2.3. Performance versus robustness: load balance and stability radius 57
3.2.3.1. Performance criterion for a configuration 57
3.2.3.2. Robustness 57
3.3. Performance measurement 57
3.3.1. Stage one: minimizing the maximum completion time 57
3.3.2. Computing a production plan minimizing machine workload 59
3.3.3. The particular case of uniform machines 60
3.4. Robustness evaluation 61
3.4.1. Finding the demands for which the production plan is balanced 61
3.4.2. Stability radius 64
3.4.3. Graphic representation 65
3.5. Extension: reconfiguration problem 68
3.5.1. Consequence of adding a qualification to the matrix Q 68
3.5.2. Theoretical example 69
3.5.3. Industrial example 70
3.6. Conclusion and perspectives 70
3.7. Bibliography 71
Chapter 4. Sensitivity Analysis for One and m Machines 73
Amine MAHJOUB, AzizMOUKRIM, Christophe RAPINE and Eric SANLAVILLE
4.1. Sensitivity analysis 74
4.2. Single machine problems 78
4.2.1. Some analysis from the literature 78
4.2.2. Machine initial unavailability for 1__Uj 79
4.2.2.1. Problem presentation 79
4.2.2.2. Sensitivity of the HM algorithm 80
4.2.2.3. Hypotheses and notations 80
4.2.2.4. The two scenario case 81
4.3. m-machine problems without communication delays 83
4.3.1. Parametric analysis 83
4.3.2. Example of global analysis: Pm__Cj 85
4.4. The m-machine problems with communication delays 87
4.4.1. Notations and definitions 88
4.4.2. The two-machine case 90
4.4.3. The m-machine case 92
4.4.3.1. Some results in a deterministic setting 92
4.4.3.2. Framework for sensitivity analysis 93
4.4.3.3. Stability studies 93
4.4.3.4. Sensitivity bounds 94
4.5. Conclusion 95
4.6. Bibliography 96
Chapter 5. Service Level in Scheduling 99
Stéphane DAUZÈRE-PÉRÈS, Philippe CASTAGLIOLA and Chams LAHLOU
5.1. Introduction 99
5.2. Motivations 101
5.3. Optimization of the service level: application to the flow-shop problem 103
5.3.1. Criteria computation 103
5.3.2. Processing time generation 104
5.3.3. Experimental results 106
5.4. Computation of a schedule service level 109
5.4.1. Introduction 110
5.4.2. FORM (First Order Reliability Method) 111
5.4.3. FORM vs Monte Carlo 112
5.5. Conclusions 118
5.6. Bibliography 119
Chapter 6. Metaheuristics for Robust Planning and Scheduling 123
Marc SEVAUX, Kenneth SÖRENSEN and Yann LE QUÉRÉ
6.1. Introduction 123
6.2. A general framework for metaheuristic robust optimization 124
6.2.1. General considerations 124
6.2.2. An example using a genetic algorithm 126
6.3. Single-machine scheduling application 127
6.3.1. Minimizing the number of late jobs on a single machine 127
6.3.2. Uncertainty of deliveries 129
6.3.2.1. Considered problem 129
6.3.2.2. Robust evaluation function 129
6.3.3. Results 130
6.4. Application to the planning of maintenance tasks 132
6.4.1. SNCF maintenance problem 133
6.4.2. Uncertainties of an operational factory 134
6.4.3. A robust schedule 135
6.4.3.1. Variations of the unexpected factors 137
6.5. Conclusions and perspectives 139
6.6. Bibliography 140
Chapter 7. Metaheuristics and Performance Evaluation Models for the Stochastic Permutation Flow-Shop Scheduling Problem 143
Michel GOURGAND, Nathalie GRANGEON and Sylvie NORRE
7.1. Problem presentation 144
7.2. Performance evaluation problem 147
7.2.1. Markovian analysis 147
7.2.2. Monte Carlo simulation 153
7.3. Scheduling problem 155
7.3.1. Comparison of two schedules 156
7.3.2. Stochastic descent for the minimization in expectation 157
7.3.3. Inhomogenous simulated annealing for the minimization in expectation 157
7.3.4. Kangaroo algorithm for the minimization in expectation 159
7.3.5. Neighboring systems 161
7.4. Computational experiment 161
7.4.1. Exponential distribution 162
7.4.2. Uniform distribution function 164
7.4.3. Normal distribution function 167
7.5. Conclusion 167
7.6. Bibliography 168
Chapter 8. Resource Allocation for the Construction of Robust Project Schedules 171
Christian ARTIGUES, Roel LEUS and Willy HERROELEN
8.1. Introduction 171
8.2. Resource allocation and resource flows 173
8.2.1. Definitions and notation 173
8.2.2. Resource flow networks 174
8.2.3. A greedy method for obtaining a feasible flow 176
8.2.4. Reactions to disruptions 176
8.3. A branch-and-bound procedure for resource allocation 178
8.3.1. Activity duration disruptions and stability 178
8.3.2. Problem statement and branching scheme 179
8.3.3. Details of the branch-and-bound algorithm 180
8.3.4. Testing for the existence of a feasible flow 182
8.3.5. Branching rules 183
8.3.6. Computational experiments 184
8.3.6.1. Experimental setup 184
8.3.6.2. Branching schemes 185
8.3.6.3. Comparison with the greedy heuristic 187
8.4. A polynomial algorithm for activity insertion 187
8.4.1. Insertion problem formulation 188
8.4.2. Evaluation of a feasible insertion 189
8.4.3. Insertion feasibility conditions 190
8.4.4. Sufficient insertions and insertion cuts 191
8.4.5. Insertion dominance conditions 192
8.4.6. An algorithm for enumerating dominant sufficient insertions 193
8.4.7. Experimental results 193
8.5. Conclusion 194
8.6. Bibliography 195
Chapter 9. Constraint-based Approaches for Robust Scheduling 199
Cyril BRIAND, Marie-José HUGUET, Hoang Trung LA and Pierre LOPEZ
9.1. Introduction 199
9.2. Necessary/sufficient/dominant conditions and partial orders 200
9.3. Interval structures, tops, bases and pyramids 201
9.4. Necessary conditions for a generic approach to robust scheduling 202
9.4.1. Introduction 202
9.4.2. Scheduling problems under consideration 204
9.4.3. Necessary feasibility conditions 205
9.4.4. Propagation mechanisms 206
9.4.4.1. Time constraint propagation 206
9.4.4.2. Resource constraint propagation 207
9.4.5. Interval structures for propagation 208
9.4.5.1. Rank-interval based structures 208
9.4.5.2. Task-interval based structures 210
9.4.6. Discussion 212
9.5. Using dominance conditions or sufficient conditions 213
9.5.1. The single machine scheduling problem 213
9.5.2. The two-machine flow-shop problem 217
9.5.3. Future prospects 221
9.6. Conclusion 222
9.7. Bibliography 222
Chapter 10. Scheduling Operation Groups: A Multicriteria Approach to Provide Sequential Flexibility 227
Carl ESSWEIN, Jean-Charles BILLAUT and Christian ARTIGUES
10.1. Introduction 227
10.2. Groups of permutable operations 228
10.2.1. History, principles and definitions 228
10.2.2. Representation and evaluation 230
10.2.2.1.Earliest start time computation 232
10.2.2.2. Latest completion time computation 234
10.2.2.3. Quality of a group schedule 234
10.3. The ORABAID approach 235
10.3.1. The proactive phase: searching for a feasible and acceptable group schedule 235
10.3.1.1. Construction of a feasible group schedule 236
10.3.1.2. Searching for acceptability of the group schedule 237
10.3.1.3. Increasing the group schedule flexibility 237
10.3.2. The reactive phase: real-time decision aid 237
10.3.3. Some conclusions about ORABAID 238
10.4. AMORFE, a multicriteria approach 238
10.4.1. Flexibility evaluation of a group schedule 239
10.4.2. Evaluation of the quality of a group schedule 240
10.4.3. Some considerations about the objective function definition 241
10.4.4. Quality guarantee in the best case 243
10.4.4.1. Advantages 243
10.4.4.2. Respect for quality in the best case 243
10.5. Application to several scheduling problems 244
10.6. Conclusion 246
10.7. Bibliography 246
Chapter 11. A Flexible Proactive-Reactive Approach: The Case of an AssemblyWorkshop 249
Mohamed Ali ALOULOU and Marie-Claude PORTMANN
11.1. Context 249
11.2. Definition of the control model 251
11.2.1. Definition of the problem and its environment 251
11.2.2. Definition of a solution to the problem 251
11.2.3. Definition of the solution quality 252
11.2.3.1. Preliminary example 252
11.2.3.2. Performance of a solution 253
11.2.3.3. Flexibility of a solution 255
11.3. Proactive algorithm 256
11.3.1. General schema of the proposed genetic algorithm 256
11.3.2. Selection and strategy of reproduction 258
11.3.3. Coding of a solution 258
11.3.4. Crossover operator 258
11.3.5. Mutation operator 259
11.4. Reactive algorithm 260
11.4.1. Functions of the reactive algorithm 260
11.4.2. Reactive algorithms in the absence of disruptions 261
11.4.2.1. A posteriori quality measures 261
11.4.2.2. Proposed algorithms 263
11.4.3. Reactive algorithm with disruptions 264
11.5. Experiments and validation 264
11.6. Extensions and conclusions 265
11.7. Bibliography 266
Chapter 12. Stabilization for Parallel Applications 269
Amine MAHJOUB, Jonathan E. PECERO SÁNCHEZ and Denis TRYSTRAM
12.1. Introduction 270
12.2. Parallel systems and scheduling 270
12.2.1. Actual parallel systems 270
12.2.2. Definitions and notations 271
12.2.3. Motivating example 273
12.3. Overview of different existing approaches 275
12.4. The stabilization approach 276
12.4.1. Stabilization in processing computing 276
12.4.2. Example 278
12.4.3. Stabilization process 280
12.5. Two directions for stabilization 280
12.5.1. The PRCP¿ algorithm 281
12.5.2. Strong stabilization 283
12.6. An intrinsically stable algorithm 286
12.6.1. Convex clustering 286
12.6.2. Stability analysis of convex clustering 290
12.7. Experiments 293
12.7.1. Impact of disturbances in the schedules of the three algorithms 294
12.7.2. Influence of the initial schedule in the stabilization process 295
12.7.3. Comparison of the schedules with and without stabilization 297
12.7.4. Test 1 - comparison for Winkler graphs 297
12.7.5. Test 2 - comparison for layer graphs 298
12.8. Conclusion 299
12.9. Bibliography 300
Chapter 13. Contribution to a Proactive/Reactive Control of Time Critical Systems 303
Pascal AYGALINC, Soizick CALVEZ and Patrice BONHOMME
13.1. Introduction 303
13.2. Static problem definition 305
13.2.1. Autonomous Petri nets (APN) 306
13.2.2. p-timePNs 307
13.3. Step 1: computing a feasible sequencing family 311
13.4. Step 2: dynamic phase 317
13.4.1. Temporal flexibility 317
13.4.2. Temporal flexibility and sequential flexibility 319
13.4.2.1. Partial order in performance evaluation 320
13.4.2.2. Partial order in proactive/reactive control 322
13.5. Restrictions due to p-time PNs 323
13.6. Bibliography 325
Chapter 14. Small Perturbations on Some NP-Complete Scheduling Problems 327
Christophe PICOULEAU
14.1. Introduction 327
14.2. Problem definitions 328
14.2.1. Sequencing with release times and deadlines 328
14.2.2. Multiprocessor scheduling 329
14.2.3. Unit execution times scheduling 330
14.2.4. Scheduling unit execution times with unit communication times 331
14.3. NP-completeness results 332
14.4. Conclusion 340
14.5. Bibliography 340
List of Authors 341
Index 347
