Home

General Purpose Petri Net Simulator

1.
2. 0 I I 0 2000 4000 6000 8000 10000 12000 Simulation results When MAX LOOP is explicitly specified to be 11 in SMU MAX LOOP 11 08 i P oze V f s Jf j osk 4 VJ Mj 05r y X O4 4 I ost 02 TE 11 2 Use of LOOP NUMBER When you simulate large Petri net models during the simulations you will notice that the MATLAB hangs without giving you any sign of life It will be better if you can see some outputs during simulations so that you are assured that the simulations are going on and that the system is dead hanging By setting the LOOP NUMBER flag in global info you can see the loop numbers when the simulation goes on 52 Let us go back to the simple example given in section 3 2 the simple Petri net This time we will set the LOOP_NUMBER flag in the MSF LOOP_NUMBER flag is set in global_info global_info LOOP_NUMBER 1 png petrinetgraph simple pn def dynamic info initial markings Place 1 3 Place 2 5 dynamic info firing times Transition 1 10 Sim Results gpensim png dynamic info global iinfo print statespace Sim R
3. 250 Figure 30 Simulation results of select_color demo In addition we can also inspect the colormap In pA the only color of any token is type A Color Map for place pA Time 0 type A Color Map for place pB Time 0 type B Color Map for place pC Time 0 type C gt gt 20 2 Required or Preferred Color This is an important issue With a very small change we can allow a transition to prefer may a color than require must a color In the example given above we forced the transition tA to select a token with color type A This is done first by selecting a token with type A color Function select token color will return tokID if a token is with type A color is available or else returned tokID value will 91 be empty And then we forced the transition to fire only if tokID is not zero meaning there is at least one token with the required color so that the transition can fire However we may also allow transition to prefer type A tokens This means if type A tokens are available they will be consumed if not one of the other existing tokens of type B or type C will be consumed The newer TDF given below prefers rather than forcing type A tokens function fire new_color over_ride selected_tokens global_info tA_def PN new_color over_ride selected_tokens global_info selecte
4. if tx times fired if T5 has already fired once then dont fire anymore fire 0 return end if isempty cols sema cols 1 which is the first avialble semafor global info my semafor task nr sema that will be mine global info semafor sema task nr then reserve it pack results global info timing task nr 1 global info timing task nr 2 sema task handler PN current_time task starting time fire else fire end 1 0 24 4 4 Post processors Post processors for all the transition are similar they just release the semafor the transitions were holding The post processor for T1 T1_post m function global_info T1_post transition PN global info function tl post task_nr 1 TASK 1 my semafor global info my semafor task nr which is my semafor global info semafor my semafor 0 release that Pack results task completion time global info timing task nr 3 PN current time task completion time 126 25 Stochastic Timer This is an advanced topic dealing with discretizing of continuous systems We know that Petri net is for discrete event simulations only However if we could discretize continuous systems then these systems can also be modeled with Petri nets However this is not easy and needs some understanding of Petri net formalism and matrix representation Interest reader is referred to a good book on this topic Dar
5. function fire new_color override selected_tokens global_info tGET NUM1 def pn new color override selected tokens global info TDF tGET NUM1 def numl input input number 1 new color num2str numl fire 1 always fire 19 1 4 TDF tGET NUM2 m The TDF will ask the user to input another number function fire new color override selected tokens global info tGET NUM2 def pn new color override selected tokens global info TDF tGET NUM2 def num2 input input number 2 new color num2str num2 fire 1 always fire 19 1 5 TDF tADD m There is no need for TDF tADD It by default inherits colors from input tokens and put the colors to the output token 19 1 6 TDF tCONVERT m function fire new_color override selected_tokens global_info tCONVERT def pn new color override selected tokens global info TDF tCONVERT def first select any token tokID select token pn pADDED 1 second get the colors of the selected token colors get color pn tokID str2num colors 1 convert color 1 into number str2num colors 2 convert color 2 into number numi num2 new color num2str numl num2 override 1 only sum as color NO inheritance fire 1 always fire 84 19 1 7 Simulation Results The statement print_colormap results pRESULT prints colors of all the places As shown in the s
6. I 0 4 H 4 fh I I i j A FP te soc ak cm jT Nj ree px A oe le EIRERERERENE nes ese es FIR j l Loy f 3 I I Ds ARAS RSE AE ARA Zi j 1 y l I I x m ES MEM po prom RN Fd I l oc L l l l l 0 50 100 150 200 250 300 73 15 3 Example 18 Using Resource Specific 74 16 Using Hourly Clock So far we have treated clock as a unitless timer it will always start at O during simulation start and will increase afterwards However in business modeling applications it will be much better to use an hourly clock a clock that uses and shows time in hours minutes and seconds The following example explains the issue CAUTION CAUTION Time in hourly format must be given as a vector with 3 columns e g 1 00 PM as 13 0 0 you can mix times in 3 column hourly format with single numbers however these single numbers will be taken as seconds E g 0 40 0 is equivalent to 40 minutes or 2400 seconds unifrnd 40 40 60 is equivalent to 2400 seconds 40 60 180 is equivalent to 180 seconds 16 1 Example 19 Hourly Clock for Lunching Clerks An office opens at 09 00 AM on every business day Customers arrive at every 30 minutes There are two clerks who will interact with the customers The clerks take 40 minutes to service a customer The office closes at 01 00 PM and no customer will be allowed into the office However those customer s alrea
7. tTRA pACD 1 tTRB pACD 1 tTRC pACD 1 ELRA pCTR1 1 tLRB pCTR1 l tLRC pCTR1 1 tTRA pCTR1 1 tTRB pCTRL 1 tTRC pCTR1 1 DOPRI EOLO 1 EOLO pCOTR2 1 pCTR2 tGPL 1 pCTR2 tGPT 1 y 23 5 Program Code TDFs 23 5 1 TDF for tGPL Adding Color function fire new_color over_ride selected tokens global info tGPL def PN new color over ride selected tokens global info oe function fire new color selected tokens global info t2 def PN new color selected tokens global info oe over ride 1 random number rand 1 if random number global info ratio A new color CAT A global info A count global info A count 1 elseif and random number gt global info ratio A random number global info ratio A global info ratio B new color CAT B global info B count global info B count 1 else new color CAT C global info C count global info C count 1 end fire 1 23 5 2 TDF for tLRA Landing A type AC function fire new color over ride selected tokens global info 110 tLRA_def PN new_color over_ride selected_tokens global_info oe function fire new color selected tokens global info tLRA def PN new color selected tokens global info oe selected tokens select toke
8. 3 00 6 00 The above screen dump shows that the LOG element is a 3 X 6 matrix Only way to see co tree properly is to feed the structure CT to function print_cotree 161 30 8 Structure for colormap Section 12 1 discusses colormap of a Petri net The program is given below clear clc pn petrinetgraph simple adder def dynamicpart initial markings p1 1 p2 1 results global_info colormap gpensim pn dynamicpart Execution of line 4 gives a structure called colormap Let us inspect this structure gt gt colormap colormap type color_map LOG 1x5 struct The structure has two elements element type identifies that this structure is for colormap and the element LOG has the rows of data for colormap gt gt size colormap LOG ans 7 00 5 00 The above screen dump shows that the LOG element is a 7 X 5 matrix meaning it has colors of 7 tokens Colormap structure as an output of gpensim contains properties color creation time and place of all the tokens that were existed during simulation run Let us see what the color of the first token is gt gt colormap LOG 1 ans time 0 place 4 color 21 45 The screen dump shows that the colors of the token were 21 and 45 We can see the colors of all the tokens that were involved during simulation by feeding colomap structure to the function print colormap 162 163 31 Usi
9. 0 0 10 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 10 1 9 1 0 0 0 10 0 0 0 0 1 1 10 0 0 0 0 0 1 25 2 8 1 1 0 0 25 0 0 0 0 1 1 25 0 0 0 0 1 0 35 1 7 2 1 0 0 35 0 0 0 0 1 1 35 0 0 0 0 0 1 50 2 6 2 2 0 0 50 0 0 0 0 1 1 50 0 0 0 0 1 0 60 1 5 3 2 0 0 60 0 0 0 0 1 1 60 0 0 0 0 0 1 75 2 4 3 3 0 0 75 0 0 0 0 1 1 75 0 0 0 0 1 0 85 1 3 4 3 0 0 85 0 0 0 0 1 1 85 0 0 0 0 0 1 157 100 2 2 4 4 0 0 100 0 0 0 0 1 1 100 0 0 0 0 1 0 110 1 1 5 4 0 0 110 0 0 0 0 1 1 110 0 0 0 0 0 1 125 2 0 5 5 0 0 125 0 0 0 0 0 0 125 0 0 0 0 0 0 gt gt Explanation Row 1 0 0 10 0 0 0 0 At time 0 the initial row shows the initial markings at time 0 Row 2 0 0 0 0 0 1 1 At time 0 both tX1 and tX2 are enabled Row 3 0 0 0 0 0 1 0 At time 0 only tX1 is allowed to fire Row 4 10 1 9 1 0 0 0 tX1 1 takes 10 minutes to fire After tX1 is fired new state is 9 1 0 Row 5 10 0 0 0 0 1 1 At time 10 both tX1 and tX2 are enabled Row 6 10 0 0 0 0 0 1 At time 10 only tX2 is allowed to fire Row 7 25 2 8 1 1 0 0 When tX2 2 completes firing time moves from 10 to 25 seconds The new state is 8 1 1 Row 8 25 0 0 0 0 1 1 At time 25 both tX1 and tX2 are enabled Row 9 25 0 0 0 0 1 0 At time 25 only tX1 is allowed to fire Row 10 35 1 7 2 1 0 0 When tX1 1 completes firing time moves from 25 to 35 seconds The new state is 7 2 1 Row 11 35 0 0 0 0 1 1 At time 35 both tX1 and tX2
10. one tenth of the least firing time of any transition in the system tX1 or tX2 Note Do not assign zero value firing time of the transition tXtra with zero value the system will never take off 61 xa tXtra gt tX1 gt tX2 Figure 23 Adding a small loop to speed up sampling rate Except adding the small loop pXtra tXtra pXtra there is no change in coding for example 13 MSF Example 14 Example for binary semaphore MSF loadbalance 2 m clear clc global info semafor 1 GLOBAL DATA binary semafor png petrinetgraph loadbalance 2 def dynamicpart initial markings pSTART 10 pXtra 1 pXtra added dynamicpart firing times tX1 10 tX2 20 tXtra 1 tXtra added sim gpensim png dynamicpart global info plotp sim pl p2 print_statespace sim PDF Example 14 Binary semaphore example with better rpintout file loadbalance 2 def m PDF function PN name set of places set of trans set of arcs loadbalance 2 def global info PN name Web Server Load Balancer set of places pSTART pl p2 pCK set of trans tX1 tX2 tCK set of arcs pSTART tX1 1 tX1 p1 1 BSTABTP NEXQ O1 CEN2U Tp lass pCK tCK 1 tCK pCK 1 62 Simulation Results Figure 24 shows the new simulation results after inclusion of the
11. Example 31 Hourly clock for lunching clerks TDF for clerk 1 function fire new color override selected tokens global info tCRK1 def PN new color override selected tokens global info ct compare time PN current time 12 0 0 if lt ct 0 fire 1 else TT fire 0 end 16 3 1 Simulation results Simulation results show that the last customer leaves at 14 40 when only one clerk functions after 12 00 Noon Time 14 40 00 State 19 Fired Transition tCRK2 Current State PEND pGEN pQUE 10 1 0 pEND 0 I I I 9 10 11 12 13 14 15 16 17 18 19 HOURS Figure 27 Plot showing time in hourly format 78 17 Hybrid Systems Petri Net Models with Fuzzy Inference This section talks about incorporating MATLAB toolboxes within Petri net models This section presents an example on how to incorporate fuzzy inference engines in Petri net models 79 18 Colored GPenSIM So far we have treated tokens in place as indistinguishable All the tokens inside a place are the same it does not matter which token arrived into the place first or last It does not matter either whether a token is deposited into a place by one transition or other But all these are going to be changed from now on every token is unique identifiable with a unique token ID When using colors in GPenSIM the following issues are important 1 2 Only transiti
12. TILH IO F ead zad Tay aR AC Na OO gat a am 054 Ama TRE sosta ansa TIFEL SETE pans n ANSI os rs pem RE SEE BET amara iia TOA Ad HOLAS saat muodsay spar CLR DOE A 5 DId mean oy aads DH prem ER UA Sets er ad DUI Ig Lu RET 7 ICY IMPMI wenbay i um d LA a puni Tae PAR AT aad aud sey RATER asd poonbeny Fuss INITIO 39 9 2 The Modular Approach Figure 13 shows a modular Petri net model consisting of a number of modules such as Service Interface Layer Initialization module Strategic module etc For each module a PDF will be created In addition there will be a PDF for the connection between modules For example we can cerate a PDF for each of the following 1 Client client_def m 2 Internet transmission internet_def m 3 Service Interface Layer sil_def m 4 Initialization module init def m 5 Iterations module interate def m 6 Strategic module strategy def m 7 Tactical amp sub tactical module tactic def m and finally 8 Profile for connecting the modules together conn pro m In the main simulation file all these 8 PDFs must be passed to the function petrinetgraph 9 9 9 9 png petrinetgraph client def internet def sil def eo iterate def strategy def tactic def dyn initial markings pSR 1 pNOI round un
13. grid on print_statespace RES PDF Example 31 Hourly clock for lunching clerks PDF function PN name set of places set of trans set of arcs clerksNEW def global info PN name The Two Clerks set of places pGEN pQUE pEND set of trans tGENNEW tCRK1 tCRK2 set of arcs pGEN tGENNEW 1 tGENNEW pGEN 1 tGENNEW pQUE 1 pQUE tCRK1 1 tCRK1 pEND 1 pQUE tCRK2 1 tCRK2 pEND 1 TDF for customer arrival Example 31 Hourly clock for lunching clerks TDF for customer arrival generation function fire new color override selected tokens global info tGENNEW def PN new color override selected tokens global info ct compare time PN current time 13 0 0 if le ct 0 fire 1 else fire 0 end 76 16 2 1 Simulation results Simulation results show that the last customer leaves at 14 10 when both clerks function all the time Time 14 10 00 State 19 Fired Transition tCRK1 Current State pEND pGEN pQUE 10 al 0 10 pCRK1 9r pCRK2 END 8 p 7 el 6 5L jp 4L J 3 2 4 LAT 0 ae 9 10 11 12 13 14 15 16 3 Case B Only one clerk functions from 12 00 Noon The only change will be the introduction of TDF for one of the clearks TDF for clerk 1 tCLR1_def m
14. loadbalance m Example 13 Example for binary semaphore MSF loadbalance m clear clc global info semafor 1 GLOBAL DATA binary semafor png petrinetgraph loadbalance def dynamicpart initial markings pSTART 10 dynamicpart firing times tX1 10 tX2 20 sim gpensim png dynamicpart global info plotp sim pl p2 Note gpensim takes three input parameters in addition to the usual static png and dynamic dynampart details the third parameter is the global info fglobal info Global info consists of two elements 1 The binary semaphore with initial value 1 this means tX1 should fire first 2 MAX LOOPE the use of this value is explained in the previous sections 12 1 3 TDF PRE for tX1 tX1_pre m function fire PN new color override selected tokens global info tX1 pre PN new color override selected tokens global info if global_info semafor 1 fire 1 else fire 0 end 12 1 4 TDF_POST for tX1 tX1_post m function PN global_info tX1 post transition PN global info function tX1 post global_info semafor 2 release semafor to tX2 12 1 5 TDF_PRE for tX2 tX2_pre m function fire PN new color override selected tokens global info tX2 pre PN new color override selected tokens global info TDF tX2 pre if global info semafor 2 fire
15. pBuffer 2 pBuffer_3 Note Due to stochastic timing up to three different outcomes are possible 35 36 9 Modular Model Building Figure 12 shows architecture of an adaptive supply chain based on service component architecture see Davidrajuh 2007 for details Figure 13 shows the equivalent Petri net model Figure 12 The system assembly 37 9 1 Example 08 Modular Model for Adaptive Supply Chain The Petri net model shown in figure 13 has many elements 11 places and 12 transitions and many connections 27 arcs Though possible it will be cumbersome to create one Petri net definition file PDF for the whole Petri net graph Instead we can divide the Petri net graph into modules as shown in figure 13 and then create individual PDFs for each of the module finally all the PDFs are combined to form the complete model In the following subsection we use modular many PDFs one PDF for each module approach Section 9 2 presents the TDF for the transition tRES interested reader is referred to Davidrajuh 2007 for details 38 The Petri net model of the distribution chain Figure 13 UTE I uornqrngsrp au Jo aPour 191 1437 ayy amarg
16. Place 3 The above statement will plot how the tokens in the places vary with time see the figure given below 15 4 5 3 5 2 5 1 5 0 5 AS Ea 10 12 14 4 2 Summary 16 18 20 Step 1 is about creating the PDF that defines the static Petri net graph The PDF for the Petri net shown in figure 5 is repeated below Example 01 A Simple Example file simple pn def m this file defines the simple petri net function PN name set of places set of tran simple pn def global info PN name A Simple Petri Net implementation set of places Place 1 Place 2 Place set of trans Transition 1 set of arcs Place 1 Transition 1 1 Place 2 Transition 1 2 Transition 1 Place 3 1 s set of arcs 3 Step 2 is for assigning the initial dynamics initial markings and firing times in the MSF After the assignment the simulations can be run and the results can also be plotted The MSF for the Petri net shown in figure 5 is repeated below Example 01 A Simple Example the main file to run simulation dynamic info initial markings Place 1 3 dynamic info firing times Transition 1 png petrinetgraph simple pn def Sim Results gpensim png dynamic info Place 2 5 10 16 print_statespace Sim Results plotp Sim Results Place 1 Plac
17. defined conditions The user defined conditions for firing a transition are kept in a TDF PRE file After a transition fires there may be some book keepings need to be done these can be coded into a TDF POST file 3 1 2 Using TDF as a test probe In addition to executing user defined conditions a TDF provides a unique functionality acting as a probe to simulation engine Let us explain 1 The role of PDF the only use of a PDF is to represent a static Petri net graph 2 The role of MSF A PDF will be loaded into memory by MSF right before the simulation start Thus an MSF first loads PDF or PDFs in modular approach into memory and then starts the simulation MSF will be blocked during simulation runs and when simulation is complete the control will be passed back to MSF along with the simulation result Therefore MSF does not have any control of what going on during simulation 3 The role of TDF Though MSF does not have any control of what going on during simulation however TDFs will be called during simulation before and after transition firings Thus if we want to inspect run time simulation properties then a TDF can be used as a probe more details given in the section on TDF Implementation details of a Petri nets Petri net m definition file Petri net m definition file Petri net m definition file Main Simulation File E g File sim1 m Implementation details of transitions Transition
18. 1 58 else fire 0 end 12 1 6 TDF_POST for tX2 tX2_post m function PN global_info tX2_post transition PN global info function tX2 post global_info semafor 1 release semafor to tX1 The plot given below shows that the queues are filled evenly this is because of the transitions fires alternatively 1 0 50 100 150 Figure 21 Printout of binary semaphore in action 59 60 13 Improving Simulation Results for Printout Let s take look again at the printout of simulation results from the previous section The figure given below look like ramp rather than pulses This is due to poor sampling recording Simulation results are recorded only whenever transition complete firing In other words simulation results are recorded only when there is a new state 5 T 4 5r 3 5 F n L 0 50 100 150 Figure 22 Printout of binary semaphore same as figure 21 We can improve sampling by adding a small loop that will generate new states faster Example 14 given below explains the trick 13 1 Example 14 Improving results printout of binary semaphore In this example we will add a small loop to the system the small loop consisting of a place pXtra and a transition tXtra is solely included to speed up the sampling rate or rate of reaching newer states The firing time of the transition tXtra has to be small lets say
19. array of place structures set_of_trans array of transition structures set_of_arcs array of arc structures Uses Used by Petrinetgraph Example function PN_name PDF PN_name Color example set of places pl set of places set of trans set of arcs simple adder def global info simple adder def m Simple Adder p2 pNUM1 pNUM2 pADDED pRESULT set of trans tGET NUM1 tGET NUM2 tADD tCONVERT set of arcs pl tGET NUM1 1 tGET_NUM1 pNUM1 1 p2 tGET NUM2 1 tGET NUM2 pNUM2 1 pNUM1 tADD 1 pNUM2 tADD 1 tADD pADDED 1 pADDED tCONVERT 1 tCONVERT pRESULT 1 Name petrinetgraph Purpose To make a static Petri net structure from the Petri net definition file s PDF s Input Names of One or more PDFs parameters Out parameters Static Petri net structure Uses build_places build_trans build_arcs incidencematrix Used by main simulation file Example in main simulation file one PDF file png petrinetgraph simple pn def multiple PDF files png petrinetgraph client def internet def sil def conn pro iterate def strategy def tactic def 170 Name plotp Purpose To plot simulation results to plot how tokens change with time Input Simulation Results the structure output by gpensim parameter
20. one structure per place consisiting the following type place name pl tokens 3 00 max capacity Inf token bank 1x3 struct Token bank is also a set of structures one for each token in the place consisitng the following tokID 1 00 creation time 0 color A B 3 Run time PN global_transitions 1xm struct A set of sturctures one structure per transition consisiting the following type transition name tl firing time 10 00 firing cost O0 times fired 0 4 STATIC PN global arcs 1x6 struct 5 STATIC PN incidence matrix 3x8 double 6 Run time PN current time 45 00 7 Run time PN token serial number 30 00 8 Run time PN X 10 00 3 00 5 00 2 00 Current Markings 9 Run time PN Firing Transitions 0 1 1 Transitions Firing at the moment one bit per transition 0 not firing 1 firing 10 Run time PN Enabled Transitions 1 O 0 Transitions enabled at the start of the cycle Apriori one bit per transition 0 not enabled 1 enabled 30 3 Structures for simulation results Simulation results from the function gpensim are kept in a structure that has two elements 150 type simulation LOG a matrix Firing Transitions a matrix Enabled Transitions a matrix State Diagram a matrix Place Names Block of strings Transition names Block of strings ADA p Matrices LOG Firing Transitions and Enabled Transitions have same the number of rows Ex
21. 1 Defining the Petri net graph in a Petri net Definition File PDF this is the static part This step consist of three sub steps a Identifying the basic elements of a Petri net graph the places b Identifying the basic elements of a Petri net graph the transitions and c Connecting the elements with arcs Step 2 Assigning the dynamics of a Petri net in the Main Simulation File MSF a The initial markings on the places and possibly b The firing times of the transitions After creating a Petri net model simulations can be done 4 1 Example 01 A Simple Example The two steps are explained below using the sample Petri net model shown in figure 7 Place 1 Transition 1 Place 2 Figure 7 A Simple Petri Net Model 4 1 1 Step 1 Defining the Petri net graph Defining the elements of a Petri net is done in a Petri net definition file PDF PDF is to identify the elements places transitions of a Petri net and to define the way these elements are connected The Petri net graph shown in figure 7 has three places one transition and three arcs The PDF for the graph is given below 13 Example 01 A Simple Example file simple pn def m this file defines the simple petri net graph function PN name set of places set of trans set of arcs simple pn def global info PN name A Simple Petri Net set of places Place 1 Place 2 Place 3 set of trans Transition 1 set
22. 250 A E TM f l N M toda 200 e 4 EU 3 TE i h 1 r a E Ei EE 150 E PI h x ri T 4 ji i Ki ri 2 i 100 Pi u d N b d Ed 50 EAE Na cal 0 L 0 5 10 15 20 25 Figure 44 Composition of specimens Prey Predator with time 131 Y2 400 350 300 250 200 150 100 50 Figure 45 300 Prey Predator Equilibrium 132 26 Measuring Robot Usage The flexible manufacturing cell at the Narvik Institute of Technology NIT Norway consists of a CNC vertical machining center Mori Seiki a CNC horizontal machining center Mori Seiki an ABB IRB2000 robot and a conveyor belt figure 12 shows the system Conveyor belts both for incoming and outgoing CNC vertical machining center ABB IRB2000 VMC Robot Fi CNC horizontal machining center HMC Figure 46 Flexible Manufacturing Cell at Narvik Institute of Technology NIT Here is the operational specification of the system somewhat simplified for our modeling purposes 1 2 3 4 5 6 To start a cycle a raw part must be available on the incoming conveyor belt and the robot is also available The robot moves a raw part from the conveyor and loads it at the horizontal machining center HMC The milling operation is performed at HMC while the robot backs off returns The robot unloads the work piece from HMC loads
23. PN structure is given in the next section 4 4 Assigning names to Places amp Transitions This means names for two places pReggieDavidrajuh 1 and pReggieDavidrajuh 2 are the same names REFER TO THE SAME PLACE because first 10 characters of these two names are the same However pReggie 1 Davidrajuh and pReggie 2 Davidrajuh are different names simply because first 10 characters of these two names are different 17 18 5 Transition Definition File TDF The previous section explained the methodology for modeling and simulation with GPenSIM consisting of two steps However in the previous section the step 1 was limited to creating only the PDF there were no TDFs created In this section we shall discuss about the TDFs too by working through the example shown in figure 8 Robot 1 Buffer 1 Machines Goods from CNC Robot 2 Buffer 2 Figure 8 Petri net model of a production facility 5 1 Example 02 TDF_PRE Example Figure 8 shows a Petri net model of a production facility where three robots are involved in sorting products machined parts from an input buffer for machined goods to output buffers There are three output buffers places available There are also three robots transitions that take the machined parts from the input buffer and put them to the respective output buffers The conditions The output buffers have limited capacity Buffer 1 buffer 2 and buffer 3 can accommodate a maximum
24. Simulink in addition to MATLAB while the GPenSIM tool used for Petri net simulation in this paper runs under the MATLAB environment only Petri nets is widely accepted by the research community for modeling and simulation of discrete event driven systems mainly due to graphical representation and the well defined semantics which makes it possible to use formal analysis of the models Jensen 1997 2 6 A minute introduction to Petri net The simple Petri net shown in figure 3 is a model for business logic computation The computation takes two database records and one business rule and produces one business decision In a Petri net sources like business rules and database records and outputs like business decisions are called places drawn as circles e g Place 1 Computations or events are called transitions drawn as vertical short bars e g Transition 1 An arc connects a place to a transition or a transition to a place representing a path for a discrete part to flow A place usually holds a number of parts like database records The number of parts inside a place is indicated by the tokens black spots within a place Business rules Place 1 Business logic computation Transition 1 Business decisions Place 3 Database records Place 2 Figure 3 Petri net model for business logic computation Part I GPenSIM Basics 3 Modeling with GPenSIM The Basics In GPenSIM definition of a Petri net graph static d
25. TIMING 23 2 The Petri net Model 106 23 2 1 The Elements e Air crafts e Runway e Exit ways for taxiing Terminal and e Control tower 23 2 2 Process Modules Figure 33 Elements of the runway 107 23 2 3 The Petri net Model ABOUT TO A LANDING LAND d 4 CONTROL 6 ABOUT TO TAKEOFF TAKEOFF Figure 34 The Petri net model showing only one terminal 23 2 4 Places and transitions e Module 1 ARRIVAL pARR tARR e Module 2 ABOUT TO LAND pWAL Wait for landing tGPL Granting Permission for landing e Module 3 LANDING pR2L Ready to Land tLR1 Landing RWY length 1 tLR2 Landing RWY length 2 tLR3 Landing RWY length 3 pACL A C Landed e Module 4 TAXIING tT2T Taxiing to Terminal tT2R Taxiing to RWY e Module 5 TERMINAL pR2B Ready to Board tBRD Boarding pR2D Ready to depart e Module 6 ABOUT TO TAKEOFF pW4T Wait for Takeoff 108 TATA dS tGPT Granting Permission for Takeoff e Module 7 TAKEOFF pR2T Ready to Takeoff tTR1 Takeoff RWY length 1 tTR2 Takeoff RWY length 2 tTR3 Takeoff RWY length 3 pACD A C Departed e Module 8 CONTROL pCTRI Runway to Control Tower pCTR2 Control Tower 2 Runway tCLC clear token color 23 3 Program Code MSF 23 3 1 MSF CESSCESEEEEEECECECECESESESESEEESESEEEEEEEEEEEESS NARVIK modeling a single runway airport CESECESESECECESCESCESESESESESEEESESEEEEEEEEEEEESS clear clc global_info ratio_A 0 30 global_in
26. Transition Definition Files TDF e TDF PRE which are run before firing a transition e TDF POST which are run after firing a transition 12 1 Example 13 Binary Semaphore Figure 20 shown below depicts a web server consisting of two server machines that will fire alternatively First client requests are queued at pSTART Then two routers tX1 and tX2 remove the client requests from the pSTART queue and put it to the queues for Web Server 1 pl and Web Server 2 p2 respectively In order to evenly distribute client requests to both servers one would expect that the two routers fire alternatively meaning that no router fires more times than the other gt tX1 tX2 Figure 20 Load balancing by alternative firing To allow the routers transitions fire alternatively we can implement a binary semaphore that can be read and manipulated by the definition files of both transitions 12 1 1 Petri net definition file loadbalance_def m PDF for Example 13 Binary Semaphore example file loadbalance def m definition of petri net graph for Norwegian trafic lights function PN name set of places set of trans set of arcs loadbalance def global info PN_name Web Server Load Balancer set of places pSTART pl p2 set of trans tX1 tX2 set of arcs pSTART tX1 1 tX1 p1 1 PSTART tX2 1 tX2 p2 1 57 12 1 2 Main Simulation File
27. Transitions Transition that created the new state 10 1 2 3 1 0 row no 5 enabled transitions Time NOT USED Enabled number of cells number of places 1 Transitions 10 0 0 0 0 1 row no 6 firing transitions Time NOT USED Enabled number of cells number of places 1 Transitions 10 0 0 0 0 1 Row no 7 state info Time Fired New State not used Transitions Transition that created the new state 20 1 1 1 2 0 154 row no 8 enabled transitions Time NOT USED Enabled number of cells number of places 1 Transitions 20 0 0 0 0 0 row no 9 firing transitions Time NOT USED Enabled number of cells number of places 1 Transitions 20 0 0 0 0 0 Function print_statespace uses the matrix State Diagram to print out simulation results State 0 Time O Initial State pl p2 p3 3 5 0 At time O enabled transitions are t1 At time 0 firing transitions are t1 State 1 Time 10 Fired Transition t1 Current State pl p2 p3 2 3 1 At time 10 enabled transitions are t1 At time 10 firing transitions are tl State 2 Time 20 Fired Transition tl Current State pl p2 p3 1 1 2 At time 20 enabled transitions are At time 20 firing transitions are Explanation Print_statespace lines Equivalent row of the matrix State Diagram State 0 Time 0 Initial State Row 1 pl p2
28. VMC 1 Pa Out buffer VMC t4 Drilling operation vary ps Out buffer HMC ts Robot part to output 1 Pe Part loaded to VMC te Robot returns 0 5 p7 HMC available t Robot returns 0 5 ps VMC available ts Robot returns 0 5 Po Robot ready return specimen operation times are given Pio Robot ready return in minutes pi Robot ready return It must be noted that there are potentials for parallel operations For example after loading a part into the HMC while the milling operation is going on the robot can retreat to its ready position and also load a part from the output buffer of HMC into VMC t and t are parallel 134 26 1 3 Simulations Lets vary the machining times of both milling and drilling operations and see for what combination of operations robot is overloaded a second robot should be commissioned Milling operation Drilling op 0 3 0 5 1 0 5 0 0 3 10096 100 90 50 0 5 100 100 90 50 1 0 90 90 82 47 5 0 50 50 47 33 Table IV Robot usage for different operation times e 9 e 9 e 9 e 9 e 135 27 Norwegian Traffic Lights As shown in the figure below Norwegian traffic lights have 4 states Red gt Red amp Yellow gt Green gt Yellow Q Figure 48 Norwegian Traffic Lights 27 1 Developing a Petri Net Model for Norwegian Traffic Light 27 1 1 State 1 RED to State 2 RED amp YELLOW RED de YELLOW C GREEN 136 27 1 2 St
29. a transition fires it can choose input tokens with specific colors 3 When new tokens are deposited into the output place new colors can be added by the transition This new color will in addition to the inherited colors unless inheritance is overridden in this case of overriding the deposited tokens into the output places will only have the new color added by the transition Let us experiment coloring with the help of a simple example candidly called simple_adder 19 1 Example 15 Simple Adder This example presents an adder that adds two numbers input by the user tGET NUMI tCONVERT tGET NUM2 pADDED pRESULT pNUM2 Figure 28 Simple Adder Petri net model of a simple adder has 6 places and 4 transitions Places p1 and p2 are just to keep the initial tokens so that the system can be started Transitions tGET NUMI and tGET NUM2 get an input number each from the user let say the numbers fed by the user are 21 and 45 Then these two transitions convert the numbers into strings 21 and 45 and then add the strings as colors to the output tokens deposited into pNUM1 and pNUM2 respectively Thus the places pNUM1 and pNUM2 have tokens with input numbers as the colors Transition tADD does nothing in terms of colors When it fires by default it deposits a token into the output place with the inherited colors Hence the token in place pADDED will have two colors 21 45 The final transition tCONV
30. code in TDF tokID1 select token color PN pAB 1 A tokID2 select token color PN pXY 1 X selected tokens tokID1 tokID2 tokens to be removed fire length selected tokens 2 MUST e Transition t select A from pAB or X from pXY at least one token be A or X Program code in TDF tokID1 select_token_color PN pAB 1 A tokID2 select_token_color PN pXY 1 X selected tokens tokID1 tokID2 tokens to be removed fire length selected tokens gt 1 MUST e Transition t prefers A from pAB or X from pXY Program code in TDF 95 96 97 22 Token Selection based on Time A transition may select input tokens based on time In the current version GPenSIM 3 0 selection can be done based on two policies FCFS First Come First Served and LCFS Last Come First Served Selection of time based token is done by executing the function select_token_time There are 4 input parameters to this function the Petri net structure at run time the input place of the transition number of tokens to be selected and finally the time based selection policy FCFS or LCES The output parameter of the function is a set of IDs of the selected tokens set of tokID Of course the number of returned tokID may be not equal to the number originally wanted by the transition depending on token availability Usage example if a transition wants
31. consists of just two rows The first row presents total activation times of each transition given in the input list The second row presents activation in percentage of the total time The function occupancy also prints the activation times and percentages on screen 7 1 Example 05 Measuring Activation Time This example is the same delay example shown in figure 10 This time we will compute the idle time of the transition activation time of the transition precisely with the help of the functions extractt and occupancy The only change this time in the MSF is that addition of the last two lines MSF Example 05 delay example for measuring activation time file delay demo m png petrinetgraph delay demo def dynamic initial markings pl 3 dynamic firing times tl 7 sim gpensim png dynamic global info print statespace sim plotp sim pl p2 duration matrix occupancy matrix extractt sim t1 occupancy sim t1 Simulation results The duration matrix computed form the simulation results shows that the transition t1 was fired at 0 30 and 60 time units and that every firing took 7 time units to complete Thus the total time t1 fired was 21 time units and the activation percentage was 21 67 31 3 percent 31 duration matrix 1 0 7 1 30 37 1 60 67 occupancy t1 total time 21 Percentage time 31 3433 occupancy_matrix 21 0000 31
32. duration The algorithm used for simulations is the priority list scheduling The order of priority high to low is assumed to be T1 T2 and T6 finally we assume two human resources generic and can do any task named Al and Bob 24 1 1 Petri net model Ten T2 epe T3 gt T5 T4 de pS3 T6 y 117 Figure 41 Petri Net model of the scheduling digraph The PDF for the Petri net model shown in figure XX2 is given below PDF schedule01_def m Example 81 Scheduling 01 file schedule01 def m PDF function PN name set of places set of trans set of arcs schedule01 def global info PN name Scheduling example 01 set of places pS1 pS2 pS3 pS6 pE pl4 p24 p35 set of trans T1 T2 T3 T4 T5 T6 set of arcs pS1 T1 1 pS2 T2 1 pS3 T3 1 pS6 T6 1 P1 TpI4 l T2 p24 l T3 p35 l pl14 T4 1 p24 T4 1 p35 T5 1 TA BE 1 TS pe 1 D6 pE 1 y 24 2 Programs In the preprocessor of each task we will try to grab a resource that is available the resources are implemented as a semafors The pre processor for task T1 T1_pre m is given below other pre processors for other tasks are similar the only change is the task_nr which is underlined in the code snippet given below function fire new_color overri
33. eatem 48 10 2 2 The main file oe ents ee 48 TH Global NO unicus ex era is 51 ELO ot MAX LOOR ad ann r cn E 51 IEL Exqmiple LIs MAX LOOP Nai a 51 14 2 User LOOP NUMBER a e a a eaa t vada ies 52 11 2 1 What are loops urinaria el a en 53 La Us DELTA S ose tpa n N suede Miu 54 LES Example 12 DELTA TIME 2a 54 12 TOR POS O poe 57 12 1 Example 13 Binary Semaphore asin teet ee y ooa ad as na 57 12 1 1 Petri net definition file loadbalance_def M ooooonoocccnnnococonocononnnononanonononanonos 57 12 1 2 Main Simulation File loadbalance m nennen 58 12 1 3 TDF PRE TOA LEAL prem Ye ee do 58 12 1 4 TDF POST Tor tX1 CtXT pt m Ya 58 DAS TDE PRE f rtX2 CtX2 prem eoi HIER rin 58 12 1 6 TDF_POST for tX2 CX2 post m0 d icis eterne Ru eor He na eoe otu ec uet 59 13 Improving Simulation Results for Printout eeeusesssss 61 13 1 Example 14 Improving results printout of binary semaphore 61 14 Prioritizing Transilions ana 65 14 1 Priorities Of transitions ea ea ea 65 14 2 Example 15 Alternating firing ana nn 65 14 3 Example 16 Priority Decrement Example 67 15 USING RESOUICES isi Ge rcd cx e x D co nn ig S FECE An not Cl CV inve n Di 71 13 17 Using IRESOUN CES c neueste cuo deesset ass cuonbussaaetanes Bats ei 71 15 1 1 Function print schedule este aet kan 71 15 2 Example
34. have colors reflecting the time they were made by tSEL Figure 31 FCFS example 22 1 1 PDF fcfs def m PDF for Example 19 Token selection based on time function PN name set of places set of trans set of arcs fcfs def global info PN name FCFS LCFS DEMO set of places pSTART pQUEUE pDLY pRDY pSEL set of trans tCOL tSEL tDLY set of arcs pSTART tCOL 1 tCOL pQUEUE 1 pQUEUE tSEL 1 tSEL pSEL 1 pDLY tDLY 1 tDLY pRDY 3 pRDY tSEL 1 99 22 1 2 MSF fefs m MSF for Example 19 Token selection based on time png petrinetgraph fcfs_def dyn initial_markings pSTART 3 pDLY 1 dyn firing_times tCOL 1 tDLY 100 tSEL 10 RES gpensim png dyn print_statespace RES print colormap RES pSEL 22 1 3 TDF tCOL_def m function fire new_color over_ride selected_tokens global_info tCOL_def PN new_color over_ride selected_tokens global_info TDF tCOL def add color new color num2str PN current time fire 1 22 1 4 TDF tSEL def m function fire new color override selected tokens global info tSEL def PN new color override selected tokens global info selected tokens select token time PN pOUEUE 1 FCFS fire 1 22 1 5 Simulation Results The simulation result clearly shows that tSEL selects tokens on FCFS basis At p
35. if isempty global_info Arrival_Times Current_AT global_info Arrival_Times 1 if le Current_AT PN current_time less than or equal global_info Arrival_Times global_info Arrival_Times 2 end fire 1 end end 23 9 4 Simulation Results T T T T 6 E 4 pBUFF 5L 4 4L E 3 4 2L J a J 0 ll ll L L li li 0 20 40 60 80 100 120 140 Figure 39 Jobs generation at predefined times 116 24 Scheduling We present two examples in this section Example xx is a warm up example In example xx we go through the better intended worst happened phenomena normally associated with scheduling Problems stated in the examples are taken from Stein 2008 24 1 Example 81 Minimizing completion time Figure 34 a digraph shows the tasks to be done to complete a work The figure shows the order in which the tasks to be done and the time required to complete each task E g Task T1 requires 4 time units and tasks T1 and T2 must be completed before task T4 task T1 task T2 task T3 task T6 time 4 time 6 time 5 time 7 CA M task T4 task T5 time 10 time 2 Figure 40 Digraph showing order of tasks to be completed Note that it will take a minimum of 16 time units to complete all the tasks as task T2 followed by T4 which requires 16 time units is the critical path the path of longest
36. it to the vertical machining center VMC and returns The drilling operation is performed at VMC and simultaneously the robot perform step 2 The robot unloads the finished part from VMC deposits it on the conveyor and returns In steady state steps 2 6 repeat Note that the specifications are very similar to the one given in Zhou and Robbi 1994 Well it has to be similar considering the simple systems we and they have there is only one way to do it 26 1 1 The Petri net model 133 The Petri net model for flexible manufacturing cell at NIT is given in figure 13 It is possible that one could come up with a slightly different model for the same system than the one shown in figure 13 Figure 47 Timed PN model for flexible manufacturing cell at NIT 26 1 2 The Petri net model The upper arm of the model consisting place pi is the start mode The left arm of the model is for the milling operation at HMC the right arm is for the drilling operation at VMC the bottom arm is for the transition between these two operations and finally the central part is for the robot movements Table III shows the meaning of the different places and transitions Table III Meanings of places and transitions for the PN model place interpretation trans interpretation time pi Raw parts ti Robot part to HMC 1 p Robot available t2 Milling operation vary P3 Part loaded to HMC tz Robot part to
37. let s inspect the source and the destination of this arc gt gt Sim Res global arcs 1 from ans type place name Place 1 tokens 0 max capacity Inf The source of this arc is the place Place 1 The destination of the arc is gt gt Sim Res global arcs 1 to ans 148 type transition name Transition 1 firing time 100 00 firing cost O0 firing condition times fired 0 The destination of the arc is the transition Transition 1 Of course figure 6 verifies the results 30 1 5 incidence matrix The incidence matrix is a matrix that depicts how the places and transitions are connected together GPenSIM uses a compact and unique format to convey this information Incidence matrix in GPenSIM is actually two matrices put together incidence matrix input incidence matrix output incidence matrix Please refer to any standard text on Petri nets to know the details of incidence matrix 30 1 6 type type identifies a Petri net type A Petri net can be un timed no concern about the firing times of the transitions timed or stochastic firing times are not deterministic 149 30 2 Run time Structures for Petri net and its elements Also discussed in the section on TDF Run time Petri net structure is available in all TDFs It consists of the following elements 1 STATIC PN Name TDF Example Production facility 2 Run time PN global places 1xn struct A set of sturctures
38. pGREEN tG Y 1 tG Y pYELLOW 1 pYELLOW tY R 1 tY R pRED 1 27 3 3 TDF tR RY function fire new color override selected tokens global info tR RY def pn new color override selected tokens global info function fire tR RY def PN pR get place pn pRED pY get place pn pYELLOW tRRY get trans pn tR RY fire pR tokens amp not pY tokens 27 3 4 TDF tY R function fire new color override selected tokens global info tY R def pn new color override selected tokens global info function fire tY R def PN pR get place pn pRED pY get place pn pYELLOW fire not pR tokens amp pY tokens 139 Part III Reference Manual 141 28 Design of the GPenSIM Simulator In this section we will look into the internals of GPenSIM simulator Like any simulators GPenSIM also has the following two major components a global timer and a queue to keep firing transitions active events in addition GPenSIM also has mechanisms functions to manipulate these two components a push function to push firing transitions into queue and a pop function to eject a firing transition from queue in order to complete or finish firing 28 1 The Main Loop Components in the main loop e A Global Timer pn current time e A Queue EIP events in progress Mechanisms functions that manipulate the components e P
39. pre m function fire PN new color override selected tokens global info t2 pre PN new color override selected tokens global info t2 pre PN priority increment PN t3 fire 1 66 TDF PRE for t3 t3_pre m function fire PN new color override selected tokens global info t3 pre PN new color override selected tokens global info t3_pre PN priority_increment PN ti fire 1 Simulation Results The results show that the mechanism is little bit flawed and need to be checked 7 r r r r T T pE1 pE2 pE3 0 2 4 6 8 10 12 14 16 18 20 14 3 Example 16 Priority Decrement Example This example is the same as for the previous example shown in figure 25 However this time we will allow t1 to fire 5 times uninterrupted and then allow t1 and t2 fire alternatively for 10 more times After this all three can fire alternatively SMU Example 16 Priority decrement global info MAX LOOP 25 global info PRIORITY t1 10 t2 5 png petrinetgraph prio def dyn initial markings pS 1 tokens initially dyn firing times t1 1 t2 1 t3 1 sim gpensim png dyn global info plotp sim pEl pE2 pE3 67 PDF Example 16 Priority Decrement file prio def m definition of petri net function PN name set of places set of trans set of arcs prio def PN
40. state 1 ROOT node Node type state 3 pl 1 Node type state 4 pl 0 Node type state 5 pl 0 Node type p2 p3 0 0 Firing event tl p2 p3 1 1 T oT Parent state Firing event t2 p2 p3 0 Inf Lom Parent state Firing event t3 p2 p3 0 1 nm Parent state Firing event tl p2 p3 1 Inf To Parent state 48 state 6 Firing event t2 pi p2 p3 1 0 Inf Node type D Parent state state 7 Firing event t3 pi p2 p3 0 0 Inf Node type T Parent state Boundedness pi 1 p2 i p3 i Inf p4 1 p4 0 5 p4 1 5 49 50 11 Global Info Global variables and parameters can be passed through different files e g SMU PDFs and TDFs by making use of the global info packet The methodology of using global info is explained below through the use of an example 11 1 Use of MAX LOOP MAX_LOOP value if added to the global_info packet will be read by the gpensim function to limit the simulation cycles to the given value Increase MAX_LOOP for large number of iterations loops 11 1 1 Example 11 MAX LOOP This is same as the example 06 This time we will experiment with global MAX LOOP setting Figure 18 Transitions firing sequentially The Petri net shown in figure 18 run for ever Thus unless specified in the SMU default maximum loop number is 200 default MAX _LOOP 200 We can stop the simulations af
41. 17 Using Resources to realize critical section sess 12 1521 MSE er tas mtn ee e e o o 12 15 22 22 PDE f def T ice adic e 2 iv 152 3 SIDE BU DEO Arsen 73 1324 MU UMAR ases rd ette uad vei d be o p E e abi eed 13 15 2 5 Result et eier 73 15 3 Example 18 Using Resource Specific 74 16 Golored GPen SIM PPP cid 80 TOAL Structure or Token A 80 17 Color Inheritance eR 82 LULA dBxample 15 Simple Ad uste th ties doter cud aa 82 17 1 1 MSE simpleradder m na ri E pies Be 83 19 1 2 PDE simple adder detect 83 17 1 3 EDF GET NUM m esse 84 17 14 TDE GET NUM 2 i ura 84 17 15 CEDE ADD M ee a saeco oie edu aa P aa apse eta is ieee 84 IO MADE ACON Y ERA eerie nn e En 84 DLL Simulation Results siii e eerte da denned 85 17 2 Example 16 Alternative Design for Simple Adder sss 85 18 Token Selection based on Color eene 88 18 1 Example 17 Selecting Input Tokens with Specific Color sss 88 18 1 1 MSE own tertii inert tabe tede oe a eas 89 18 1 2 PDE PC asa 89 18 1 3 TDF 4GEN ea dd aid 89 18 1 4 TDESfortA amp tB and tOna aa eee an Ra 90 13 1 5 Simulation results uiu een ea E Ped p haga ene 90 18 2 Required or Preferred Color udo ti ret eios ticae beige 91 182 1 Simulation dye toni baud nha e dE MEILE ce Rade Rs Dash daa each 92 18 2 Example 18 Selecting Input Tokens with 2
42. 2 Node type D Parent state 4 state 8 Firing event t2 pl p2 p3 p4 0 2 0 3 Node type T Parent state 6 Boundedness pl 2 p2 2 p3 2 p4 3 gt gt The screen output given above is equivalent to the graphic shown in figure 15 10 1 3 Event simulation instead of coverability tree Lets try event simulation of the same Petri net the main file to find the reachable states 45 clear clc clear the workspace amp screen first png petrinetgraph cotree example def dyn initial markings pl 2 p4 1 tokens initially dyn firing times t1 2 t2 1 t3 3 tokens initially Results gpensim png dyn print statespace Results The function print cotree will print the state flow on the screen COTREE Example Petri Net in Figure 15 Time 0 New markings pl p2 p3 p4 2 0 0 1 At time O enabled transtions are tl At time 0 firing transtions are tl Time 2 Fired Transition tl New markings pl p2 p3 p4 1 1 1 1 At time 2 enabled transtions are t1 t2 t3 At time 2 firing transtions are t1 t2 Time 3 Fired Transition t2 New markings p1 p2 p3 p4 0 1 0 2 At time 3 enabled transtions are At time 3 firing transtions are tl Time 4 Fired Transition tl New markings p1 p2 p3 p4 0 2 1 2 At time 4 enabled transtions are t2 At time 4 firing transtions are t2 Time 5 Fired Transition t2 New markings
43. 3 1 2 A A E 105 23 1 3 Runway RWY and taxiways TWY sese 105 23 1 4 The three categories of Us ca 105 29 9 GOVEMINE IM ut an 106 23 1 6 Timing for simiulatiODS scie ii na daa 106 232 Ihe Petri net Modele tse allie din 106 292 A Elementsin ena E do E E E E E E 107 23 229 Process Modules sr en rnit 107 2323 Ihe Petri nel Model aussi E pte eptut edd 108 23 2 4 Places and transitions uec essere e enne AFIN ORNA TREE A NEST esa mee eg Ue Ende 108 233 Program O dec 109 DAMEN cL S 109 234 Program Code PDE suite ei 109 23 5 Program Code OI ds Den 110 235 1 TDE for tGPh Adding Colob ncn i bie 110 23 5 2 TDF for tLRA Landing A type AC secs cid Er aa di 110 23 5 3 TDF for tLRB Landing B type AC eese 111 23 5 4 TDF for tLRC landing C type AC eese 111 23 5 5 TDF for tTRA Take Off A type AC nennen 111 23 5 6 TDF for tL RB Lake Off B type AC ea 112 23 5 7 TDF for tTRC Take Off C type AC iiec ua 112 23 5 8 TDF for tCLC removing color in tokens seen 113 2367 o A Ne Lern 113 23 HN IS VIC SUD ETE EACH HT HT 115 23 8 Improvement to simulation model job arrival in predefined times 115 23 9 Example 26 Arrivals at predefined times eee 115 A A ht amati snae s matum 115 23 9 PDE A opi 2k va Naas O ONE ea Se 116 2393 TDP MGEN defi iia at DO PA TU MAR CA RA De EN 116 299 Simulation Resuls nee O
44. 3433 7 2 Example 06 Measuring Activation time This is another example for measuring activation time Figure 11 below shows a simple system where two transitions fire sequentially one after the other Figure 11 Transitions firing sequentially The code below is for the main simulation file Example 06 Measuring Timing MSF measure_timing m clear clc global_info MAX LOOP 11 GLOBAL DATA MAX SIMULATION CYCLES png petrinetgraph measure timing def dynamicpart initial markings pi 10 dynamicpart firing times t1 1 t2 100 sim gpensim png dynamicpart global info print statespace sim plotp sim pl p2 duartion martix extractt sim tl t2 disp Duartion Martix disp duartion martix fprintf n n occupancy martix occupancy sim t1 t2 fprintf n n disp Occupancy Martix disp occupancy_martix 32 Simulation results Duartion Martix 1 NNNNNPPRRR 0 101 202 303 404 505 1 102 203 304 405 1 102 203 304 405 506 101 202 303 404 505 Simulation Completion Time occupancy tl total time Percentage occupancy t2 total time Percentage 6 time 1 1858 500 time 98 8142 Occupancy Martix 6 0000 500 0000 1 1858 98 8142 506 33 34 8 Stochastic Firing Times So far the firing times for transitions are assumed to be deterministic thus the simulat
45. 4 oldest tokens from the input place pBUFF then the transition will execute the following statement function fire new color override selected tokens global info tLR A def PN new color override selected tokens global info selected tokens select token time PN pBUFF 4 FCFS fire 1 If pBUFF has more than equal to 4 tokens then tokIDs of the 4 oldest tokens will be returned in selected tokens Otherwise if pBUFF has less than 4 tokens then tokIDs of all the tokens will be returned Similarly if a transition wants 2 youngest tokens from the input place pBUFF then the transition will execute the following statement function fire new color override selected tokens global info tLR A def PN new color override selected tokens global info selected tokens select token time PN pBUFF 2 LCFS fire 1 98 22 1 Example 19 Token selection based on time Figure 24 shows the example for token selection based on time pSTART has 3 initial tokens initial tokens are of course colorless tCOL add colors to the tokens it deposits into pQUEUE The branch pDLY tDLY pRDY is a delay just to keep tSEL wait until all the three tokens are deposited into pQUEUE tCOL adds color to tokens followingly e Gets current time from the system e Converts current time into ASCII string e Adds the ASCII string as color This means all the three tokens deposited into pQUEUE will
46. 6 Simulation Results Finding the Bottleneck for varying arrival rate OVW AL 0 9 mg pR2B ume m pW4T 0 8 0 7 4 o Jl I 0 5 El I os Pl 0 3 0 2 0 1 y 0 200 400 600 800 1000 1200 1400 Figure 35 Arrival of ACs every 60 min 113 Arrival of ACs every 40 min Figure 36 pW4L pR2B pW4T 16 14 600 500 400 300 200 100 Arrival of ACs every 20 min 37 Figure 114 23 7 Discussion e For all frequencies like flights every 60 min 40 min and 20 min maximum number of flights waiting in the air pWAL is 1 Therefore RWY is not the bottleneck e Condition 1 at any time only one AC in RWY is satisfied structurally How to satisfy ATC Condition 2 Landing has priority over takeoff Onlyone gate is used in the model Thus Gate is the bottleneck in simulations CpR2B However single RWY is obviously a problem considering close down for maintenance and for fault tolerance e How can the Petri net model easily modified for Stavanger Sola Double RWY 23 8 Improvement to simulation model job arrival in predefined times In the Petri net model shown in figure 30 the aircraft arrival generator or generally job arrival generator is given as a loop that will create aircraft arrivals with specific intervals this could be slightly improved by using a stochastic value e g normrnd 45 5
47. 7 definition file Transition n definition file Figure 5 Transition Definition Files 3 20 Global info The different files main simulation file MSF Petri net definition files PDFs and transition definition files TDFs can access and exchange global parameters values through a packet called global_info If a set of values is need to be passed to different files then these values are packed together as a global info packet global info packet is visible in all the files so that the values in the packet can be read and even changed See chapter 9 for details 3 3 Integrating with MATLAB environment The most important reason for developing GPenSIM and the most advantage of it is its integration with the MATLAB environment so that we can harness diverse toolboxes available in the MATLAB environment see figure 6 10 For example by writing a user M file that combines GPenSIM with Fuzzy Logic toolbox we can experiment with Fuzzy Petri Nets by combining GPenSIM with the Control systems toolbox we can experiment hybrid discrete continuous control applications etc Optional MATLAB Toolboxes such as Fuzzy Control Systems Optimization Statistics etc Main Petri Net Transition Simulation Definition Definition File Files Files MSF PDFs TDFs Figure 6 Integrating GPenSIM with the MATLAB environment 11 12 4 Using GPenSIM The methodology for creating a Petri net model consists of two steps Step
48. A Tool for Modeling and Simulation of Discrete Event Systems GPenSIM General Purpose Petri Net Simulator GPenSIM Web site http www davidrajuh net gpensim Reggie Davidrajuh University of Stavanger Norway Email reggie davidrajuh uis no Version 4 1 September 2010 11 CONTENTS lijlzg ez iiiad ix Te Installing GR SINS aii nica Ear AS 2 Introducing Petri Netas iii 2 1 Elements or PS UTC US ee do eet recta ested acce IDA D odes 3 2 2 Formal Definition of Petri nets sauna 4 2 2 1 Input and Output Places of a Transition 5 2 3 Enabled Transitions eec decern ee 5 2 4 P tri net dynamics iaceo er i SERERE OUO EATUR TA CURE EAS LUISA S EUR enl 5 2p Coverability Tree kennen een 5 235 Wy Petri nets t ii A R O A aS 6 2 6 A minute introduction to Petri niet 2 u ea 6 Part l GPenSIM Basics 3 Modeling with GPenSIM The Basics eese 3 1 Transition Definition Files ierit eade ee 9 SAT Using TDF PRE and DDE POST 2 22 ae Alan 9 3 1 2 Using T DE as a t st Proben ae en 9 B t A e bcp e E fodebdt ems idera EOS M IL IM 10 3 3 Integrating with MATLAB environment eeesseeeseeeeeeeneeee enne enne enne 10 LMEITNPeECLCDhSID M 13 4 1 Example 01 A Simple Example u nenne EIER 13 4 1 1 Step 1 Defining the Petri net graph ea ees 13 4 1 2 Step 2 The main simulation file assigning the initi
49. At time 10 firing transtions are t1 Time 20 Fired Transition tl New markings ps pEl pE2 1 2 0 At time 20 enabled transtions are tl t2 At time 20 firing transtions are t1 Time 30 Fired Transition tl New markings pS pEl pE2 0 3 0 At time 30 enabled transtions are At time 30 firing transtions are 5 5 2 Case II t1 is preferred but t2 can also fire Conditions for firing e as before t1 will fire if it is enabled meaning no TDF for t1 e t2 will fire is t1 is not enabled or if t1 has fired at least once Now t2 can fire as soon as t1 has fired for the first time TDF function fire PN new color override selected tokens global info t2 pre PN new color override selected tokens global info TDF for t2 t2 pre m Case II tl get trans PN t1 if or is_enabled PN ti tl times fired gt 1 fire 1 else fire 0 end Simulation results The following may occur where t2 may also fire 26 0 8 i A 4 og L L L L L L L 2 4 6 8 10 12 14 16 18 20 5 6 Using TDF POST We study an application of TDF POST through an example in section XXX 27 28 6 Internal Clock Internal clock is discrete in the sense it is updated whenever a transition is complete If we take a close look into the figures generated by the plotp function the figures look like ramp rather than pulses This is due to poor sampling recording as s
50. DED 1 second get the colors of the selected token colors get color pn tokID numl str2num colors 1 convert color into number num2 str2num colors 2 convert color into number sum numl num2 new color num2str sum override 1 only sum as color NO inheritance global info sum sum sum is added to global info fire 1 always fire transition PN global info fire or not new color override seleted tokens global info firing condition 174 REFERENCES C G Cassandras and S Lafortune Introduction to Discrete Event Systems Boston MA Springer Science Business Media LLC 2007 GPenSIM web page http www davidrajuh net gpensim Darren J Wilkinson Stochastic Modelling for Systems Biology Chapman amp Hall CRC NY 2006 ISBN 10 1 58488 540 8 Read especially about Gillespi s algorithm in chapter 06 James D Stein T Murata Petri nets Properties analysis and applications Proceedings of the IEEE vol 77 pp 541 580 1989 R Davidrajuh Event driven simulation modeling and analysis with GPenSIM Communications of the IIMA Published by the International Information Management Association vol 3 pp 53 71 2003 C A Petri and W Reisig Petri net Scholarpedia vol 3 p 6477 2008 R Davidrajuh and I Molnar Designing a new tool for modeling and simulation of discrete event systems Issues in Information Systems v
51. EEEEEEEEES File sil def m Definition of the Service Interface Layer CECECEECEEEEEEEEEEEEEEEEEEEEEEESEEEEES PN_name Service Interface Layer set of places pRFC pRTC pBl set of trans tINIT set of arcs pRFC tINIT 1 tINIT pB1 1 9 2 5 Iterations module interate_def m function PN name set of places set of trans set of arcs iterate def 55 56 55 85 55 5s Ss 56 56 65 85 S5 Ss So Sb 76 6 f 5 So So 56 76 76 76 16 6 76 76 76 76 6 5 5 76 76 File iterate def m Definition of the Iterations module 35 56 95 85 5 55 S5 S6 56 f 55 Ss Ss So Sb 6 fo 5 S5 Ss So 56 76 76 56 56 6 76 76 76 76 6 6 5 76 76 PN_name Iterations Module set of places pNOI pB6 set of trans tIT tRES set of arcs pNOI tIT l pB6 tIT 1 pB6 tRES 1 9 2 6 Strategic module strategy_def m function PN name set of places set of trans set of arcs strategy def CESEECEEEEEEEEEEEEEEEEEEEEECEEEEEESES File strategy def m Definition of the Strategic Module EESECECEEEEEEEEEEEEEEEEEEEEEEEEEEEES PN name Strategic Module set of places pB2 pB3 set of trans tSD set of arcs pB2 tSD 1 tSD pB3 1 9 2 7 Tactical amp sub tactical module tactic def m function PN name set of places set of trans set of arcs tactic def 56 56 55 85 55 5s So 56 56 6 5 55 Ss So S6 76 56 56 5 6 56 76 76 76 16 6 6 76 76 76 76 6 5 6 6 76 File tacti
52. ERT does five activities 82 First it gets the two colors strings 21 and 45 of the token in place pADDED Then it converts the strings into numbers 21 and 45 It adds these two numbers together to make the sum 66 Then it coverts the sum into a string 66 and Finally it adds this string as color to the token deposited into the place pRESULT The transition will also override inheritance so that the sum will be the only color of the token deposited into prESULT ne D des 19 1 1 MSF simple_adder m MSF for Example 15 simple_adder m clear clc pn petrinetgraph simple adder def dynamicpart initial markings p1 1 p2 1 results gpensim pn dynamicpart print_colormap results pl p2 pNUMI1 pNUM2 pADDED pRESULT 19 1 2 PDF simple adder def m PDF for Example 15 simple adder def m function PN name set of places set of trans set of arcs simple adder def global info PN name Color example Simple Adder set of placesz pl p2 pNUM1 pNUM2 pADDED pRESULT set of trans tGET NUM1 tGET NUM2 tADD tCONVERT set of arcs pl tGET NUM1 1 tGET_NUM1 pNUM1 1 p2 tGET NUM2 1 tGET NUM2 pNUM2 1 pNUM1 tADD 1 pNUM2 tADD 1 tADD pADDED 1 pADDED tCONVERT 1 tCONVERT pRESULT 1 83 19 1 3 TDF tGET NUMI m The TDF will ask the user to input a number
53. N_name Scheduling example 02 set of places pS1 pS2 pS3 pS4 pE p19 pX set of transs Tl T2 T3 PA T5 LET TT TS THO set of arcs pS1 T1 1 pS2 T2 1 pS3 T3 1 pS4 T4 1 T1 pI9 1 plS9 T9 1 Bar ge 1 82 BEC 1 83 pE 1 pg ex 4 2x pX T5 1 pX T6 l pX T7 1 pX TS8 1 UT5B TpE l1 T6 pE l T7 pE l T8 pE l MSF schedule02 m Example 82 MSF scheule02 m clear clc no of employees 4 no of tasks 9 global info semafor zeros 1 no of employees employees available global info my semafor zeros 1 no of tasks global info PRIORITY T1 T2 T3 T4 T5 T6 T7 T8 T9 global info timing zeros no of tasks 3 png petrinetgraph schedule02 def dynamicpart initial markings pS1 1 pS2 1 pS3 1 pS4 1 dynamicpart firing times T1 3 T2 2 T3 2 T4 2 T5 4 T6 4 T7 4 T8 4 T9 9 sim global info gpensim png dynamicpart global info grid on plotp sim pl4 p24 p35 pE timing global_info timing three_chaps Al Bob Chuck four chaps Al Bob Chuck Don if no of employees 3 print schedule timing three chaps else print schedule timing four chaps end 124 24 4 3 Pre processor for T1 T2 T3 T4 and T9 The only job of the preprocessors Tl pre to T4 pre and
54. S uM ute dudo d eeu MEETS ERR QUERN 116 24 ScHhedulitig usada 117 24 Example 81 Minimizing completion time eese 117 ZANT Pete MODE natos 117 242 suci kaa seas ta PE aaa 118 A cett teda ues Diod eti M LM IA NE 120 243 1 E SUMMARY nassen 122 24 4 Bxample 82 Scheduling IL cese paisa anida 122 244 Petri Net Modelado ti 123 2442 2 Programmine ze RIES 124 24 4 3 Pre processor for T1 T2 T3 T4 and T9 uussseesseneennnnnnnn 125 DA AA POSUDIOGESSODSas nenn 126 25 5 Stochastic EI BE usn uel ex la m Fu CU CF 127 25 Example 25 The Prey Predator ecological equilibrium ss 127 252 Converting the dynamics to Petri nets anna 127 23 3 Simulation files 1 nudae dee ita 128 25 3 1 The Main Simulation Pile peo eI n et b usi etna mi 128 2592 JPetrset Definition Dieses 128 25 3 3 Definition of stochastic timer time advancement m sess 128 25 3 4 Transition Definition File t1 def m eerie eee ene ne etn 129 vi 25 3 5 Transition Definition File t2_ def m oo cece cc ceeeeeccccseececcecececceeececeeners 130 25 3 6 Transition Definition File t3 def m ococccnnnncncnonnnnninnnnnnnnnnononinicinocininonanes 130 25 4 The Simulation Results eese esses eese eene teens tette t enano soon 131 26 Measuring Robot Usage uuusunnnnnnnnnnnnnnnnnnnnn
55. SEL 3 tokens arrive the first token had color 0 then arrive a token with color 1 and finally come token with color 2 step 7 Firing event tSEL Starting time 120 Finishing Time 130 Current markings pSTART pQUEUE pDLY pRDY pSEL 0 0 0 0 3 Completion time 130 100 Displaying token colors WARNING processing takes time Color Map for place pSEL Time 110 Qt Time 120 10 vq Time 130 9 Yt 2 22 1 6 Simulation results for LCFS Let s change selection policy to LCFS function fire new color override selected tokens global info tSEL def PN new color override selected tokens global info selected tokens select token time PN pOUEUE 1 LCFS fire 1 Then the simulation result also depicts LCFS selection by tSEL step 7 Firing event tSEL Starting time 120 Finishing Time 130 Current markings pSTART PQUEUE pDLY pRDY pSEL 0 0 0 0 3 Completion time 130 Displaying token colors WARNING processing takes time Color Map for place pSEL Time 110 2 Time 120 13 r2 Time 130 rg 1 r2 101 102 Part II Applications 104 23 Modeling a Single Runway Airport This project is to model a single runway airport The aim is to propose a simple dynamic Petri net model that describes the traffic flow of a single runway RWY due to schedule i e estimated times of arrivals and departures 23 1 Description o
56. T9 pre is to grab an available so that they can start However the preprocessors for T5 T8 have one more job to do that is to make sure that they fire only once or consume only one token after T4 has fired Pre processor for T1 T2 T3 T4 and T9 are similar function fire new color override selected tokens global info T1 pre PN new color override selected tokens global info Tl pre task nr 1 TASK 1 occu semafor global info semafor semafor occu semafor row cols find semafor find any available semafor value 0 if isempty cols sema cols 1 which is the first avialble semafor global info my semafor task nr sema that will be mine global info semafor sema task nr then reserve it pack results global info timing task nr 1 global info timing task nr 2 sema task handler PN current_time task starting time fire else fire end 1 0 Pre processor for T5 T6 T7 and T8 are similar they first check whether the transition is already fired once If yes then no more firing Other wise they try to grab a semafor function fire new color override selected tokens global info T5 pre PN new color override selected tokens global info T5 pre task nr 5 TASK 5 occu_semafor global_info semafor semafor occu_semafor row cols find semafor find any available semafor value 0 tx get_trans PN T5 125
57. This is denoted by w p t 2 2 3 Enabled Transitions A transition T in a Petri net is said to be enabled if Cassandras and Lafortune 2007 x p 2 wp t for all p Ile The transition t in figure 2 is enabled since the numbers of tokens in the input places p 2 and p 2 are at least as large as the weight of the arcs connecting them to ti w p t 2 and w p t 2 2 4 Petri net dynamics The markings of a Petri net which is the distribution of tokens to the places represent the state of the Petri net A Petri net representing a discrete event system where the transitions represent events goes through many states during a simulation process The different states could be represented with the row vector of markings the 4 th tuple x x p x p x p The number of states an infinite capacity net can have is generally infinite since each place can hold an arbitrary non negative integer number of tokens Murata 1989 A finite capacity net on the other hand will have a given number of possible states The state transition function f X XT N of a Petri net is defined for a transition t T if and only if x p gt wp t for all p e I l If Fon is defined then x fot where x p xlp wlp 1 wit p puo 2 4 1 Coverability Tree Petri Nets helps proving many behavioral properties of a system including e Reachability Boundedness Conservativeness Liven
58. U 2 celobal plaggsonoseien seele aas terat ufi ocase S as 147 30 1 3 global transitions ood ade aie He NR 148 30 4 Globales runa a Na een to 148 30 1 3 MCCAIN EE D eere a Leak Anden 149 301 6 e Aa S 149 30 2 Run time Structures for Petri net and its elements seeseeeee 150 30 3 Structures for simulation results ococcccnnnnnnnnnnnnnnnnonononononinonononicinacononinininanineness 150 304 Example suisse te ar tac kei ein 151 301 O ray cosets Hr DEREN 153 30 4 2 Firing Transitions and Enabled transitions eene 153 304 3 Stile Diagram A Er er 153 30 4 4 Place Names and Transition Names esee enne 156 30 5 Example 2 for State Diagratn iiie terii Va Seen IS US ee dida Edda EN ue iius 156 30 6 Off line Graphical Display oci Uo Ip ERE Readiness aq Ital een am 160 30 7 Struet ure for CORTES iii Alanis 161 30 8 Str cture for COMA iii ek 162 31 Using MSF and petrinetgraph eceeceeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeesenees 164 32 Description of the Main Functions uuussunnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn 166 REFERENCES raras allan daa 175 vil viii PREFACE Petri net is being widely accepted by the research community for modeling and simulation of discrete event systems There are a number of Petri net tools available for academic and commercial use These tools are advanced tools powerful enough to model
59. _token_color PN pBUFF 1 type A select_token_color PN pBUFF 1 type B selected tokens tokID1 tokID2 one of these token must be removed fire selected tokens FIRE ONLY IF Selected tokens IS NOT EMPTY Now we see that tokens in pA have both type A and type B colors Color Map for place pA Time 0 type A type B Color Map for place pB Time 0 type B Color Map for place pC Time 0 type C gt gt 93 21 Summary Token Selection based on Color 21 1 Token Selection From A Single Input Place Let s say that place pAB has tokens with many colors including A B X Y A BLAS AP LAS SY UB RN UA B X Y jJ pAB t e Transition t selects token with color A from pAB meaning tokens with color A Jor A B or A X are relevant Program code in TDF e Transition t selects A or B from pAB Program code in TDF e Transition t prefers A or B from pAB Program code in TDF 94 e Transition t selects a token with A and B from pAB Program code in TDF 21 2 Token Selection From Multiple Input Places Let s say that place pAB has tokens with colors A B A B and pXY has tokens with colors X Y X Y h PAB E pXY e Transition t selects A from pAB and Y from pXY Program
60. al dynamics 14 4 13 The Simulations AA O an 14 4 1 4 Viewing the simulation results with print statespace sse 13 J2 O ac Beh e Td e ei 16 4 3 Static DN SEU COUT ar osse ont ae tns i Sh 17 4 4 Assigning names to Places amp Transitions oooooccnnnnccnoncccnoncccnnnnnononnnonononononcnnnnncconnnos 17 5 Transition Definition File TDF 4 u 4 4 20u0200 nennen 19 5 1 Example 02 TDE PRE Example 22 22 ia 19 UN MEO CUu AUDI seo nn RI 19 5 2 Step l the definition fes duode egrs nnns os 20 odd Defining the Petri net graph srecen en 20 5 2 2 Coding the user defined firing conditions of the Transitions 20 5 3 Step 2 Assigning the initial dynamics and running the simulations 21 E eden 2l 54 Run time PN Str c s sales 23 5 5 Example 03 Implementing Preference through TDF_PRE 24 33 1 Case thas strictly preferred i uisi pass 24 5 5 2 Case II tl is preferred but 12 can also Tre anne ae an 26 5 6 Usine TIDE POS TA AE 27 6 lriternal Clock vis anne cc ec ata cece i Pa E ER CREE UE COL c E ee 29 6 1 Example 04 Delay Example arios 29 7 Measuring Activation Timing uurssssssnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn 31 7 1 Example 05 Measuring Activation Time ssssseesesesesresseseresreeressersresreeseeseeseesrs 31 iii 7 2 Example 06 Mea
61. and 45 of the token in place pADDED no change Then it converts the strings into numbers 21 and 45 no change It adds these two numbers together to make the sum 66 no change Then it coverts the sum into a string 66 and REVISED Finally it adds this string as color to the token deposited into the place pRESULT The transition will also override inheritance so that the sum will be the only color of the token deposited into pRESULT In addition the sum will be stored as an element of global info di eS The new TDF for tCONVERT is given below function fire new color override selected tokens global info tCONVERT def pn new color override selected tokens global info TDF tCONVERT def first select any token from pADDER tokID select token pn pADDED 1 second get the colors of the selected token colors get color pn tokID numi str2num colors 1 convert color 1 into number num2 str2num colors 2 convert color 2 into number sum numl num2 new_color num2str sum set the sum as the new color global_info sum sum sum is added to global_info override 1 only sum as color NO inheritance fire 1 always fire There will be slight modifications in the MSF too 1 To start the simulations we have to pass global info with the element sum to gpensim 2 After simulations we do not need to print the colormap to study the results instead we
62. arcs delay demo def global info 29 PN_name Delay Demo set of places pl p2 set of trans ti set of arcs pl tl 1 ti p2 1 TDF function fire new color over ride selected tokens global info tl def PN new color over ride selected tokens gl function fire tl pre rest mod PN current time 30 fire rest 5 any number less than 7 would do obal_info Simulation results 30 7 Measuring Activation Timing We are going to find out how much time each transitions take or occupy out of the total time From the simulation results there are two functions that can compute activation time of each transition given in the input list Function extractt creates a simple matrix called duration matrix in which first column is the transition transition index that fired the second column is the start time for firing and the third column is the completion time for firing Function extractt returns duration matrix with three columns 1 Column 1 The firing transition 2 Column 2 firing start time 3 Column 3 firing finishing time Alternatively we can use the function occupancy to measure activation times function occupancy first computes the duration matrix by calling the function extractt Then from the duration matrix it computes the occupancy matrix Occupancy matrix
63. are enabled Row 12 35 0 0 0 0 0 1 At time 35 only tX2 is allowed to fire 158 159 30 6 Off line Graphical Display After simulations by the function gpensim the simulation results has all the necessary information for off line graphical display The simulation results lets call it Sim_Results has three elements that can be used for graphical display figure 32 Off line graphical display of simulation results A Java C etc based program for Graphical Display of simulation results Simulation Results Elements Stat Diagram Flace Names Trans fon_Names Figure 16 Off line after gpensim simulation graphical display of simulation results step by step Figure 51 Off line graphical display 1 State Diagram a matrix 2 Place Names Block of strings 3 Transition names Block of strings 160 30 7 Structure for co tree Section 7 1 discusses obtaining co tree of a Petri net The program is given below the main file to get the co tree png petrinetgraph fig 8 def sources pl 1 CT cotree png sources print_cotree CT Execution of line 4 gives a structure called CT for the co tree Let us inspect this structure gt gt CT CT type COTREE LOG 3x6 double The structure has two elements element type identifies that this structure is for co tree and the element LOG has the rows of data for co tree gt gt size CT LOG ans
64. ask T4 time 2 time 1 time 1 time 1 Y AAA task T9 task T5 task T6 task T7 task T8 time 8 time 3 time 3 time 3 time 3 Figure 42 Digraph for example 82 In this example too the priority of tasks are assumed as previously top to bottom T1 T2 seg T9 When three resources Al Bob Carter are used the completion time is found to be 12 time units This is a perfect storm scenario finishing the job by the time of the critical path T1 T3 which is 12 time units 122 The results above shows that when we add more resources we make things worse as completion time is now increased Now the completion time is 15 time units 24 4 1 Petri Net Model Figure given below shows the Petri net model Note that the weight of arc between T4 and pX is 4 This means every time T4 fires it puts 4 tokens into pX pS1 T1 p19 T9 pS2 gt T2 pS3 gt T3 T5 T6 4 059 mr T7 T8 This means we have to make sure that these 4 tokens are consumed by the 4 transitions T5 T6 T7 and T8 one token for each transition 123 24 4 2 Programming PDF schedule02_def m Example 82 Scheduling 02 file schedule02 def m PDF function PN name set of places set of trans set of arcs schedule02 def global info P
65. ask5 25 27 Task6 27 34 120 When we use two resources Al and Bob the time taken is 18 time units to complete all the tasks Example 81 MSF scheule01 m no of employees 2 print_schedule timing Al Bob A kkk Taskl 0 4 Task3 4 9 Task5 9 11 Task6 11 18 kkk Bob kkk Task2 0 6 Task4 6 16 However if we use three resources Al Bob and Carter then the maximum time needed is the critical path time that is 16 time units Example 81 MSF scheule01 m no_of employees 3 print_schedule timing Al Bob Carter A Taskl 0 4 Task6 4 11 Bob Task2 0 6 Task4 6 16 kkk Carter kkk Task3 0 5 Task5 5 7 121 24 3 1 In Summary When only one resource Al is used Completion time 34 time units Usage of resources 100 When two resources Al and Bob are used Completion time 18 time units Idle time Bob 2 time units When three resources Al Bob and Carter are used Completion time 16 time units Idle time Al 5 time units Carter 9 time units 4 24 4 Example 82 Scheduling II Figure 36 shows another example task T1 task T2 task T3 t
66. ate 2 RED amp YELLOW to State 3 GREEN C GREEN 27 1 3 State 3 GREEN to State 4 YELLOW 137 27 1 4 State 4 YELLOW to State 1 RED 27 2 Transition Definitions State 1 RED to state 2 RED amp YELLOW Transition tR gt RY will fire only if there is a token in place RED and there is no token in place YELLOW if there are tokens in both places then tRY gt G will fire State 4 YELLOW to state 1 RED Transition tY gt R will fire only if there is a token in place YELLOW and there is no token in place RED 27 3 Program Code for the Petri Net Model 27 3 1 Main Simulation File oe the main file to run simulation clear clc global info MAX LOOP 5 stop after 5 states one cycle pn petrinetgraph NO light def dynamic info initial markings pRED 1 Results gpensim pn dynamic info global info print statespace Results plotp Results pRED pYELLOW pGREEN 138 27 3 2 PDF function PN_name set_of_places set_of_trans set_of_arcs NO light def global info file pn def m definition of petri net graph for Norwegian trafic lights PN name Pet Net graph for trafic light NOR set of places pRED pYELLOW pGREEN set of trans tR RY tRY G tG Y tY R set of arcs pRED tR RY 1 tR RY pRED 1 tR RY pYELLOW 1 pRED tRY G 1 pYELLOW tRY G 1 tRY G pGREEN 1
67. ation results When the results are returned they can be also analyzed with tools like print_statespace plotp extract occupancy etc Input Static Petri net structure output from petrinetgraph parameters initial dynamics global_info Out parameters Simulation results global info Uses gpensim_ver initial_markings init_token_bank firing_times state_space timed_gpensim Used by main simulation file Example in main simulation file simualtion Results global info gpensim png dyn global info print statespace simualtion Results 167 Name gpensim_ver Purpose Prints the current version of gpensim Input None parameters Out parameters None Uses None Used by gpensim main simulation file Example in main simulation file gpensim equivalently gpensim ver 20 H gt static PN sturcture initial_markings IE H initial state static PN sturcture initial m arkings initial run time PN sturcture global info initial run time PN structure init token bank initial run time PN structure firing times firing times initial run time PN structure firing times gt initial run time PN structure global info P lt sim_results global_info color_map timed_pensim 168 Name Main Simulation File MSF Purpose 1 To declare global variables global info 2 T
68. below 25 3 Simulation files The program snippets using GPenSIM is given below e First in the main simulation file we have to set the flag for stochastic timer global info STOCHASTIC 1 e Second we have to define the stochastic timer in the file time advancement m 25 3 1 The Main Simulation File MSF file for Example 25 Predator Pey example THIS EXAMPLE USES STOCHASTIC TIMER global info MAX LOOP 10000 global info c 1 005 6 global info STOCHASTIC 1 set the flag for stochastic timer global info LOOP NUMBER 1 set this flag as MAX LOOP is large pn petrinetgraph predator prey def dynamicpart initial markings Prey 50 Predator 100 sim gpensim pn dynamicpart global info NOTE print function print_statespace can not be used applications using stochastic timer tere plotp sim Prey Predator figure 28 plot sim LOG 2 sim LOG 3 figure 29 25 3 2 Petri net Definition File PDF for Example 25 predator prey def m function PN name set of places set of trans set of arcs predator prey def global info PN_name predator prey p 151 set of places Prey Predator DUMP set of trans t1 t2 t3 set of arcsz Prey t1 1 t1 Prey 2 Prey t2 1 Predator t2 1 t2 Predator 2 Predator t3 1 t3 DUMP 1 25 3 3 Definition of stochastic timer time ad
69. c def m Definition of the Tactical subtactical modules 35 55 55 85 55 Ss So 56 56 6 5 5s Ss So So 06 6 56 55 6 56 76 76 76 76 6 6 76 76 76 6 6 5 6 6 76 PN name Tactical amp sub tactical Module s set of places pB4 pB5 set of trans tTD tSUB1 tSUB2 tSUB3 tSUB4 tSUM set of arcs tTD pB4 4 pB4 tSUB1 1 pB4 tSUB2 1 pB4 tSUB3 1 pB4 tSUB4 1 tSUB1 pB5 1 tSUB2 pB5 1 tSUB3 pB5 1 tSUB4 pB5 1 pB5 tSUM 4 41 9 2 8 Profile for connecting the modules together conn_pro m function PN_name set_of_places set_of_trans set_of_arcs conn_pro EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEES File conn pro m Definition of the connections between the modules CESSSESEECEECECESCESCESESESESESESESEEESES PN name Connections Profile set of places set of trans set of arcs pSR tcs 1 client internet tCS pRFC 1 internet SIL EPRTC ESC 1 SIL internet ESC pRR l internet client PBL TEIT Lodo init iterations UETT BBI 1 iterations init EXP BB2 1 pB3 tTD 1 ESUM pB6 1 tRES pRTC 1 iterations strategy strategy tactical tactical iterations iterations SIL AP de oe oe oe oe oe oe oe oe 9 3 Transition definition file for tRES tRES def m function fire new color override selected tokens global info tRES def PN new color override s
70. ce the value by 1 PN priority decrement PN t3 priority of t2 is now 9 14 2 Example 15 Alternating firing Transitions t1 t2 and t3 should fire alternatively figure 25 A TP YA P x7 M z MA LA 157 pt l PRE a A ae Pd S 1 Nass MXN y LT 2 i A NC de FL b gt 2 NM 2 EN r4 TN Y ae IN E 2 M1 roe k 3 de t C X Figure 25 Alternating firing of t1 t2 and t3 65 MSF Example 15 Priority Increment example global_info MAX LOOP 20 png petrinetgraph prio_def dyn initial_markings pS 1 tokens initially dyn firing times t1 1 t2 1 t3 1 sim gpensim png dyn global info plotp sim pEl pE2 pE3 PDF Example 15 Priority Increment example file prio def m definition of petri net function PN name set of places set of trans set of arcs prio def PN name Priority Example Petri Net for production facility set of places pS pEl pE2 pE3 set of trans t1 t2 t3 set of arcs pS tl1 1 pS t2 1 pS t3 1 UEL pEI l1 EL pS l1 U E2 pE2 1 E2 pS 1l E3S pE3 1 t3 pS 1 TDF PRE for t1 t1_pre m function fire PN new color override selected tokens global info tl pre PN new color override selected tokens global info tl pre PN priority increment PN t2 fire 1 TDF PRE for t2 t2
71. ception for stochastic timer applications LOG generally has less rows The LOG matrix can become large as it has all the simulation results Each raw of LOG matrix represents changes due to firing of a transition and has the following elements The new markings the new state Fired transition Parent state matrix raw number from which this state was obtained Firing start time and Firing completion time Vh Opa Bau The Firing Transitions matrix contains information about all the firing transitions at each inspection time Each row of the Firing Transitions starts with inspection time element 1 and then rest of the elements are represents transitions if element is 1 then the corresponding transitions was firing at the inspection time Similarly the Enabled Transitions matrix contains information about all the enabled transitions at each inspection time Each row of the Enabled Transitions starts with inspection time element 1 and then rest of the elements are represents transitions if element is 1 then the corresponding transitions was enabled at the inspection time State Diagram represents sequences of states and the transitions that make state changes State Diagram is used by the print system print_statespace State Diagram consists of three different types of information Row 1 is the new state Row 2 is the enabled transitions after the new state Row 3 is the firing transitions after the new stat
72. complex and large systems In this book we introduce a new Petri Net simulator called GPenSIM General Purpose Petri Net Simulator GPenSIM runs on MATLAB platform GPenSIM is designed with one specific goal allowing Petri net models to integrate with other MATLAB toolboxes By integrating Petri net models with other toolboxes numerous benefits can be reaped For example by integrating with MATLAB Fuzzy Toolbox we can experiment with Fuzzy Petri Nets by combining with MATLAB Control Systems Toolbox we can create hybrid discrete continuous systems Hence the main goal of this book is to introduce GPenSIM a platform with which we can create Petri net models incorporating many other toolboxes libraries and functions that are already available on the MATLAB platform There are many examples worked out in this book These examples are simple and easy to follow However this book is not an introduction to Petri nets Reader should know Petri net basics beforehand in order to start working with this book Both the simulator GPenSIM and codes for examples M files can be downloaded from the web site http www davidrajuh net gpensim Reggie Davidrajuh Stavanger Norway September 2010 ix 1 Installing GPenSIM Installation takes five simple steps 1 Unzip the GPenSIM pack Unzip the GPenSIM toolbox functions file s under a directory say d GPenSIM GPenSIM32 Note Due to size limitations there may be one zip file GPe
73. creen dump below e pt has no colors pl p2 pNUM1 pNUM2 pADDED e p2has no colors e pNUMI has 21 as the color e pNUM2 has 45 as the color e pADDED has both 21 and 45 as colors and e pRESULT has 66 as the color input number 1 21 input number 2 45 Color Map for place pl Color Map for place p2 Color Map for place pNUM1 Time 0 21 Color Map for place pNUM2 Time 0 45 y Color Map for place pADDED Time 0 217 45 Color Map for place pRESULT Time 0 66 19 2 Example 16 Alternative Design for Simple Adder In the previous subsection the sum is stored as a color inside a token that was deposited on the place pRESULT You may prefer getting the sum as a variable too so that it can be freely used as you want You can achieve this with a simple design change 85 In addition to storing the sum as a color on the deposited token you can also let the transition tCONVERT to store the sum as an element of global_info In fact global_info is meant for this kind of activities getting information somewhere within a transition so that the information can be passed to subsequent transitions and back to the main simulation file The new tCONVERT given below does the same five activities but the last activity includes storing the sum as an element of global_info The final transition tCONVERT does five activities 1 no change It gets the two colors strings 21
74. d tokens select token color PN pBUFF 1 type A fire 1 This transition always fires if enabled because fire 1 regardless of type A tokens are available or not It will also consume type A tokens if available if selected tokens list is not empty Let us think about a generic case if a transition needs m tokens from an input place to fire arc weight m and has obtained n numbers preferred tokens selected tokens list has n tokIDs If m is greater than n then the system consumes removes n number of specific tokens identified by the tokIDs in the selected tokens list and the rest m n tokens will be other arbitrary tokens in the input place 20 2 1 Simulations TDFs for tA tB and tC are changed so that tokens with specific colors are preferred not required Simulations show that now pA pB and pC have tokens with all colors Color Map for place pA Time 0 type A type B type C Color Map for place pB Time 0 type A type B type C Color Map for place pC Time 0 type A type B type C gt gt 92 20 2 2 Example 18 Selecting Input Tokens with 2 or more colors In this example we make a tiny change to tA so that tA make select either type A or type B color function fire new_color over_ride selected_tokens global_info tA_def PN new_color over_ride selected_tokens global_info TDF tA def tokID1 tokID2 select
75. d tokens global info tTRA def PN new color selected tokens global info selected tokens select token with colors PN pR2T 1 CAT A if isempty selected tokens fire 1 else fire 0 end 23 5 6 TDF for tTRB Take Off B type AC function fire new color over ride selected tokens global info tTRB def PN new color over ride selected tokens global info function fire new color selected tokens global info tTRB def PN new color selected tokens global info selected tokens select token with colors PN pR2T 1 CAT B if isempty selected tokens fire 1 else fire 0 end 23 5 7 TDF for tTRC Take Off C type AC function fire new color over ride selected tokens global info tTRC def PN new color over ride selected tokens global info function fire new color selected tokens global info tTRC def PN new color selected tokens global info selected tokens select token with colors PN pR2T 1 CAT C if isempty selected tokens fire 1 else fire 0 end 112 23 5 8 TDF for tCLC removing color in tokens function fire new_color over_ride selected_tokens global_info tCLC_def PN new_color over_ride selected_tokens global_info function fire new_color selected_tokens global_info tCLC_def PN new_color selected_tokens global_info over_ride 1 fire 1 23
76. de selected tokens global info T1_pre PN new_color override selected tokens global info Tl_pre task_nr 1 TASK 1 occu semafor global info semafor semafor occu semafor row cols find semafor find any available semafor value 0 if isempty cols sema cols 1 which is the first avialble semafor global info my semafor task nr sema that will be mine global info semafor sema task nr then reserve it pack results global info timing task nr 1 sema task handler global info timing task nr 2 PN current time task starting time 118 fire else fire end ll H ll o In the post processor of each task we will release the semafor after use The post processor for task T1 T1_post m is given below again the post processors for the other task are similar we only need to change the fask nr function global info T1_post transition PN global info function T1 post task_nr 1 TASK 1 my semafor global info my semafor task nr which is my semafor global info semafor my semafor 0 release that Pack results task completion time global info timing task nr 3 PN current time task completion time Finally the MSF schedule01 m is given below Example 81 MSF scheule01 m clear clc no of employees 2 no of tasks 6 global info semafor global info my semafor zeros 1
77. def pn global info cl global_info c 1 c2 global_info c 2 c3 global_info c 3 Prey get_place pn Prey PRED get place pn Predator hl cl Prey tokens h2 c2 Prey tokens PRED tokens h3 c3 PRED tokens H hl h2 h3 probabilities prol h1 H pro2 h2 H pro3 h3 H R rand 1 fire R lt pro2 25 3 6 Transition Definition File t3_def m function fire new_color override selected_tokens global_info t3 def pn new color override selected tokens global info function fire t3 def pn global info tRES implementation cl global_info c 1 c2 global_info c 2 c3 global_info c 3 Prey get_place pn Prey PRED get place pn Predator hl cl Prey tokens h2 c2 Prey tokens PRED tokens h3 c3 PRED tokens H hl h2 h3 probabilities prol h1 H pro2 h2 H pro3 h3 H R rand 1 fire R lt pro3 This is the reason for manipulating simulation results log file directly as done in the example above We give below code snippet from MSF for prey predator example 130 NOTE print function print_statespace tree plotp sim Prey Predator figure 28 plot sim LOG 2 sim LOG 3 figure 29 25 4 The Simulation Results 400 r r T 1 fF RRR Prey N Predator 350 f a Lh T 300 H 4 l zi j i M J
78. dy reside inside the office will be serviced 1 Case A What time the last customer will leave the office after finishing his her business 2 Case B Suppose there will only one clerk available from 12 00 Noon how the departure time of the last customer will change 16 1 1 Functions for hourly clock First of all we want to start the simulation at 09 00 AM This can be fed into the model through the global info packet global info STARTING AT 9 0 0 start 09 00 00 HH MM SS In MSF to assign firing times to clerk 40 minutes each and customer arrival every 30 minutes we may either use the hourly clock format or times in seconds dyn firing times tGENNEW 30 60 tCRK1 unifrnd 40 40 60 tCRK2 O 40 0 Note Because of the use of hourly clock formats the functions print statespace and plotp display time information in hourly formats 75 16 2 Case A Two clerks work all the time MSF Example 31 Hourly clock for lunching clerks clear clc global info LOOP NUMBER 1 global info MAX LOOP 50 global info STARTING AT 9 0 0 start 09 00 00 HH MM SS COMPOSE 555555 png petrinetgraph clerksNEW def DYNAMIC DETAILS dyn initial_markings pGEN 1 pQUE 1 dyn firing_times tGENNEW 30 60 tCRK1 unifrnd 40 40 60 tCRK2 O 40 0 SIMULATE RES gpensim png dyn global_info plotp RES pEND
79. e Place 1 tokens 0 max capacity Inf The first place is identified by its name as Place 1 It has no tokens at the simulation end The element max_capacity is NOT USED We can also inspect a place by passing its identifier to the function get place gt gt pl get place Sim Res Place 1 pl type place name Place 1 tokens 0 max_capacity Inf 147 30 1 3 global transitions global transitions is the set of all transitions in the Petri net global transitions can be studied by the same approach applied to inspecting global places 30 1 4 Global arcs global arcs is the set of all arcs in the Petri net gt gt Sim Res global arcs ans 1x3 struct array with fields type from to weight name Screen dump shows that global arcs consists of three arcs Let s inspect the first arc of global arcs gt gt Sim Res global arcs 1 ans type arc from 1x1 struct to 1x1 struct weight 1 00 name Arc 475 The first arc of the set of arcs has 5 elements type this element identifies the type arc of the element as an arc from this element identifies the source of the arc to this element identifies the destination of the arc weight this element identifies the weight of the arc the weight of the arc is 1 name an ASCII string identifier to the arc a unique identifier is generated for every arc the unique identifier for this arc is Arc 475 CIS Mapas Further
80. e This is further explained in example given below Places Names and Transition Names are names of all the places and the transitions respectively 30 4 Example 1 In order to inspect the structure for simulation results let us visit a small example The program code snippet given below shows the main simulation file png petrinetgraph simple pn def dynamic initial markings p1 3 p2 5 dynamic firing times t1 10 11 sim gpensim png dynamic global info 151 print_statespace sim sim LOG function PN_name set_of_places set_of_trans set_of_arcs simple pn def global info PN name A Simple Petri Net definition set of places pl p2 p3 set of trans t1 10 set of arcs pl tl 1 p2 tl 2 Wil ps 1 Let us inspect the structure sim RESULTS gt gt sim sim type simulation LOG 3x7 double Firing Transitions 3x2 double Enabled Transitions 3x2 double State Diagram 9x6 double Place Names 3x2 char Transition Names tl 152 30 4 1 LOG Type simulation identifies that the structure was obtained by after simulation run and was output by the function gpensim The LOG matrix is a 3 X 10 matrix containing the simulation results The easiest way to understand the simulation results is to use the function print_statespace However we can inspect this structure on our own gt
81. e 2 Place 3 4 3 Static PN structure In the main simulation file given in the previous subsection first we get a static Petri Net structure called png in the example as the output parameter of function gpensim png petrinetgraph simple pn def The static PN structure png is a compact representation of the static Petri net graph A static PN structure consists of 5 elelements e g in png name A Simple Petri Net global places 1x3 struct No of places 3 global transitions 1x1 struct global arcs 1x3 struct incidence matrix 1 00 2 000 0 O 1 00 The elements of a static PN structure are 1 name the ASCII string identifier of the Petri net 2 global places the set of all places in the Petri net 3 global transitions the set of all transitions in the Petri net 4 global arcs the set of all arcs in the Petri net and 5 incidence matrix the matrix that depicts how the places and transitions are connected together It must be emphasized that static PN structure is much simpler than run time PN structure A static PN structure is one of the parameters that are input to the function gpensim to start simulation During simulation run time state information and other run time information will be added to the PN structure thus the PN structure will contain dynamic information in addition to static details during simulation the PN structure is called run time PN structure Details of run time
82. elected tokens global info function tRES def pl get_place PN pNOI fire pl tokens 0 42 10 Coverability Tree Coverability tree co tree is a very important issue in the analysis of Petri net models In coverability analysis we determine the states that are reachable from a given initial state This section shows how GPenSIM can be used to obtain co tree of a Petri net The methodology is creating a co tree of a Petri net is almost same as running simulations on a Petri net the only difference is that in step 3 instead of the function gpensim we use the function cotree Step 1 Creating Petri net definition files PDFs and transition definition files TDFs Step 2 Creating main simulation file SMF with dynamic info initial markings and firing times Step 3 Running the SMF using the function cotree instead of gpensim 10 1 Example 09 Cotree with finite states This simple example deals with the Petri net shown in figure 14 The co tree of this Petri net is shown in figure 15 Let us find the co tree using GPenSIM ont Der Figure 14 The Petri net for coverability analysis 43 ti v x T 11 T t R v uz liom E n to ti v TEHER To Figure 15 The reachable states of the Petri net shown in figure 14 10 1 1 Petri net definition file The Petri net definition file is given below PDF for Example 09 Cot
83. eriment setting DELTA TIME In the figure shown below let pl has 5 initial tokens Also let firing time of tl is 7 seconds Though t1 can fire 5 times successively we want it to fire only at the start of every 30 seconds This means t1 is delayed by 30 7 23 seconds 54 Figure 19 Delay Example During the waiting time of 23 seconds t1 is enabled but not firing time advancement will be done in time units of 7 4 1 75 seconds if DELTA_TIME is not explicitly specified MSF Example 12 DELTA TIME file delay demo m global info MAX LOOP 1000 global info DELTA TIME 0 1 png petrinetgraph delay demo def dynamic initial markings p1 3 dynamic firing times tl1 7 sim gpensim png dynamic global info print statespace sim plotp sim p1 p2 Simulation results When DELTA_TIME is not explicitly specified meaning by default DELTA_TIME 1 75 pi p Simulation results When DELTA_TIME is explicitly specified to be 5 0 ER T k PENES p 25H E 2L 4 15 4 1 4 0 5 E A 0 l L 0 10 20 30 40 50 60 70 80 Simulation results When DELTA_TIME is explicitly specified to be 0 1 2 5 0 5 pi p2 10 20 30 56 40 50 60 70 12 TDF POST As stated in the earlier sections there are two types of
84. ess Reversibility One technique used to prove properties of a Petri Net is a coverability tree a coverability tree consists of a tree of markings and possible transitions between Nodes that are a repetitive state are left as leaves and not extended The Coverability tree can be infinite markings consists omega or finite markings do not contain omega An infinite coverability tree is unbounded Reachability is merely a question of whether there is a path from one node to another in the tree 2 5 Why Petri nets Several tools could be used for simulation of discrete event systems Automata Stateflow and Petri nets high level are some of the most commonly used Davidrajuh and Molnar 2009 The lack of structure possibilities hierarchy in Automata is a serious shortcoming for modeling large systems since a large and complex system should be decomposed into modules and sub systems Stateflow developed by The MathWorks extends the Simulink part of MATLAB with functionality similar to Petri net charts are used for graphical representation of hierarchical and parallel states and for the event driven transitions between them Stateflow 2010 A Petri net model of a discrete event system could easily be converted into a Stateflow model and vice versa but learning Stateflow is much more difficult than learning Petri net due to the syntactic semantic and graphical details in Stateflow Stateflow also requires some knowledge of
85. esults The output on screen is different as loop numbers are printed during simulations According to the screen output the simulations are complete after 3 loops Loop nr 1 Loop nr 2 Loop nr 3 A Simple Petri Net definition Number of places 3 Initial Markings Place 1 Place 2 Place 3 3 5 0 step 1 Firing event Transition 1 Starting time 0 Finishing Time 10 Current markings Place 1 Place 2 Place 3 2 3 1 step 2 Firing event Transition 1 Starting time 10 Finishing Time 20 Current markings Place 1 Place 2 Place 3 1 1 2 Completion time 20 It is always a good idea to set the LOOP NUMBER flag global info LDOP NUMBER 1 in the MSF By setting the LOOP NUMBER flag simulation loop number will be displayed during the simulation thus we know that simulation is going on and the computer is not hanging 11 2 1 What are loops See chapter 19 Design of GPenSIM for more details 53 OK we do see loop numbers during simulations a kind of assurance that something is going on But what are loops To understand loops we need to understand the theory for general discrete event simulations DES Any DES software consists of three main elements 1 Global timer Global timer or current time synchronizes all the activities Global timer must not be changed by any transitions events In GPenSIM global timer can be accessed in TDFs by calling pn current_time where pn is the r
86. etails is given in the Petri net Definition File PDF There may be a number of PDFs if the Petri net model is divided into many modules and each module is defined in a separate PDF While the Petri net definition file has the static details the main simulation file MSF contains the dynamic information such as initial tokens in places firing times of transitions of the Petri net Static Petri net graph Main Petri net definition File Simulation E g File pn_def m File E g File sim1 m dynamic details Figure 4 Separating the static and dynamic Petri net details 3 1 Transition Definition Files In addition to these two files main simulation file MSF and Petri net definition file PDF there can be a number of transition definition files TDF too These TDF are classified into two types TDF_PRE and TDF_POST TDF_PRE files are run before firing a transition TDF_POST files are run after firing a transition 3 1 1 Using TDF_PRE and TDF POST According to the Petri net theory a transition can fire enabled transition when there are enough tokens in the input places However in real life situations an event representing a transition can have additional restrictions for firing for example event 2 has preferences priority over event 1 thus event 2 is allowed to fire even though both event 1 and event 2 are enabled to fire In GPenSIM literature these additional restrictions are called user
87. f the Model Though the runway to be modeled is simple it consists of the important elements of the runway dynamics 23 1 1 Assumptions In order to obtain a relatively simple model for simulation and dynamic analysis purposes the following modeling assumptions are made e There are only three types of aircrafts A C handled by the airport e The three types of A Cs use pre calculated runway length 23 1 2 Model elements The important elements of the model are e Runway RWY e Four taxiways TWY e Aircrafts A Cs arriving taxing engaged in terminals and departing e Rules that govern the interaction between A C and use of the RWY The characteristic properties of each of the model elements are as follows 23 1 3 Runway RWY and taxiways TWY A single 2500 m runway is considered with two 90 TWY on both end and two rapid exit taxiways RETs located at approx 1000 m and 1500 m from approach end threshold see figure 2 23 1 4 The three categories of A Cs The difference between aircraft is based on International Civil Aviation Organization ICAO threshold speed categories A to E Only aircraft with categories A B and C are considered The selected traffic mix contains the following types of aircraft with percentage 1 Category A e g lighter Cessna A C 30 2 Category B e g Medium Business Jets 10 3 Category C General Passenger Traffic 60 Category A B and C A Cs occupy 1500 2000 2500 meters of t
88. files as it realizes the main simulation loop Example inside gpensim sim_results global_info timed_pensim png global_info timed_pensim gt global info H lt MAX LOOP MAX LOG SIZE max loop logsize gt PN EIP time punch PN EIP time punch log record Bop colormap_record complete firing gt PN global info lt PN global_info time_advancement PN EIP parent_index global_info PN EIP global_info gt EIP PN LOG MAX_LOG_SIZE Loop Nr MAX_LOOP lt true false simulations complete 173 Name Transition Definition File TDF Purpose To run user defined conditions and to test probe simulation Input PN run time Petri net structure parameters global_info global info packet Dummy variables new color override false selected tokens Out parameters fire or not fire 0 don t fire 20 new color colors assigned by transition override override 0 don t override 20 selected tokens toklDs of any selected tokens for removal consumption global info updated if updated by the transition global info packet Uses Used by Firing conditions Example function fire new color override selected tokens global info tCONVERT def pn new color override selected tokens global info TDF tCONVERT def first select an token tokID select token pn pAD
89. fo ratio_A 0 10 global_info ratio_B 0 30 global_info ratio_C 0 60 png petrinetgraph select color def dyn initial markings pGEN 30 RES gpensim png dyn global info plotp RES pA pB pC print colormap RES pA pB pC 20 1 2 PDF The Petri net definition file is given below PDF for Example 17 COLOR Selection EXAMPLE function PN name set of places set of trans set of arcs select color def global info PN name SELECT COLOR Example set of places pGEN pBUFF pA pB pC set of trans tGEN tA tB tC set of arcs pGEN tGEN 1 tGEN pBUFF 1 pBUFF tA 1 tA pA l1 pBUFF tB 1 tB pB 1 DB EF bEC 1 EC pe 1 20 1 3 TDF tGEN_def m The first transition definition file is for the transition tGEN The only task of this transition definition file is to produce tokens with a color either type A or type B function fire new color over ride selected tokens global info tGEN def PN new color over ride selected tokens global info random number rand 1 89 if random_number lt global_info ratio_A new color type A elseif random number global info ratio A global info ratio B new color type B else new color type C end fire 1 From the above code it is visible that the transition always fire if enabled fire 1 h
90. fo ratio_B 0 10 global_info ratio_C 0 60 global_info MAX LOOP 200 global info LOOP NUMBER 1 ARRIVAL FREQUENCY 30 the main variable STATIC DETAILS png petrinetgraph single rwy def DYNAMIC DETAILS dyn initial markings pARR 100 pCTR2 1 dyn firing times tARR ARRIVAL FREQUENCY tGPL 0 tLRA 5 tLRB 7 tLRC 9 ET2T 5 tBRD 45 tT2R 5 tGPT 0 tTRA 5 tTRB 7 tTRC 9 SIMULATE RES global_info gpensim png dyn global_info print_statespace RES plotp RES pW4L pR2B pW4T 23 4 Program Code PDF function PN_name set_of_places set_of_trans set_of_arcs single_rwy_def global_info PDF single_rwy_def PN_name SINGLE RWY set_of_places pARR pW4L pR2L pACL pR2B pR2D pW4T pR2T pACD pCTR1 pCTR2 109 set of trans tARR tGPL tLRA tLRB tLRC tT2T tBRD tT2R tGPT tTRA tTRB tTRC tCLC set_of_arcs pARR tARR 1 tARR pARR 1 tARR pW4L 1 pWAL tGPL 1 tGPL pR2L 1 pR2L tLRA 1 pR2L tLRB 1 pR2L tLRC 1 tLRA pACL 1 tLRB pACL 1 tLRC pACL 1 DACH 227 1 ET2T uSRJB 1 pR2B tBRD 1 tBRD pR2D 1 pR2D tT2R 1 tT2R pW4T 1 pWAT tGPT 1 tGPT pR2T 1 pR2T tTRA 1 pR2T tTRB 1 pR2T tTRC 1
91. gt sim LOG ans Columns 1 3 Column 4 Col 5 Col 6 Col 7 New state marking Firing Parent Firing Firing Transition state Start Stop raw Time Time no 3 00 5 00 0 0 0 0 0 2 00 3 00 1 00 1 00 1 00 0 10 11 1 00 1 00 2 00 1 00 2 00 10 11 20 22 30 4 2 Firing_Transitions and Enabled_transitions Firing Transitions represents status firing or not of all the transitions at different inspection times The first element in each row is the inspection time followed by the status of the transitions gt gt sim Enabled Transitions ans 0 1 00 10 00 1 00 20 00 0 Row 1 at time O t1 was enabled Row 2 at time 10 t1 was also enabled Row 3 at time 20 t1 was NOT enabled 30 4 3 State Diagram gt gt sim State Diagram ans 0 0 3 5 0 0 0 0 0 0 0 0 10 1 2 3 10 0 0 0 10 0 0 0 153 OoOoOon ooo FPRPOFRRO 20 20 20 EXPLANATION 1 1 1 2 0 0 0 0 0 0 0 0 0 0 0 row no 1 state info Time NOT USED Initial State NOT USED number of cells number of transitions 0 0 3 5 0 0 row no 2 enabled transitions Time NOT USED Enabled number of cells number of places 1 Transitions 0 0 0 0 0 1 row no 3 firing transitions Time NOT USED Enabled number of cells number of places 1 Transitions 0 0 0 0 0 1 Row no 4 state info Time Fired New State not used
92. hat run time PN structure is one of the 5 input parameters This run time PN structure has all the important run time details hence we can inspect this PN structure to study what s going on during simulation Run time PN structure has 21 elements given below are some of them possessing important run time properties PN global places has complete set of current tokens for each place 2 PN global transtions has details about how many times each transition has fired so far 3 PN current time the internal clock time 4 PN token serial number the total number of tokens generated so far 5 PN X the current marking current state 6 PN Firing Transitions indicates which transitions are currently firing 7 PN Enabled Transitions indicates which transitions are currently enabled 1 STATIC Name TDF Example Production facility 2 Run time global places 1x4 struct 3 Run time global transitions 1x3 struct 4 STATIC global arcs 1x6 struct 5 STATIC incidence matrix 3x8 double 6 Run time current time 45 00 7 Run time token serial number 30 00 8 Run time X 10 00 3 00 5 00 2 00 9 Run time Firing Transitions o 1 1 10 Run time Enabled Transitions 1 O 0 23 5 5 Example 03 Implementing Preference through TDF PRE In this example figure 9 transitions t1 and tZ both competes for tokens in pS we prefer t1 over t2 t2 t3 d Figure 9 Petri net model of a pr
93. he RWY for landing and take off respectively 105 Figure 32 Elements of the runway 23 1 5 Governing rules The following rules are used to control the interactions between A C and the use of the runway 1 Arrivals have priority on departures A landing aircraft will not normally be permitted to cross the runway threshold on its final approach until the preceding departing A C has crossed the end of the runway or has started a turn or until all preceding landing A C are clear off the RWY That is the model is governed by elementary air traffic control ATC principles such as only one aircraft at a time on RWY and arrivals have priority over departures 23 1 6 Timing for simulations Runway occupancy times ROT for landing and departures are assumed to be equal for a specific category A C e Category A A Cs take 5 minutes and first 1500 m of the RWY e Category B A Cs take 7 minutes and first 2000 m of the RWY e Category C A Cs take 9 minutes and the whole 2500 m of the RW Y Besides e For arriving A Cs taxiing through any TWYs takes 5 minutes e For departing A Cs lineup time for take off is same taxiing time for arriving A Cs e A Cs arrive at a rate of 15 60 minutes assume random timing e Arrived A C take service time offloading and on boarding passengers and goods of about 45 minutes e Initially there may be some A Cs parked on turf or terminals assume any number of A Cs e YOU MAY ASSUME ANY OTHER
94. idrajuh 2003 Cassandras and Lafortune 2007 10 Carl Adam Petri invented Petri nets in 1962 as part of his dissertation titled Kommunikation mit Automaten at the University of Bonn Petri and Reisig 2008 2 1 Elements of Petri nets a5 W t p3 3 P3 Figure 1 Sample Petri net A Petri net contain four types of elements tokens places arcs and transitions Tokens represent objects in the Petri net models such as materials in a material flow system data in a information flow A token is represented with a dot in Petri net models When the number of tokens becomes large it is usually represented with the number of tokens see figure 1 Places are passive elements such as input and out buffers conveyor belts etc Places hold tokens Figure 1 shows places p poand ps with 4 3 and 1 tokens black spots Each place is capable of holding any number of tokens Arcs are connections between places and transitions Arcs are bipartite meaning it is not possible to have an arc connecting two places together or two transitions together Each arc has a weight which is the number of tokens that are transported simultaneously when the transitions of which the arc is connected to fires Transitions are active elements like machines robots etc Transitions correspond to events and are connected by arcs to places When a transition fire the number of tokens within the places connected to the firing transition are changed accord
95. ifrnd 2 4 pB6 1 dyn firing times tCS normrnd 5000 50 tSC normrnd 5000 50 tINIT unifrnd 280 320 tRES unifrnd 1 10 tSD unifrnd 80 100 ETD unifrnd 25 35 tSUBl unifrnd 10 15 ESUB2 unifrnd 10 15 tSUB3 unifrnd 10 15 tSUB4 unifrnd 10 15 Results gpensim png dyn print_statespace Results 9 2 2 Client client_def m function PN name set of places set of trans set of arcs client def 35 55 55 85 55 5s S5 S6 56 5 55 S5 Ss Ss Sb 7o fo f 5 Ss So 56 76 76 76 16 6 76 76 76 76 6 5 6 76 76 File client def m Definition of client 95 5 56 5 56 5 56 s 56 s 06 o 76 6 76 6 76 16 76 6 76 6 76 6 70 6 70 6 0 6 0 6 0 6 5 6 PN name Client set of places pSR pRR set of trans set of arcs 9 2 3 Internet transmission internet_def m function PN name set of places set of trans set of arcs internet def 95 85 85 55 5 55 55 55 S5 56 95 S5 55 56 5 56 76 6 6 76 6 6 76 6 5 76 0 6 5 6 5 6 5 5 55 File internat def m Definition of internet transmission 40 95 85 55 55 5 55 55 5 55 56 55 55 56 76 5 56 76 56 6 76 6 6 76 6 6 6 0 6 6 0 5 6 0 5 65 PN_name Internet Transmission set of places set of trans tCS tSC j set of arcs 9 2 4 Service Interface Layer sil_def m function PN name set of places set of trans set of arcs sil def EESECECEEEEEEEEEEEEEEEEEEE
96. imulation results with timing are recorded only when a transition complete firing In other words simulation results are recorded only when there is a new state We will discuss an import internal clock issue thorough an example When a transition completes firing the internal clock is advanced by the firing time of the transition When a Petri net system has enabled transitions but none is firing then the internal clock time is advanced by an amount which is equal to 4 of the minimum firing time of all transitions 6 1 Example 04 Delay Example In the figure shown below let p1 has 5 initial tokens Also let firing time of t1 is 7 seconds Though t1 can fire 5 times successively we want it to fire only at the start of every 30 seconds This means t1 is delayed by 30 7 23 seconds t1 Figure 10 Delay Example During the waiting time of 23 seconds t1 is enabled but not firing time advancement will be done in time units of 7 4 1 75 seconds See the gpensim system file timed_pensim m for implementation details MSF Example 04 delay example file delay demo m png petrinetgraph delay demo def dynamic initial markings pl 3 dynamic firing times tl 7 sim gpensim png dynamic global info print statespace sim plotp sim pl p2 PDF Example 04 delay example file delay demo def m function PN name set of places set of trans set of
97. in the system when the simulations are complete Input Simulation Results the structure output by gpensim parameters Out parameters None Uses None Used by main simulation file Example in main simulation file results gpensim pn dynamicpart print finalcolors results Name print cotree Purpose To print cotree structure Input Cotree structure the structure output by cotree parameters Out parameters None Uses print markings Used by main simulation file Example in main simulation file cotree_structure cotree png dyn initial_markings print_cotree cotree_ structure 172 Name timed_pensim Purpose This is the main M function for Petri net simulation Inside the main loop transitions are randomly chosen and checked whether they are enabled or not If they are enabled the token removal and deposition in respective places happens Then the happenings are recorded in the simulation results LOG Input Static Petri net structure output from petrinetgraph parameters global_info Out parameters Simulation results global info Uses max_loop print_loop_nr simulations_complete enabled_transition start_firing complete_firing stochastic_timer_advancement global_timer_advancement pack_sim_results Used by gpensim Note This is one of the most important M
98. ing to the arcs weights and directions when a transition fires it consumes tokens input parts from the input places and puts tokens output parts into the output places For a transition to be able to fire the number of tokens in the input places must be equal or higher than the weights of the arcs connecting the input places to the transition The transition will then be an enabled transition Figure 2 shows the state of the sample Petri net from figure 1 after the transition T1 has fired once a5 W t p3 3 P3 Figure 2 Sample Petri net after one cycle 2 0 Formal Definition of Petri nets A Petri net is a four tuple P T A xy Where Pis the set of places P Bee T is the set of transitions T lr Loss mo A is set of arcs from places to transitions and from transitions to places A c Px T u TxP and X is the row vector of markings tokens on the set of places x x p x p lalo le N xo is the initial marking 2 2 1 Input and Output Places of a Transition In the Petri net in figure 2 the places p and p are inputs to transition fj and ps is an out place of transition fi It is convenient to use tj to represent the set of input places to transition tj and O t to represent the set of output places to transition t when describing a Petri net i r p P p t e Aj ol lo e P p t e A We see from figure 2 that the weight of the arc from input place p to transition f has a weight 2
99. ions presented so far are deterministic However in real life systems all the firing times are stochastic GPenSIM provides a limited facility for stochastic firing times We can use any of the MATLAB standard probability distribution functions for stochastic firing times The following are the most used 1 Guassian normal random function 2 Binormial random function 3 Poission random function and 4 Uniform random function 8 1 Example 07 Stochastic firing times We refer to the CNC production system shown in figure 9 we no longer assume that the firing times are deterministic 1 Robot 1 takes random time Binaomially distributed with seed 10 and factor 0 9 milliseconds binornd 10 0 9 2 Robot 2 takes random time normally distributed with mean 1 and standard deviation 0 1 milliseconds normrnd 1 0 1 3 Robot 3 takes random time uniformly distributed with min 8 and max 10 milliseconds unifrnd 8 10 Thus the Petri net definition file is to be changed accordingly Example 07 TDF example with stochastic timing the main simulation file png petrinetgraph tdf example def dynamics initial markings pFrom_CNC 20 initial tokens here comes the STOCHASTIC TIMING dynamics firing times tRobot_1 binornd 10 0 9 tRobot 2 normrnd 1 0 1 tRobot 3 unifrnd 8 10 Results gpensim png dynamics print statespace Results plotp Results pFrom CNC pBuffer_1
100. l arcs 1x3 struct incidence matrix 1 00 2 00 0 0 O 1 00 Screen dump given above shows that the Petri net structure has 7 elements The elements are 1 name the ASCII string identifier of the Petri net 2 global places the set of all places in the Petri net 3 global transitions the set of all transitions in the Petri net 4 global arcs the set of all arcs in the Petri net 5 incidence matrix the matrix that depicts how the places and transitions are connected together and 6 type not used Let us study the elements and their respective data structures one by one 146 30 1 1 name Name is an ASCII string identifier for the Petri net From the screen dump given above we already know the name of the Petri net which is A Simple Petri Net implementation We can also inspect the name anytime by typing Sim_Res name gt gt Sim Res name ans A Simple Petri Net implementation 30 1 2 global places global places is the set of all places in the Petri net Let s inspect the global places by typing Sim res global places gt gt Sim Res global places ans 1x3 struct array with fields type name tokens max capacity The screen dump given above shows that there are three places inside the global places 1X3 and that each place has the following elements type name tokens and max capacity Let s inspect the places individually The first place gt gt Sim Res global places 1 ans type place nam
101. machined parts already put in output pBuffer 1 is less than 3 In addition number of tokens in pBuffer 1 should be less than that of pBuffer 2 coding these two user defined conditions into the TDF PRE for tRobot 1 is given below As the name of the transition is tRobot_1 this TDF must be named tRobot 1 pre m file tRobot 1 pre m function fire new color override selected tokens global info tRobot 1 pre PN new color override selected tokens global info bl get place PN pBuffer 1 b2 get place PN pBuffer 2 fire bl tokens b2 tokens amp bl tokens 3 Similarly the definition files for tRobot 2 and tRobot 3 are created satisfying the given conditions file tRobot 2 pre m function fire new color override selected tokens global info tRobot 2 pre PN new color override selected tokens global info b2 get place PN pBuffer 2 fire b2 tokens 5 file tRobot 3 pre m function fire new color override selected tokens global info tRobot 3 pre PN new color override selected tokens global info bl get place PN pBuffer 1 b3 get place PN pBuffer_3 fire bl tokens b3 tokens amp b3 tokens 2 20 5 3 Step 2 Assigning the initial dynamics and running the simulations Given below is the main simulation file tdf_example m Example 02 TDF example the main file to run simulation tdf example m png petrine
102. meaning that aircraft arrives at about every 45 minutes with STD 5 minutes But still this will not help we have to generate arrivals at specific or predefined times Generating arrivals at predefined times can be elegantly done with the help of global info as shown in the following example 23 9 Example 26 Arrivals at predefined times Figure 38 Arrival at predefined times Let us assume that jobs arrive at pre defined times e g at the following time 4 10 22 34 36 and 75 23 9 1 MSF Example 26 A Example for pre defined arrival times file profile pn def m clear clc global info MAX LOOP 500 global info Arrival Times 4 10 22 34 36 75 png petrinetgraph arrivals def dynamic initial markings pGEN 1 sim gpensim png dynamic global info print statespace sim plotp sim pBUFF 115 23 9 2 PDF Example 26 A Example for pre defined arrival times file arrivals def m function PN name set of places set of trans set of arcs predefined def global info PN name Demo for pre assigned arrival times set of places pGEN pBUFF set of trans tGEN set of arcs pGEN tGEN 1 tGEN pGEN 1 tGEN pBUFF 1 23 9 3 TDF tGEN_def m function fire new_color override selected_tokens global_info tGEN_def PN new_color override selected_tokens global_info fire 0 to start with
103. micpart firing times tX1 10 tx2 20 dynamicpart resources semafor resource as semafor sim gpensim png dynamicpart plotp sim pl p2 grid on print schedule sim 15 2 2 PDF cr_def m Example 72 Binary semaphore example file cr def m PDF function PN name set of places set of trans set of arcs cr def global info 72 PN_name Implementing Critical region with resources set_of_places pSTART pl p2 set_of_trans tX1 tX2 set_of_arcs pSTART tX1 1 tX1 p1 1 START EX2 1 EX2 p2 1 15 2 3 TDF tX1 pre m function fire PN new color override selected tokens global info tX1 pre PN new color override selected tokens global info tX1 pre oe acquired PN acquire resource PN tX1 if acquired if not suceeded PN priority increment PN tX1 increase trans priority end fire acquired 15 2 4 TDF tX1 post m function PN global info tX1 post transition PN global info tX1 post released PN release resource PN tX1 release semafor 15 2 5 Results Plot 10 T T T T T 7 l l gL laa m dr IRI E l l l p2 j l j 8 l In qM Gee I l l l a amt l l l I Bel TE A 707077 At Sir 0 70077 I I I 7 If B lest Esci Ee y REDDE asis E j l l 5
104. n with colors PN pR2L 1 CAT A if isempty selected tokens global info tLRA count global info tLRA count 1 fire 1 else fire 0 end 23 5 3 TDF for tLRB Landing B type AC function fire new color over ride selected tokens global info tLRB def PN new color over ride selected tokens global info oe function fire new color selected tokens global info tLRB def PN new color selected tokens global info oe selected tokens select token with colors PN pR2L 1 CAT B if isempty selected tokens global info tLRB count global info tLRB count 1 fire 1 else fire 0 end 23 5 4 TDF for tLRC landing C type AC function fire new color over ride selected tokens global info tLRC def PN new color over ride selected tokens global info oe function fire new color selected tokens global info tLRC def PN new color selected tokens global info oe selected tokens select token with colors PN pR2L 1 CAT C if isempty selected tokens global info tLRC count global info tLRC count 1 fire 1 else fire 0 end 23 5 5 TDF for tTRA Take Off A type AC 111 function fire new color over ride selected tokens global info tTRA def PN new color over ride selected tokens global info function fire new color selecte
105. nSIM v4 0 zip or two zip files GPenSIM v4 0 pack 1 zip and GPenSIM v4 0 pack 2 zip zip files Similarly unzip the examples file Examples v4 0 zip under a directory say d GPenSIM Examples 2 Set MATLAB Path Command Start MATLAB Go to the file menu in MATLAB and select set path command MATLAB File Edt View Web Window Help New gt Current Directe Open Culo d Close Command Window Ctrlew Import Data Save Workspace As Preferences ent state 1 Page Setup Print Bp dero 1 IM_Siprint_cotree m 2E _S sources_matrix m 3 Acheck For dominance m 4 ei gpensim Sicotree m Exit MATLAB Culo state 5 Firing event t3 pl p2 p3 p4 0 1 0 0 Setting path command Select Add folder Adding folder 3 Add GPenSIM Directory A new dialog box will appear Browse through the directories and select the directory where you have unzipped the GPenSIM toolbox functions ce aaa nave Adding GPenSIM directory 4 Test Installation Go to MATLAB command window and type gpensim if the following or similar output is printed then the installation is complete gt gt gpensim GPenSIM version 4 0 Lastupdate september 2010 http www davidrajuh net gpensim 2 Introducing Petri net This section gives a brief introduction to Petri nets For further details interested readers are referred to Murata 1989 Dav
106. name Priority Example Petri Net for production facility set of places pS pEl pE2 pE3 set of trans t1 t2 t3 set of arcs pS tl1 1 pS t2 1 pS t3 1 UEl pEl 1 tI pS l1 VEZ pE2 1 EZ ps 1 ES pES 1 t3 pS 1 TDF_PRE for t1 tl_pre m function fire PN new_color override selected tokens global info tl pre PN new color override selected tokens global info tl_pre PN priority_decrement PN ti fire 1 TDF PRE for t2 t2_pre m function fire PN new color override selected tokens global info t2 pre PN new color override selected tokens global info t2 pre PN priority decrement PN t2 fire 1 TDF PRE for t3 t3 pre m function fire PN new color override selected tokens global info t3 pre PN new color override selected tokens global info t3_pre PN priority decrement PN t3 fire 1 Simulation Results Again not perfect 68 14 12 10 pE1 pE2 i pE3 I 10 15 69 20 25 70 15 Using Resources In engineering systems there are always resources like human resources to operate some machines printers as common resources in a network etc Just like machines and robots resources can also be represented with transitions or places depending on the situation However GPenSIM offe
107. ng MSF and petrinetgraph Main Simulation File MSF calls at least three other GPenSIM functions directly e petrinetgraph e gpensim and e print_statespace print_colormap plotp etc PDFs PN graph MainSimulationFile petrinetgraph simulation results or cotree print statespace Figure 52 Collaboration Diagram for MSF 164 global_info PNname set of places set of trans set of arcs petrinetgraph Se rd MINA y la e Ss Ss o S amp Ao Sa place name A place A ES zx a 2 P P 3 9 build_places place Su Blo Sz P a 2 E Ej 3 3 o oO 27 y zy trans name trans build_trans trans source destination arc weight farc incidencematrix PN Pleas o name E E Y Ed gt Y 5 og E A QN o P E t 8 4 5 E E is place 35 2d G 3 ES x 3 E x amp amp y S E lo i get_place get_trans Figure 53 Collaboration Diagram for petrinetgraph 165 32 Description of the Main Functions This section presents detailed description of some of the main GPenSIM functions The following functions are described in detail cotree extractp gpensim gpensim ver MSF PDF petrinetgraph plotp print cotree print finalcolors print statespace timed pensim TDF Name cotree Purpose Creates the coverability tree of a Petri net Input Static Petri net sturcture the structure ou
108. nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn 133 26 1 PheiPetrrnetimodelw unn tdt tete teet ee ntis 133 26 1 2 The dPetrrnetmodel nieder eter tette rer a Ran 134 26 13 SUL AMOS Arata 135 27 Norwegian Traffic Lights uices ixi id 136 27 1 Developing a Petri Net Model for Norwegian Traffic Ligh t 136 27 1 1 State 1 RED to State 2 RED YELLOW essnneeennn 136 27 1 2 State 2 RED amp YELLOW to State 3 GREEN eee 137 27 13 State GREEN to State 4 YELLOW ea aaa 137 27 1 4 State 4 YELLOW to State 1 RED esee 138 27 2 Transition BellniiollSs ass 138 27 3 Program Code for the Petri Net Model essen 138 27 3 1 Main Simulation File cccccsssssccececccecsesessececesccecsesessaceecescesenesenseaeees 138 BE PU Um 139 DB A CEN 139 2h34 A AIR 139 Part Ill Reference Manual 22 222020022an00000nnnnnnn0nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn 140 28 Design of the GPenSIM Simulator cecus 142 28 1 s o C a Fare o 142 29 Further Work Future Extensions esses sess s sess 144 30 Data structures in GPenSIM ce eeeeeeeeeeeee enne e enne nena annnm 146 30 1 Static Structures for Petri net and its elements eese 146 BOR MAMI sete UR ERROR RRN es 147 3
109. no of employees employees available zeros 1 no of tasks global info PRIORITY T1 T2 T3 T4 T5 T6 global_info timing zeros no_of_tasks 3 png petrinetgraph schedule01 def dynamicpart initial markings pS1 1 pS2 1 pS3 1 pS6 1 dynamicpart firing times T1 4 T2 6 T3 5 T4 10 T5 2 T6 7 sim global info gpensim png dynamicpart global info timing global info timing print schedule timing Al Bob 119 In the MSF we are using a print function called print_schedule m to make better printout This function is given below function print_schedule timing list_of_names function print schedule timing list of names no of employees length list of names timing rows timing cols size timing for employee 1 no of employees disp disp list of namesfemployee for i 1 timing rows if eq timing i 1 employee disp Task num2str i Yu num2str timing i 2 num2str timing i 3 1 end end end disp 24 3 Results When we use only one resource Al the time taken will be summation of all the time for individual tasks 34 time units Example 81 MSF scheule01 m no_of_employees 1 print schedule timing A1 The result of simulation is A x Taskl 0 4 Task2 4 10 Task3 10 15 Task4 15 25 T
110. oduction facility MSF MSF prefer m dyn firing times t1 10 t2 7 dyn initial_markings pS 3 png petrinetgraph prefer def sim_results gpensim png dyn print_statespace sim_results plotp sim_results pEl pE2 PDF function PN_name set_of places set_of trans set of arcs prefer def global info PDF prefer def PN_name Preference example set of places pS pEl pE2 set of trans t1 t2 set of arcs pS t1 1 t1 pEl l pS t2 1 t2 pE2 1 5 5 1 Case I tl is strictly preferred Conditions for firing e t1 will fire if it is enabled meaning no TDF for t1 e t2 will fire only is t1 is not enabled Surely t2 will starve function fire PN new color override selected tokens global info t2 pre PN new color override selected tokens global info 24 TDF PRE for t2 t2_pre m Case I if is enabled PN tl fire 0 else fire 1 end Simulation results 3 T T T T A pE1 SHE pE2 2 5r Y e FG ee 2b a pS y 1 54 P d E ra 1 ra P d 0 5 Pi E Y ox L E L L 0 5 10 15 20 25 30 Time 0 New markings ps pEl pE2 3 0 0 At time 0 enabled transtions are tl t2 At time 0 firing transtions are tl Time 10 Fired Transition t1 New markings ps pEl pE2 2 1 0 At time 10 enabled transtions are tl t2 25
111. of 3 5 and 2 machined parts respectively In addition the robots should be operated in a manner that at any time buffer 2 should have more parts than buffer 1 and buffer 1 should have more parts than buffer 3 The conditions stated above shall be coded in the TDF_PRE files 5 1 1 Creating M Files In this example the following M files are created in the two steps e Step 1 In addition to creating the PDF TDF PRES for the three transitions must be also created This is because there are user defined conditions attached to the transitions e Step 2 In the MSF assigning the initial dynamics initial markings and firing times and running the simulations 19 5 2 Step 1 the definition files 5 2 1 Defining the Petri net graph Let s call the PDF for the Petri net in figure 6 as tdf example def m Example 02 TDF example file tdf example def m function PN name set of places set of trans set of arcs tdf example def global info PN name TDF Example Petri Net for production facility set of places pFrom CNC pBuffer 1 pBuffer 2 pBuffer 3 set of trans tRobot 1 tRobot 2 tRobot 3 set of arcs pFrom CNC tRobot 1 1 pFrom CNC tRobot 2 1 pFrom CNC tRobot 3 1 tRobot l pBuffer 1 1 tRobot 2 pBuffer 2 1 tRobot 3 pBuffer 3 1 5 2 2 Coding the user defined firing conditions of the Transitions tRobot 1 will fire only if the number of tokens
112. of arcs Place 1 Transition 1 1 Place 2 Transition 1 2 Transition 1 Place 3 1 Explanation First assign a name or label for the Petri net PN name A Simple Petri Net Second the places are to be identified with place names set of places Place 1 Place 2 Place 3 Third the transitions are to be identified by stating their names set of trans Transition 1 Finally how the elements are connected is defined connecting arcs are to be defined by listing the source the destination and the weights of each arc For example the first arc is from Place 1 source to Transition 1 destination with a unit arc weight gt set of arcs Place 1 Transition 1 1 Place 2 Transition 1 2 Transition 1 Place 3 1 4 1 2 Step 2 The main simulation file assigning the initial dynamics After writing the Petri net definition file PDF e g simple pn def m we need to write the main simulation file MSF In the MSF first we load the static Petri net graph by passing the name of the PDF without the ending m to the function petrinetgraph gt png petrinetgraph simple pn def Second the dynamics such as initial markings on the places and the firing times of the transition are to be assigned Normally we stuff these two information into a packet e g dynamic info in this example and then pass this packet to function gpensim g
113. ol X pp 472 477 2009 Stateflow 2010 The MathWorks Inc Stateflow 7 4 Design and simulate state machines and control logic http www mathworks com products stateflow 2010 K Jensen Coloured Petri Nets Basic Concepts Analysis Methods and Practical Use 2 ed vol 1 Springer 1997 Zhou M C and Robbi A D 1994 Application of Petri net methodology to manufacturing systems Computer Control of Flexible Manufacturing Systems Research and Development Edited by Joshi S B and Smith J S Chapman amp Hall Hong Hong Davidrajuh R 2007 A Service Oriented Approach for Developing Adaptive Distribution Chain International Journal of Services and Standards ISSN Online 1740 8857 ISSN Print 1740 8849 Vol 3 No 1 pp 64 78 175
114. oload Petri net graphs PDFs and to create a static Petri net graph with the function petrinetgraph 3 Toassign initial dynamics and 4 To start the simulation with gpensim When the results are returned they can be also analyzed with tools like print statespace plotp extractp occupancy etc Input parameters Out parameters Uses petrinetgraph gpensim etc tools like plotp print statespace etc Used by Example FILE MSF for MIC mic_new m global_info LOOP_NUMBER 1 print loop number during simulation COMPOSE 3 3 png petrinetgraph client def internet def sil def conn pro iterate def strategy def tactic _def 7 modules DYNAMIC DETAILS dyn initial markings pSR 1 pNOI round unifrnd 2 4 pB3 1 dyn firing times tCS normrnd 5000 50 tSC normrnd 5000 50 tINIT unifrnd 280 320 tRES unifrnd 1 10 tSD unifrnd 80 100 ETD unifrnd 25 35 tSUBI unifrnd 10 15 i ESUB2 unifrnd 10 15 tSUB3 unifrnd 10 15 tSUB4 unifrnd 10 15 SUIMULATE RES gpensim png dyn print_statespace RES 169 Name Petri net Definition File PDF Purpose To define a static Petri net graph Input Optional global_info parameters Out parameters PN_name a text string of text set_of_places
115. ons are tRobot 1 tRobot 2 tRobot 3 At time 15 Firing transtions are tRobot 1 tRobot 2 tRobot 3 45 State 10 Fired Transition tRobot 3 Current State pBuffer 1 pBuffer 2 pBuffer 3 pFrom CNC 3 5 2 0 At time 45 Enabled transtions are gt gt Given below is the plot of how the number of tokens in different places varies with time pFromcNC eei pBuffer 10r pBuffer ge pBuffer 90 22 5 4 Run time PN structure Incidentally TDF_PRE can also be used as a probe into simulation engine The MSF prepares the static Petri net PN structure and the initial dynamic information so that the simulation can be started Once the simulation is started there is no way of knowing what s going on The MSF is blocked until the simulation is complete and the result is given back to the MSF Then we can analyze the results e g with the help of print_statespace During simulations control is passed to TDF_PRE if there is any In the TDF a copy of run time PN structure is available so that we can inspect it to study what s going on Let s take a look into TDF for Robot_1 discussed in the previous subsection file tRobot 1 pre m function fire new color override selected tokens global info tRobot 1 def PN new color override selected tokens global info PN dump contents of PN every time tRobot 1 pre is called In TDF given above we see t
116. ons can manipulate colors see section 12 Colors are inherited by default that is when a token fires it collects all the colors from the consumed input tokens and then it passes these to the deposited output tokens However color inheritance can be prevented by overriding see section 12 An enabled transition can select specific input tokens based on preferred colors see section 13 An enabled transition can select specific input tokens based on the time tokens are created see section 14 Structure of tokens this is discussed in the following subsection 18 1 Structure of Tokens A token has a structure consisting of 3 elements 1 2 E g tokID integer value a unique token ID creation_time integer value the time the token was created by a transition Please note that this time may be different from less than the time the token was actually deposited into a place t_color set of strings a set of colors tokID 101 creation_time 30 t_color TAMIL NORSK ENGLISH 80 81 19 Color Inheritance In GPenSIM colored tokens can only utilized by transitions since transitions are active transition definition files can be coded with controlling colored tokens 1 When a transition fire it inherits colors of all input tokens thus new tokens deposited into output places would have all the colors inherited from the input tokens NOTE inheritance of colors can be prohibited by overriding 2 When
117. or more colors 93 19 Summary Token Selection based on Color 94 19 1 Token Selection From A Single Input Place ooconnnoconnnnccnnnccnconnnconnnnnnoncnonanacinnnos 94 19 2 Token Selection From Multiple Input Places eee 95 20 Token Selection based on Time eese 98 20 1 Example 19 Token selection based on time 99 20 1 PDE fefsudef Tuned ise euasit epo neos qi imt epit ue 99 2012F AVES Feel as 100 20 1 3 PEDE COL dem EEE 100 20454 TDBRSBSEL dern sehe denn 100 201 5 Simulation Result Nr oh O 100 20 1 6 Simulation results Tor LERS iustos ende Pe oM RI DUM se a taa Uo Bera a OU E 101 21 Using Hourly CloCK acomodar ir 75 21 1 Example 31 Hourly Clock for Lunching Clerks eee 75 21 1 1 Functions for hourly clock na 75 21 2 Case A Two clerks work all the 6 au 76 212 1 Simulation results ceedings e eH dai EE A enced 74 21 3 Case B Only one clerk functions from 12 00 Noon eee 77 Zi SIMAO resultieren 78 22 Hybrid Systems Petri Net Models with Fuzzy Inference 79 Part Il Applications 103 23 Modeling a Single Runway Airport uuussussnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn 105 293 1 Description of the Model aussen 105 29 121 Assumplion ioo ere t ot ab PERS E PASSAU E TEE PUN NUN eae rae 105 2
118. owever it also add a color type A type B or type C to new tokens deposited into pBUFF 20 1 4 TDFs for tA tB and tC The only task of this transition definition file for tA tB and tC is to select tokens with specific color In the TDF for tA we force the transition tA to select type A tokens only function fire new color over ride selected tokens global info tA def PN new color over ride selected tokens global info TDF tA def tokID select token color PN pBUFF 1 type A selected tokens tokID this token must be removed none other fire selected tokens FIRE ONLY IF Selected tokens IS NOT EMPTY First tokens from input place pBUFF with color type A is selected by using the function select token color The third parameter 1 is the number of tokens needed If selection is successful then the identity number of the selected token tokID is returned as the output parameter By copying tokID to selected tokens we inform the system that this token must be consumed by the transition Finally we allow the transition to fire only if tokID is not empty meaning that there exist a token with type A color 20 1 5 Simulation results Figure 23 shows the plot of tokens in pA pB and pC Since type C is produced 60 of the time there will about 6 times more tokens in pC than in pA and pB The results shown in figure 23 agrees 90
119. p1 p2 p3 p4 0 2 0 3 46 At time 5 enabled transtions are At time 5 firing transtions are 10 2 Example 10 Cotree with infinite states This simple example deals with the Petri net shown in figure 16 The co tree of this Petri net is shown in figure 17 Let us find the co tree using GPenSIM Oe i 5 OE Figure 16 Cotree example 1 0 0 0 t 0 1 1 0 ta t3 1 O w 0 0 O 1 1 t 0 1 w 0 to ts 1 0 w 0 0 O w 1 Figure 17 Co tree 47 10 2 1 Petri net definition file The Petri net definition file is given below PDF Example 10 Cotree example 2 file function PN name set of places set of trans set of arcs fig 9 def PN name Petri net in fig 4 12 set of places pl p2 p3 p4 set of trans t1 t2 t3 set of arcs pl tl 1 tl pa 1 tL p3 1 p2 t2 1 t2 p1 1 p2 t3 1 p3 t3 1 t3 p3 1 t3 p4 1 10 2 2 The main file The main file after phases 2 amp 3 is given below Example 10 Cotree example 2 the main file to get co tree clear clc png petrinetgraph fig 9 def dyn initial markings pl 1 CT cotree png dyn print cotree CT The print system will print the following on the screen which is equivalent to the graphical co tree shown in figure 17 Petri net in fig 4 12
120. p3 3 5 0 At time 0 enabled transitions are Row 2 ti At time 0 firing transitions are Row 3 155 t1 State 1 Time 10 Row 4 Fired Transition t1 Current State pl p2 p3 2 3 1 At time 10 enabled transitions are Row 5 El At time 10 firing transitions are Row 6 ti State 2 Time 20 Row 7 Fired Transition t1 Current State pl p2 p3 1 1 2 At time 20 enabled transitions are Row 8 At time 20 firing transitions are Row 9 30 4 4 Place_Names and Transition_Names gt gt sim Place Names ans pl p2 p3 Since there is only 1 transition is the system gt gt sim Transition Names ans 30 5 Example 2 for State Diagram Figure shown below depicts a web server consisting of two server machines tX1 and tX2 that will fire alternatively To allow alternative firing we can implement a binary semaphore that can be read and manipulated by the definition files of both transitions 156 gt 1x1 tX2 MSF global_info semafor 1 GLOBAL DATA binary semafor png petrinetgraph loadbalance def dynamicpart initial markings pSTART 10 dynamicpart firing times tX1 10 tX2 15 sim gpensim png dynamicpart global info plotp sim pl p2 print statespace sim Let s inspect the State Diagram element of the simulation results sim sim State Diagram ans
121. ree example 1 function PN name set of places set of trans set of arcs cotree example def PN name COTREE Example Petri Net in Figure 14 set of places pl p2 p3 p4 set of trans ti t2 t3 set of arcs pl tI l1 tl p2 l ti p3 l p2 t2 1 p3 t2 1 t2 p2 1 t2 p4 1 p1 t3 1 p3 t3 1 p4 t3 1 10 1 2 The main file The main file after phases 2 amp 3 is given below Example 09 Cotree example 1 the main file to find the reachable states clear clc clear the workspace amp screen first png petrinetgraph cotree example def dyn initial markings pl 2 p4 1 tokens initially Results cotree png dyn initial markings print cotree Results The function print cotree will print the following on the screen which is equivalent to the graphical co tree shown in figure 14 44 COTREE Example Petri Net in Figure 14 state 1 ROOT node pl p2 p3 p4 2 0 0 1 state 2 Firing event t1 p1 p2 p3 p4 1 1 1 1 Node type Parent state 1 state 3 Firing event tl pi p2 p3 p4 0 2 2 1 Node type Parent state 2 state 4 Firing event t2 pl p2 p3 p4 1 1 0 2 Node type Parent state 2 state 5 Firing event t3 pl p2 p3 p4 0 1 0 0 Node type T Parent state 2 state 6 Firing event t2 pl p2 p3 p4 0 2 1 2 Node type Parent state 3 state 7 Firing event tl pl p2 p3 p4 0 2 1
122. ren J Wilkinson Stochastic Modelling for Systems Biology Chapman amp Hall CRC NY 2006 ISBN 10 1 58488 540 8 Read especially about Gillespi s algorithm in chapter 06 Stochastic timer So far we have been using inbuilt global timer for simulations We did not use any user defined timer or time series for advancing the clock Sometimes we do need to use special timers to advance the simulation time by ourselves In this case we use stochastic timer Predator J P UM DUMP AH Figure 43 Petri net model of the Prey Predator interaction 25 1 Example 25 The Prey Predator ecological equilibrium The equilibrium is stated by 2 simple differential equations known as Lotka amp Volterra equation e The specimen prey e g rabbit r mutates by itself and depleted by predators e g foxes f Tarn Br f dt e The specimen predator e g fox grows due to rabbits access to food and depleted by its own population competition for food Ey f Gr f dt e a f y and 6 are parameters representing the interaction of the two species 25 2 Converting the dynamics to Petri nets Of course the equilibrium is determined by classical partial differential equations Without using mathematical solutions which demands high mathematical skills for higher order 127 systems when many specimen types are involved we go for the analytical reasoning using Petri nets Equivalent Petri net model for the interaction is given
123. rs global resources as a mechanism to simply the models also provided is a print function called print_schedule to print the usage of the resources Given below is a simple example that explains the usage of resources An larger example on scheduling is given in the applications part 15 1 Using Resources The resources are to be declared first in the MSF For example if there three human resources named Al Bob and Chuck then the following declaration will be added to the MSF dynamicpart resources Al Bob Chuck Reserving a resource can be done through the function resource_request For example acquired PN resource reuqest PN T1 seek any resource seek specific resources both Al and Bob acquired PN resource request PN Ti Al Bob In the first case transition T1 seeks reserves one instance of a resource any resource If allocation was successful the flag acquired will be true In the second case T1 seeks two resources but specific resources like Al and Bob this time Releasing the resources a transition has to release all the resources it is holding releasing some or specific resources is not possible release all the resources if any held by T1 released PN resource _ release PN T1 15 1 1 Function print schedule function print schedule sim results For every resource utilized
124. s set_of_place_names global_info optional Out parameters TOKEN_MATRIX contains tokens of places with time Uses extractp extracts tokens from the SIM results structure Used by main simulation file Example in main simulation file sim gpensim png dynamic plotp sim pl p2 p3 Name print_statespace Purpose To print simulation results Input Simulation Results the structure output by gpensim parameters Out parameters None Uses print markings print statespace enabled trans print statespace firing trans print statespace state Used by main simulation file NOTE Not for use with simulations using stochastic timer Example in main simulation file Simulation results gpensim png dynamic print statespace Simulation results Name print colormap Purpose To print colors of the tokens Input Simulation Results the structure output by gpensim parameters set of place names Out parameters None Uses print colormap for place Used by main simulation file Example in main simulation file results gpensim pn print_colormap results dynamicpart pNUM1 pADDED pRESULT 171 Name print_finalcolors Purpose To print colors of the final state colors of the tokens that are left
125. small loop new simulation results and its printout is due to faster sampling pi 3 5 p2 2 57 E 0 5 F J 0 I I I I 0 20 40 60 80 100 120 140 160 180 200 Figure 24 Improved printout due to faster sampling 63 64 14 Prioritizing Transitions In discrete systems we need to increase or decrease priority of an event s in order to give fair chance to the competing events There are some basic facilities in GPenSIM to change priorities of transitions 1 Initial declaration of priorities in the main simulation file 2 Increasing priority of a specific transition 3 Decreasing priority of a specific transition 14 1 Priorities of transitions Initial declaration of priorities in the main simulation file can be done using the global_info global info PRIORITY t1 5 t2 2 t3 10 In the above line we are simply saying that t3 has top priority followed by t2 and t1 has the least priority When we assign priority we can assign any integer value both negative and positive Higher the value better the priority is Increasing priority of a specific transition can be done using the function priority increment which will increase the value just by 1 PN priority increment PN ti priority of tl is now 6 Decreasing priority of a specific transition can be done using the function priority decrement which will redu
126. suring Activation time 0d ias 32 8 Stochastic Firing TIMES canina 35 8 1 Example 07 Stochastic firing times aa 35 9 Modular Model Building uursssnnnnsnnnnnnunnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn 37 9 1 Example 08 Modular Model for Adaptive Supply Chain 38 92 The Modular Approach tx coii taa 40 9 2 The main simulation file MIC 2006 new m esee 40 9 22 Client RARA 40 9 2 3 Internet transmission internet_def m ooooooncnnccnnnnononannnnonnnnnnnnnononononnononannanannnos 40 92 4 Service Interface Layer SU deb Bi ri 41 9 2 5 Iterations module interate_def m oonoocococoncnnccnnonnnonnnnonccnononnnnononononcononnnnanonnnos 41 9 2 6 Strategic module strategy efi u a 41 9 2 7 Tactical amp sub tactical module tactic_def M oconnococcconcccconanonananononocnnnnnnanononos 41 9 2 8 Profile for connecting the modules together conn_pro M eeeen 42 9 3 Transition definition file for tRES tRES_def m ooocccnnnnnnononanonoccnnonannananonononn n 42 10 Goverability Tre 8 43 10 1 Example 09 Cotree with finite States ooo Tert a 43 IO I T Petr aiet detimition Ile ooi ae Rai 44 IOMA Thema leo nett to Bde este ooi om aenea bos T putt 44 10 1 3 Event simulation instead of coverability tree seen 45 10 2 Example 10 Cotree with infinite states ooo 47 10 21 a a Ree aq end
127. t dynamic info initial markings Place 1 3 Place 2 5 gt dynamic info firing times Transition 1 10 4 1 3 The Simulations Function gpensim will do the simulations if the Petri net graph the static part and the initial markings and firing times the dynamic part are passed to it Sim Results gpensim png dynamic info 14 The output argument Sim Results is the simulation results The output argument Sim Results is a structure for the simulation results In order to comprehend the simulation results easily the function print statespace could be used 4 1 4 Viewing the simulation results with print_statespace gt print statespace Sim Results The output is given below Explanation Of course Transition 1 takes 10 milliseconds to produce a token on Place 3 after removing 1 and 2 tokens from Place 1 and Place 2 respectively Time 0 New markings pl p2 p3 3 5 0 At time O enabled transtions are tl At time 0 firing transtions are tl Time 10 Fired Transition tl New markings pl p2 p3 2 3 1 At time 10 enabled transtions are tl At time 10 firing transtions are tl Time 20 Fired Transition tl New markings pl p2 p3 1 1 2 At time 20 enabled transtions are At time 20 firing transtions are gt gt In addition to the ASCII output we can also view the output graphically For example gt plotp Sim Results Place 1 Place 2
128. t currently enabled END transitions global_ Any Enable timer Un Transition advancement YES Y start firing pushes a firing start firin transition into EIP queue Ming sorted in increasing stochastic_ compltion time timer_ Y NO Was Eb advancement record firing transitions EIP YES NO Stochastic 2 system Empty EIP YES NO complete firing pops a firing transition from EIP queue the firing transition with least Y completion time top of EIP complete firing Figure 50 Main loop for simulation 143 29 Further Work Future Extensions There are numerous possibilities for extending GPenSIM We give blow just two e Adaptive GPenSIM a version of GPenSIM in which the arc weights are not fixed and can vary during the simulation run o Self adaptive In each TDF the arc weight of the transition can be changed o Forced adaptive in a specific TDF arc weights of any transition can be varied e Real time soft PLC simulator Instead of global timer the real time clock of the computer can be used In this case the GPenSIM is no longer just a simulator but it becomes a soft Programmable Logic Controller 144 145 30 Data structures in GPenSIM GPenSIM uses data structures to pass information between the functions Some of the structures 1 Structure for Petri net PN there are two Petri net structures a Static PN structure is created b
129. ter a couple of simulation cycles The statement given below limits the simulation cycles to 11 by assigning the value 11 to MAX LOOP global info MAX LOOP 11 GLOBAL DATA MAX SIMULATION CYCLES The code below is for the main simulation file Example 11 Measuring Timing MSF measure timing m clear clc global info MAX LOOP 11 GLOBAL DATA MAX SIMULATION CYCLES png petrinetgraph measure timing def dynamicpart initial markings pl 10 51 dynamicpart firing times ti 1 t2 100 sim gpensim png dynamicpart global info plotp sim pl p2 Simulation results When MAX LOOP is not explicitly specified meaning by default MAX LOOP 200 1 T T p2 0 95 081 UI UNT o A III MN 0 5 0 4 t TUN OAND 0 3 WN 0 2 01H
130. tgraph tdf example def dynamics initial markings pFrom CNC 20 initial machined parts dynamics firing times tRobot 1 10 tRobot 2 5 tRobot 3 15 Results gpensim png dynamics print statespace Results plotp Results pFrom CNC pBuffer 1 pBuffer 2 pBuffer_3 The output of print statespace is given below is one of the 2 possible outcomes 5 3 1 Outcome 1 State 0 Initial State pBuffer_1 pBuffer_2 pBuffer_3 pFrom_CNC 0 0 0 10 At time 0 Enabled transtions are tRobot_1 tRobot_2 tRobot_3 At time 0 Firing transtions are tRobot_2 Time 5 State 1 Fired Transition tRobot_2 Current State pBuffer_1 pBuffer_2 pBuffer_3 pFrom_CNC 0 1 0 9 At time 5 Enabled transtions are tRobot_1 tRobot_2 tRobot_3 At time 5 Firing transtions are tRobot_1 tRobot_2 Time 10 State 2 Fired Transition tRobot_2 Current State pBuffer 1 pBuffer 2 pBuffer_3 pFrom CNC 0 2 0 7 At time 10 Enabled transtions are tRobot 1 tRobot 2 tRobot 3 At time 10 Firing transtions are tRobot 1 tRobot 2 Time 15 State 3 Fired Transition tRobot 2 Current State 21 pBuffer_1 pBuffer_2 pBuffer_3 pFrom_CNC 0 3 0 6 At time 15 Enabled transtions are tRobot 1 tRobot 2 tRobot 3 At time 15 Firing transtions are tRobot 1 tRobot 2 Time 15 State 4 Fired Transition tRobot 1 Current State pBuffer 1 pBuffer 2 pBuffer 3 pFrom CNC 1 3 0 5 At time 15 Enabled transti
131. this function prints a matrix where each row represents the transition that used the resource start time end time oe oe oe oe oe oe In addition the following are also displayed K ST LE SI and LT oe oe 71 15 2 Example 17 Using Resources to realize critical section This example is the same as the one that is described under the section Global Info however we make use of resources rather than global info Figure 26 shown below depicts a web server consisting of two server machines that will fire alternatively First client requests are queued at pSTART Then two routers tX1 and tX2 remove the client requests from the pSTART queue and put it to the queues for Web Server 1 pl and Web Server 2 p2 respectively In order to evenly distribute client requests to both servers one would expect that the two routers fire alternatively meaning that no router fires more times than the other gt tX1 tX2 Figure 26 Load balancing by alternative firing To allow the routers transitions fire alternatively these two transition seek a semafor resource If a transition does not get the semafor its priority is increased so that next time it will get it 15 2 1 MSF cr m Example 17 use of resource for realizing critical function png petrinetgraph cr def dynamicpart initial markings pSTART 20 dyna
132. tokID consisting of tokID for 0 4 tokens If X is empty then no tokens are available with the required color If X consists on 1 2 or 3 tokID then the request by the transition is partially fulfilled If X consists of 4 tokID then the request is fulfilled fully 20 Example 17 Selecting Input Tokens with Specific Color Figure given below depicts a production process Place pGEN represents raw materials and transition tGEN represents a machine that produces 3 types of products e type A with 10 production rate e type B with 30 production rate and e type C with rest 60 of the time Though buffer pBUFF contains all three types of products Transition tA is supposed to select type A products only Similarly tB selects type B products and tC selects type C products only pGEN Figure 29 Selecting tokens with specific color 88 During simulations tGEN adds new color to tokens that will be deposited in pBUFF The new color will be type A 10 of the time type B 30 of the time and type C 60 of the time Since tA will consume only tokens with color type A tokens with color type A are deposited in pA similarly pB and pC will have only tokens with color type B and type C respectively 20 1 1 MSF The main simulation file is given below it shows that number of initial tokens in pGEN is 100 MSF for Example 17 COLOR Selection EXAMPLE global_in
133. tput by petrinetgraph parameters Intial markings Out parameters Cotree structure Uses sources matrix enabled transition new marking check for dominance good name Used by main simulation file NOTE Cotree algorithm is similar to the one by Cassandras amp Lafortune 1998 Example in main simulation file png petrinetgraph cotree example def dyn initial markings p1 2 p4 1 cotree sturcture cotree png dyn initial markings print cotree cotree sturcture PN global places sources 09 sources matrix gt old state COTREE parent lt new state ch eck for dom gt transition PN enabled transit true false new markings transition PN new markings 166 Name extractp Purpose To extract tokens from the Simulation results structure Input Simulation Results the structure output by gpensim parameters set of place names Out parameters TOKEN MATRIX First row 0 set of place indices Second amp subsequent rows first column is time other columns are tokens Uses None Used by main simulation file Plotp Example in main simulation file sim gpensim png pl p2 p3 pl p2 p3 print the token matrix plotp sim extractp sim dynamic Name gpensim Purpose To run simulations and output simul
134. un time Petri net structure 2 Event Scheduler Event scheduler is a loop mainly performing two actions a First checking for any enabled transitions if there are any enabled transition and if they can fire then they will be put in queue called firing transitions implemented in file start_firing m b Second checking the queue for firing transitions When a firing transition is complete it will be removed from the queue implemented in file complete_firing m In GPenSIM file timed_pensim m implements event scheduler 3 Queue discussed above Thus loop number comes from timed_pensim which is called by gpensim The loop number states how many cycles of event scheduler has taken place so far NOTE Chapter 16 Design of GPenSIM gives more details 11 3 Use of DELTA_TIME Section 6 Internal Clock describes an example example 04 delay in which there are enabled transitions but not firing blocked This is situation the clock is advanced by a time interval equal to one fourth of the minimal firing time of any transition We can override this value for timer advancement by assigning a new value to DELTA_TIME Lets repeat the example 04 We will study three cases this time 1 DELTA TIME is not explicitly specified by default delta time equals to of least firing time 2 DELTA TIME 5 3 DELTA TIME 0 1 11 3 1 Example 12 DELTA TIME This example is the same as example 04 But this time we will exp
135. ushing firing transitions into Queue function start_firing e Popping a firing transition from Queue in order to complete it function complete firing The components and the functions are realized in the M file timed pensim m Figure 37 shown below summarizes the main loop realized in the M file timed pensim m Start firing any enabled transitions add firing transitions to EIP queue sorted in increasing completion time y Complete a firing transition from the top of EIP with the shortest completion time Increase global timer copy transition completion time into global timer if any transition is copmpleted otherwise if EIP was empty just move global timer by an incremental value Figure 49 Simplified main loop of the simulation However actual coding of M file timed pensim m is little more complicated due to the processing of stochastic systems as shown in the following figure Figure 38 presents the actual loop for simulation coded in the M file timed gpensim m 142 Increases global timer value by a fixed percentage of the minimal firing time of any transition Increases global timer value by gillespi s algorithm etc Simulations A Complete YES v Pack simulation NO results Y ge
136. vancement m 1111111 CHANGING GLOBAL TIME time advancement is for CHANGING GLOBAL TIME this time series is a realization of Gilespi algorithm function pn global info time advancement pn global info cl global_info c 1 c2 global_info c 2 c3 global_info c 3 128 Prey PRED get_place pn Prey get place pn Predator hl cl Prey tokens h2 c2 Prey tokens PRED tokens h3 c3 PRED tokens H hl h2 h3 probabilities global info prol h1 H global info pro2 h2 H global info pro3 h3 H delta T 1 exp 1 H pn current time pn current time delta T CHANGING GLOBAL TIME 1 1 25 3 4 Transition Definition File t1 def m function fire new color override selected tokens global info tl def pn new color override selected tokens global info function tl def cl global_info c 1 c2 2global info c 2 c3 global_info c 3 Prey PRED get place pn Prey get place pn Predator hl cl Prey tokens h2 c2 Prey tokens PRED tokens h3 c3 PRED tokens H hl h2 h3 probabilities prol h1 H pro2 h2 H pro3 h3 H R rand 1 fire R lt prol 129 25 3 5 Transition Definition File t2 def m function fire new color override selected tokens global info t2 def pn new color override selected tokens global info function fire t2
137. will inspect the global info The new MSF is given below MSF for Example 16 Simple Adder with Color Version 2 FILE simple adder 2 m 86 clear clc pn petrinetgraph simple adder def dynamicpart initial markings p1 1 p2 1 global info sum 0 this is necessary results global info gpensim pn dynamicpart global info print value of the element global info sum disp The sum of two numbers num2str global info sum The result printed on the screen is given below input number 1 21 input number 2 45 The sum of two numbers 66 gt gt 87 20 Token Selection based on Color A transition may select input tokens based on color This is done by executing the function select_token_color There are 4 input parameters to this function the Petri net structure at run time the input place of the transition number of tokens to be selected and finally the required color of the token The output parameter of the function is a set of IDs of the selected tokens set of tokID Of course the number of returned tokID may be not equal to the number originally wanted by the transition depending on availability Usage example if a transition wants 4 tokens from the input place pBUFF with color TYPE A then the transition will execute the following statement X select_token_color PN pBUFF 4 TYPE A The returned value X is a set of
138. y the function petrinetgraph b Run time PN structure is available during simulation copy of run time PN structure is available in TDFs 2 Structure for Place this structure is created by the function place 3 Structure for Transition this structure is created by the function transition 4 Structure for Arc this structure is created by the function are 5 Structure for Token tokens are removed consumed and added deposited during simulations 6 Structure for simulation results this structure is created by the function gpensim 7 Structure for Co Tree this structure is created by the function cotree 8 Structure for Co Tree this structure is created by the function gpensim 30 1 Static Structures for Petri net and its elements In order to inspect these structures let us visit the example given in section 3 again The program code snippet given below shows the main simulation file pn petrinetgraph simple pn def dynamic info initial markings Place 1 1 Place 2 2 dynamic info firing times Transition 1 10 Sim Results gpensim pn dynamic info print statespace Sim Results After execution of the first line of the program snippet given above the function gpensim returns the Petri net structure as an output variable called pn Lets inspect this variable gt gt pn pn name A Simple Petri Net implementation global places 1x3 struct global transitions 1x1 struct globa

General Purpose Petri Net Simulator

Contents

Download Pdf Manuals

Related Search

Related Contents