Discrete Event Systems in Dioid Algebra and Conventional Algebra: Declerck/Discrete Event Systems in Dioid Algebra and Conventional Algebra

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. Content: Chapter 1 Introduction: Discrete Event Systems (pages 1–8): Philippe Declerck Chapter 2 Consistency (pages 9–52): Philippe Declerck Chapter 3 Cycle Time (pages 53–78): Philippe Declerck Chapter 4 Control with Specifications (pages 79–118): Philippe Declerck Chapter 5 Online Aspect of Predictive Control (pages 119–140): Philippe Declerck Discrete Event Systems in Dioid Algebra and Conventional Algebra......Page 2 Copyright......Page 3 Contents......Page 4 1.1. General introduction......Page 8 1.3. Scientific context......Page 9 1.3.1. Dioids......Page 10 1.3.2. Petri nets......Page 11 1.3.3. Time and algebraic models......Page 12 1.4. Organization of the book......Page 14 2.1.1. Models......Page 16 2.1.2. Physical point of view......Page 18 2.1.3. Objectives......Page 19 2.2. Preliminaries......Page 21 2.3.1. P-time event graphs......Page 24 2.3.2. Dater form......Page 28 2.3.3. Principle of the approach example 2......Page 30 2.4. Analysis in the “static? case......Page 32 2.5. “Dynamic? model......Page 35 2.6. Extremal acceptable trajectories by series of matrices......Page 38 2.6.1. Lowest state trajectory......Page 39 2.6.2. Greatest state trajectory......Page 42 2.7. Consistency......Page 43 2.7.1. Example 3......Page 48 2.7.2. Maximal horizon of temporal consistency......Page 51 2.7.3. Date of the first token deaths......Page 54 2.7.4. Computational complexity......Page 55 2.8. Conclusion......Page 57 3.1. Objectives......Page 59 3.2.1. Objective......Page 61 3.2.2. Matrix expression of a P-time event graph......Page 62 3.2.3. Matrix expression of P-time event graphs with interdependent residence durations......Page 63 3.2.4. General form Ax ≤ b......Page 65 3.2.5. Example......Page 66 3.2.6. Existence of a 1-periodic behavior......Page 67 3.2.7. Example continued......Page 71 3.3.1. Approach 1......Page 73 3.3.2. Example continued......Page 75 3.3.3. Approach 2......Page 76 3.4. Conclusion......Page 81 3.5. Appendix......Page 82 4.1. Introduction......Page 85 4.2. Time interval systems......Page 86 4.2.1. min, max, + algebraic models......Page 87 4.2.2. Timed event graphs......Page 88 4.2.3. P-time event graphs......Page 89 4.2.4. Time stream event graphs......Page 90 4.3.1. Problem......Page 94 4.3.2. Pedagogical example: education system......Page 95 4.3.3. Algebraic models......Page 97 4.4.1. Fixed-point formulation......Page 98 4.4.2. Existence......Page 101 4.4.3. Structure......Page 109 4.5. Algorithm......Page 113 4.6.1. Models......Page 117 4.6.2. Fixed-point formulation......Page 119 4.6.3. Existence......Page 120 4.6.4. Optimal control with specifications......Page 122 4.6.5. Initial conditions......Page 123 4.7. Conclusion......Page 124 5.1.1. Problem......Page 125 5.1.2. Specific characteristics......Page 126 5.2.1. Objective......Page 128 5.2.2. Example 1......Page 129 5.2.3. Trajectory description......Page 130 5.2.4. Relaxed system......Page 131 5.3.1. Objective......Page 133 5.3.2. Fixed-point form......Page 134 5.3.3. Relaxed system......Page 135 5.4. Control on a sliding horizon problem 3: onlineand offline aspects......Page 136 5.4.1. CPU time of the online control......Page 137 5.5. Kleene star of the block tri-diagonal matrix and formal expressions of the sub-matrices......Page 138 5.6. Conclusion......Page 144 Bibliography......Page 147 List of Symbols......Page 154 Index......Page 157

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.