IST / DEEC / ACSDC

MEEC 2007-2008

Industrial Automation
(Automao de Processos Industriais)

Discrete Event Systems

h // http://www.isr.ist.utl.pt/~pjcro/courses/api0708/api0708.html i i l / j / / i0708/ i0708 h l
Prof. Paulo Jorge Oliveira pjcro @ isr.ist.utl.pt Tel: 21 8418053 or 2053 (internal)
API P. Oliveira Page 1

IST / DEEC / ACSDC

MEEC 2007-2008

Syllabus:
Chap. 5 CAD/CAM and CNC [1 week] ... Chap. 6 Discrete Event Systems [2 weeks] Discrete event systems modeling. Automata. Petri Nets: state, dynamics, and modeling. Extended and strict models. Subclasses of Petri nets. Chap. 7 Analysis of Discrete Event Systems [2 weeks]
API P. Oliveira Page 2

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Some pointers to Discrete Event Systems

History: Tutorial: i l http://prosys.changwon.ac.kr/docs/petrinet/1.htm http://vita.bu.edu/cgc/MIDEDS/ h // i b d / / S/ http://www.daimi.au.dk/PetriNets/ http://www.ppgia.pucpr.br/~maziero/petri/arp.html (in Portuguese) http://wiki.daimi.au.dk:8000/cpntools/cpntools.wiki http://www.informatik.hu-berlin.de/top/pnk/download.html

Analyzers, and Simulators:

Bibliography:

* Cassandras, Christos G., "Discrete Event Systems - Modeling and Performance Analysis", Aksen Associates, 1993. * Peterson, James L., "Petri Net Theory and the Modeling of Systems", Prentice-Hall,1981. * Petri Nets and GRAFCET: Tools for Modelling Discrete Event Systems R. DAVID, H. ALLA, New York : PRENTICE HALL Editions, 1992
P. Oliveira Page 3

API

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Generic characterization of systems resorting to input / output t t relations l ti State equations:

&(t ) = f ( x(t ),u(t ),t ) x y(t ) = g ( x(t ),u(t ),t )

in continuous time (or in discrete time) Examples?

API

P. Oliveira

Page 4

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Open loop vs close-loop ( the use of feedback)

Advantages of feedback? (to revisit during SEDs supervision study)

API P. Oliveira Page 5

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Example of close-loop with feedback

API

P. Oliveira

Page 6

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Discrete Event Systems: Examples Set of events: E={N, S, E, W}

API

P. Oliveira

Page 7

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Characteristics of systems with continuous variables 1. State space is continuous 2. The state transition mechanism is time-driven Characteristics of systems with discrete events 1. State space p is discrete 2. The state transition mechanism is event-driven Polling is avoided!
API P. Oliveira Page 8

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Taxonomy of Systems

API

P. Oliveira

Page 9

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Levels of abstraction in the study of Discrete Event Systems

Languages Timed languages Stochastic timed languages

API

P. Oliveira

Page 10

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Discrete Event Systems: Examples Queueing systems

Queue Clients arrival

Server Clientes departure

API

P. Oliveira

Page 11

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Discrete Event Systems: Examples Computational Systems

CPU Processes P Arrival

CPU Processes Departure

CPU

API

P. Oliveira

Page 12

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Systems Theory Objectives

Modeling and Analysis Design e synthesis Control / Supervision Performance assessment and robustness Optimization

Applications of Discrete Event Systems

Queueing systems Operating systems and computers Telecommunications networks Distributed databases Automation
API P. Oliveira Page 13

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Discrete Event Systems

Typical modeling methodologies

Automata

GRAFCET

Augmenting in modeling capacity and complexity

Petri nets
API P. Oliveira Page 14

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Automata Theory and Languages

Genesys of computation theory Definition: A language L, defined over the alphabet E is a set of strings of finite length with events from E. Exemplos: E={, ,} L1={, , , } L2={all strings of length 3}

How to build a machine that talks a given language?

or

What language talks a system?

API P. Oliveira Page 15

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Properties of languages Kleene-closure E*: set of all strings of finite length of E, including the null element .

