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