Discrete event system
The theory of discrete event systems, sometimes also referred to as discrete event dynamic systems to emphasize the evolution in time, encompasses a variety of classes of problems and of modelling approaches. A succinct definition of a discrete event system that sets such systems apart from others is hard to give. Two key features of a discrete event system are: i) its dynamics is event driven as opposed to time driven, i.e. the behaviour of a discrete event system is governed only by occurrences of different types of events over time rather than by ticks of a clock; and ii) its state variables belong to a discrete (not necessarily finite) set. Theoretical disciplines that support the study of discrete event systems include systems theory (cf. Automatic control theory), operations research and theoretical computer science. In this article, three important approaches to the description and analysis of discrete event systems will be given. It depends on the field of application which one is the more suitable to use. Common to these approaches are various monotony properties, see [a5]. Related theoretical disciplines are characterized by terms like queueing theory, hybrid systems, Petri nets (cf. Petri net), path algebras, and generalized Markov processes (cf. Markov process). Applications are found specifically in the areas of flexible manufacturing, communication networks and logistic systems.
Logical approach.
Problems in which the precise ordering of events, and not their timing, is of interest, which must satisfy a given set of specifications, are conveniently modelled within the context of the theory of automata and formal languages (cf. Formal languages and automata). A discrete event system is typically represented as a set of state variables that are linked by transitions. The set of state transitions, called events, can be considered as the alphabet of a language, and sequences of events as words (cf. Word) within that language. An automaton can be viewed simply as a device that generates a language by the manipulation of the alphabet according to a specific set of rules. Control aspects can be added in the sense that certain events (i.e. transitions) can be disabled by an external controller. The resulting systems and control theory for discrete event systems is known as supervisory control theory. This theory addresses the synthesis of controllers (i.e. supervisors) for discrete event systems to satisfy a set of qualitative specifications on the admissible orderings of the events that can be executed by the system.
Let the automaton be described by
![]() |
where
is the set of states;
is the set of events associated with the transitions;
is the partial transition function;
is the feasible event function:
is the set of all events
for which
is defined;
is the initial state;
is the set of marked states (upon entering a marked state, the system has completed some operation or task). The language generated by
is denoted by
;
is the language consisting of all prefixes of
. The language marked by
is defined by
. Let
be partitioned into two disjoint subsets,
![]() |
where is the set of controllable events, i.e. events that can be disabled by the supervisor, and
is the set of uncontrollable events (i.e. those events cannot be prevented from happening by control). Formally, a supervisor is a function
![]() |
For each generated up till now by
(under the control of
),
is the set of enabled events that
can execute at its current state
. The resulting system of
and
is denoted by
, to suggest that "G is under the supervision of S" . The supervisor
is said to be non-blocking if
is non-blocking, i.e.
. A principal result is the following. Let
, the desired language, be given and satisfy
and
. There exists a non-blocking supervisor
for
(given) such that
if and only if the following two conditions hold:
1) ;
2) . References for this area are [a2] and [a7]. See also Control system.
Timed approach.
Modelling of discrete event systems via the max-plus algebra approach is suitable when timing of the events plays an essential role. The starting point is a "linear" model, linear in the sense of the max-plus algebra, i.e. the algebra in which the admissible operations are maximization and addition, rather than the more conventional addition and multiplication. The basic system studied is defined by the recurrence relation
![]() |
where is an
-vector and
an
-matrix with elements in
. The "number"
has been added because it is the neutral element with respect to maximization. The numerical evaluation of the recurrence relation is completely standard, except that the conventional addition is replaced by maximization, and the conventional multiplication is replaced by addition. Just as with linear recurrence relations in the conventional setting, the eigenvalue and eigenvector are important quantities to describe the behaviour of the recurrence relation in the max-plus algebra setting (cf. also Eigen value). In the max-plus algebra, the inverse of the eigenvalue is a measure for the throughput of the system. The eigenvalue
and eigenvector
in the latter case are defined as usual, i.e. by
, where, however, the used operations are maximization and addition again. Thus, one has
![]() |
Associated with the recurrence relation is a weighted digraph with nodes and an arc from node
to node
if
. This graph is called the precedence graph of
and is denoted by
. If
, then the weight of the corresponding arc in the graph equals
. The mean weight of a path of
is defined as the sum of all weights along this path (called the weight of the path), divided by the length of this path. If such a path happens to be a circuit, then one talks about the mean weight of the circuit, or equivalently, the cycle mean. The quantity
can be interpreted as the maximum of the weights of all paths of length
that start at node
and end at node
. A basic result is the following. Given a square matrix
, with
strongly connected, then
has one and only one eigenvalue and at least one eigenvector. The eigenvalue equals the maximum cycle mean of
, where the maximum is taken with respect to all circuits of
. A well-known numerical procedure to calculate the eigenvalue is the Karp algorithm, which reads:
![]() |
where and
are to be evaluated in the max-plus algebra; the other operations (subtraction and division) are conventional ones.
Various extensions exist. If input and output terms are added to the recurrence relation, one enters the field of "discrete event systems theory" , which has many parallels which the conventional linear systems theory. Other extensions are, for instance, the study of systems where the underlying algebra is more exotic than the conventional or max-plus algebra, and the study of recurrence relations where the elements are stochastic quantities. There is a natural relationship with the description of flows of tokens in so-called (timed) event graphs, which are a special class of (timed) Petri nets. Within the terminology of the theory of Petri nets (cf. Petri net), it is easy to give a discrete event interpretation of max-plus linear systems. The
th component of
can often be interpreted as the time instant at which node
in
has become active for the
th time. Thus, the argument
refers to a counter rather than to time. Within such applications,
refers to the travelling time from node
to node
, or to the holding time at node
, of the
th token. References for this area are [a2], [a3] and [a1].
Stochastic approach.
Yet another approach to discrete event systems is given by the theory of perturbation analysis. This theory is motivated by the fact that the state trajectory (or sample path) of a discrete event system observed under a given set of conditions contains a surprising amount of information about the behaviour of the system under different conditions one might be interested in. This is particularly important when analytical models are unavailable or simply inadequate for discrete event systems of considerable complexity, especially in a stochastic environment. The aim is to satisfy a set of quantitative specifications and to optimize the performance of a discrete event system. Two basic problems are
i) evaluate for all
;
ii) find to minimize
. Here,
is some parameter to be chosen from some set
and
is the performance measure of interest;
is the performance obtained over a specific sample path of the system and
denotes the expectation with respect to all
, where
represents all random occurrences in the system. The theory of perturbation analysis describes conditions under which
, where
is a possibly small quantity and
, can be determined from the original experiment through which
was obtained. Thus, it is not necessary to execute a new experiment with parameter
. Besides, a complicating factor is that the new experiment would be run with respect to another (also unknown)
. For small
one thus obtains an estimate for
. The next question to be considered is under which conditions one has
![]() |
where the argument has been added for clarity. This equality refers to unbiasedness of the estimator (cf. Unbiased estimator). For many situations this question has been answered satisfactorily. References for this area are [a2], [a4] and [a6].
References
[a1] | F.L. Baccelli, G. Cohen, G.J. Olsder, and J.-P. Quadrat, "Synchronization and linearity: an algebra for discrete event systems" , Wiley (1992) |
[a2] | C.G. Cassandras, S. Lafortune, G.J. Olsder, "Introduction to the modelling, control and optimization of discrete event systems" A. Isidori (ed.) , European Control Conf. , Springer (1995) pp. 75 |
[a3] | R.A. Cuninghame-Green, "Minimax algebra" , Lecture Notes in Economics and Mathematical Systems , 166 , Springer (1979) |
[a4] | P. Glasserman, "Gradient estimation via perturbation analysis" , Kluwer Acad. Publ. (1991) |
[a5] | P. Glasserman, D.D. Yao, "Monotone structure in discrete-event systems" , Wiley (1994) |
[a6] | Y.C. Ho, X. Cao, "Perturbation analysis of discrete event dynamic systems" , Kluwer Acad. Publ. (1991) |
[a7] | P.J. Ramadge, W.M. Wonham, "Supervisory control of a class of discrete event processes" SIAM J. Control Optim. , 25 (1987) pp. 206–230 |
Discrete event system. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Discrete_event_system&oldid=46731