Discrete event systems

Contents

• The beginning of the story
• The Max Plus approach in a few words
• The research team
• Some surveys and course notes
• Other sources of information

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

• transportation networks,
• communication and computer networks,
• CPU of computers themselves,
• manufacturing workshops, in particular their modern "flexible" form.

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

• synchronization (our main concern),
• mutual exclusion or competition in the use of common resources, which requires a policy to arbitrate conflicts and define priorities, all kinds of problems generally referred to under the generic terminology of scheduling.

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 logical approach which considers the occurrence of events or the impossibility of this occurrence ("deadlock") and the series of these events, but which does not consider the precise time of those occurrences, that is, which does not consider performances; W.M. Wonham et P. Ramadge, and after them numerous researchers, have extended the paradigm of control to Automata and Formal Language Theory: the control can inhibit some state transitions to avoid running into undesired behaviors (more mathematically, one tries to force the automaton to produce only a specified sublanguage of the language this automaton can produce without control);
• the quantitative approach which addresses the issue of "performance evaluation" (evaluated by the number of events occurring in a given lapse of time), and that of performance optimization; in this general framework, two schools can be distinguished:
  • the "perturbation analysis" approach, opened by Y.C. Ho (by the way, probably the father of the expression "Discrete Event Dynamic Systems") and all the variants which followed, the purpose of which is to solve all kinds of non classical optimization problems, due to the "discrete event" aspect, generally in a stochastic framework;
  • the "Max Plus" approach, which is the center of our research activity in this field, and thus the main concern hereafter.

The Max Plus approach in a few words

In a few words, this approach is characterized by:

• the use of an adequate algebra, the so-called "Max Plus" algebra (essentially, the addition of two numbers consists of their maximum, whereas the multiplication of two numbers is the usual plus; for example 3 plus 5 equals 5, and 3 times 5 equals 8), or more generally, the dioid algebra (or idempotent semiring);
• the limitation to certain classes of DES, indeed those which only involve synchronization phenomena (this assumes that competition is already settled by a scheduling policy at a higher level); essentially, these systems can be modelled, in the Petri net paradigm, by the subclass of event graphs;
• the performance evaluation focus (the corresponding event graphs are thus timed event graphs).

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.

However,

• on the one hand, our interest is not necessarily limited to DES which are linear in any dioid algebra;
• on the other hand, dioid algebra has other applications in addition to that of DES theory, and these applications are also of interest for us.

Want to know more? . . .

• your browser accommodate frames;
• your browser does not accommodate frames.

Small glossary

DES

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