Discrete Event Systems in Dioid Algebra and Conventional Algebra

ISBN-13: 9781848214613 / Angielski / Twarda / 2012 / 164 str.

Philippe Declerck

Opis

This book concerns the use of dioid algebra as (max, +) algebra to treat the synchronization of tasks expressed by the maximum of the ends of the tasks conditioning the beginning of another task - a criterion of linear programming. A classical example is the departure time of a train which should wait for the arrival of other trains in order to allow for the changeover of passengers.
The content focuses on the modeling of a class of dynamic systems usually called -discrete event systems- where the timing of the events is crucial. Events are viewed as sudden changes in a process which is, essentially, a man-made system, such as automated manufacturing lines or transportation systems. Its main advantage is its formalism which allows us to clearly describe complex notions and the possibilities to transpose theoretical results between dioids and practical applications.

Spis treści

Chapter 1. Introduction  1

1.1. General introduction  1

1.2. History and three mainstays  2

1.3. Scientific context   2

1.3.1. Dioids   3

1.3.2. Petri nets   4

1.3.3. Time and algebraic models   5

1.4. Organization of the book   7

Chapter 2. Consistency   9

2.1. Introduction    9

2.1.1. Models   9

2.1.2. Physical point of view   11

2.1.3. Objectives   12

2.2. Preliminaries   14

2.3. Models and principle of the approach   17

2.3.1. P–time event graphs   17

2.3.2. Dater form   21

2.3.3. Principle of the approach (example 2)  23

2.4. Analysis in the static case  25

2.5. Dynamic model   28

2.6. Extremal acceptable trajectories by series of matrices    31

2.6.1. Lowest state trajectory   32

2.6.2. Greatest state trajectory  35

2.7. Consistency    36

2.7.1. Example 3   41

2.7.2. Maximal horizon of temporal consistency   44

2.7.3. Date of the first token deaths    47

2.7.4. Computational complexity   48

2.8. Conclusion   50

Chapter 3. Cycle Time   53

3.1. Objectives    53

3.2. Problem without optimization    55

3.2.1. Objective   55

3.2.2. Matrix expression of a P–time event graph   56

3.2.3. Matrix expression of P–time event graphs with interdependent residence durations   57

3.2.4. General form Ax b   59

3.2.5. Example    60

3.2.6. Existence of a 1–periodic behavior   61

3.2.7. Example continued   65

3.3. Optimization    67

3.3.1. Approach 1   67

3.3.2. Example continued   69

3.3.3. Approach 2   70

3.4. Conclusion   75

3.5. Appendix    76

Chapter 4. Control with Specifications   79

4.1. Introduction    79

4.2. Time interval systems    80

4.2.1. (min, max, +) algebraic models   81

4.2.2. Timed event graphs   82

4.2.3. P–time event graphs   83

4.2.4. Time stream event graphs   84

4.3. Control synthesis   88

4.3.1. Problem    88

4.3.2. Pedagogical example: education system   89

4.3.3. Algebraic models    91

4.4. Fixed–point approach  92

4.4.1. Fixed–point formulation  92

4.4.2. Existence   95

4.4.3. Structure   103

4.5. Algorithm    107

4.6. Example    111

4.6.1. Models   111

4.6.2. Fixed–point formulation  113

4.6.3. Existence   114

4.6.4. Optimal control with specifications  116

4.6.5. Initial conditions    117

4.7. Conclusion   118

Chapter 5. Online Aspect of Predictive Control    119

5.1. Introduction    119

5.1.1. Problem    119

5.1.2. Specific characteristics   120

5.2. Control without desired output (problem 1)  122

5.2.1. Objective   122

5.2.2. Example 1   123

5.2.3. Trajectory description   124

5.2.4. Relaxed system  125

5.3. Control with desired output (problem 2)  127

5.3.1. Objective   127

5.3.2. Fixed–point form  128

5.3.3. Relaxed system  129

5.4. Control on a sliding horizon (problem 3): online and offline aspects   130

5.4.1. CPU time of the online control   131

5.5. Kleene star of the block tri–diagonal matrix and formal expressions of the sub–matrices  132

5.6. Conclusion   138

Bibliography    141

List of Symbols    149

Index    153