Concatenation:

La Lb := s E * : s = sa sb , sa La , sb Lb
Prefix-closure:

L := s E * : tE * st L
API

}
Page 16

P. Oliveira

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Automata Theory and Languages

Definition: A deterministic automata is a 5-tuple

(E, X, f, x0 ,F)
onde: E X f x0 F - finite alphabet (or possible events) - finite set of states - state transition function - initial state f: X x E ->X x0 X

- set of final states or marked states F E

API

P. Oliveira

Page 17

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Example of a automata (E, X, f, x0 ,F)

E = {, ,} X = {x, y, z} x0 = x F = {x, {x z} f(x, ) = x f(y, ) = x f(z, ) = y
API

f(x, ) = z f(y, ) = y f(z, ) = z

f(x, ) = z f(y, ) = y f(z, ) = y

P. Oliveira Page 18

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Example of a stochastic automata (E, X, f, x0 ,F)

E = {, } X = {0, 1} x0 = 0 F = {0} f(0, ) = {0, 1} f(1, ) = {} f(0, ) = {} f(1, ) = 0

API

P. Oliveira

Page 19

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Given a language

G=(E, X, f, x0 ,F)
Generated language

L(G) := {s : f(x0,s) is defined}

Marked language

Lm(G) := {s : f(x0,s) F}
API P. Oliveira Page 20

10

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Example: marked language of an automata b 0 a b 1 a

Lm(G) := {a, aa, ba, aaa, baa, bba, }

Note: all strings with events a e b, followed by event a.

API

P. Oliveira

Page 21

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Automata equivalence: The automata G1 e G2 are equivalent if

L(G1) = L(G2) e Lm(G1) = Lm (G2)

API P. Oliveira Page 22

11

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Example of an automata:
Objective: To validate a sequence of events

API

P. Oliveira

Page 23

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Deadlocks (inter-blocagem) Example: 1 a 0 g 2 The state 5 is a deadlock. The states 3 and 4 constitutes a livelock.
API

g a 3 a b

How to find the deadlocks and the livelocks? Methodologies g for the analysis Of Discrete Event Systems
P. Oliveira Page 24

12

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Deadlock: in general the following relations are verified

Lm (G ) Lm (G ) L(G )
An automata G has a deadlock if and is not blocked when

Lm (G ) L(G )
Lm (G ) = L(G )

API

P. Oliveira

Page 25

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Deadlock: Example: 1 a 0 g 2 The state 5 is a deadlock. The states 3 and 4 constitutes a livelock.
API

g a 3 a b

Lm (G ) = {ab, ag , abgab, abgabgab,...} , a, ab, ag , aa, aab, L(G ) = abg , aaba, abga,...
5

(Lm (G ) L(G ))

Lm (G ) L(G )
P. Oliveira Page 26

13

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Alternative way to detect deadlocks: Example: 1 a 0 g 2 The state 5 is a deadlock. The states 3 and 4 constitutes a livelock.
API

g a 3 a b

5 0

0 g 5

a 1 a b 3 b 4 a 3
P. Oliveira Page 27

2 0

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Timed Discrete Event Systems

API

P. Oliveira

Page 28

14

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Petri nets
Developed by Carl Adam Petri in his PhD thesis in 1962. Definition: A marked Petri net is a 5-tuple

(P, T, A, w, x0)
where: P T A w x0
API

- set of places - set of transitions - set of arcs - weight function - initial marking A (P x T) (T x P) w: A x0 : P
P. Oliveira Page 29

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Example of a Petri net (P, T, A, w, x0)

P={p1, p2, p3, p4, p5} T={t1, t2, t3, t4} A={(p1, t1), (t1, p2), (t1, p3), (p2, t2), (p3, t3), (t2, p4), (t3, p5), (p4, t4), (p5, t4), (t4, p1)} w(p (p1, t1) )=1, w(t ( 1, p2) )=1, w(t ( 1, p3) )=1, w(p (p2, t2) )=1 w(p3, t3)=2, w(t2, p4)=1, w(t3, p5)=1, w(p4, t4)=3 w(p5, t4)=1, w(t4, p1)=1 x0 = {1, 0, 0, 2, 0}

API

P. Oliveira

Page 30

15

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Petri nets Rules to follow (mandatory):

An A arc (di (directed t d connection) ti ) can connect t places l to t transitions t iti An arc can connect transitions to places A transition can have no places as inputs (source) A transition can have no places as outputs (sink) The same happens with the input and output transitions for places

API

P. Oliveira

Page 31

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Example of a Petri net (P, T, A, w, x0)

P={p1, p2, p3, p4, p5} T={t1, t2, t3, t4} A={(p1, t1), (t1, p2), (t1, p3), (p2, t2), (p3, t3), (t2, p4), (t3, p5), (p4, t4), (p5, t4), (t4, p1)} w(p (p1, t1) )=1, w(t ( 1, p2) )=1, w(t ( 1, p3) )=1, w(p (p2, t2) )=1 w(p3, t3)=2, w(t2, p4)=1, w(t3, p5)=1, w(p4, t4)=3 w(p5, t4)=1, w(t4, p1)=1 x0 = {1, 0, 0, 2, 0}

Petri net graph

p1 t1 p2 t2 p4 3 t4 2 p3 t3 p5

API

P. Oliveira

Page 32

16

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Alternative definition of a Petri net

A marked Petri net is a 5-tuple

where: P T I O

(P, T, I, O, 0)
- set of places - set of transitions - transition input function - transition output function - initial marking I: P T O: T P

0
API

0 : P
P. Oliveira Page 33

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Example of a Petri net and its graphical representation

Alternative definition

p1
(P, T, I, O, 0)
P={p1, p2, p3, p4, p5} T={t1, t2, t3, t4} I(t1)={p1} I(t2)={p2} I(t3)={p3, p3} I(t4)={p4, p4, p4, p5} O(t1)={p2 , p3} O(t2)={p4} O(t3)={p5} O(t4)={p1}

t1 p2 t2 p4 3 t4 2 p3 t3 p5

0 = {1, 0, 0, 2, 0}

API

P. Oliveira

Page 34

17

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Petri nets The state of a Petri net is characterized h i d by b the h marking ki of all places.
p2

p1 t1 p3 3 t2

The set of all possible markings of a Petri net corresponds to its state space space.

How does the state of a Petri net evolves?

API

P. Oliveira

Page 35

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Dynamics of Petri nets A transition i i tj is i enabled bl d if: if

pi P : ( pi ) # ( pi , I (t j ))
A transition tj is enabled to fire, resulting in a new marking given by

( pi ) = ( pi ) # ( pi , I ( t j )) + # ( pi ,O( t j ))

API

P. Oliveira

Page 36

18

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Petri nets
Example of evolution of a P i net Petri Initial marking: 0 = {1, 0, 1, 2, 0}

.
p2 t2 p4

p1 t1

. . ..
3

. .. p
2

This discrete event system can not change state. It is in a deadlock!

t3
5

.p
t4
P. Oliveira

API

Page 37

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Petri nets: Conditions and Events

Conditions: a) The server is idle. b) A job arrives and waits to be processed c) ) The Th server i is processing i th the job j b d) The job is complete Events 1) Job arrival 2) Server starts processing 3) Server finishes processing 4) The job is delivered Event Pre-conditions Pre conditions 1 2 3 4
API

