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.

Auteur

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.

Texte du rabat
Scheduling is a diverse research area, and scheduling problems arise from many application domains, such as production systems, logistics and computer science. Solving scheduling problems requires the use and knowledge of tools such as combinatorial optimization and exact or approximated algorithms. Flexibility is at the interface between predictive deterministic approaches and reactive or 'on-line' approaches. It exists when some information (which may not be complete or perfect) about the problem is known, which is fairly reliable and where it is likely that there will be a difference between the forecast plan and its execution. the purpose of flexibility is to provide on or more solutions tailored to the nature of the application in order to provide the ideal solution. Robustness, which characterizes the performance of an algorithm when data are subject to uncertainty, is defined as being able to be resistant to approximations and ignorance.

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, treating them with an emphasis on either flexibility o robustness, or both.

Contenu

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</...