Petri nets and time
A Petri net is a graph-based structure consisting of places and transitions. The net simulates the dynamic behavior of a system by continuously firing enabled transitions when tokens are removed and inserted into places. The presence of a token in a place represents the availability or meeting a precondition of a process that is represented by a transition. In our possibilistic timed Petri network, a token is associated with a time stamp, specifically, a possibility distribution of its availability. In a timed Petri network, each transition has a duration corresponding to the time taken by the process being modeled. Consider a precise timed Petri network, in which every token and transition is associated with a precise time and duration respectively. Assume that a process takes d units of time to perform; the transition corresponding to the process is associated with d units of time. Suppose a token arrives in a place with time stamp t and a transition with precise duration d fires at time t, the newly created token after the firing of the transition now has a time stamp t+d.
In a possibilistic timed Petri network, each token is associated with a possibilistic distribution time stamp, say f(x), and each place is also associated with a possibilistic distribution of processing time, say g(y). When the transition fires in a simple case with one place and an arc, the token created after the firing has a new time distribution given by f(x)⊕g(y). When firing of a transition depends on many tokens, having different time distributions, it is not straightforward how to compute when to fire a transition and how to compute the time stamp of the new tokens.
The algorithm to find the firing a transition and to fire this transition is an extension of a typical algorithm for firing a transition in a Petri net. This algorithm takes into account the timestamps in tokens, durations, enabling and effective enabling time of transitions.
algorithm FireTransition(PN)
input: Petri network PN
output: Success or NoTransitionToFire
begin
Token MinToken ← +Infinity
Transition Firing ← ∅
for all transitions T of PN do
begin
token MaxToken ← -1
for all input places P of transition T do
begin
assume P is enabled
if number of tokens in P < #(P, Input(T)) then P is not enabled
else if MaxToken < max(tokens in P) then MaxToken ← max(tokens in P)
end
if P is enabled and MinToken > MaxToken and MinToken > enabling time of T then
begin
Firing ← T
MinToken ← max(MaxToken, enabling time of T)
end
end
if Firing = ∅ then return NoTransitionToFire
Token NewToken ← (MinToken + duration of Firing)
update enabling time of Firing using NewToken
for all input places P of Firing do
remove minimal token from P
for all output places P of Firing do
add token NewToken into P
return Success
end