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.

Table of Contents:
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

About the Author :
Jean-Charles Billaut is Professor in Computer Science in the Polytechnic School of the University of Tours, France. he teaches assembly language and operations research (graph theory and dynamic programming). He is also member of the board of the French OR Society (President in 2006 and 2007). 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.