Introduction to Generalized Stochastic Petri Nets (GSPN) in Manufacturing Systems
Explore Generalized Stochastic Petri Nets (GSPN) to model manufacturing systems and evaluate steady-state performances. Learn about stochastic Petri nets, inhibitors, priorities, and their applications through examples. Delve into models of unreliable machines, productions systems with priorities, and reachability graphs to understand system behaviors.
Uploaded on Oct 05, 2024 | 0 Views
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 5 Generalized stochastic Petri nets (GSPN) Learning objectives : Introduce generalized stochastic Petri nets (GSPN) Model manufacturing systems using GSPN Able to evaluate the steady-state performances Textbooks : M. Ajmone Marsan, G. Balbo, G. Conte, S. Donatelli, and G. Franceschinis, Modelling with Generalized Stochastic Petri Nets. J. Wiley, 1995 G. Chiola, M. Ajmone Marsan, G. Balbo, and G. Conte. Generalized stochastic Petri nets: A definition at the net level and its implications. IEEE Transactions on Software Engineering, 19(2):89--107, 1993 1
Plan Introduction to stochastic Petri nets by examples Petri nets with inhibitors and priority Generalized stochastic Petri nets Applications Extensions 2
Example 1 Consider an unreliable machine with: 1/ : mean time between failures (MTTF) 1/ : mean time to repair (MTTR) 1/p : mean processing time Markov chain Stochastic Petri net model p1 p3 p p2 Legend: 1 0 t2 (p) t1 t3 immediate tr. t4 ( ) timed tr. t5 ( ) p4 3
Example 1 Reachability graph Stochastic Petri net model p1 1000 p3 t1 t4 p2 Legend: 0001 0100 t3 t2 (p) t1 t3 immediate tr. t2 t5 t4 ( ) timed tr. 0010 t5 ( ) p4 Removing transient states leads to an isomorphic CTMC : p 0100 0001 4
Example 1 Results 0001= ( + ) 0100= ( + ) Failure rate (frequence of t4) = ( + ) Production rate (frequence of t2) : p = p ( + ) Remark : The conflict between t2 and t4 is solved by competition of clocks (failure models) p1 p3 p2 Legend: t2 (p) t1 t3 p immediate tr. 0100 0001 t4 ( ) timed tr. t5 ( ) p4 5
Example 2 Two types of products P1 and P2 are produced. The production of each product requires two operations with o the first operation on a shared flexible machine o the second operation on a dedicated machine. P1 has priority to the shared machine but cannot preempt on- going operations There is at most one product of each type in the system at all moment When the production of a product is finished, a new one of the same type is dispatched into the system 6
Example 2 Stochastic Petri net model : i : priority level i Higher priority of 2 than 1 p1 p4 2 1 t1 t4 p7 p2 p5 M t2 t5 p3 p6 t3 t6 P2 P1 P1 has priority to the shared machine 7
Example 2 Reachability graph : Markov chain : 1001001 M1 p1 p4 M2 0101000 2 t1 1 t1 t4 p7 M2 0101000 M4 0010100 t2 p2 p5 t3 M3 0011001 M t4 t2 t5 M5 1000100 t5 M4 0010100 p3 p6 t3 M7 0100010 M5 1000100 t3 t6 t5 M6 0010011 t6 1000011 M8 t1 t6 M7 0100010 Convention : Immediate transitions have priority over timed transitions t2 t3 t6 0010011 M8 8
Example 2 M2 0101000 Results for the case i = = : = = = = = 1/5 M4 0010100 Utilization ratio of the shared machine: + + + = 4/5 M5 1000100 M7 0100010 Production rate of P1 (frequence of t3) : + = 0010011 M8 p1 p4 2 1 Production rate of P2 (frequence of t6) : + = (!!!) t1 t4 p7 p2 p5 M t2 t5 p3 p6 t3 t6 9
Remarks It is not obvious to build directly the Markov chain Stochastic Petri nets offer an elegant tool for generation of correct Markov chain models of complex systems Immediate transitions seem a good way for representation of conflicts and priorities 10
Plan Introduction to stochastic Petri nets by examples Petri nets with inhibitors and priority Generalized stochastic Petri nets Applications Extensions 11
Definition PN = (P, T, I, O, M0, H, ) where : P T I : P T IN : PRE function, i.e. arcs from places to transitions and their weights O : P T IN : POST function, i.e. arcs from transitions and places their weights M0 : P IN : initial marking H : P T IN : generalized inhibitor arcs : T IN : priority degrees of transitions set of places set of transitions 12
Example t2 p3 t6 t4 p6 = = = t1 2 p2 K p1 = = = = p4 t5 t7 t3 p7 Effect of inhibitor : Transition t5 is not firable if M(p6) 2 . Effect of priority : Transitions t1, t6 and t7 are not allowed to fire if at least one transition of higher priority is firable. 13
Firing rules R1 : A transition t is said to have concession in marking M if M(p) I(p, t), p t and M(p) < H(p, t), p t. Let (M) the set of transitions that have concession in M R2 : A transition tj is said firable if tj (M) and j k, tk (M) R3 : Firing a transition t leads to the following marking : M' = M + O(t) - I(t) t set of input places of transition t t set of output places of t t set of places linked to t by inhibitor arcs 14
Structures of conflicts (Without priority) : A transition tm is said in effective conflict with tl at marking M if - tm has concession in M - tl is firable - tm no longer has concession in M' such that M(tl > M'. Example : t2, t3 and M1 obtained after firing t1. t2 p3 t6 t4 p6 = = = t1 2 p2 K p1 = = = = p4 t5 t7 t3 p7 15
Structures of conflicts (with priority) : A transition tk is said in indirect effective conflict with tl having the same degree of priority in M if tk is firable in M, tl is firable in M, firing tl leads to a sequence of higher priority transitions such that, after , no transition of priority higher than k is firable, tk is not firable in M' such that M(tl > M'. p3 Example : t3 t1 = p1 p5 = p4 t2 = p2 16
Structural properties of PN If the Markov chain of a stochastic Petri net has a finite state space and is ergodic, then Y 0, CY = 0 - it is consistent : X 0, XTC = 0 - and it is conservative : where C = O - I. 17
Plan Introduction to stochastic Petri nets by examples Petri nets with inhibitors and priority Generalized stochastic Petri nets (GSPN) Applications Extensions 18
Definition GSPN = (P, T, I, O, M0, H, , W) where PN = (P, T, I, O, M0, H, ) is a Petri net with inhibitors and priority composed of: transitions of priority 0 that are timed transitions with exponentially distributed firing times (timed transitions) transitions of priority n 1 that are immediate transitions (n-immediates transitions) W : T IR+ : is a function such that W(t) is the rate of the exponential distribution, i.e. inverse of the mean firing time, if t is timed W(t) is a weight associated with t if t is immediate 19
Tangibles and intangibles markings A marking M is said tangible if no immediate transition is firable. It is said intangible if at least one immediate transition is firable. 20
Dynamics of GSPN To each timed transition is associated a clock initiated with the corresponding exponential distribution For a tangible marking, clocks of all firable transitions tick down at the same speed the next transition to fire is that whose clock reaches zero first (Clock competition) 21
Weight of immediate transitions = routing probability Dynamics of GSPN For an intangible marking, a firable transition ti fires next with probability : P tiM ( )= W ti ( ) W t ( ) ( ) t E M where E(M) is the set of firable transitions. All transitions in E(M) are immediate transitions of the same degree. Firing ti leads to a new marking If the new marking is till intangible, the above is repeated. Otherwise, clocks of new transitions are generated and the system evolves from the new tangible marking 22
Impacts The sequence of tangible markings is a CTMC. the average sojourn time in a tangible marking M is exponentially distributed with mean 1 W t ( ) ( ) t E M where E(M) is the set of transition firable at M, and W(t) is the parameter of the exponential distribution of t the probability of firing a firable transition tk in a tangible marking M is: ( )= t E M W tk ( ) P tkM W t ( ) ( ) 23
Generation of the isomorphic CTMC The CTMC can be derived from the reachability graph (RG) : (i) by establish a one-to-one correspondence between the states of the CTMC and tangible markings CTMC Reachability graph M t 1 M* 1*routing probability of t2 tk 24
Generation of the isomorphic CTMC (ii) by introducing an arc (or a state-transition) u for all arc t of RG connecting two tangible markings. The rate of u is W(t) CTMC Reachability graph M t W(t) M* M M* 25
Generation of the isomorphic CTMC (iii) by introducing an arc v for all path t1t2 tk of RG connecting two tangible markings M and M* via intangible markings M1, M2, , Mk-1. The rate of v is : W(t1) P(t2 / M1) .P(t3 / M2) P(tk / Mk-1) where P tiM ( )= W t ( ) t E M ( ) W ti ( ) CTMC Reachability graph M t M* 26
Performance evaluation Steady state distribution : j : probablity of being in tangible marking Mj kMj ( ) j Firing frequency of a timed transition tk k= j : tk E Mj ( ) where k(Mj) is the firing rate of tk in Mj Average number of tokens in place p : E M(p) = Mjp ( ) j j Average sojourn time of tokens in a place p (Little's law): t t p E M(p) E dp = 27
Methodology 1. Construction of the GSPN model 2. Validation of the model. For example, the verification of the consistency and conservativeness. 3. Definition of performance measures 4. Generation of the reachability graph 5. Derive the isomorphic CTMC 6. Verification of the ergodicity of the CTMC 7. Compute the steady state distribution of the CTMC 8. Computation of the performance measures Remark : Softwares are available for automatic generation and solution of CTMC (GreatSPN, ) 28
Plan Introduction to stochastic Petri nets by examples Petri nets with inhibitors and priority Generalized stochastic Petri nets Applications Extensions 29
Failure-prone production line Assumption : idle machines cannot fail Parameters : i : failure rate i : repair rate pi: production rate H : buffer capacity M2 M1 B 30
Failure-prone production line : GSPN model p1 p5 p10 H+1 p3 p7 p2 p6 p9 t2 t3 t7 t1 t8 t6 t4 t9 t5 t10 p4 p8 M2 M1 B 31
Failure-prone production line structural properties Conservative as the GSPN is covered by three p-invariants : {p1, p2, p3, p4} {p2, p3, p9, p10} {p5, p6, p7, p8} Consistent as the GSPN is covered by three t-invariants: {t1, t2, t3, t6, t7, t8} {t4, t5} {t9, t10} p1 p5 p10 H+1 p3 p7 p2 p6 M2 M1 B p9 t2 t3 t7 t1 t8 t6 t4 t9 t5 t10 32 p4 p8
Failure-prone production line : performances Production rate (frequency of t7) t7 ( ) j TH= j / Mj(p6) 0 Average WIP ( ) j Mjp9 WIP = j UM1= j UM2 = j Utilization ratios of the machines : j / Mj(p2) 0 j / Mj(p6) 0 Idle rate of the machines IM1= jetIM2= j j / Mj(p3) 0 j / Mj(p5) 0 p1 p5 p10 H+1 p3 p7 p2 p6 p9 t2 t3 t7 t1 t8 t6 t4 t9 t5 t10 33 p4 p8
An NC machine The operation cycle of the machine is as follows : Phase 1 : Read informations of the product to process Phase 2 : Simultaneous execution of two commands: preparation of machining tools and preparation of NC program Phase 3 : Process the product Phase 4 : Test of the quality. If the quality is insufficient, then the machine repeats phases 2 and 3 for other treatments. Otherwise, the product is unloaded. 34
An NC machine : GSPN model t9 p9 t7 r p2 p3 t3 p5 p8 p4 p6 p7 r = 1-q p1 t1 t2 t4 t5 t6 q t8 with r + q = 1. Phase 1 : Read the product informations Phase 2 : Simultaneous execution of two commands: tool preparation and NC program loading Phase 3 : Process the product Phase 4 : Quality test. With probability q, the quality is insufficient, then the machine repeats phases 2 and 3 for other treatments. Otherwise, the product is unloaded. 35
An NC machine : structural properties t9 p9 t7 r p2 p3 t3 p5 p8 p4 p6 p7 p1 t1 t2 t4 t5 t6 q t8 with r + q = 1. Phase 1 : Read the product informations Phase 2 : Simultaneous execution of two commands: tool preparation and NC program loading Phase 3 : Process the product Phase 4 : Quality test. With probability q, the quality is insufficient, then the machine repeats phases 2 and 3 for other treatments. Otherwise, the product is unloaded. 36
An NC machine : Markov chain M1 100000000 1 Reachability graph M3 001100000 Markov Chain M1 100000000 t1 000110000 M4 001001000 M2 010000000 M5 t2 M3 001100000 t3 t4 M7 000000100 000110000 M4 001001000 t3 q 6 t4 M5 r 6 M6 000011000 t5 M9 000000001 M7 000000100 t9 p9 t6 t8 M8 000000010 t7 t7 r t9 M9 p2 000000001 p3 t3 p5 p8 p4 p6 p7 p1 t1 t2 t4 t5 t6 37 q t8
An NC machine : Steady state analysis The state-transition diagam is strongly connected and the CTMC is ergodic. M1 100000000 1 Steady state distribution is solution of the system = M3 001100000 000110000 M4 001001000 M5 ( + ) = + q M7 000000100 = q 6 r 6 = = r M9 000000001 + + + + + = 38
An NC machine : Performances M1 100000000 - Production rate (frequency of t9) : 1 TH = 9 M3 001100000 - mean production cycle : 000110000 M4 001001000 T = 1/TH M5 - mean time of phase 2 (Little's law): M7 000000100 + + + q 6 Nb of tokens in p3 and p5 frequency of arrivals in p3 = = 3 4 5 q 2 d r 6 1 1 7 6 M9 000000001 - Utilization ratio of the machine : D = 7 t9 p9 t7 r p2 p3 t3 p5 p8 p4 p6 p7 p1 t1 t2 t4 t5 t6 39 q t8
Plan Introduction to stochastic Petri nets by examples Petri nets with inhibitors and priority Generalized stochastic Petri nets Applications Extensions 40
Choice of immediate transitions with random switches Each random switch is associated with a set S of transition and it indicates, for each marking, the probability of firing a transition of this set Switches which are functions of markings are particularly useful Example : t1 o if M(p2) < M(p3) , P(t1) = 1, P(t2) =0 p2 p1 o if M(p2) > M(p3), P(t1) = 0, P(t2) =1 o if M(p2) = M(p3), P(t1) = 0.5, P(t2) = 0.5 t2 p3 41
Marking dependent firing times Example : t(M) = t * Min{M(p), p t} 42
Approximation of general distribution Consider a random variable D of mean D and standard deviation D. p1 D p2 Case : D > D. The delay of the subn-etwork N1 and D have the same mean and same standard deviation if : 2 2 n D n +1 1 2 n D 2 D n(n +1) D n +1 1 D D n = 1= 2 n D n(n +1) D 2= N1 : p1 p2 n 43
Approximation of general distribution Consider a random variable D of mean D and standard deviation D. p1 D p2 Case : D < D. The delay of the subnetwork N2 and D have the same mean and same standard deviation if : ( ), r1= 2 D D ( ) 2+ D 2 2 2+ D 2 h= 2 D D 1 - r1 N2 : h p1 r1 p2 44
