Discrete event systems
Contents
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? . . .
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.
Last update by Guy
Cohen Jan. 14, 2000