Now we are moving into Generalized Stochastic Petri Nets.
In other words, it's called GSPN.
In GSPN, transitions are allowed to be either timed or immediate.
If you recall in the Petri Nets, the transitions are immediate whereas in the stochastic Petri
net the transitions are timed and we assume that each time the transition is exponential
distribution whereas in GSPN, the transitions are allowed to be either timed or immediate.
That means you have the combination of few transitions could be timed, few transitions
could be immediate also.
Transitions with zero firing time, that is nothing but the immediate transitions (drawn
as thin black bars) are called immediate transitions.
Immediate transitions have higher priority over timed transitions.
If several immediate transitions compete for firing, firing probabilities should be specified
to resolve these conflicts.
Now let us consider an example for the GSPN.
Consider M/M/1/5 queueing system.
Here arrival follows a Poisson process with the rate lambda.
Service time is exponential distribution with the rate µ; one server serving one job at
a time; not more than five jobs permitted in the whole system.
So let us draw the stochastic, let us draw the GSPN for the M/M/1/5 queueing system.
M/M/1/5.
We can use the stochastic Petri net which we have drawn for M/M/1 queuing system.
From that we can develop the M/M/1/5 queueing system.
That is the easy one.
That is the advantage with the stochastic Petri net GSPN and so on.
From one model, you can always add some more features to get the another model.
So here we have a restriction with not more than five jobs permitted in the whole system.
So we can go for the M/M/1 queueing system first.
Then we can add, we can include the feature of finite capacity.
So this is M/M/1 queueing system.
Now I have to make a restriction maximum 5 tokens in the place Psystem.
So what I can do, I can draw two arcs.
Whenever six tokens in the place Psystem, all six tokens will be removed at the same
time.
Immediately, five tokens will be deposited to the place Psystem.
That means the latest token, when it comes whenever the system size is five, the sixth
token comes, then all six tokens will be removed and in turn five tokens will be deposited.
Therefore, one token is removed.
So this transition is called tloss.
So whenever I write small t, that means that is the immediate transition.
Whenever we write capital T, that means it is a timed transition.
So this timed transition with the empty rectangle bar, that means it is exponential distribution.
Sometimes we can write, we can draw the rectangle bar with the shaded one.
That is called the timed transition with the constant time.
So here this is the GSPN of M/M/1/5 queuing system with the one place and two timed transitions
and one immediate transition.
If you see the reachability graph for this GSPN, the possible number of tokens in the
places, we have only one places, therefore, the number of tokens in the places will be
0, 1, 2, 3, 4 and 5.
The markings can be possible with the transition firing with the rate lambda, with the rate
lambda and so on whereas 5 to 4, 4 to 3, 3 to 2, 2 to 1, 1 to 0, the transition firing
with the rate µ.
So this is the reachability graph for the G -- the above GSPN, and this is same as the
continuous-time Markov chain of M/M/1/5 queueing system.
Suppose your interest is to find out what is the steady-state probability that the system
is empty?
That means what is the probability that the system is empty, that is p0 in steady state?
That is same as what is the probability that -- what is the steady-state probability that
the place Psystem has no tokens?
Both are one and the same.
In the CTMC, what is the probability that the system is in the state 0 in steady state?
That is same as what is the probability that in steady state, the place Psystem has no
tokens?
Therefore, whatever the measures you wanted for the system instead of making a continuous-time
Markov chain, you can make a stochastic Petri net or GSPN and get the measures in the Petri
net level instead of the state in the Markov chain whenever you are able to get the underlying
reachability graph is isomorphic to the continuous-time Markov chain.
Now we are moving into the another extension of Petri Net.
We started with the Petri Net.
Then we discussed stochastic Petri Net.
Then we have discussed generalized stochastic Petri Net.
Now we are going to discuss Stochastic Reward Nets.
A marking M(t) in a Stochastic Petri Net is called vanishing if at least one immediate
transition is enabled at time t.
A marking which is not vanishing is called tangible markings.
Let M¯(t) be the set of all possible markings at time t.
A guard function g(t) associated with the transition T is a Boolean function defined
over M¯(t) such that the transition T does not fire if the gT(t) is equal to 0.
That means even if it enabled and not inhibited, and it fires, if it is enabled and not inhibited,
and g(t) is equal to 1.
A reward is a non-negative weight associated with each markings.
So we are first defining what is the reward and what is a guard function.
Along with the reward and the guard function, we are going to define the Stochastic Reward
Nets.
A stochastic reward net is an extension of generalized stochastic Petri Net that allows
extensive marking dependency and expresses complex enabling or disabling conditions for
transitions through guard functions, or by assigning one or more reward rates to each
tangible marking.
That means you should know what is tangible marking and you should know what is guard
function and also you should know what is reward rates.
By using these three concepts, the extension of GSPN will be called stochastic reward nets
or in other words, it is SRN.
For a given SPN or SRN, an extended reachability graph is a directed graph with the marking
of the reachability set as the nodes and a directed edge from node M1(t) to M2(t) if
M2(t+T) can be obtained from M1(t) by firing a single transition capital T.
To each edge in an extended reachability graph, some stochastic information is attached.
The stochastic information could be the multiplicative inverse of the mean firing time of the transition
or could be the probability of firing of the transition.
If the expected number of transitions that fires in a finite time is finite, then it
can be shown that a given extended reachability graph can be reduced to a homogeneous continuous-time
Markov chain.
Not all the extended reachability graph will be reduced into the homogeneous Markov chain.
Whenever the condition of expected number of transitions that fire in a finite time
is finite, then only the extended reachability graph can be reduced to the homogeneous continuous-time
Markov chain.
To get the throughput, delay or any other performance measures of the system, which
you are considering, appropriate rewards rates are assigned to the markings of the SRN.
You know the meaning of marking.
So when you assign reward rates to the marking, then you can find out the measures of your
interest.
As SRN is automatically transformed into the Markov reward model and the required measures
of the SRN can be obtained by either a steady-state analysis or transient analysis of the underlying
Markov reward model.
So by assigning proper reward rates, you can study the Markov chain with the rewards called
the Markov model, Markov reward model.
The same way here the stochastic Petri Net along with the assigning reward rates, you
can call it as a stochastic reward nets.
Let's see the simple example of a stochastic reward net.
Consider the Example 6 with the two places Pon and Poff and the two transitions, one
is called a Tfailure and the other transition is called Trepair.
This transition is an input ard and this is the output arc.
Similarly, this is the input arc and this is the output arc.
Assume that Tfailure is exponential distribution with the parameter lambda.
The Trepair, that is also exponential distributed with the parameter µ.
We assume that we have two components.
We have two components in the system.
Each component failure is exponential distribution with the rate lambda.
Therefore, there is another symbol called asterisk.
If the two tokens in the place Pon, then the rate will be 2?.
If one token in the place Pon, then the rate will be ?. For that we have used the asterisk.
That means the actual rate of this transition will be ? times number of tokens in the input
place corresponding to the input arc.
So here if two tokens in the place Pon, then the transition Tfailure has a rate 2?.
Otherwise, it is ?. Therefore, the reachability graph will be (2, 0), (1, 1), (0, 2) and the
corresponding transitions are 2?, ?, (0, 2) to (1, 1) that is µ, (1, 1) to (2, 0) that
is µ.
So this is same as the time-homogeneous continuous-time Markov chain.
Suppose my interest is to find out the availability.
Whenever two tokens in the place Pon or one token in the place Pon, that means the system
is available.
So by assigning the reward rate ri is equal to 1 for the number of tokens in the place
Pon, if it is greater than or equal to 1, that is 1 or if it is 0, number of tokens
in the place Pon, that is equal to 0, that reward rate is 0, then the availability is
nothing but summation ri pi(t) where i is nothing but the marking.
So i is nothing but this is the marking.
Suppose you treat this as a marking 2 and you treat this as a marking 2 and this is
as a marking 3, therefore, here i is running from 1 to the.
So by assigning a proper reward rates ri's, you can get the availability.
The further extensions of the stochastic Petri nets are Markov Regenerative Stochastic Petri
Net, Fluid Stochastic Petri Nets and Coloured Petri Nets.
These are all the references.