View source for 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|Automatic control theory]]), [[Operations research|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 [[#References|[a5]]]. Related theoretical disciplines are characterized by terms like [[Queueing theory|queueing theory]], hybrid systems, Petri nets (cf. [[Petri net|Petri net]]), path algebras, and generalized Markov processes (cf. [[Markov process|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|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|alphabet]] of a language, and sequences of events as words (cf. [[Word|Word]]) within that language. An [[Automaton|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

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d1102301.png" /></td> </tr></table>

where

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d1102302.png" /> is the set of states;

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d1102303.png" /> is the set of events associated with the transitions;

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d1102304.png" /> is the partial transition function;

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d1102305.png" /> is the feasible event function: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d1102306.png" /> is the set of all events <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d1102307.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d1102308.png" /> is defined;

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d1102309.png" /> is the initial state;

<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023010.png" /> is the set of marked states (upon entering a marked state, the system has completed some operation or task). The language generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023011.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023012.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023013.png" /> is the language consisting of all prefixes of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023014.png" />. The language marked by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023015.png" /> is defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023016.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023017.png" /> be partitioned into two disjoint subsets,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023018.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023019.png" /> is the set of controllable events, i.e. events that can be disabled by the supervisor, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023020.png" /> is the set of uncontrollable events (i.e. those events cannot be prevented from happening by control). Formally, a supervisor is a function

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023021.png" /></td> </tr></table>

For each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023022.png" /> generated up till now by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023023.png" /> (under the control of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023024.png" />), <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023025.png" /> is the set of enabled events that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023026.png" /> can execute at its current state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023027.png" />. The resulting system of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023029.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023030.png" />, to suggest that  "G is under the supervision of S" . The supervisor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023031.png" /> is said to be non-blocking if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023032.png" /> is non-blocking, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023033.png" />. A principal result is the following. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023034.png" />, the desired language, be given and satisfy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023035.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023036.png" />. There exists a non-blocking supervisor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023037.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023038.png" /> (given) such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023039.png" /> if and only if the following two conditions hold:

1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023040.png" />;

2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023041.png" />. References for this area are [[#References|[a2]]] and [[#References|[a7]]]. See also [[Control system|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|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

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023042.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023043.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023044.png" />-vector and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023045.png" /> an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023046.png" />-matrix with elements in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023047.png" />. The  "number"  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023048.png" /> 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|Eigen value]]). In the max-plus algebra, the inverse of the eigenvalue is a measure for the throughput of the system. The eigenvalue <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023049.png" /> and eigenvector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023050.png" /> in the latter case are defined as usual, i.e. by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023051.png" />, where, however, the used operations are maximization and addition again. Thus, one has

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023052.png" /></td> </tr></table>

Associated with the recurrence relation is a weighted digraph with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023053.png" /> nodes and an arc from node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023054.png" /> to node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023055.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023056.png" />. This graph is called the precedence graph of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023057.png" /> and is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023058.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023059.png" />, then the weight of the corresponding arc in the graph equals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023060.png" />. The mean weight of a path of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023061.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023062.png" /> can be interpreted as the maximum of the weights of all paths of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023063.png" /> that start at node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023064.png" /> and end at node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023065.png" />. A basic result is the following. Given a square matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023066.png" />, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023067.png" /> strongly connected, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023068.png" /> has one and only one eigenvalue and at least one eigenvector. The eigenvalue equals the maximum cycle mean of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023069.png" />, where the maximum is taken with respect to all circuits of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023070.png" />. A well-known numerical procedure to calculate the eigenvalue is the Karp algorithm, which reads:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023071.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023072.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023073.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023074.png" /> 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|Petri net]]), it is easy to give a discrete event interpretation of max-plus linear systems. The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023075.png" />th component of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023076.png" /> can often be interpreted as the time instant at which node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023077.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023078.png" /> has become active for the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023079.png" />th time. Thus, the argument <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023080.png" /> refers to a counter rather than to time. Within such applications, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023081.png" /> refers to the travelling time from node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023082.png" /> to node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023083.png" />, or to the holding time at node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023084.png" />, of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023085.png" />th token. References for this area are [[#References|[a2]]], [[#References|[a3]]] and [[#References|[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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023086.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023087.png" />;

ii) find <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023088.png" /> to minimize <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023089.png" />. Here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023090.png" /> is some parameter to be chosen from some set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023091.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023092.png" /> is the performance measure of interest; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023093.png" /> is the performance obtained over a specific sample path of the system and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023094.png" /> denotes the expectation with respect to all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023095.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023096.png" /> represents all random occurrences in the system. The theory of perturbation analysis describes conditions under which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023097.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023098.png" /> is a possibly small quantity and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d11023099.png" />, can be determined from the original experiment through which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d110230100.png" /> was obtained. Thus, it is not necessary to execute a new experiment with parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d110230101.png" />. Besides, a complicating factor is that the new experiment would be run with respect to another (also unknown) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d110230102.png" />. For small <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d110230103.png" /> one thus obtains an estimate for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d110230104.png" />. The next question to be considered is under which conditions one has

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d110230105.png" /></td> </tr></table>

where the argument <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d110/d110230/d110230106.png" /> has been added for clarity. This equality refers to unbiasedness of the estimator (cf. [[Unbiased estimator|Unbiased estimator]]). For many situations this question has been answered satisfactorily. References for this area are [[#References|[a2]]], [[#References|[a4]]] and [[#References|[a6]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  F.L. Baccelli,   G. Cohen,   G.J. Olsder,   and J.-P. Quadrat,   "Synchronization and linearity: an algebra for discrete event systems" , Wiley  (1992)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  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</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.A. Cuninghame-Green,   "Minimax algebra" , ''Lecture Notes in Economics and Mathematical Systems'' , '''166''' , Springer  (1979)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  P. Glasserman,   "Gradient estimation via perturbation analysis" , Kluwer Acad. Publ.  (1991)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  P. Glasserman,   D.D. Yao,   "Monotone structure in discrete-event systems" , Wiley  (1994)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  Y.C. Ho,   X. Cao,   "Perturbation analysis of discrete event dynamic systems" , Kluwer Acad. Publ.  (1991)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  P.J. Ramadge,   W.M. Wonham,   "Supervisory control of a class of discrete event processes"  ''SIAM J. Control Optim.'' , '''25'''  (1987)  pp. 206–230</TD></TR></table>