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

Table of Content

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

About the author

Philippe Declerck is Senior Lecturer LISA / ISTIA Laboratory at University of Angers, France.