2 Modeling and Control of Discrete-event Dynamic Systems

discrete variables and relations defined on them. A hybrid system is a combination

of both.
Sometimes the relations of system variables are not treated with respect to time.
Then they describe the static behavior of the studied systems. However, time is
mostly involved in the analysis and synthesis of systems and dynamic system
behavior is considered.
Figure 1.1 illustrates the classification of continuous and discrete systems
considering dynamic behavior. In order to simplify the illustration, a system with
one variable is depicted. Figure 1.1.a shows the case when the continuous variable
x(t ) is a continuous function over a continuous time interval. The function domain
and co-domain are real numbers. A system is continuous if it is defined by
continuous variables and continuous functions such as the function depicted in
Figure 1.1.a. A discrete system is given by discrete variables and discrete functions
or relations as illustrated by Figure 1.1.b. The system in Figure 1.1.b consists of
one object in the form of one variable that takes on values from the set of real
numbers in discrete time points.

Figure 1.1. Properties of one-variable system

Figures 1.1.c and 1.1.d show the mixed/hybrid cases when the system is semi-
continuous. Usually, a system has more than one object or variable. Then a set of
variables can be aggregated into one or more vector variables. Note that the case
 Basic Description of Discrete-event Dynamic Systems 3

depicted in Figure 1.1.b can be understood either as a discrete representation of a

continuous system or as a representation of the system that is discrete by its nature.
The role of the semantics or interpretation is obvious. Therefore, the discrete or
digital representation of continuous systems has to be distinguished from the
representation of systems that are discrete in their nature and substance. The
discrete representation of a continuous system is obtained by sampling continuous
variables at discrete time points.
Continuity and discreteness of a system is one aspect of the view on system
properties. Another aspect is that CVDS are time-driven systems. The reason for
the dynamic development of system states is time. On the other hand, discrete
systems can be time-driven or event-driven.

States

q4

q3

q2
q1

e1 e3 e1 e2 e2 t

Figure 1.2. An event-driven system

Let us compare Figures 1.1 and 1.2. The discrete variable q describes the state
of the system. There are four states q1, q2, q3, and q4, q1-4 for short, and three events
e1, e2, and e3, e1-3 for short. Figure 1.2 shows that the state change is event-driven.
The events occur at discrete time points and the state changes depend on the events
only. Such systems are called discrete event dynamic systems or DEDS for short
(Ho 1991; Ho and Cassandras 1983). They are also called discrete event systems
(Ramadge and Wonham 1987; Zhou and DiCesare 1993; Jafari 1995; Bogdan et al.
2006). As mentioned earlier, Figure 1.1.b has a double meaning. It can represent
either time-driven CVDS or event-driven DEDS when the events occur at discrete
time points and cause the change of system states as depicted in Figure 1.1.b.
The applied system analysis and synthesis methods depend on the system
nature. In this textbook we will study systems that are fully discrete in their nature
and event-driven, i.e., discrete event dynamic systems. Their name expresses their
specific character. DEDS are characterized by a set of states which the system can
take, and by the set of events that cause the state changes at discrete time points.
The events may take place asynchronously as opposed to the synchronous nature in
a discrete time system. The change of states and occurrence of events are the
essence of the DEDS dynamic behavior.
A primary task of the DEDS theory is creating a DEDS model. Without such a
model it would be impossible to analyze and control DEDS just as it is true in
classic CDVS control theory. Obviously we are interested in a model that is
4 Modeling and Control of Discrete-event Dynamic Systems

sufficiently general and includes the DEDS dynamics. There are two ways to
consider the dynamics:

1. To specify values of the system variables and system relations in defined

discrete time points; and
2. To specify time order of the states or events.

The latter case means that time is not explicitly expressed and only the precedence
relations for DEDS states and events are given. The order of events can be
determined by means of their indexing. In other words, it is given which event
happens before some other events. Such an approach is more abstract and avoids
problems related to the time relativity.
The control of DEDS can be designed if there is a DEDS model available.
Control engineering design methods perform the following tasks:
• Formulation and specification of the given system control tasks;
• Determination of control algorithms;
• Design of technical means necessary for the control implementation;
• Creation and verification of control programs; and
• Implementation, testing and maintenance of the control system function.
Control engineering is an applied interdisciplinary technical science. To a
considerable extent, the solution methods are independent of the technological
substance of controlled systems. For a control it is important to achieve such an
influence of various agents on the system that parameters and behavior of the
system are as required (Kozák 2002; Jörgl 1993). The system behavior and various
influences on it are given by physical, chemical, biological or other quantity values.
What is important from the viewpoint of control is the information the quantities
carry, but not their physical substance.
Automatic control is based on the information manifestations of the system. In
other words, a system is described by means of information about the spatial
location of objects, time, system parameters, properties, characteristics, etc. Time
is substantial for the dynamics of events. As mentioned earlier, the time evolution
of system variables is called the process and in the context of DEDS, it is called the
discrete process.