Pos conditions Pos-conditions b c d,a P. Oliveira Page 38

a,b c d

19

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Petri nets: Conditions and Events

Event 1 2 3 4
Job arrival

Pre-conditions a,b c d
Start of processing

Pos-conditions b c d,a End of processing Job is delivered

Jobs waits processing

Job is beeing processed

Job is complete

Server is idle API P. Oliveira Page 39

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Petri nets
Modeling mechanisms
Concurrence Conflict

t1
t1

t2

t2

API

P. Oliveira

Page 40

20

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Petri nets
Modeling mechanisms
Mutual Exclusion Producer / Consumer

t1

Critical Section

t2

Critical Section

to produce

to consume

API

P. Oliveira

Page 41

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Petri nets
Modeling mechanisms
Producer / Consumer with finite capacity Readers / Writers

s
to produce

t n

B
n n

to consume
to read

n n

to write

B'

API

P. Oliveira

Page 42

21

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Discrete Event Systems

Example of a simple automation system modelled using PNs
t9

An automatic soda selling machine accepts 50 c and $1 coins and sells 2 types of products: SODA A, that costs $1.50 and SODA B, that costs $2.00. Assume that the money return operation is omitted.

t1

p2

t4 p4

t5 p1 t2 t6 p3 t3

t7

p5

