A method for modeling workflow processes using a Petri net based multilevel formalism is proposed, which yields modular and hierarchical descriptions of the organization, the processes, resource management, and user interactions. The models allow the synthesis of agent based software in which mobile agents guide the cases through the organization units; the software can be interactively executed for simulation purposes or distributed within a computer network for implementing a workflow management system. A tool for editing and simulating the models is presented.
Since the early nineties, Workflow Management Systems (WfMS) has been widely
used to improve organizational performance in a broad variety of industries [
According to the Workflow Management Coalition (WfMC, an international
nonprofit organization responsible for the establishment of standards and some
common grounds in the field), a WfMS is: “A system that defines, creates and
manages the execution of workflows through the use of software, running on one or
more workflow engines, which is able to interpret the process definition, interact with
workflow participants and, where required, invoke the use of IT tools and
applications” [
Workflow is concerned with the partial or full automation of business processes
[
Workflow management aims to improve process performance and help to achieve
business goals with high efficiency [
Although PN provides clear and unambiguous models, when the systems are large
and complex the handling and building of ordinary PN models becomes a difficult
task. In this paper we propose a multilevel modeling technique based in the n-Level
Net System (n-LNS) formalism [
Using this formalism, in this paper a general technique for conceiving multi-level
models is proposed, allowing a systematic construction of the model [
The remainder of this paper is organized as follows. Section II summarizes the nLNS formalism. In Section III we present a methodology for the modeling of workflows using n-LNS; section IV presents some simulation results and the last section some conclusions and future work.
The formalism follows the approach of nets within nets introduced by R. Valk in [
An n-LNS model consists mainly of an arbitrary number of nets organized in n levels according to a hierarchy; n depends on the degree of abstraction that is desired in the model. A net may handle as tokens, nets of deeper levels and symbols; the nets of level n permits only symbols as tokens, similarly to CPN (Colored PN). Interactions among nets are declared through symbolic labeling of transitions.
Figure 2 sketches pieces of the components of a 4-LNS model. The level 1 is represented by the net NET1, the level 2 by the nets NET2,1 and NET2,2, the nets NET3,1, NET3,2, NET3,3, and NET3,4 compose the level 3, and the nets NET4,1, NET4,2, NET4,3 form the level 4.
A net of level i is a tuple NETi = (typeneti, μi), where is composed by a PN structure, the arcs weight (π((p, t), lab) or π((t, p), lab)) expressed as multi sets of variables and symbols, and a transition labeling function declaring the net interaction. μi is the marking function (see fig. 1).
A n-LNS model, called net system, is a n-tuple NS= (NET1, NET2, … NETn) where NET1 is the highest level net, and NETi = {NETi,1 , NETi,2, ... , NETi,r} is a set of r nets of level i.
The components of a model may interact among them through synchronization of transitions. The synchronization mechanism is included in the enabling and firing rules of the transitions; it establishes that two or more transitions labeled with the same symbol must be synchronized. A label may have the attributes ≡, ↓, ↑, which express local, inner, and external synchronization respectively.
A transition t of a net of level i NETi is enabled with respect to a label lab if: -There exists a binding bt that associates the set of variables appearing in all π((p,t),lab). - It must fulfill that ∀p ∈•t, π((p, t), lab)<bt> ⊆ μi(p).
(<bt> is not necessary when the level net is n). - The conditions of one of the following cases are fulfilled: Case 1. If there is not attributes then the firing of t is autonomously performed.
Case 2. If lab has attributes one must consider the combination of the following situations:
{≡} It is required the simultaneous enabling of the transitions labeled with lab≡ belonging to other nets into the same place p’ of the next upper level net. The firing of these transitions is simultaneous and all the (locally) synchronized nets remain into p’. {↓}) It is required the enabling of the transitions labeled with lab↑ belonging to other lower level nets into •t. These transitions fire simultaneously and the lower level nets and symbols declared by π((p, t), lab)<bt> are removed.
{↑}) It is required the enabling of at least one of the t’∈ p’•, labeled with lab↓, of the upper level net where the NETi is contained. The firing of t provokes the transfer of NETi and symbols declared into π ((p’, t’), lab)<bt>.
The firing of transitions in all level nets modifies the marking by removing π((p, t), lab)<bt> in all the input places and adding π((t, p), lab)<bt> to the output places.
In fig. 2, NET1 is synchronized through the transition labeled with a↓ with NET2,2, NET3,2, NET3,4 and NET4,2 by mean the transitions (locally synchronized) labeled with a↑; all these transitions must be enabled to fire. The simultaneous firing of the transitions removes these nets from the input places.
NET2,1, NET3,1 and NET4,1 are synchronized through the transitions labeled with b↓, b≡, b↑ respectively; the firing of the transitions changes the marking of NET2,1 and NET3,1; NET4,1 is removed from the place of NET2,1.
NET3,3 is removed from the input place of NET2,2 and NET4,3 is removed from NET3,3; this interaction is established by c↓, c↓↑, c↑, respectively. c3
↓ a x, y x NET3(4) c1 a≡↑ NET4(3) c3 c↑
c2 NET2(1
NET3(2) c2
a≡↑ a≡↑, c↓ NET2(2)
NET3(3)
c↓↑ NET1 c1 c2
NET4(1)
c1 ↑ b
c3 b ≡↓
NET3(1)
c2 c2 NET4(2) ↑ a
≡ b The use of n-LNS induces a modular and hierarchical modeling methodology allowing describing separately the environment and the behavior of all the involved components in a workflow problem, and then, integrated such models into a global one through transition synchronization.
As mentioned before, the workflow problem can be clearly described using only 3 levels of the n-LNS (see fig. 3).
The highest level net (1) describes the organization structure, i.e. the different organizational units involved in the solution of the workflow problem (case) and the relations (flow of information, tasks or documents) among them.
The second level net describes the general behavior of an entity (software agent)
which guides a process (current case) within the organizational units and executes the
tasks within the departments expressed in the WF-process definition net (both types of
nets modeled as nets of level 3 and described later); this entity net will be a token-net
for the net of level 1 [
For the sake of readability the proposed method is illustrated through a case study dealing with claim processes in an insurance company.
Consider the following description: “Define the WF for the claim processes in an insurance company in which a customer claims the insurance policy of a personal property (real state, car, life insurance). The company must receive the claim, request personal data from the customer (insurance policy number, etc.), and verify the insurance validity, payments, and beneficiaries. It must do the adjustment of real damages, validate the case, calculate the corresponding assessment, do the necessary payments to the customer if the complain is valid, or inform in case that the process has some invalid data”.
Now we are going to describe the different nets that compose the model at the three levels.
This net describes the general structure of the company and the possible workflow between every pair of organizational units or departments. First, the different departments in which some tasks are executed are identified; then one must consider all the possible flows. The departments are represented by places and the flows by transitions (see Fig. 4); the firing of a transition means that the next task will be performed in the organizational unit that represents the output place of the fired transition. Furthermore, places for representing resources may be added in a classical structure allocation-release.
The tokens in this net are nets of level 2; for example in place P1 of the model of Fig.4, there is a token Net2,1 which will be detailed later. If needed, add transitions for allowing the cancelation of cases (see T7 and T9 for Fig. 4). Once this net is defined one must add synchronization attributes to the transitions. Also it is recommended to add an initial transition (for the beginning of the case) and a final transition (for the termination of the case). All transitions should include the internal (↓) synchronization attributes; it implies that the token-nets of level 2 must have some transitions labeled using the same symbols, with the external (↑) synchronization attributes.
The case begins with the firing of the transition t1, and ends with the firing of the transition t6 according to fig. 4. Finally define Net1,1 = (G, TOKEN1,1, LABEL1,1, VAR1,1, τ, λ, χ, π). We can also include in this model another kind of information, for example, the available resources for each department. This can be achieved adding places to the obtained net (like the labeled as ResourceI in fig. 4). The allowed tokens for this net are symbols for the places which represent resources, and a net of level 2 (Net2,1) for the places which model organizational units.
Define Net2,1 = (G, TOKEN2,1, LABEL2,1, VAR2,1, τ, λ, χ, π), which models the net that handles the case. This net must also include as marking the level 3 nets describing all the tasks the agent is able to perform during a WF-process execution.
Figure 5 shows the Net2,1 for this case study. A net Net3,1 is included as token in place P2, and the rest of the third level nets (Net3,2, Net3,3, etc.) are added as tokens for P1. T1 represents the beginning of the execution of the task in the plan in P2, and T2 represents the ending of execution of such a task. For synchronizing the beginning and ending of the tasks execution it is necessary to add labels as showed in fig. 5; the labels B.Claim_register↑↓ in T1 and E.Claim_register↑↓ in T2; both transitions must be synchronized internally (↓). Finally, the transition T3 is used to synchronize externally the displacement of this net within the organization with the net of level 1 (labels mValida↑↓, mAdjust↑↓, etc.).
• WF-Process definition net. In general it is a net having a simple structure, which describes the sequences of tasks an displacement operations required to accomplish a WF-process; every stage in the plan is specified as place representing the tasks or the displacement operations; two transitions (input and output) represent the beginning/ending of a task; they are synchronized with T1 and T2 of the net Net2,1. The transitions representing displacements must be synchronized with T3, also of Net2,1. All the transitions must be externally↑ synchronized.
It is also necessary to add a place for the beginning of the case and another one for the ending of the case (as p0 and p18 respectively in fig. 6). Finally define Net3,1 =(G, TOKEN3,1,LABEL3,1,VAR3,1, τ, λ, χ, π); an example of this net is showed in Fig.6. • Involved tasks. These nets describe in detail the operations involved in the execution of the tasks. In general they are nets having a simple state machine structure. We can obtain each net identifying the operations required for each task and its precedence order; with this information model each net adding also a transition for the external↑ synchronization of the beginning and another one for the ending of the task execution (see the labels B.Claim_register↑ in T0 and E.Claim_register↑ in T5 in Fig. 7a). For each task i define the nets Net3,i = (G, TOKEN3,i, LABEL3,i,VAR3,i, τ, λ, χ, π), for i=2,3,….r, r is the number of tasks plus 1. Fig. 7 shows the models of two tasks.
Although the model construction is easily performed by following the proposed modeling methodology, the size of models becomes large as the complexity and quantity of activities in the system grow. In the absence of analytical procedures for verifying the correct functioning of the resulting models, interactive simulation appears as a useful and suitable solution for validating the obtained models. This task is enlightened by the use of a simulation software tool.
In this section we describe the simulation procedure for n-LNS models and the tool for editing and executing such models.
The simulation of n-LNS models consist in the interactive execution of the models according to the rules for enabling and firing transitions. We are going to briefly describe a procedure, usually named token player, which implements such rules.
The n-LNS models, edited through a visual interface, are coded into a XML file
according to the standard format Petri net markup language (PNML) [
From the Data model, a set of objects representing every Netij are built. Every object evolves as the corresponding Netij by verifying the transition enabling conditions and the transition firing mechanism. Both enabling and firing procedures involve interactions among Netij-objects for checking synchronizations declared on the labels.
The simulation of the case of study has been performed through the execution of the 3-level net model described above. This task was possible with the help of MASGAS, a software tool that allows the visual edition and the interactive execution of multi level net models expressed in n-LNS.
The tool provides facilities for the interactive execution of the model: for a current marking the system indicates, through the highlighting of transitions, which transitions are enabled with respect to which label; then the user selects the transition to fire. After the firing the new markings of the involved nets are reached and displayed on the corresponding windows.
Based on n-LNS, MASGAS provides a complete syntactic control over the
different hierarchical levels of the net system; this avoids nesting of upper level nets
allowed by other net within nets simulators [
Below we are including several views of the edited model. Every net is built in a single window and it can be saved and updated for model adjustments.
In Fig. 4 it is showed the net which describes the company structure where the workflow tasks will be performed (net of level 1). Notice that the transition t1 is enabled (label begin); when it is fired, the given case begins and the net that guides such case is generated (as the token in P1 also in Fig. 4).
In Fig. 5 the Net2,1, described in section 3, is showed; the edited net shows the defined initial marking. At this situation the entity is ready to perform the initial task in the pertinent department (Net1,1 in Fig. 4, where this net is contained). When transition t1 of Net2,1 is fired, it means that the net contained in its place p2 (net Net3,1 in Fig. 6) indicates that a particular task (one net as Net3,2 in Fig. 7) need to be performed and will be selected (thanks to transitions synchronization) from the available tasks described by token-nets in place p1. The firing of B.Claim_register produces the evolution of this net indicated in Fig. 8.
Figure 6 shows the edited model for the Workflow Process definition Net Net3,1; when transition t0 is fired (B.Claim_register↑ label), that indicates the beginning of the execution of the corresponding task (Claim_register task in Fig. 7a, in which t0 of Net3,2 is fired with respect also to the label B.Claim_register↑; the firing is performed at the same time that t0 from the net Net3,1 of Fig. 6). The nets Net3,1 and Net3,2 are released (returned to the places P1 and P2 respectively) after the firing of the transition T2 of Net2,1. When the given task needs to be performed in a different department than the current one, the transition Move_Next_Department is used (Fig. 9, label mValida in T2), and indicates that the entity migrated to another department within the organization (as indicated in Fig. 10, label mValida).
Figure 11 shows the evolution of some nets of the system after several transitions firings.
Fig. 8. Level 2 net (Mobile entity Net), after the firing of the transition T1: a token net of place
P1 and the token net of place P2 are placed into P3
Modeling and simulation play an important role during the earliest stages of the developing life-cycle of workflow management systems. This work presented a modeling methodology for the specification of workflow processes. The use of n-LNS allows modular and hierarchical descriptions of the workflow management system. The models can be separately defined and then related through transition labeling; furthermore, the models may be easily updated because of the modularity and flexibility of the complete model. This feature allows addressing large systems exhibiting more complex behaviors than that obtained using “flat” PN.
Additionally, the model components lead to interactive software modules that implement a distributed agent-based management system. In fact, the net of level 2 describes the general behavior of a mobile agent that evolves through the computer network, and executes the tasks specified in the WF-process net.
Current research addresses the problem of fault tolerance for inter-organizational workflow management in which mobile agents move through internet.