Imperial College London

ISE-2 Surprise 97 Project

Petri Net Models

Written by Nick Chapman

Petri net models have emerged as a very promising modelling tool for systems that exhibit concurrency, synchronisation and randomness. The use of stochastic Petri nets has become particularly important in the modelling of automated manufacturing systems.
A stochastic Petri net (SPN) is essentially a high level model that generates a stochastic process. SPN performance evaluation is simply the modelling of the given system using SPNs and generating the stochastic process that governs the systems behaviour. This stochastic process is then further analysed using known techniques such as Markov Chain models and Semi-Markov chain models. The use of SPNs is considerably useful to the modeler as it is a graphical model and is convenient in the obtaining a credible high level model of a system.
As a modelling tool SPNs offer several advantages:

1. They provide a convenient framework for correctly and faithfully describing an AMS and for generating the underlying stochastic process.
2. Their analysis can be automated and there are available several software tools for this purpose.
3. They can exactly model non-product form features, such as priorities, synchronisation, forking, blocking and multiple resource holding.
4. They can be used a both logical and quantitative analysis.
5. Even if their analysis is intractable, they serve as a ready simulation model.

The Classic Petri Net

Preliminary Definitions

Definition: A Petri net is a four-tuple (P,T,IN,OUT) where
P = {p,p2,p3,...,…pn}
T = {t1,t2,t3,...,…pn}
PuT not= 0, PnT = 0
IN : (P X T) ® N is an input function that defines directed arcs from places to transitions, and
OUT : (P X T) ® N is an output function that defines directed arcs form transitions to places.
Graphically places are represented by circles and transitions represented by horizontal or vertical bars. If IN (pi, tj) = k, where k > 1 is an integer, a directed arc from place pi to transition tj is drawn with the label k. If k = 1 we include an unlabeled arc and if k = 0 then no arc is drawn.
Places of Petri nets usually represent states or resources in the system while transitions model the activities of the system.

Representational Power

1. Sequential Execution: In Figure 1.1, transition t2 can fire only after the firing of t1. This impose the precedence of constraints "t2 after t1." Such precedence constraints are typical of execution parts in an AMS. Also, this construct models the casual relationship among activities.
2. Conflict: Transitions t1, t2 and t3 are in conflict in Figure 1.2. All are enabled but the firing of any leads to the disabling of the other transitions. Such a situation will arise, for example, when a machine has to choose among part types or a part has to choose among several machines. The resulting conflict may be resolved in a purely non-deterministic way or in a probabilistic way, by assigning appropriate probabilities to the conflicting transitions.
3. Concurrency: In Figure 1.3, the transition t1, t2, and t3 are concurrent. Concurrency is an important attribute of AMS interactions. A necessary condition for transitions to be concurrent is the existence of a forking transition that deposits a token in two or more output places.
4. Synchronisation: Often, parts in a AMS wait for resources and resources will wait for appropriate parts to arrive. The resulting synchronisation of activities can be captured by transitions of the type shown in Figure 1.4. Here, t1 will be enabled only when a token arrives into the place currently without token. The arrival of a token into this place could be the result of possibly complex sequence of operations elsewhere in the rest of the Petri net model. Essentially transition t1 models the joining operation.
5. Merging: When parts from several streams arrive for service at the same machine the resulting situation can be depicted as in Figure 1.5. Another example is the arrival of several parts of several sources to a centralised warehouse.
6. Confusion: A situation where concurrency and conflicts co-exist as in Figure 1.6. Both t1 and t3 are concurrent while t1 and t2 are in conflict, and t2 and t3 are also in conflict.
7. Priorities: The classical Petri net discussed so far have no mechanism to represent priorities. Inhibitor nets defined later include special arcs called inhibitor arcs to model priorities.

Stochastic Petri Nets

The concept of associating random time durations was first investigated independently by Natkin (1980) and Moloy (1981) and this was the origin for the emergence of stochastic Petri Nets and their extensions as a principal performance modelling tool.

Definition: A Stochastic Petri Net is a six-tuple (P, T , IN, OUT, M0, F) where (P, T , IN, OUT, M0) is a Petri net and F is a function with domain (R(M0) X T), which associates with each transition in each reachable marking, a random variable.

This is a very general definition of a stochastic Petri net.

The basic philosophy underlying the use of various classes of stochastic Petri net in performance evaluation is the equivalence of their marking process, under appropriate distributional assumptions, to a Mrkov or Semi-Markov process with discrete state space. The typical steps in stochastic Petri net evaluation include:

1. Modelling the given system by a stochastic Petri net.
2. Generating the marking process.
3. Computing the steady state probability distribution of states of the marking process
4. Obtaining the required performance measures from the steady state probabilities.