Flexibility and Robustness in Scheduling

Scheduling is a broad research area and scheduling problems arise from several application domains (production systems, logistic, computer science, etc.). Solving scheduling problems requires tools of combinatorial optimization, exact or approximated algorithms. Flexibility is at the frontier between predictive deterministic approaches and reactive or "on-line" approaches. The purpose of flexibility is to provide one or more solutions adapted to the context of the application in order to provide the ideal solution. This book focuses on the integration of flexibility and robustness considerations in the study of scheduling problems. After considering both flexibility and robustness, it then covers various scheduling problems, treated with an emphasis on flexibility or robustness, or both.

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

Aziz Moukrim is Professor in Computer Science at the the University of Technology of Compiegne, France, and is a member of the UTC-CNFRS research laboratory (Heudiasyc). He teaches algorithmic and operations research (Scheduling, logistics and transportation systems). He is also co-leader of the CNRS Group (Scheduling and Transportation Networks).

Eric Sanlaville is Associate Professor In Computer Science at the University of Clermont-Ferrand, France. He teaches algorithmics and operations research (both in deterministic and stochastic settings). He has been a member of het board of the French OR Society since 004.