This paper presents a new net-reduction methodology to facilitate the analysis of large workflow models. We propose an enhanced algorithm based on reducible subnet identification which preserves both soundness and completion time distribution. Moreover we outline an approach to model the dynamic behavior of business processes by exploiting the power of a class of non-Markovian stochastic Petri net models.
Recently, business process redesign (BPR) has been receiving a lot of attention. In addition to the literature on the management aspects of BPR [AH02],[HC93], several modeling frameworks and software tools to support the redesign trajectory have been presented. Typically, they offer little support for the analytical verification of desirable model properties.
This can be addressed by modeling business processes using Petri nets [Mur89]. The suitability of Petri nets for this field is discussed in [Aal98]. However, few results in workflow systems take into account the notion of time [AHR00],[Zer02] and offer analysis as a means to evaluate the completion time distribution. We need to compute the distribution of completion time. Using the computed completion time distribution we can check whether a design satisfies user requirements. For example, the probability can be computed of violating a certain deadline constraint. It should be clear that such information cannot be obtained if the analysis only yields the average completion time.
Two methods have been proposed for developing a framework to the completion time distribution of workflows. In [AHR00], a compositional approach based on the method of Fast Fourier Transform for analyzing discrete stochastic Petri nets was developed. In [Zer02] a reductional method based on Petri net transformations and closure properties of phase type distribution was proposed. These two methods seem to be very suitable for certain classes of workflows. As an alternative version of these two methods, we extend the repertoire of available analyzable workflows to take into account more complex interaction structures.
Much research has been reported about reduction techniques for general Petri nets. In particular, stepwise refinement and abstraction methods [SM83],[Val79] have been developed for Petri nets, where the reduction technique can be used as a ”divide-and-conquer” approach for the analysis of liveness, boundedness, resource requirements, etc., for complex Petri nets. Our new reduction rule is similar in spirit to this, in that it preserves at the same time correctness and stochastic behavior in workflow modeling. Moreover a general methodology for the modeling and evaluation of workflows, based on a Stochastic Workflow Nets (SWF-net) is presented. The SWF-net is a stochastic counterpart of a class of untimed Petri nets called ”Workflow nets” (WF-net) introduced by Van der Aalst in [Aal98] for workflow analysis.
The major contributions of our work are the following: • the definition of the SWF-net modeling framework that accommodates in quite a natural way the evolution of the workflow instances. • the design of an efficient algorithm based on successive reductions of a Petri net to determine the completion time distribution of large workflow models. Since analytic-numeric methods such as the ones proposed here are rather fast (as compared to simulation), they can be repeated to assess the effect of changes in system design or even to obtain an optimal design.
The paper is organized as follows: Section 2 defines Petri nets, workflow nets, and verification criteria. Section 3 introduces the SWF-net framework and apply it to an example of workflow that serves as a case study throughout the paper. In Section 4 the concept of reducibility is given and the reduction algorithm is developed. The general analytical solution of the SWF-net models of Workflows is then discussed in Section 5 and an application is shown in Section 6. Finally, conclusions are given in Section 7. 2
The classical Petri net is a directed bipartite graph with two nodes types called places and transitions. The nodes are connected via directed arcs. Connections between two nodes of the same type are not allowed. Places are represented by circles and transitions by rectangles.
Definition 1 . A Petri net is a triple (P, T, Ξ): - P is a finite set of places, - T is a finite set of transitions (P ∩ T = ∅), - Ξ ⊆ (P × T) ∪ (T × P) is a set of arcs (flow relation) A place p is called an input place of a transition t iff there exists a directed arc from p to t. Place p is called an output place of transition t iff there exists a directed arc from t to p. A set of input (resp. output) transitions of a place p ∈ P is denoted by •p (resp. p•) and the set of input (resp.output) places of a transition t ∈ T is denoted by •t (resp. t•); for X ⊆ (P ∪ T ), •X = x∈X •x and X• = x∈X x•.
At any time a place contains zero or more tokens, drawn as black dots. The state, often referred to as marking, is the distribution of tokens over places. We will represent a state as follows: p1 + 2p2+ p3 is the state with one token in place p1, two tokens in p2, one token in p3. A Petri net PN and its initial marking are denoted by (PN , M0 ). Transitions change the state of the net according to the following firing rule: (1) A transition t is said to be enabled iff each input place p of t contains at least one token. (2) An enabled transition may fire. If transition t fires, then t consumes one token from each input place p of t and produces one token for each output place p of t. The firing rule specifies how a Petri net can move from one state to the next one. A firing sequence σ = t1t2...tn is enabled if, starting from the initial marking, it is possible to subsequently fire t1, t2, ...tn. A marking M is reachable from the initial marking if there exists a enabled firing sequence resulting in M . The reachability set R(M0) is the set of all markings reachable from the initial marking M0. The reachability graph associated with a reachability set can be constructed as follows: Represent each state by a vertex and place a directed edge from vertex Vi to vertex Vj if the state Vj can result from the firing of some transition enabled in Vi Definition 2 (Live). A Petri net (PN , M0 ) is live iff, for every reachable state M’ and every transition t there is a state M ” reachable from M which enables t. Definition 3 (Bounded, Safe). A Petri net (PN , M0 ) is bounded iff for each place p there is a naturel number n such that for every reachable state the number of tokens in p is less than n. The net is safe iff for each place p and for every reachable state the maximum number of tokens in p does not exceed 1.
Definition 4 (Path) Let PN be a Petri net. A path C from a node n1 to a node nk is a sequence < n1, n2, ..., nk > such that < ni, ni+1 > ∈ Ξ for 1 ≤ i ≤ k − 1. Definition 5 (Strongly connected). A Petri net is strongly connected iff, for every pair of nodes (i.e., places and transitions) x and y, there is a path leading from x to y. A Petri net which models the control-flow dimension of a workflow, is called a Workflow net (WF-net). It should be noted that a WF-net specifies the dynamic behavior of a single case in isolation.
Definition 6 (WF-net). A Petri net PN = (P, T , Ξ) is a WF-net (Workflow net) if and only if: (i) There is one source place i ∈ P such that •i = ∅ (ii) There is one sink place o ∈ P such that o• = ∅ (iii) Every node x ∈ P ∪ T is on a path from i to o.
A WF-net has one input place (i) and one output place (o) because any case handled by the procedure represented by the WF-net is created when it enters the workflow management system and is deleted once it is completely handled by the workflow management system, i.e., the WF-net specifies the life-cycle of a case. The third requirement in Definition 6 has been added to avoid dangling tasks and/or conditions, i.e., tasks and conditions which do not contribute to the processing of cases.
The three requirements stated in Definition 6 can be verified statically, i.e., they only relate to the structure of the Petri net. However, there is another requirement which should be satisfied: For any case, the procedure will terminate eventually and the moment the procedure terminates there is a token in place o and all other places are empty.
Moreover, there should be no dead tasks, i.e., it should be possible to execute an arbitrary task by following the appropriate route through the WF-net. These two additional requirements correspond to the so-called soundness property.
Definition 7 (Sound). A procedure modeled by a WF-net PN = (P , T , Ξ) is sound if and only if: (i) For every state M reachable from state i, there exists a firing sequence leading from state M to state o. (ii) State o is the only state reachable from state i with at least one token in place o. (iii) There are no dead transitions in (PN, i).
In [Aal98] it is shown that soundness corresponds to liveness and boundedness . To link soundness to liveness and boundedness, an extended net P N = (P , T , Ξ) was defined. P N is the Petri net obtained by adding an extra transition t∗ which connect o to i. The extended Petri net P N = (P , T , Ξ) is defined as follows: P = P , T = T ∪ {t∗}, and Ξ = Ξ ∪ { (o, t*), (t*, i)}. In the remainder we will call such an extended net the short- circuited net of PN. Note that P N is strongly connected.
Theorem 1 . A WF-net PN is sound if and only if (P N , i) is live and bounded. Proof 1 See [Aal98].
We refer the reader to [AH02] for more details and explanations about all these notions. 3
Modeling the complex dynamic behavior of workflows requires highly representative and expressive tools. To attack the problem, we resort to the SWF-net models, which combine representation power with modeling features that significantly improve their expressiveness and allow for a compact modeling of workflow aspects. SWF-net models are defined as follows:
2. W : T −→ IR+ − {0} (weight function). The weight function W is added to each transition to resolve conflicts, we denote the weight W (t) of a transition t ∈ T with wt. The delay function F will be used to sample transition delays that represent the firing time of actual transition execution. A transition t ∈ T is called timed if Ft(0) < 1. A transition t ∈ T is called immediate if Ft(0) = 1. Pictorially, square boxes represent stochastic timed transitions and thin bars represent immediate transitions. An enabled transition can fire after time delay sampled from a delay function F . The probabilistic study of a WF-net is made by examining the marking process M(t), obtained by constructing a reachability graph for the net. Markings in which at least one immediate transition is enabled are called vanishing markings. On the other hand, markings in which only timed transitions are enabled are called tangible markings. In the case of tangible marking, any enabled transition can fire next, conflicts are solved on basis of the weights of the enabled transitions, we assume implicitly preselection policy, this in contrast to the race semantics. The preselection policy is reasonable in the context of workflow management, since tasks are often performed by human resources whose work typically cannot (or will not) be cancelled upon completion of other tasks. (see [MBBC89] for a comprehensive treatment of the preemption policies modeling). However, for a vanishing marking, only the enabled immediate transitions are allowed to fire and conflicts are solved on the basis of weights. As the time spent by the process in the latter is zero, since they enable at least one immediate transition, they can be eliminated from a study of the marking process as they have no effect on the state probabilities. We thus obtain a reduced reachability graph in which the vanishing states are no longer explicitly present. A SWF-net captures the dynamic behavior of a single case in isolation within a workflow. The stochastic process that it induces expresses the way that a specific case or workflow instance is handled. This is the reason that the net is uncolored: all tokens refer to the same case.
As it is well known, the addition of stochastic times with infinite support distribution to Petri nets does not change the logical behavior of the model, and therefore all the well known results obtained for WF-nets still apply to SWF-nets. All the considered SWF-nets are supposed to be sound. In this paper we focus on the time between the start and the end of the processing of a single case. Informally stated, this is the completion time. For a meaningful semantics of the completion time, we will insist on any SWF-net to be sound. In the sequel a SWF-net will be simply denoted by (P, T, Ξ).
In the following, we present the guidelines for the SWF-net modeling of workflows through an example of a workflow application which includes most of the typical features of the workflows we are considering here. The dynamic behavior of a workflow can be described as follows. The tasks and the precedence relations among them that constitute a business process are described by a WF-net, in which each task is a transition t ∈ T . We distinguish transitions Ti ∈ T , which stand for tasks, and transitions ti ∈ T that do not have a counterpart in the workflow system. Transition Ti ∈ T have assigned enabling delays with a general distribution FTi (t) with support (0, ∞), whereas transitions ti ∈ T do not consume time for their enabling (timeless), but can have assigned a probability p(ti) (calculated on basis of weights) to model random selection of tokens for firing (random switches).
Fig. 1 shows a workflow model of one business process (Order Processing). The execution of the task (T1) spawns two tasks (T2, T3) that can be processed independently. As an example let (T1) represent the registration of the customer order that invokes two subsequent tasks. After registering the order there is a check to see if the desired goods are available (T2). In parallel a bill is sent to the customer (T3). If the goods are available, they are shipped to the customer (T5). If the goods are not available, there are two possibilities. If the missing products have already been reordered, no replenishment is needed, if the goods have not been reordered yet, replenishment is needed (T4). The occurrence of each of the two previous possibilities is followed by the execution of the task update (T8). The immediate transitions (timeless) t1, t2 and t3 have been added to model the three possible outcomes of executing task T2. After sending the bill, two things can happen: either the payment is received (T6) or a reminder needs to be sent (T7). This process is repeated each period‘ (i.e., a customer can receive many bills for the same order) and it is assumed that eventually the customer will pay. Similarly, the goods are eventually shipped. Therefore, eventually, the customer pays and the goods are shipped. After this the order is archived (T9).
T8 i
T1 P1
P2 t1 P7 T4 t2 P4 t3
P5 T2 P3
P6 T5 P9
T9 o T7 T3
T6
P8 The SWF-net shown in Fig.1 clearly illustrates that we focus on the control-flow dimension. We abstract from resources, applications, and technical platforms. Each task has an unlimited number of resources. The availability of resources is an important factor in the completion time of an actual workflow; as the lack of resources may cause queueing times. We focus on the intrinsic quality of the workflow by not regarding resources. According to [AH02], the usual way to design a business process is to design its structure first and then to allocate resources to it. Therefore, the potential completion time characteristic is used during the design phase, after which appropriate resources are assigned to obtain a completion time behavior that is satisfactory. 4
SWF-net reduction rule is used to transform SWF-nets into smaller SWF-nets which preserve soundness and completion time distribution. In this section we introduce a notion of reducible subnet which is pertinent for tackling the problem of complexity. 4.1
Reduction rule 1: Reducible subnet (RSN ): Let G = (P, T, Ξ) be a SWF-net and X ⊆ P ∪ T be a set of nodes, then N = (P ∩ X, T ∩ X, Ξ ∩ (X × X)) is a RSN of G, iff ∃p, q ∈ P such that,
2. p• ⊆ X ∧ q• ∩ X = ∅ (p is the unique input place and q is the unique output place) 3. ∀ x ∈ X- {p, q}: •x ∪ x• ⊆ X (nodes in X - {p, q} are disconnected from all other nodes outside of X) 4. N is safe Rule. A RSN N may be replaced by a single transition tf with input set •tf = {p}, with output set tf• = {q} and as its firing time distribution the completion time distribution of the considered RSN (see Fig.2). (In section 5 an analytic method is proposed to show how to estimate the completion time distribution.). The reduced net derived from G by applying the RSN reduction rule w.r.t. set X of nodes of G is: G = ({P − X} ∪ {p, q}, {T − X} ∪ {tf }, {Ξ − (X × X)} ∪ {(p, tf ), (tf , q)}) p q p tf q We illustrate the necessity of the fourth condition in Fig.3. The shaded net meets the first three conditions of the RSN reduction rule, but violates the fourth condition, although the global net is sound. Theorem 2 The transformation rule RSN preserves soundness, i.e. if a WF-net is sound, then the WF-net transformed by the RSN rule is also sound.
Proof: Let PN be a sound WF-net. Let PN’ be a net which is obtained by applying the transformation rule RSN1 on PN. We have to prove that PN’ is a sound WF-net. It is easy to see that PN’ is a WF-net. There is still one input and one output place and the P N is strongly connected. (P N is the short cutted Petri net PN’ with an extra transition t∗ which connect place o and place i.) By theorem 1 we know that to prove soundness, it suffices to show (P N , i) is live and bounded. (P N , i) is live and bounded. Therefore, we have to prove that the RSN reduction rule preserves liveness and boundedness: this follows from results in[Val 79] and related work.
Theorem 3 The transformation rule RSN preserves completion time distribution, i.e., a completion time distribution of a SWF-net equals that of the SWF-net transformed by the RSN rule.
Proof: Let SWF-net G be derived from SWF-net G by applying the RSN reduction rule w.r.t. some set X of nodes of G, and let {tf } be the fused transitions of G . Let’s consider our RSN (with the unique input place p and a unique sink place q) in isolation. According to lemma 1, every token which enters the RSN from a place p will eventually reach a place q and the moment there is a token in place q all other places of the RSN are empty since the short-circuited net (that is, the net obtained after adding a transition with the output place q as it is only input and the input place p as it is only output) is live and safe. Therefore, the completion time distribution of the isolated RSN equals the firing time distribution of {tf } which obviously imply the preservation of the global completion time distribution of both nets G and G . 4.2
Reduction rule 2: Reducible subnet (RSN ): Let G = (P, T, Ξ) be a SWF-net and X ⊆ P ∪ T be a set of nodes, then N = (P ∩ X, T ∩ X, Ξ ∩ (X × X)) is a RSN of G, iff ∃p, q ∈ T such that,
2. p• ⊆ X ∧ q• ∩ X = ∅ (p is the unique input transition and q is the unique output transition) 3. ∀ x ∈ X- {p, q}: •x ∪ x• ⊆ X (nodes in X - {p, q} are disconnected from all other nodes outside of X) 4. N is safe.
Rule. A RSN N may be replaced by a single transition tf with input set •p, with output set q• and as its firing time distribution the completion distribution of the considered RSN (see Fig.4).
p q tf Theorem 2 and theorem 3 are still valid for a transition bordered RSN.
Both types of reducible subnets can be identified on an efficient manner. We have a detection algorithm that is quadratic on the size of the input net.
In the following we present a general method development technique which entails isolating the RSN from the original model, analyzing the isolated subsystem and replacing the subsystem by an equivalent atomic net (timed transition with one input place and one output place) whose completion time distribution equals that of the isolated RSN . 5
This approach is based on the general solution method for Semi Markov Process (SMP) [Cin75], which applies for the solution of any SWF-net model. By taking into account the special structure of the workflow models, we greatly enhance the efficiency of the completion time computation.
Definition 9 A SWF-net is an Semi-Markov stochastic Petri nets (SMSPN) if its underlying marking process is a SMP.
Definition 9 does not give an immediate description of the modeling features allowed for SMSPN . Since Markov processes are special cases of SMP, the SPN and GSPN classes of Petri nets belong in fact to SMSPN class. However, to guarantee that the marking process is indeed an SMP, some restrictions must be imposed on the concurrent enabling of the transitions. Because of their generality, it is not easy to check whether a given SWF-net model is a SMSPN or not. In general, the marking process must be inspected, but this can be a very costly check for complex models. A way to build SWF-net that are SMSPN analytically solvable models is to prescribe conditions on the net structure in such a way that a specific structure is definitely found in the underlying marking processes. To this aim, a sufficient constraint to be imposed on the net structure, is the following one: Condition: The firing time of all concurrent transitions must be exponentially distributed. In this case, the Markov property holds (at least) each time a general transition fires or it is disabled. This constraint is the one usually adopted [DTGN84], for it provides an easily checked condition to test for the existence of SMP structure in the underlying marking process. This condition is at least satisfied for a SWF-net state machine (SWF-net where each transition has exactly one input place and one output place).
In the following, let’s denote the Laplace Stieltjes transform (LST ) of a function F (t) by F ∼(s) = 0∞ e−stdF (t) ([Tri02]).
Theorem 4 Let G = (P, T, Ξ) be a SWF-net which is a SMSPN , and Q(t) be a semiMarkov kernel over the reachability set R(M0). The LST of case completion time is given by:
F ∼(s) = e (I − Q∼(s))−1 e’ where e = (1, 0, ......, 0), e = (0, ........0, 1)T and I is the identity matrix. proof : Let Q = {Q(i,j)(t) : i, j ∈ R(M0), t ∈ IR+} be a semi-Markov kernel over the reachability set R(M0) {finite set of all markings that can be generated from the initial marking M0 } and let F(i,j)(t) be the distribution of the first passage time from state i to 1 R(∼i,j)(s) state j. It follows from [Cin75] that: F(∼j,j)(s) = 1 − R(∼j,j)(s) and F(∼i,j)(s) = R(∼j,j)(s) , where R∼(s) = (I − Q∼(s))−1, R∼(s) = [R∼(s)]i,j , Q∼(s) = [Q(∼i,j)(s)]i,j and I is the identity matrix.
The LST of the distribution of the first passage time from the root node to the sink node in the considered reachability graph, which is in fact the distribution of the completion time of a workflow instance, follows immediately.
Remarks: 1- The symbolic evaluation of (I − Q∼(s))−1 is computationally hard. To alleviate this inconvenient, we can use an indexed equivalence over semi-Markov process as specified and defined by [Bra02], which is based on a state aggregation of the SMP . This agregation is O(n3) for all states in the worst case if heavily interconnected. 2- It may happen that an input place p of the RSN N = (P ∩ X, T ∩ X, Ξ ∩ (X × X)) is not a source place, i.e, •p ∩ X = ∅. To obtain its SWF-net version with the same completion time distribution, it suffices to add one place and one immediate transition adjacent to the input place of the place bordered RSN. Therfore, Theorem 4 still applies to any RSN. 3-The completion time distribution of a transition bordered RSN can be estimated by simply adding one place and one immediate transition adjacent to the input transition of the RSN and one transition and one place adjacent to the output transition of the RSN. 6
Our procedure is best explained through the example of SWF-net modeling the processing of orders (Fig.1).
Step 1: Detection of RSNs: RSN1 (see Fig.5)
T8 i T1 P1
P2
T7 T3 t1 P7 T4 RSN1 t2 T2 P3 t3 P6 T5 P9
P5
T9 o P4
T6
P8 Let’s denote by p(ti) = wt1 +wwtt2i +wt3 a probability to fire an immediate transition ti.
Q(p1, p5, t) Q(p1, p6, t) Q(p1, p7, t) Q(p5, p9, t) Q(p6, p7, t) Q(p7, p1, t) Q(∼p1,p5)(s) Q(∼p1,p6)(s) Q(∼p1,p7)(s) Q(∼p5,p9)(s) Q(∼p6,p7)(s) Q(∼p7,p1)(s) = = = = = = = = = = = = p(t3)FT2 (t) p(t2)FT2 (t) p(t1)FT2 (t) FT5 (t) FT4 (t) FT8 (t) p(t3)FT∼2 (s) p(t2)FT∼2 (s) p(t1)FT∼2 (s) FT∼5 (s) FT∼4 (s)
FT∼8 (s) Then, using (theorem 4 ) the LST of the completion time distribution of RSN1 is given by: p(t3)FT∼2 (s)FT∼5 (s) ψ1(s) = 1−p(t2)FT∼2 (s)FT∼4 (s)FT∼8 (s)−p(t1)FT∼2 (s)FT∼8 (s) Step 3 Replace RSN1 by its corresponding atomic SWF-net (see Fig.7) i T1
P1 P2
P4 T*1
P9
The probability β for a case to exit from a place P4 is given by: β = wT6 /wT6 + wT7
Using (theorem 4 ), the LST of the completion time distribution of RSN2 is given by: Step 5 Replace RSN2 by its corresponding atomic SWF-net (see Fig.9) βFT∼3 (s)FT∼6 (s) ψ2(s) = 1−(1−β)FT∼3 (s)FT∼7 (s) i
T1
P1 P2
T*1 T*2
P8
P9 Thus, the original net with 9 tasks has been reduced to an equivalent simple net with only 4 tasks. Our reductional approach decrease greatly the computation effort to analyze the resulting net with more advanced approximative methods [AHR00],[Zer02], or numerical approaches supported by the fairly recent developments in Laplace inversion algorithms [AW92] that can provide numerically stable inversions even for discontinuous functions. 7
Due to the state explosion, a wide range of modeling problems concerning the evaluation of complex workflows, according to aspects like soundness and completion time distribution, are very difficult to handle if they are not decomposed into separate submodels. Our reductional approach offers a suitable solution by means of structural decomposition and aggregation. This approach is based on the identification of general reducible subnets. We have designed an efficient algorithm to perform subnet identification and aggregation, which can be readily incorporated into existing workflow modeling tools. Moreover, the analytical approach presented here can be extended to a larger class of non-Markovian stochastic Petri nets [PST98].