The paper presents an architecture of a Petri net based framework for modelling and control of workflow processes. It focuses on the PNEditor module and briefly discusses workflow engine based on the models designed using the PNEditor. Then the paper describes method of synthesis Separating feasible places and an algorithm for reducing the number of places in the resulting Petri net.
There are many different Petri net tools and Petri net based tools for modelling
workflow processes, such as CPN ([
The problem of the most existing editors (let us just mention Viptool as a prominent example), is that they were implemented with different aims, mostly to analyze the model, but they do not provide all the information needed for the generation of a deployable application, such as resource management.
Another problem is with the case generation. Usually, a model obtained via
a Petri net modelling tool can be understood as a general definition of a model
of a process, while the single cases can be understood as instances of the process.
Using an analogy with object-oriented programming, a model can be understood
as a class, while single cases can be understood as objects of that class. In Petri
net based modelling tools, the realization of cases is often done using coloured
Petri nets ([
Another important feature for a successful application of models is a hierarchy, which enables not only to model on different level of abstraction but also to 2
For the above mentioned reason, we develop a new framework for modelling and control of workflow processes based on Petri nets. Presently, it consists of two modules, PNEditor and PNEngine.
PNEditor enables to design a model, which is basically a place/transition nets
enriched with the feature for distinguishing between static and dynamic places
([
The development version of the PetriFlow PNEditor can be downloaded via: http://pneditor.matmas.net/
PNEngine is a light version of a workflow engine based on the models provided by PNEditor. User registered in PNEngine is able to upload processes and thus becoming their owner. The owner of the process can then assign other users to roles defined in the process. Only user assigned to a given role is able to fire transitions contained in the role. Further, PNEngine enables to create new cases for a given process and to control the cases processing according to the business logic given by the Petri net modelling the process. The business logic layer is implemented in J2EE, the connection with the database and persistence of the cases is realized using Hibernate. The user interface is realized via Java Server Pages. The PNEngine is running on a Tomcat server. It enables the users to perform an activity from the task list for actually processed cases, i.e. to fire enabled transitions of the correspondent copy of the net, via a web browser. After a user performs an activity from the task list for a given case, the corresponding transition is fired, the new marking is computed and the task list is updated. Different cases of the same process are able to communicate over static places. 3
PNEditor offers usual features of a graphical editor for designing place/transition nets. It enables to draw place/transition nets, i.e. labeled places, transitions, weighted arcs and markings with multiple tokens per place. The further functionality is saving the net to a file, the definition of roles, subnets (nested nets), saving of predefined subnets to files and their reuse as reusable components, replacement of subnets, definition of static places, which exists once per process, and other standard features, such as unlimited undo-redo actions.
For a better illustration, Fig. 1 gives an overview of the functionality of the PetriFlow PNEditor module: 1. Drawing tool selection: from left: object selection tool, inserting places, inserting transitions, arc drawing, adding/removing tokens/transition firing 2. Square with double border represents a subnet 3. Place with shadow represents a static place 4. Panel with roles: buttons from left: add a role, edit role properties, delete a role.
– role A contains set of transitions: begin, task A, finish (total of 3) – role B contains set of transitions: begin and all nested transitions in subnet task B (total of 6) 5. Buttons for adding or removing transitions from the currently selected roles 6. Both roles are selected so the information icons are displayed on top of the transitions in the diagram: black person icon on the transition describes the situation in which all the selected roles contain this transition 7. White person icon on the transition describes the situation in which only some selected roles contain this transition 4
Usually, business modeller models a task as atomic transitions. On a more detailed level, typically a task can be started, finished, paused, continued or cancelled. Each of such tasks can be illustrated with a part of Petri net given in Fig. 2, which can be understood as a subnet on a more detailed level and should be used as a reusable component.
cancel pause continue
paused not started start started finish
finished
The place “not started” in Fig. 2 describes a state, in which the task has not yet been started and “finished” describes the state reached after the task is finished.
It would be very practical to model workflow processes using such reusable components and in general to give modeller an option to design and use his own reusable components possibly without any semantical restriction.
Another situation in which reusable components represents a desirable feature is in case of complex processes assembled from a relatively independent units with exactly defined inputs and outputs. The PNEditor supports subnets allowing each subnet to have more nested subnets so that the whole hierarchy can be build up in a place/transition net.
In case the user creates a workflow model where the tasks will be represented by transitions, PNEditor gives a choice of replacing a transition with a subnet. The subnets can be replaced by existing stored subnets. In this way, individual transitions can be converted to custom subnets representing reusable components.
In order to explain the concept of subnets, we have to recall some
basic definitions of place/transition nets (for more details see e.g. [
Neighbourhood of a place p ∈ P w.r.t. the net N is a subnet Np = ({p}, Tp, Fp, Wp) of N with the set of places formed by the place itself and the set of transitions Tp = {t ∈ T |(t, p) ∈ F ∨ (p, t) ∈ F } formed by the the union of the preset and the postset of the place p in the net N , i.e. by surrounding transitions of p in net N .
Recall that two place/transition nets are isomorphic, when there exists a bijective mapping between the sets of places and a bijective mapping between the sets of transitions, which preserves arcs and their weights. We say that a place p in a place/transition net is said unique place of the net, if there is no place p0 in the net with the isomorphic neighbourhood.
In the PNEditor, identities of the interface places are not saved when storing a subnet to make it a reusable component, i.e. a subnet is stored just as an ordinary net with an additional information which places form its interface. When replacing one subnet by another stored subnet, the interface places of the replaced subnet are identified with the interface places of the stored replacing net according to the following rules: 1 2 2 3 3 1. In the first place, only unique interface places are identified: A unique interface place p of the replaced subnet is considered to be equal to a unique interface place p0 of the stored replacing subnet, if the neighbourhood of p w.r.t. the replaced subnet is isomorphic to the neighbourhood of p0 w.r.t. the replacing stored net. 2. In the second step, if there exists exactly one unique interface place of the replaced subnet and exactly one unique interface place of the replacing stored net satisfying that their neighbourhoods w.r.t. the respective subnets are not isomorphic, then these interface places are considered to be equal. This correspond to a predicate, that if it is unambiguously possible, then the interface places should be identified. 3. Remaining interface places of replacing subnet replacing stored net are changed to ordinary places and remaining interface places of replaced net become interface places of the replacing net. It means that it is left to the user to identify manually by further editing which remaining interface places of the replaced subnet equal to the remaining interface places of the replacing net. An example of the use of the subnet concept in the PNEditor is illustrated in Fig. 4: 1. The transition is created and converted to subnet 2. Visualization of the inside of the subnet 3. The subnet is modified and saved to a file 4. New subnet is created, selected command for replacing subnet 5. The result of 2 identical subnets
Thus, behind the visualization of a hierarchical process model in the PNEditor using the subnet concept is a single flat place/transition net. 5
We could design process models manually – which can be tedious and errorprone. There is also the possibility to collect logs from real-time processes and let an algorithm do the work for us. Workflow management systems such as the PNEngine can also be used to collect the logs. We just need simple p/t net with all transitions always enabled that will represent expecting activities.
There are multiple methods of Petri net synthesis already invented [
As usual we use the following notations. For details see [
An alphabet is a finite set A. The set of all strings (words) over an alphabet A is denoted by A∗. The empty word is denoted by λ. A subset L ⊆ A∗ is called language over A. For a word w ∈ A∗, |w| denotes the length of w and |w|a denotes the number of occurrences of a ∈ A in w. Given two words v, w, we call v prefix of w if there exists a word u such that vu = w. A language L is prefix-closed, if for every w ∈ L each prefix of w also belongs to L.
Let T be a finite set of activities and C be a finite set of cases. And event is an element of T × C. And event log is an element of (T × C)∗.
Given a case c ∈ C we define the function pc : T × C → T by pc(t, c0) = t if c = c0 and pc(t, c0) = λ else. Given an event log σ = e1 . . . en ∈ (T ×C)∗ we define the process language L(σ) of σ by L(σ) = {pc(e1) . . . pc(ei)|i ≤ n, c ∈ C} ⊆ T ∗.
A net is a triple N = (P, T, F ), where P is a set of places, T is a finite set of transitions satisfying P ∩ T = ∅, and F ⊆ (P × T ) ∪ (T × P ) is a flow relation. Let x ∈ P ∪ T be an element. The preset •x is the set {y ∈ P ∪ T |(y, x) ∈ F }, and the post-set x• is the set {t ∈ P ∪ T |(x, y) ∈ F }.
A marking of a p/t net N = (P, T, F, W ) is a function m : P → N0 assigning m(p) tokens to a place p ∈ P . A marked p/t net is a pair (N, m0), where N is a p/t net, and m0 is a marking of N , called initial marking.
A transition t ∈ T is enabled to occur in a marking m of a p/t net N if m(p) ≥ W (p, t) for every place p ∈ •t. If transition t is enabled to occur in a marking m, then its occurrence leads to the new marking m0 defined by m0(p) = m(p) − W (p, t) + W (t, p) for every place p ∈ P . That means t consumes t W (p, t) tokens from p and produces W (t, p) tokens in p. We write m −→ m0 to denote that t is enabled to occur in m and that its occurrence leads to m0. A finite sequence of transitions w = t1 . . . tn, n ∈ N is called an occurrence sequence enabled in m and leading to mn if there exists a sequence of markings m1, . . . , mn such that m −→ m1 −t→2 . . . −t→n mn. The set of all occurrence sequences enabled t1 in the initial marking m0 of a marked p/t net (N, m0) forms a language over T and is denoted by L(N, m0).
Let (N, mp), N = ({p}, T, Fp, Wp) be a marked p/t net with only one place p (Fp, Wp, mp are defined according to the definition of p). The place p is called feasible (w.r.t. L(σ)), if L(σ) ⊆ L(N, mp), otherwise non-feasible.
Denoting T = {t1, . . . , tn}, a region of L(σ) is a tuple r = (r0, . . . , r2n) ∈ N2n+1 satisfying for every ct ∈ L(σ) (c ∈ L(σ), t ∈ T ): (1) (2) n r0 + X(|c|ti · ri − |ct|ti · rn+i) ≥ 0.
i=1
Every region r of L(σ) defines a place pr via m0(pr) := r0, W (ti, pr) := ri and W (pr, ti) := rn+i for 1 6 i 6 n. The place pr is called corresponding place to r.
Given language L over T , W C(L) = {w ∈ L, t ∈ T : wt ∈/ L} is called a set of wrong continuations of L over T .
Let r be a region of L(σ) and let W C ⊆ W C(L(σ)) is a set of wrong continuations. The region r is a separating region (w.r.t. W C) if for every wt ∈ W C: n r0 + X(|w|ti · ri − |wt|ti · rn+i) < 0.
i=1
A separating region r w.r.t. a set of wrong continuations W C ⊆ W C(L(σ)) can be calculated (if it exists) as a non-negative integer solution of a homogeneous linear inequation system with integer coefficients of the form AL(σ) · r ≥ 0
BW C · r < 0.
The matrix AL(σ) consists of rows act = (act,0, . . . , act,2n) for all ct ∈ L(σ), satisfying act · r ≥ 0 ⇔ (1). This is achieved by setting for each ct ∈ L(σ): act,i = 1
for i = 0, |c|ti for i = 1, . . . , n, −|ct|ti−n for i = n + 1, . . . , 2n.
The matrix BW C consists of rows bwt = (bwt,0, . . . , bwt,2n) for all wt ∈ W C, satisfying bwt · r < 0 ⇔ (2). This is achieved by setting for each wt ∈ W C: bwt,i = 1
for i = 0, |w|ti for i = 1, . . . , n, −|wt|ti−n for i = n + 1, . . . , 2n.
The linear inequation system mentioned can be solved using linear
programming ([
Given an event log σ with set of activities T we search for a preferably small finite marked p/t net (N, m0) such that L(σ) ⊆ L(N, m0) and L(N, m0)\L(σ) is small. According to the method of Separating feasible places we first create a p/t net with all transitions T but no arcs or places. This way, any occurrence sequence is enabled. Then we keep adding feasible places, until each wrong continuation of W C(L(σ)) is prohibited. Each feasible place is created according to one wrong continuation wt ∈ W C(L(σ)). We only calculate separating region w.r.t. {wt} if wt is not already prohibited by already added places, because one place can prohibit multiple wrong continuations. For details see Algorithm 1. 5.3
Algorithm for Reducing the Number of Places In some cases (see Fig. 5) we observed more than necessary number of places in the resulting net, so we created an algorithm for reducing the number of places in the resulting net. This algorithm is also implemented in the PNEditor.
Given a finite set A, the symbol |A| denotes cardinality of A.
Our solution to this problem was to first identify which wrong continuations are prohibited by which places. Each place can prohibit multiple wrong continuations. This information is easy to get: we temporarily remove places P 0 ⊆ P from the marked p/t net (N, m0), N = (P, T, F, W ) and if the net permits given input : An event log σ output: (N, m0), N = (P, T, F, W ) such that L(σ) ⊆ L(N, m0) L(σ) ← process language of σ; A ← empty matrix; (P, T, F, W, m0) ← (∅, activities of σ, ∅, ∅, ∅); foreach w ∈ L(σ) do
add row aw to matrix A; end foreach w ∈ W C(L(σ)) do if w ∈ L(N, m0) then r ← integer solution of A · r ≥ 0, bw · r < 0, r ≥ 0 such that r is minimal; if such solution r exist then p ← corresponding place to r;
P ← P ∪ {p}; end end end coveredW rongContinuations ← {w ∈ W C(L(N, m0))}; foreach p ∈ P do
P ← P \ {p}; undo ← F alse; foreach w ∈ coveredW rongContinuations do if w ∈ L(N, m0) then undo ← T rue; break; end end end if undo then
P ← P ∪ {p};
end
Algorithm 1: The method of Separating feasible places: We add places that
permit all correct continuations and prohibit at least one wrong continuation.
In case a given wrong continuation is already prohibited by an already added
place we do not need to create new one for the wrong continuation – it would
be unnecessary. We slightly modified the existing algorithm – we moved the
cleaning of unnecessary places after computing initial marked p/t net. See the
original algorithm in [
The original method of Separating feasible places constructed each place from exactly one wrong continuation and all correct continuations. We will be constructing new places in the same way except we will be using one or more wrong continuations simultaneously.
First, we pick two places p1, p2 ∈ P . We determine which wrong continuations W Cp1,p2 ⊆ W C are prohibited by these places. Then we construct a new place p3 from W Cp1,p2 using the original method.
Now we compare what is “better”: the two places p1, p2 or the one place p3. We need to define what “better” actually is. We assumed that if the net has overall fewer places, fewer arcs then it is better. We decided to measure the complexity of the net N = (P, T, F, W ) as: complexity(N ) = |P | +
X p∈P,t∈T
W (p, t) + W (t, p).
If the net has lower complexity without p1, p2 and with p3, we replace p1, p2 with p3, else we pick another pair of p1, p2 and repeat the cycle until we tried every combination.
When we make a replace, we run the algorithm again until no replace is made. The algorithm terminates because we have finite number of places.
We decided to test just two places at a time because we sought a fast algorithm. Testing every possible subset of the places would not be practical as it would have exponential time complexity according to the number of places.
Let N ∗ be a set of all possible p/t nets. Let neighbour be a function N ∗ × P × P → {0, 1}. For a given p/t net N = (P, T, F, W ) and p1, p2 ∈ P is neighbour(N, p1, p2) = 1 when ∃t ∈ T : p1 ∈ •t ∧ p2 ∈ •t ∨ p1 ∈ t • ∧p2 ∈ t•, otherwise neighbour(N, p1, p2) = 0.
Further we observed that each combination of places p1, p2 ∈ P , that were later merged to one place p3, were in the same preset or post-set of some transition, i.e. neighbour(N, p1, p2) = 1. We used this observation to improve average case performance of the algorithm. Instead of testing each possible pair p1, p2 ∈ P , for each p1 ∈ P we pick p2 ∈ P such that neighbour(N, p1, p2) = 1. For details see Algorithm 2.
Experimental results were positive (see Fig. 6 and Fig. 7).
a b c d a 2 2 input : Marked p/t net (N 0, m00), N 0 = (P 0, T 0, F 0, W 0) output: Marked p/t net (N, m0), N = (P, T, F, W ) such that
L(N, m0) = L(N 0), |P | ≤ |P 0| and complexity(N ) ≤ complexity(N 0) (P, T, F, W, m0) ← (P 0, T 0, F 0, W 0, m00); A ← empty matrix; foreach w ∈ L(N, m0) do
add row aw to matrix A; end oldN umP laces ← |P |; while True do foreach p1, p2 ∈ P : p1 6= p2 ∧ neighbour(N, p1, p2) do coveredW C ← ∅; foreach p ∈ {p1, p2} do
P ← P \ { }
p ; foreach w ∈ W C(L(N, m0)) do if w ∈ L(N, m0) then
coveredW C ← coveredW C ∪ {w}; end end
P ← P ∪ {p}; end B ← empty matrix; foreach w ∈ coveredW C do
add row bw to matrix B; end r ← integer solution of A · r ≥ 0, B · r < 0, r ≥ 0 such that r is minimal; if such solution r exist then oldComplexity ← complexity(N ); p3 ← corresponding place to r; P ← P \ {p1, p2} ∪ {p3}; newComplexity ← complexity(N ); P ← P ∪ {p1, p2} \ {p3}; if newComplexity < oldComplexity then
P ← P \ {p1, p2}; if Pt∈T (W (p3, t) + W (t, p3)) > 0 then
P ← P ∪ {p3}; end break; end end end if |P | = oldN umP laces then
break; end oldN umP laces ← |P |; end
Algorithm 2: Algorithm for reducing complexity. 6
Although there are many methods for synthesis of Petri nets from logs (sequences, languages, partial languages, etc.), the main drawback when used in practice remains: the obtained nets are still too complicated in comparison with human made models. There are different reasons. Remember, that a net without places enables all sequences of transitions, and each place restricts behaviour by removing some sequences. Often, one reason for getting compicated models is that not each valid sequence is presented in the logs and therefore synthetised net obtain too much places restricting too much behaviour. Obviously, such cases cannot be solved by optimizing algorithms as presented in this paper. However, in the case that the logs are complete, optimization is a crucial step for acceptance of process mining in practice. The presented algorithm provides a simple step towards this direction. However, much of the work still has to be done in this area to nd the right mixture between accuracy of the resulting nets and their readability.