Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
---|---|---|---|---|---|
Searching... | 30000010240328 | QA402 D35 2013 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
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.
Author Notes
Philippe Declerck, LISA/ISTIA, University of Angers, France.
Table of Contents
Chapter 1 Introduction | p. 1 |
1.1 General introduction | p. 1 |
1.2 History and three mainstays | p. 2 |
1.3 Scientific context | p. 2 |
1.3.1 Dioids | p. 3 |
1.3.2 Petri nets | p. 4 |
1.3.3 Time and algebraic models | p. 5 |
1.4 Organization of the book | p. 7 |
Chapter 2 Consistency | p. 9 |
2.1 Introduction | p. 9 |
2.1.1 Models | p. 9 |
2.1.2 Physical point of view | p. 11 |
2.1.3 Objectives | p. 12 |
2.2 Preliminaries | p. 14 |
2.3 Models and principle of the approach | p. 17 |
2.3.1 P-time event graphs | p. 17 |
2.3.2 Dater form | p. 21 |
2.3.3 Principle of the approach (example 2) | p. 23 |
2.4 Analysis in the "static" case | p. 25 |
2.5 "Dynamic" model | p. 28 |
2.6 Extremal acceptable trajectories by series of matrices | p. 31 |
2.6.1 Lowest state trajectory | p. 32 |
2.6.2 Greatest state trajectory | p. 35 |
2.7 Consistency | p. 36 |
2.7.1 Example 3 | p. 41 |
2.7.2 Maximal horizon of temporal consistency | p. 44 |
2.7.3 Date of the first token deaths | p. 47 |
2.7.4 Computational complexity | p. 48 |
2.8 Conclusion | p. 50 |
Chapter 3 Cycle Time | p. 53 |
3.1 Objectives | p. 53 |
3.2 Problem without optimization | p. 55 |
3.2.1 Objective | p. 55 |
3.2.2 Matrix expression of a P-time event graph | p. 56 |
3.2.3 Matrix expression of P-time event graphs with interdependent residence durations | p. 57 |
3.2.4 General form Ax ≤ b | p. 59 |
3.2.5 Example | p. 60 |
3.2.6 Existence of a 1-periodic behavior | p. 61 |
3.2.7 Example continued | p. 65 |
3.3 Optimization | p. 67 |
3.3.1 Approach 1 | p. 67 |
3.3.2 Example continued | p. 69 |
3.3.3 Approach 2 | p. 70 |
3.4 Conclusion | p. 75 |
3.5 Appendix | p. 76 |
Chapter 4 Control with Specifications | p. 79 |
4.1 Introduction | p. 79 |
4.2 Time interval systems | p. 80 |
4.2.1 (min, max, +) algebraic models | p. 81 |
4.2.2 Timed event graphs | p. 82 |
4.2.3 P-time event graphs | p. 83 |
4.2.4 Time stream event graphs | p. 84 |
4.3 Control synthesis | p. 88 |
4.3.1 Problem | p. 88 |
4.3.2 Pedagogical example: education system | p. 89 |
4.3.3 Algebraic models | p. 91 |
4.4 Fixed-point approach | p. 92 |
4.4.1 Fixed-point formulation | p. 92 |
4.4.2 Existence | p. 95 |
4.4.3 Structure | p. 103 |
4.5 Algorithm | p. 107 |
4.6 Example | p. 111 |
4.6.1 Models | p. 111 |
4.6.2 Fixed-point formulation | p. 113 |
4.6.3 Existence | p. 114 |
4.6.4 Optimal control with specifications | p. 116 |
4.6.5 Initial conditions | p. 117 |
4.7 Conclusion | p. 118 |
Chapter 5 Online Aspect of Predictive Control | p. 119 |
5.1 Introduction | p. 119 |
5.1.1 Problem | p. 119 |
5.1.2 Specific characteristics | p. 120 |
5.2 Control without desired output (problem 1) | p. 122 |
5.2.1 Objective | p. 122 |
5.2.2 Example 1 | p. 123 |
5.2.3 Trajectory description | p. 124 |
5.2.4 Relaxed system | p. 125 |
5.3 Control with desired output (problem 2) | p. 127 |
5.3.1 Objective | p. 127 |
5.3.2 Fixed-point form | p. 128 |
5.3.3 Relaxed system | p. 129 |
5.4 Control on a sliding horizon (problem 3): online and offline aspects | p. 130 |
5.4.1 CPU time of the online control | p. 131 |
5.5 Kleene star of the block tri-diagonal matrix and formal expressions of the sub-matrices | p. 132 |
5.6 Conclusion | p. 138 |
Bibliography | p. 141 |
List of Symbols | p. 149 |
Index | p. 153 |