Flexibility and Robustness in Scheduling

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.

• Preface 13Chapter 1. Introduction to Flexibility and Robustness in Scheduling 15Jean-Charles BILLAUT, AzizMOUKRIM and Eric SANLAVILLE1.1. Scheduling problems 151.1.1. Machine environments 161.1.2.Characteristics of tasks 171.1.3. Optimality criteria 181.2. Background to the study 191.3. Uncertainty management 201.3.1. Sources of uncertainty 211.3.2. Uncertainty of models 221.3.3. Possible methods for problem solving 231.3.3.1. Full solution process of a scheduling problem with uncertainties 231.3.3.2. Proactive approach 241.3.3.3. Proactive/reactive approach 241.3.3.4. Reactive approach 251.4. Flexibility 251.5. Robustness 261.5.1. Flexibility as a robustness indicator 271.5.2. Schedule stability (solution robustness) 281.5.3. Stability relatively to a performance criterion (quality robustness) 291.5.4. Respect of a fixed performance threshold 301.5.5. Deviation measures with respect to the optimum 301.5.6. Sensitivity and robustness 311.6. Bibliography 31Chapter 2. Robustness in Operations Research and Decision Aiding 35Bernard ROY2.1. Overview 352.1.1. Robust in OR-DA with meaning? 362.1.2. Why the concern for robustness? 372.1.3. Plan of the chapter 382.2. Where do “vague approximations” and “zones of ignorance” come from? – the concept of version 382.2.1. Sources of inaccurate determination, uncertainty and imprecision 382.2.2. DAP formulation: the concept of version 402.3. Defining some currently used terms 412.3.1. Procedures, results and methods 412.3.2. Two types of procedures and methods 422.3.3. Conclusions relative to a set ˆR of results 432.4. How to take the robustness concern into consideration 432.4.1. What must be robust? 442.4.2. What are the conditions for validating robustness? 452.4.3. How can we define the set of pairs of procedures and versions to take into account? 462.5. Conclusion 472.6. Bibliography 47Chapter 3. The Robustness of Multi-Purpose Machines Workshop Configuration 53Marie-Laure ESPINOUSE, Mireille JACOMINO and André ROSSI3.1. Introduction 533.2. Problem presentation 533.2.1. Modeling the workshop 543.2.1.1. Production resources 543.2.1.2. Modeling the workshop demand 553.2.2. Modeling disturbances on the data 553.2.3. Performance versus robustness: load balance and stability radius 573.2.3.1. Performance criterion for a configuration 573.2.3.2. Robustness 573.3. Performance measurement 573.3.1. Stage one: minimizing the maximum completion time 573.3.2. Computing a production plan minimizing machine workload 593.3.3. The particular case of uniform machines 603.4. Robustness evaluation 613.4.1. Finding the demands for which the production plan is balanced 613.4.2. Stability radius 643.4.3. Graphic representation 653.5. Extension: reconfiguration problem 683.5.1. Consequence of adding a qualification to the matrix Q 683.5.2. Theoretical example 693.5.3. Industrial example 703.6. Conclusion and perspectives 703.7. Bibliography 71Chapter 4. Sensitivity Analysis for One and m Machines 73Amine MAHJOUB, AzizMOUKRIM, Christophe RAPINE and Eric SANLAVILLE4.1. Sensitivity analysis 744.2. Single machine problems 784.2.1. Some analysis from the literature 784.2.2. Machine initial unavailability for 1__Uj  794.2.2.1. Problem presentation 794.2.2.2. Sensitivity of the HM algorithm 804.2.2.3. Hypotheses and notations 804.2.2.4. The two scenario case 814.3. m-machine problems without communication delays 834.3.1. Parametric analysis 834.3.2. Example of global analysis: Pm__Cj 854.4. The m-machine problems with communication delays 874.4.1. Notations and definitions 884.4.2. The two-machine case 904.4.3. The m-machine case 924.4.3.1. Some results in a deterministic setting 924.4.3.2. Framework for sensitivity analysis 934.4.3.3. Stability studies 934.4.3.4. Sensitivity bounds 944.5. Conclusion 954.6. Bibliography 96Chapter 5. Service Level in Scheduling 99Stéphane DAUZÈRE-PÉRÈS, Philippe CASTAGLIOLA and Chams LAHLOU5.1. Introduction 995.2. Motivations 1015.3. Optimization of the service level: application to the flow-shop problem 1035.3.1. Criteria computation 1035.3.2. Processing time generation 1045.3.3. Experimental results 1065.4. Computation of a schedule service level 1095.4.1. Introduction 1105.4.2. FORM (First Order Reliability Method) 1115.4.3. FORM vs Monte Carlo 1125.5. Conclusions 1185.6. Bibliography 119Chapter 6. Metaheuristics for Robust Planning and Scheduling 123Marc SEVAUX, Kenneth SÖRENSEN and Yann LE QUÉRÉ6.1. Introduction 1236.2. A general framework for metaheuristic robust optimization 1246.2.1. General considerations 1246.2.2. An example using a genetic algorithm 1266.3. Single-machine scheduling application 1276.3.1. Minimizing the number of late jobs on a single machine 1276.3.2. Uncertainty of deliveries 1296.3.2.1. Considered problem 1296.3.2.2. Robust evaluation function 1296.3.3. Results 1306.4. Application to the planning of maintenance tasks 1326.4.1. SNCF maintenance problem 1336.4.2. Uncertainties of an operational factory 1346.4.3. A robust schedule 1356.4.3.1. Variations of the unexpected factors 1376.5. Conclusions and perspectives 1396.6. Bibliography 140Chapter 7. Metaheuristics and Performance Evaluation Models for the Stochastic Permutation Flow-Shop Scheduling Problem 143Michel GOURGAND, Nathalie GRANGEON and Sylvie NORRE7.1. Problem presentation 1447.2. Performance evaluation problem 1477.2.1. Markovian analysis 1477.2.2. Monte Carlo simulation 1537.3. Scheduling problem 1557.3.1. Comparison of two schedules 1567.3.2. Stochastic descent for the minimization in expectation 1577.3.3. Inhomogenous simulated annealing for the minimization in expectation 1577.3.4. Kangaroo algorithm for the minimization in expectation 1597.3.5. Neighboring systems 1617.4. Computational experiment 1617.4.1. Exponential distribution 1627.4.2. Uniform distribution function 1647.4.3. Normal distribution function 1677.5. Conclusion 1677.6. Bibliography 168Chapter 8. Resource Allocation for the Construction of Robust Project Schedules 171Christian ARTIGUES, Roel LEUS and Willy HERROELEN8.1. Introduction 1718.2. Resource allocation and resource flows 1738.2.1. Definitions and notation 1738.2.2. Resource flow networks 1748.2.3. A greedy method for obtaining a feasible flow 1768.2.4. Reactions to disruptions 1768.3. A branch-and-bound procedure for resource allocation 1788.3.1. Activity duration disruptions and stability 1788.3.2. Problem statement and branching scheme 1798.3.3. Details of the branch-and-bound algorithm 1808.3.4. Testing for the existence of a feasible flow 1828.3.5. Branching rules 1838.3.6. Computational experiments 1848.3.6.1. Experimental setup 1848.3.6.2. Branching schemes 1858.3.6.3. Comparison with the greedy heuristic 1878.4. A polynomial algorithm for activity insertion 1878.4.1. Insertion problem formulation 1888.4.2. Evaluation of a feasible insertion 1898.4.3. Insertion feasibility conditions 1908.4.4. Sufficient insertions and insertion cuts 1918.4.5. Insertion dominance conditions 1928.4.6. An algorithm for enumerating dominant sufficient insertions 1938.4.7. Experimental results 1938.5. Conclusion 1948.6. Bibliography 195Chapter 9. Constraint-based Approaches for Robust Scheduling 199Cyril BRIAND, Marie-José HUGUET, Hoang Trung LA and Pierre LOPEZ9.1. Introduction 1999.2. Necessary/sufficient/dominant conditions and partial orders 2009.3. Interval structures, tops, bases and pyramids 2019.4. Necessary conditions for a generic approach to robust scheduling 2029.4.1. Introduction 2029.4.2. Scheduling problems under consideration 2049.4.3. Necessary feasibility conditions 2059.4.4. Propagation mechanisms 2069.4.4.1. Time constraint propagation 2069.4.4.2. Resource constraint propagation 2079.4.5. Interval structures for propagation 2089.4.5.1. Rank-interval based structures 2089.4.5.2. Task-interval based structures 2109.4.6. Discussion 2129.5. Using dominance conditions or sufficient conditions 2139.5.1. The single machine scheduling problem 2139.5.2. The two-machine flow-shop problem 2179.5.3. Future prospects 2219.6. Conclusion 2229.7. Bibliography 222Chapter 10. Scheduling Operation Groups: A Multicriteria Approach to Provide Sequential Flexibility 227Carl ESSWEIN, Jean-Charles BILLAUT and Christian ARTIGUES10.1. Introduction 22710.2. Groups of permutable operations 22810.2.1. History, principles and definitions 22810.2.2. Representation and evaluation 23010.2.2.1.Earliest start time computation 23210.2.2.2. Latest completion time computation 23410.2.2.3. Quality of a group schedule 23410.3. The ORABAID approach 23510.3.1. The proactive phase: searching for a feasible and acceptable group schedule 23510.3.1.1. Construction of a feasible group schedule 23610.3.1.2. Searching for acceptability of the group schedule 23710.3.1.3. Increasing the group schedule flexibility 23710.3.2. The reactive phase: real-time decision aid 23710.3.3. Some conclusions about ORABAID 23810.4. AMORFE, a multicriteria approach 23810.4.1. Flexibility evaluation of a group schedule 23910.4.2. Evaluation of the quality of a group schedule 24010.4.3. Some considerations about the objective function definition 24110.4.4. Quality guarantee in the best case 24310.4.4.1. Advantages 24310.4.4.2. Respect for quality in the best case 24310.5. Application to several scheduling problems 24410.6. Conclusion 24610.7. Bibliography 246Chapter 11. A Flexible Proactive-Reactive Approach: The Case of an AssemblyWorkshop 249Mohamed Ali ALOULOU and Marie-Claude PORTMANN11.1. Context 24911.2. Definition of the control model 25111.2.1. Definition of the problem and its environment 25111.2.2. Definition of a solution to the problem 25111.2.3. Definition of the solution quality 25211.2.3.1. Preliminary example 25211.2.3.2. Performance of a solution 25311.2.3.3. Flexibility of a solution 25511.3. Proactive algorithm 25611.3.1. General schema of the proposed genetic algorithm 25611.3.2. Selection and strategy of reproduction 25811.3.3. Coding of a solution 25811.3.4. Crossover operator 25811.3.5. Mutation operator 25911.4. Reactive algorithm 26011.4.1. Functions of the reactive algorithm 26011.4.2. Reactive algorithms in the absence of disruptions 26111.4.2.1. A posteriori quality measures 26111.4.2.2. Proposed algorithms 26311.4.3. Reactive algorithm with disruptions 26411.5. Experiments and validation 26411.6. Extensions and conclusions 26511.7. Bibliography 266Chapter 12. Stabilization for Parallel Applications 269Amine MAHJOUB, Jonathan E. PECERO SÁNCHEZ and Denis TRYSTRAM12.1. Introduction 27012.2. Parallel systems and scheduling 27012.2.1. Actual parallel systems 27012.2.2. Definitions and notations 27112.2.3. Motivating example 27312.3. Overview of different existing approaches 27512.4. The stabilization approach 27612.4.1. Stabilization in processing computing 27612.4.2. Example 27812.4.3. Stabilization process 28012.5. Two directions for stabilization 28012.5.1. The PRCP∗ algorithm 28112.5.2. Strong stabilization 28312.6. An intrinsically stable algorithm 28612.6.1. Convex clustering 28612.6.2. Stability analysis of convex clustering 29012.7. Experiments 29312.7.1. Impact of disturbances in the schedules of the three algorithms 29412.7.2. Influence of the initial schedule in the stabilization process 29512.7.3. Comparison of the schedules with and without stabilization 29712.7.4. Test 1 – comparison for Winkler graphs 29712.7.5. Test 2 – comparison for layer graphs 29812.8. Conclusion 29912.9. Bibliography 300Chapter 13. Contribution to a Proactive/Reactive Control of Time Critical Systems 303Pascal AYGALINC, Soizick CALVEZ and Patrice BONHOMME13.1. Introduction 30313.2. Static problem definition 30513.2.1. Autonomous Petri nets (APN) 30613.2.2. p-timePNs 30713.3. Step 1: computing a feasible sequencing family 31113.4. Step 2: dynamic phase 31713.4.1. Temporal flexibility 31713.4.2. Temporal flexibility and sequential flexibility 31913.4.2.1. Partial order in performance evaluation 32013.4.2.2. Partial order in proactive/reactive control 32213.5. Restrictions due to p-time PNs 32313.6. Bibliography 325Chapter 14. Small Perturbations on Some NP-Complete Scheduling Problems 327Christophe PICOULEAU14.1. Introduction 32714.2. Problem definitions 32814.2.1. Sequencing with release times and deadlines 32814.2.2. Multiprocessor scheduling 32914.2.3. Unit execution times scheduling 33014.2.4. Scheduling unit execution times with unit communication times 33114.3. NP-completeness results 33214.4. Conclusion 34014.5. Bibliography 340List of Authors 341Index 347