t8

p1: machine with $0.00; t1: coin of 50 c introduced; t8: SODA B sold. P. Oliveira Page 43

API

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Extentions to Petri nets

Switches [Baer 1973]
f e f e f e f e

Possible to be implemented with restricted Petri nets.

API

P. Oliveira

Page 44

22

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Extentions to Petri nets

Inhibitor Arcs Equivalent to nets with priorities

Can be implemented with restricted Petri nets? Zero tests... Infinity tests...
API P. Oliveira Page 45

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Extentions to Petri nets

P-Timed nets

Job arrival

Start of processing

End of processing

Job is delivered

Jobs waits processing

Job is beeing processed

Job is complete

Server is idle

API

P. Oliveira

Page 46

23

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Extentions to Petri nets

T-Timed nets

Job arrival

Start of processing

End of processing

Job is delivered

Jobs waits processing

Job is beeing processed

Job is complete

Server is idle

API

P. Oliveira

Page 47

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Extentions to Petri nets

Stochastic nets

Stochastic switches

Transitions with stochastic timmings described by a stochastic variable with known pdf

q0

q1

q2

q0+q1+ q2 =1

API

P. Oliveira

Page 48

24

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Discrete Event Systems

Sub-classes of Petri nets
State Machine: Petri nets where each transition has exactly one input arc and one output arc. Marked Graphs Petri nets where each place has exactly one input arc and one output arc.

API

P. Oliveira

Page 49

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Discrete Event Systems

Example of DES:
Manufacturing system composed b 2 machines by hi (M1 and d M2) and da robotic manipulator (R). This takes the finished parts from machine M1 and transports them to M2. No buffers available on the machines. If R arrives near M1 and the machine is busy, y, the p part is rejected. j If R arrives near M2 and the machine is busy, the manipulator must wait. Machinning time: M1=0.5s; M2=1.5s; RM1 M2=0.2s; RM2 M1=0.1s;
API P. Oliveira Page 50

M1

M2

25

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Discrete Event Systems

Example of DES:
Variables of M1 M2 R x1 x2 x3
M1 M2

Example of arrival of parts:

1 em { 0.1, 0.7 , 1.1, 1.6 , 2.5 } a( t ) = 0 em todos os outros ins tan tes

x1={Idle, Busy, Waiting} x2={Idle, Busy} x3={Idle, Carrying, Returning}

API

P. Oliveira

Page 51

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Discrete Event Systems

Example of DES:
Definition of events: a1 d1 r1 r2 d2 r3
API

- loads part in M1 - ends part processing in M1 - loads manipulator - unloads manipulator p and loads M2 - ends part processing in M2 - manipulator at base
P. Oliveira Page 52
R M1 M2

26

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Discrete Event Systems

a1 d1 r1 r2 1 2 3 4 t
x1
W B I

x2

B I

r3 d2

x3
R C I

1
API

P. Oliveira

Page 53

IST / DEEC / ACSDC

Chap. 6 Discrete Event Systems

Discrete Event Systems

Example of DES:
Events: a1 - loads part in M1 d1 - ends part processing in M1 r1- loads manipulator r2- unloads manipulator and loads M2 d2- ends part processing in M2 r3- manipulator at base

pea nova

M1

M2

Idle

Idle r1

Idle r2 Busy d2

rejeita pea Busy d1 W iti Waiting

M2

Carrying

M1

Returning
R

r3

API

P. Oliveira

Page 54

27