Petri Nets
Petri nets are one of the best known techniques for specifying business processes
in a formal and abstract way and, as such, Petri nets are an important
basis for process languages. “Formal” means that the semantics of process
instances resulting from process models specified in Petri nets is well defined
and not ambiguous. Petri nets are “abstract”, because they disregard the execution
environment of a business process, so that all aspects other than the
functional and process perspectives are not covered. The functional perspective
in itself is treated in an abstract way, as will be explained below.
In this section, Petri nets are introduced in a pragmatic manner. A large
body of literature is available in the Petri net area; the main references relevant
to business process management are discussed in the bibliographical notes.
In his Ph.D. thesis, Carl Adam Petri generalizes automata theory by concurrency.
He introduces a new modelling approach that has a graphical representation
as well as an equivalent mathematical formalization. Petri nets can
be used to model dynamic systems with a static structure. The static structure
is represented by a Petri net, and the dynamic behaviour is captured by
the token play of the Petri net.
Petri nets consist of places, transitions, and directed arcs connecting places
and transitions. They are bipartite graphs, so that arcs never connect two
places or two transitions. In graphical notations, places are represented by
circles, transitions by rectangles, and connectors by directed arcs. Transitions
have input and output places. The input places of a transition are the places
at the sources of its incoming arcs. Accordingly, a transition’s output places
are located at the end of its outgoing arcs.
The dynamics of the system represented by a Petri net is modelled by
tokens that reside on places. While the structure of Petri nets is fixed, the
tokens may change their position according to firing rules. The current distribution
of the tokens among the places determines the state of the Petri net
and, thus, of the system modelled by it.
A transition may fire if it is enabled. A transition is enabled if there is a
token in each of its input places. If the transitions fires, one token is removed
from each input place and one token is added to each output place. Different
classes of Petri nets exhibit different restrictions on the tokens in a Petri net;
this will be discussed later in this section.
The movement of the tokens in the Petri net according to firing rules is
called token play. The token play is often considered to be a flow of tokens, although this is not exactly true, since tokens are removed from input places
and added to output places; they do not flow from input places to output
places.
Because transitions can change the state of a Petri net, they are considered
active components, which typically represent events, operations, transformations,
or transportations. A place is a passive component, that stands for a
medium, a buffer, a state, or a condition. Tokens are used to represent physical
objects or information objects. In the context of business processes, transitions
represent activities and places containing tokens represent states of the
process instances.
Since Petri nets describe the structure of a system, a Petri net represents
a business process model, and its transitions represent activity models. The
instance level is captured by tokens. This means that the firing of a transition
represents an activity instance. Each process instance is represented by at least
one token; due to split and join nodes, the number of tokens that collectively
characterize one process instance may vary during the lifetime of the process
instance.
Since there can be multiple process instances of one process model, the
tokens in a Petri net may belong to different process instances. This will be
discussed in more detail in Section 4.4, where workflow nets, a Petri net class
specifically tailored towards representing business processes, are discussed.
A Petri net characterizing a business process model is shown in Figure 4.27.
The transitions in this Petri net correspond to activity instances, while the
places and the arcs characterize the execution constraints of the activity instances.
The process starts when a token is put on place p1. The token is
represented by a black dot in that place. Since there is a token on all input
places of the receive order transition, this transition is enabled, and it can
fire.
Once the receive order transition fires, a token is removed from p1 and
a token is put on p2, representing the execution of the receive order activity
instance. The execution time of this activity instance is not represented; in
Petri nets, transitions fire instantly without consuming time.
After the process order transition has fired, concurrent branches are
opened, since the firing of the process order transition puts tokens on both p3 and p4, enabling the send order and update inventory transitions. The
complete order transition is enabled only when both of these transitions have
fired. When the process completes there is one token in p7.
To summarize, the Petri net represents the process model, while the tokens
represent process instances. Since tokens in classical Petri nets cannot
be distinguished from each other, classical Petri nets can only host a single
process instance.
After informally discussing the basic structure of Petri nets and the dynamic
behaviour of the systems represented, we give a formal definition:
Definition 4.1 A Petri net is a tuple (P, T, F) with
• a finite set P of places,
• a finite set T of transitions such that T \ P = ;, and
• a flow relation F (P × T) [ (T × P).
• A place p 2 P is an input place of a transition t 2 T if and only if there
exists a directed arc from p to t, i.e., if and only if (p, t) 2 F. The set of
input places for a transition t is denoted •t.
• A place p is an output place of a transition t if and only if there exists a
directed arc from t to p, i.e., if and only if (t, p) 2 F. The set of output
places for a transition t is denoted t•.
• p• and •p denote the sets of transitions that share p as input places and
output places, respectively.
Graphical representations of Petri nets can be mapped onto a tuple (P, T, F),
and vice versa. For instance, the Petri net shown in Figure 4.27 can be represented
by (P, T, F) such that
• P = {p1, p2, p3, p4, p5, p6, p7},
• T = {t1, t2, t3, t4, t5},
• F = {(p1, t1), (t1, p2), (p2, t2), (t2, p3), (t2, p4), (p3, t3), (p4, t4), (t3, p5),
(t4, p6), (p5, t5), (p6, t5), (t5, p7)}.
The state of the Petri net is characterized by the distribution of tokens on
the places of the net. The dynamic behaviour of a system is represented by
state changes, which are subject to firing rules. As detailed below, there are
different firing rules for different classes of Petri nets.
Definition 4.2 The marking (or state) of a Petri (P, T, F) net is defined by
a function M : P ! N mapping the set of places onto the natural numbers,
where N is the set of natural numbers including 0.
The marking of a Petri net represents its state. The state of the Petri net
shown in Figure 4.28 is represented by M(p1) = M(p3) = M(p6) = 1 and
M(p2) = M(p4) = M(p5) = M(p7) = 0. If the places are totally ordered
by their identifier (as, for instance, in p1, p2, . . . , p7), the marking can be
expressed by an array. In the example, M = [1, 0, 1, 0, 0, 1, 0].
After having discussed the structure of a Petri net and its state, the dynamic
behaviour of a Petri net is addressed.
Definition 4.3 Let (P, T, F) be a Petri net and M a marking. The firing of
a transition is represented by a state change of the Petri net.
• M t! M0 indicates that by firing t, the state of the Petri net changes from
M to M0.
• M ! M0 indicates that there is a transition t such that M t! M0.
• M1 ! Mn means that there is a sequence of transitions t1, t2, . . . tn−1 such
that Mi
ti! Mi+1, for 1 i < n.
• A state M0 is reachable from a state M if and only if M ! M0.
Based on these fundamental definitions, a number of Petri net classes are
introduced that differ with respect to their firing behaviour and the structure
of their tokens.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment