Discrete event systems


The beginning of the story

System and Control Theory, alias Automatic Control, focussed from the very beginning on systems generally described by ordinary differential or partial differential equations to which the corresponding physical phenomena obey. The advent of computers sometimes inclines one to describe their evolution by using discrete time dynamic equations, which does not change the intrinsic continuous nature of this evolution.

On the other hand, linearity is a very welcome mathematical property which greatly simplifies the handling of mathematical models. In the 70's and 80's, Nonlinear Automatic Control emerged, after the 60's have been the golden age of Linear System Theory. Nonlinear Automatic Control generally addresses "smooth" dynamical equations only.

With the advances in technology, Man started building more and more complex and completely artificial systems, at least at the conceptual level of their operation which is appropriate for their management and control. To fix ideas, let us quote

These are of course but a few examples. In these systems, the main dynamic mechanism in task succession stems from the following phenomena

This type of dynamics cannot be captured by differential equations or by their discrete time analogues. This is certainly the reason why those systems, which are nevertheless true dynamic systems, have long been disregarded by Automatic Control experts and have been rather considered by Operations Researchers, specialists of Manufacturing, Computer scientists, etc., according to the application domain of interest, while no general "System Theory" managed to emerge. However, one can mention a graphically oriented theory (Petri nets), a probabilistic theory (queueing networks), etc., which had no strong connections with System Theory.

What was new in the 80's was the fact that the Automatic Control world happened to take these new systems into account. They were then referred to as "Discrete Event (Dynamic) Systems" (DES or DEDS). The word "discrete" does not mean that "time is discrete", nor does it necessarily implies that "state is discrete" (indeed, as one can see, state variables may assume continuous values) but this word refers to the fact that the dynamics are made up of events; these events may possibly have a continuous evolution once they start, but this is not what one is interested in: the primary focus is on the beginning and the end of such events, since ends can cause new beginnings.

To end up with this general description, let us say that the theory of DES can be divided presently into two or three main approaches:

The Max Plus approach in a few words

In a few words, this approach is characterized by:

In this framework, timed event graphs can be considered as linear systems which are relevant to a theory having a strong analogy with conventional linear system theory.


Want to know more? . . .

Small glossary

discrete event system
Dioid or idempotent semiring
algebraic structure endowed with an addition which is associative, commutative, with a "zero" element, with a multiplication which is associative, with a "one" element, the multiplication being distributive with respect to addition, zero being absorbing for multiplication (zero times a equals zero for all a); at last, addition is idempotent, namely a plus a equals a for all a.
Event graph
Petri net in which each place has a single upstream (input) and a single downstream (output) transition, hence there is no competition in the supply of tokens to places nor in the consumption of tokens out of places; transitions may have several inputs and outputs, hence synchronization constraints can be represented in those graphs.

  Back to the list of contents

Last update by Guy Cohen Jan. 14, 2000