1.2 Discrete Variables and Relations

The notion of DEDS has been specified in the previous section. It is based on the
discrete character of the individual variables and relations. It is useful to study the
property of discreteness in some detail.

Definition 1.1. Let D be a finite set of n elements, i.e.,

D = {d 1 , d 2 ,..., d n } (1.1)
 Basic Description of Discrete-event Dynamic Systems 5

Let v be a variable taking on values only from set D , i.e.,

v = di ∈ D (1.2)

then v is a discrete variable.

Definition 1.2. Let two non-empty finite sets D and E be given:

D = {d1 , d 2 ,..., d n } (1.3)

E = {e1 , e2 ,..., em } (1.4)

A binary relation R from D into E is defined by

R ⊆ D× E (1.5)

where symbol × denotes the Cartesian product.

If a relation is defined on the sets for which D = E = A then R ⊆ A × A and we
say that R is a binary relation on A . The relation R can be empty. If, e.g.,
(d 2 , e3 )∈ R we write d 2 R e3 . Functions or mappings are subsets of relations.
They are special relation cases as formally given next.

Definition 1.3. Let a binary relation R from D = {d1 , d 2 ,...d n } into

E = {e1 , e2 ,..., em } be given. Let for any two elements of D × E

(d , e )∈ D × E, (d
i j k , el ) ∈ D × E ,
(1.6)
i ∈ {1,2,..., n}, j ∈ {1,2,..., m}, k ∈ {1,2,..., n}, l ∈ {1,2,..., m}

If the following implication holds true

(d i ) (( )
= d k and e j ≠ el ⇒ d i , e j ∉ R and (d k , el ) ∉ R ) (1.7)

then the relation R is a discrete function or a discrete mapping notated f defined

on the domain

DOM = {di1 , di2 ,..., dis } (1.8)

(
where DOM is the set of all first elements of the pairs d i , e j belonging to the )
relation R . A co-domain of the function is set CDOM that consists of all the
( )
second elements of the pairs d i , e j belonging to the relation R

CDOM = {ei1 , ei2 ,..., eiu } (1.9)

6 Modeling and Control of Discrete-event Dynamic Systems

We write

e j = f (d i ), d i ∈ DOM , e j ∈ CDOM (1.10)

The right-hand side of Equation (1.7) is an AND conjunction of two

propositions. If the premise is true, they both are true. It means that both ordered
( )
pairs d i , e j and (d k , el ) cannot belong to the relation R. However, one of them
can be in R. Another formulation of this can be as follows. A function is a binary
relation from set D = { d1 , d 2 ,..., d n } into set E = { e1 , e2 ,..., em } if there are no two
( )( )
ordered pairs d p , er , d p , ev in R such that er ≠ ev .

1.3 Discrete Processes

Let a finite set Σ be given as

Σ = { e1 , e2 ,..., en } (1.11)

The set Σ is called the event set. We assume that an event eik ∈ Σ occurs at the
time point τ ik . Let a sequence of events be given as

σ~ = ei1 , ei2 ,..., eik ,..., ei N (1.12)

where e i ∈ Σ occurs in the discrete time point τ i1 , ei2 ∈ Σ in time point τ i2 , etc.,
1

eik in time point τ i , etc., and eiN in time point τ i , τ i 〈τ i 〈.....〈τ i 〈.....〈τ i . The
k N 1 2 k N

sequence σ~ is called a discrete process. In this particular case when elements of a

sequence are events we speak about the event string.
Figure 1.3 shows layout of a manufacturing system including a milling machine
M, a grinding machine G and three belt conveyors C1–C3. The parts to be
processed in the manufacturing system come into the system irregularly with
various gaps as a sequence one by one part. Maximum three parts can be fed up on
the conveyor C1. Input of a part is detected by a photo-sensor P11. The part is
stopped by a stopper at the end of C1. Presence of the part at the end of the
conveyor is signalized by a photo-sensor P12. If the milling machine M is free and
a part is available at the end of C1, the part is transferred by the transportation
means T1 into the milling machine. After milling the part is transferred by T2 onto
the conveyor C2. The photo-sensor P21 detects input of the part on the conveyor
C2. In the conveyor section between the sensors P21 and P22 there can be
maximum two parts. The same mechanism holds for loading of the grinding
machine G. Maximum four parts can be loaded on the conveyor section P31–P32.