Introduction to Petri Nets Dynamic Behavior Modeling in Manufacturing Systems
This material delves into Petri nets as a tool for modeling dynamic behavior in manufacturing systems. It covers formal definitions, analysis methods, reduction, synthesis, and properties of Petri net models. The content explores various reduction rules with accompanying illustrations, providing insights into the modeling of manufacturing systems using Petri nets.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Chapter 3 Petri nets part II Learning objectives : Introduce Petri nets Dynamic behavior modeling of manufacturing systems using PN Analysis of Petri net models Textbook : J.-M. Proth and X. Xie, Petri nets: a tool for design and management of manufacturing systems, John Wiley & Sons, 1996 C. Cassandras and S. Lafortune, Introduction to Discrete Event Systems, Springer, 2007 1
Plan Introduction to Petri nets Formal definitions Petri net models of manufacturing system Elementary classes of Petri nets Properties of PN models Analysis methods Reduction and Synthesis of ordinary Petri nets Timed Petri nets Modeling repetitive manufacturing systems Time Petri nets 2 2
Reduction and synthesis of ordinary Petri nets 3
Petri net reduction R1 : Merging of serial places p1 p12 M0(p12) = M0(p1) + M0(p2) t p2 Conditions : p1 = {t}, t = {p1}, t = {p2} 4
Petri net reduction R2 : Merging of serial transitions t1 p t12 t2 Conditions : M0(p) = 0, p = {t1}, p = {t2}, t2 = {p}. 5
Petri net reduction R3 : Removal of identical places t1 t1 p1 p2 p1 t2 t2 Conditions : M0(p1) = M0(p2), p1 = p2, p1 = p2 . 6
Petri net reduction R4 : Removal of identical transitions t2 t1 t1 Conditions : t1 = t2, t1 = t2 . 7
Petri net reduction R5 : Removal of implicit places p t Conditions : p = p , M0(p) > 0. 8
Petri net reduction R6 : Removal of neutral transitions t p Conditions : t = t = {p}, p p {t}. 9
Petri net reduction Thereom (property perservation of reduction rules) : Let N be a Petri net and N' be a reduced net obtained by rules R1- R6. Then, N is live iff (if and only if) N' is live; N is bounded iff N' is bounded; N is safe iff N' is safe, if place p of rule R5 is such that M0(p) = 1; N is reversible iff N' is reversible, if place p2 of rule R1 has a single input transition. 10
Petri net reduction Example (homework): p2 t3 p1 t1 t2 p5 t7 t9 p7 t8 p8 p9 t10 r2 r3 r1 p6 t4 p3 p4 t6 t5 R2: (t1,p1,t2), (t4,p3,t5), (t7, p7, t8), (t9, p9, t10) R2: (t78, p8, t9,10) + R5 Bounded, not live, not reversible, not safe. 11
Petri net reduction Example: p2 t3 p1 t1 t2 p5 t7 t9 p7 t8 p8 p9 t10 r2 r3 r1 p6 t4 p3 p4 t6 t5 Bounded Live reversible R2: (t1,p1,t2), (t4,p3,t5), (t7, p7, t8), (t9, p9, t10) R2: (t78, p8, t9,10) + R5 R2: (t12, p2, t3), (t45, p4, t6) + R5 R1: (r2, t123, p5), (r3, t456, p6) + R5 12
Top-down Petri net synthesis Principle: Top-down synthesis starts from an initial PN that is expanded progressive. At each step, a place or a transition is replaced by a Petri net. Expansion of a transition t Assumption : t is not 2-firable, i.e. it cannot be simultaneously fired twice. tin p0 Definitions : A bloc is a PN with a source transition Tin and a sink transition Tout The associated PN of a bloc is a PN obtained by connecting Tout to Tin with an place p0 containing 1 token. A bloc is said well-formed if its associated PN is live, M0 is the only reachable marking such that p0 is marked, and Tin is the only firable transition at M0. tout 13
Top-down Petri net synthesis Examples of well-formed blocs. Tin Tin Tout Tout 14
Top-down Petri net synthesis Theorem : Let N, B and N' be an initial PN, associated PN of a well-formed bloc, and the PN obtained by expansion. Then N' is live (resp. bounded or reversible) of N and B are live (resp. bounded or reversible). Expansion of a place p equivalent to the expansion of a transition p t p' Bottom-up Petri net synthesis approaches also exist. 15
P-timed Petri nets Definition: A P-timed Petri net is a triplet (N, M0, tempo) where (N, M0) is a marked Petri net with N = (P, T, Pre, Post); tempo : P R+is a temporization function that associates with each place pi a time tempo(pi) = di. 17
P-timed Petri nets Evolution of the marking over time t1 t1 t1 t1 d1 d1 p1 d1 p1 p1 d1 p1 t2 t2 t2 t2 d2 d2 p2 d2 p2 p2 d2 p2 t3 t3 t3 t3 Mi(p1) d1 Md(p1) Mi(p2) d2 t1 t2 18
P-timed Petri nets Firing rules: R1: for a time di. It is said unavailable during this time and becomes available after. R2: At any time, the marking M is the sum of two markings Mu and Ma corresponding to respectively unavailable tokens and available ones. R3: A transition is firable if it is at marking Ma. R4: The firing of a transition is the same as for untimed Petri nets. Each token arriving in a place pi should stay at least Assumption : transitions fire as soon as they are enabled (earliest operating mode). 19
P-timed Petri nets Reachability of a P-timed Petri net: The state of the PN is represented by the number of tokens in each place and the remaining sojourn time of each token. Transition from marking M1 to M2 is labeled as tj / d where tj is the transition and d the sojourn time in M1. When several transitions fires simultaneously, it is marked (ti, tj ) / d. d1 = 2 p1 t2/1 t1/2 (t1t2) /0 1 (0) 1 (0) 0 2 (1,3) 1 (2) 1 (2) 1 (2) 1 (3) t1 d2 = 3 p2 (t1t2)/2 t2 20
P-timed Petri nets Theorem: If the underlying PN (N, M0) is bounded and the temporizations are rational numbers, then (i) reachability graph is finite; (ii) the earliest operating mode leads to a periodic regime (also called stationary regime) in finite time for any given priority rule for conflict transitions sorting. 21
P-timed Petri nets Definitions: - Firing frequency fi of a transition ti is the number of times ti fires during a time unit; - Cycle time Ci = 1 / fi. Thereom 1: For any periodic regime of a bounded PN, the firing frequency vector F = (f1, f2, , fm) is a t-invariant. Theorem 2: For any strongly connected P-timed event graph, the firing frequency is the same for all transitions and the cycle time is given by C = max{C( ), } where is the set of elementary circuits and C( ) = p tempo(p) / M0( ). Example: 22
T-timed Petri nets Definition: A T-timed Petri net is a triplet (N, M0, tempo) where (N, M0) is a marked Petri net with N = (P, T, Pre, Post); tempo : T R+is a temporization function that associates with each transition ti a time tempo(ti) = di. 23
T-timed Petri nets Evolution of the marking over time t1 t1 t1 d1 d1 d1 t1 d1 p1 p1 p1 p1 t2 t2 d2 d2 t2 d2 d2 t2 p2 p2 p2 p2 t3 t3 d3 d3 t3 d3 t3 d3 Mn(p1) Mr(p1) Mn(p2) t1 d1 t2 d2 24
T-timed Petri nets Firing rules: R1: Each token is either reserved for the firing of a transition tj or not reserved. R2: At any time, the marking M is the sum of two markings Mr and Mn of reserved tokens and not reserved ones. R3: A transition is firable if it is at marking Mn. R4: During the firing of a transition tj, tokens needed for its firing are reserved in its input places. The firing completes after a time dj. At this moment, reserved tokens are removed and not reserved tokens are added to its output places. Assumption : transitions fire as soon as they are enabled (earliest operating mode). 25
T-timed Petri nets Reachability of a T-timed Petri net: The state of the PN is represented by the number of tokens in each place and the remaining firing time of each transition firing. Transition from marking M1 to M2 is labeled as tj / d where tj is the transition and d the sojourn time in M1. When several transitions fires simultaneously, it is marked (ti, tj ) / d. p1 t2/1 t1/2 (t1t2) /0 1 (0) 1 (0) 0 2 (1,3) 1 (2) 1 (2) d1 = 2 1 (2) 1 (3) t1 p2 (t1t2)/2 t2 d2 = 3 26
T-timed Petri nets Theorem: If the underlying PN (N, M0) is bounded and the temporizations are rational numbers, then (i) reachability graph is finite; (ii) the earliest operating mode leads to a periodic regime (also called stationary regime) in finite time for any given priority rule for conflict transitions sorting. 27
T-timed Petri nets Definitions: - Firing frequency fi of a transition ti is the number of times ti fires during a time unit; - Cycle time Ci = 1 / fi. Thereom 1: For any periodic regime of a bounded PN, the firing frequency vector F = (f1, f2, , fm) is a t-invariant. Theorem 2: For any strongly connected T-timed event graph, the firing frequency is the same for all transitions and the cycle time is given by C = max{C( ), } where is the set of elementary circuits and C( ) = t tempo(t) / M0( ). Example: 28
Equivalence of P-timed and T-timed Petri nets d1=0 p1 p2 d2=0 p2 p1 t d p5 d5=d p4 p3 d4=0 p4 d3=0 p3 P-timed T-timed t2 d1=0 t1 d2=0 t1 t2 p d t5 d5=d t3 t4 d4=0 t4 t3 d3=0 T-timed P-timed 29
Algebra representation of T-timed event graphs Notation: xi(k) : starting time of k-th firing of transition ti Recursive equations: x1(k) = max{x1(k-1)+d1, x2(k-1) + d2} x2(k) = x1(k-1)+d1 x1(1) = x2(1) = 0 (max, +) linear algebra representation: x1(k) = x1(k-1) d1 x2(k-1) d2 x2(k) = x1(k-1) d1 x2(k-1) where = +, = max, = - (nul element) p3 p1 t1 d1 = 2 p2 t2 d2 = 3 ( ) ( ) ( ( ) ) 1 x k x k d d d Matrix representation: 1 1 1 2 = 1 x k x k 1 2 2 30
Algebra representation of T-timed event graphs Notation: xi(k) : starting time of k-th firing of transition ti mij: initial marking of place connecting ti to tj Recursive equations: xi(k) = max{xj(k-mij)+dj, (i,j) P} (max, +) linear algebra representation: ( i j ij j p3 p1 t1 d1 = 2 p2 t2 d2 = 3 ( ) ) ( ) = x k x k m d j Results hold also for P-timed event graphs Extended theory of (max, +) linear algebra available in the book "Synchronization and Linearity: An Algebra for Discrete Event Systems" 31
Modeling repetitive manufacturing systems with timed Petri nets 32
System specifications System: a manufacturing system composed of three machines M1, M2, M3 producing two types of parts P1 and P2. Part routing: P1 : (M1, 4), (M2, 2), (M3, 1) P2 : (M3, 2), (M2, 1) Product mix: 50% P1 and 50% P2. Transportation resources: Each on-going part requires a pallet. There are 2 pallets for P1 and one for P2. Assumptions: Repetitive or cyclic production: One P1 and one P2 are produced in each production cycle; Each machine serves the parts cyclically according to the following input sequences: M1: <P1>, M2: <P1, P2>, M3: <P1, P2>. 33
Modeling repetitive manufacturing systems Step 1 : Modeling part routings P1 t2(2) t3(1) t1(4) P2 t5(1) t4(2) Repeat twice the model of P1 if a production cycle is (2*P1, 1*P2). 34
Modeling repetitive manufacturing systems Step 2 : Modeling transportation resources (process circuits) P1 t2(2) t3(1) t1(4) P2 t5(1) t4(2) 35
Modeling repetitive manufacturing systems Step 3 : Modeling input sequences of the machines (command circuits) p3 t1(4) t2(2) t3(1) p2 p1 P1 p9 M3 M2 M1 p8 p7 p6 p10 P2 p4 t5(1) t4(2) p5 36
Results Strongly connected t-timed event graph; Live, bounded, reversible; Cycle time of elementary circuits : t1p1t2p2t3p3t1 t4p4t5p5t4 t1p6t1 t2p8t5p7t2 t3p10t4p9t3 t2p2t3p10p4t5p7t2 t2p8t5p5t4p9t3p3t1p1t2 System cycle time : C = max{C( ), } = 6. M( ) 2 1 1 1 1 1 4 C( ) 7/2 3/1 4/1 3/1 3/1 6/1 10/4 System throughput rate: one P1 + one P2 per 6 time units. Maximum thoughput rate with C = 4 reached if M0(p2) = M0(p3) = 1, i.e. start with an on-going P1 at time 0. 37
Definition A time Petri net is a triplet (N, M0, INT) where (N, M0) is a marked Petri net with N = (P, T, Pre, Post); INT : T R+x R+is a temporization function that assicates with each transition t an interval [a, b]. INTi = [ai, bi] = time interval associated with transition ti is such that ai ( 0 ai) is the minimal time during which ti remains firable before it actually fires bi (0 b ) is the maximum time during which ti remains firable before it is forced to fire. Assumption: No transition is two-firable, i.e. can initiate two simultaneous firings. (relaxable assumption) 39
Example Proc. B proc. A Initial state: M0 = [1000101], 1 t1 6 p5 p1 p3 (2,3) (1,6) t1 fires at 1 t3 t1 State : M1 = [0111101], 1 t2 6, 2 t3 3, 1 t5 4 p4 p2 p6 Case t2 fires next at 1+ 2 (1,4) (1,6) t2 t4 t5 1 2 3, M2 = [1011101], 1 t1 6, max{0, 2 - 2} t3 3 - 2, max{0, 1 - 2} t5 4 - 2. (1,4) p7 Proc. C Case t3 fires next at 1+ 2 2 2 3, M2 = [0101011], 1 t4 4, max{0, 1 - 2} t2 6 - 2, max{0, 1 - 2} t5 4 - 2. Case t5 fires next at 1+ 2 1 2 4, M2 = [0110101], max{0, 1 - 2} t2 6 - 2, max{0, 1 - 2} t5 4 - 2. 40
State of a time Petri net at any time t S = (M, I) where M is the marking at time t; I indicate, for each firable transition ti, the interval (EFTi, LFTi) of remaining time to actual firing, i.e. ti can fire at any time in [t + EFTi, t + LFTi]. Proc. B proc. A p5 p1 p3 (2,3) (1,6) t3 t1 p4 p2 p6 (1,4) (1,6) t2 t4 t5 (1,4) p7 Proc. C Example : At time t=0, S = (M0, I1 = (1, 6)). At time t = 1, S = (M1, I2 = (1, 6), I3 = (2, 3), I5 = (1, 4)). 41
Firing rules R1 : With any given state S = (M, I) at time t, transition ti is the next transition at time t + if (i) ti is firable at M, (ii) EFTi mink{LFTk}. Proc. B proc. A p5 p1 p3 (2,3) (1,6) t3 t1 p4 p2 p6 (1,4) (1,6) R2 : Firing ti leads to the state S' = (M', I') with M(t> M', EFTi' = max(0, EFTi - ), LFTi' = LFTi - , for all other on-going transitions ti, EFTi' = ai, LFTi' = bi, for all newly enabled transitions ti. t2 t4 t5 (1,4) p7 Proc. C Remark: Starting from a state, an infinite number of states can be reached by choosing different . 42
State classes A state class is a group of states reachable by firing the same transition ti. Class representation: C = (M, D) where M is the marking and D the domain of remaining times of all firable transitions Canonic form of a class C = (M, D) where D is expressed as follows: ai ti bi, for any firable transition ti; tj - tk gjk, for all couples of firable transitions tj and tk where ai = earliest date of ti ai = latest date of ti gjk = largest difference of tj - tk. Ck Sk ti at 1 ti at 20 ti Ci =(M', I1+I2+ ) S1=(M', I1) S1=(M', I20) 43
State class graph Proc. B proc. A Initial state: M0 = [1000101], 1 t1 6 t1 fires at 1 State : M1 = [0111101], 1 t2 6, 2 t3 3, 1 t5 4 Case t2 fires next state class C2 = {M2 = [1011101], D2} D2 = {1 t1 6 (new transition), D2(a) (old transitions)} D2(a) = 1 t2 6 t2 t3 2 t3 3 t2 t5 1 t5 4 change of variables by t3 = t2+t3', t5 = t2+t5' 1 t2 6 t2 t2+t3' 2 t2 + t3' 3 1 t2+t5' 4 Fourier-Motzkin elimination of t2 p5 p1 p3 (2,3) (1,6) t3 t1 p4 p2 p6 (1,4) (1,6) t2 t4 t5 (1,4) p7 Proc. C Fourier-Motzkin elimination ( ( 1 1 , , j r B x x = ) ( ) , , , , , x A x x x B x x 1 1 1 1 r i r r j r t2 t2+t5' ) ( ) , , A x x 1 1 i r D2 = 1 4-t5' 2-t3' 6 1-t5' 3- t3' 1 3- t3' 2-t3' 4-t5' 1-t5' 6 1 t2 6 2-t3' t2 3-t3' 1-t5' t2 4-t5' 1 t1 6 0 t3 2 0 t5 3 -2 t3-t5 D2(a)= 0 t3' 0 t5' 0 t3' 0 t5' 44
A producer-consumer data transfer protocole BE t3 t1 t2 t5 p1 p2 cons prod BF t4 prod Ready to send a message p1 Sending a message p2 Arrival of the message at the consumer site cons Consumer reading the message BE Buffer empty BF Buffer full t1 producer sending a message t2 transmission medium t5 message reading t3 normal arrival at an empty buffer t4 Arrival at a full buffer and overwriting existing message (undesired situation) Specification 1 : INT1 = [4, 6], INT2 = [2, 3], INT3 = INT4 = [0, 0], INT5 = [0, 2]. Specification 2 : INT1 = [4, 6], INT2 = [2, 3], INT3 = INT4 = [0, 0], INT5 = [0, 4]. 45
Topics not addressed in Chapters 2-3 Supervisory control with automata theory Color Petri nets Petri net controls Petri net models synthesis 46
Topics not addressed in Chapters 2-3 Supervisory control with automata theory Timed Petri nets Color Petri nets Petri net controls Petri net models synthesis 47
