Диссертация (1137084), страница 24
Текст из файла (страница 24)
When anactivity ∈ fires in a marking (,), it defines and sets new data object values: ′ = ()().Firing of an exclusive gateway XOR in a marking (,) results in producing a token to one of theoutgoing sequence flows sf ∈ SF, for which SF (sf)() = . If for all outgoing sequence flows sfholds SF (sf)() = , then a token is added to the flow default(XOR ).9In this section, we use the following notations: =1 ∪ ... ∪ , =1 ∪ ... ∪ , XOR =XOR1 ∪ ... ∪ XOR ,SF=SF1 ∪ ...
∪ SF , where 1 ,..., , 1 ,..., , XOR1 ,..., XOR , SF1 ,...,SF are sets of nodes, activities,exclusive gateways and sequence flows of models BPMN1 ,...,BPMN respectively.101Interacting BPMN ModelsIn this section, BPMN models are introduced, which represent different participants,interacting through message flows [7, 167]. In Figure 3.15 a reader can see a fragment of thearchitectural changes process model (see Figure 3.11), in which new requirements are sent asmessages from a customer to the architecture team.
The message flow is shown as a dashed linewith white arrow at the side of a message receiver (activity New Requirement Request) and whitecircle at the side of a sender (activity New Requirement Formulated).Each participant is usually visualized as a pool within the entire BPMN model. Note that incontrast to lanes sequence flows cannot cross pools borders.Definition 16. A BPMN model with participants is a tuple BPMN = (BPMN , MF), inthat– a set BPMN = {BPMN1 ,...,BPMN } is the set of BPMN models with data,– a set MF ⊂ ( × )/(1 × 1 )/.../( × )10 is the set of message flows.A marking of a BPMN model with participants BPMN = (BPMN , MF) can be representedas (1 ,..., ,′ ), where is a marking of BPMN model for ∈ 1,, and ′ ∈ (MF → N).An initial marking is represented as (10 ,...,0 , 0 ′ ), where 0 is an initial marking of acorresponding BPMN model.Figure 3.15: Fragment with participantsMessage flows extend the firing rules of activities.
In addition to the standard enablingconditions presented earlier, each incoming message flow of an activity must contain at least10 = 1 ∪ ... ∪ and 1 ,..., are disjoint sets of all activities of the base BPMN models, forming modelsBPMN1 ,...,BPMN respectively.102one token to make this activity enabled, i.e., activity New Requirement Request in Figure 3.15will become enabled only when some request will be sent from the customer.
When an activityfires, apart from the standard operations with tokens on sequence flows, it consumes a token fromeach incoming message flow and produces a token to each outgoing message flow.BPMN pools and messages allow to model and simulate systems with multiple participantsworking in parallel and can be synchronized via message flows. This is the only modellingelement allowed to cross pool’s boundary. Note that in Figure 3.11 the processes of customerand architecture team have independent starts and ends. Message flows is the only mechanismthat binds them together.3.3.1Algorithms for Event Log GenerationIn this section, we present our approach for the generation of event logs.
We will consider thedifferent types of BPMN models described earlier. The remainder of the section is organized asfollows: firstly, an algorithm for generating event logs from base BPMN models is described; then,each next section explains a specific enhancement of the algorithm.Basic Approach for Event Log GenerationThis section is devoted to an algorithm used for the simulation of base BPMN models as theyare defined above.
An event log corresponds to the Definition 12. Recall that we assume eachevent appear one in the log. Each trace corresponds to an execution of a single process instance.In other words, all tokens in a model created during generation of one trace relate to the sameinstance of a process being simulated.Algorithm 6 presents a base simulation approach. During a model execution it constructs a setof event logs, each of which consists of traces.Firing of an activity leads to the creation of an event with certain attributes, such as its nameand resource.
If lanes are presented in a model, they are used during the generation in order tospecify resources involved in the execution of activities. For example, when generating a log forprocess model shown in Figure 3.11 using our approach, one will obtain in each event the name ofperforming group (Customer or Architecture Team) and performer role (Analyst or Architect).When replaying a process model, a number of assumptions concerning the order of node firingsmust be specified. In Algorithm 6 all events and gateways are fired first, and only then activitiesare executed.
Before checking whether activities are enabled, all possible firings of gateways arecarried out. Note that there can be a cyclic firing of gateways. In that case according to Algorithm 6the log generation process will be terminated and the trace will not be added to a log.103Algorithm 6 Basic event log generationInput:– BPMNmodel = (, , XOR , AND ,start ,end ,cancel , SF,EF, ,,res),– is a number of logs to generate,– is a maximal number of traces in each log,– and is a maximal number of firings per trace.Output: a set of event logs = {1 ,..., }, where = ( , , , ), ∈ 1..1: Function generate(BPMNmodel , , , )2: ← {}3:For ← 1 up to do4: ← {}5: ← {}6: ← {}7: ← {}8: ← ( , , , )9:For ← 1 up to do10: ← ∐︀̃︀11: ← 012: ← 0▷ 0 — is an initial marking of BPMNmodel13:Repeat14: ← 15:For ∀ ∈ ∪ ∪ do16:If is enabled then17: ← (,,BPMNmodel )18:f ← 19:break20:EndIf21:EndFor22:If not then23: ← { ∈ ⋃︀ is enabled}24:If = ∅ then25:f ← ▷ deadlock is reached, terminate execution26:else27: ← ℎ()▷ select an activity to fire28:execute(, BPMNmodel , , )▷ this procedure is described in Algorithm 729:EndIf30:EndIf31: ← + 132:Until < and ∃ such that ∈ and ( ) > 033:If ∀ ∈ ( ) = 0 then34: ← ∪ {}35:EndIf36:EndFor37: ← ∪ 38:EndFor39:return 40: EndFunctionAfter that we have the entire set of activities enabled at a particular step of simulation.
Thus,each of them can fire with the equal probability. Due to the invisible nature of gateways execution,it is enough to find the first enabled gateway and then it can be immediately fired. By invisiblenature we mean, that there are no records in the event log corresponding to the gateway firings.They are needed for the control-flow management only.104In contrast, activities require more careful handling. All enabled activities are found and onlythen a random one is fired. Outgoing sequence flows of fired exclusive gateways are selectedrandomly as well.
Therefore, there are two stages in simulation. Firstly, all events and gatewayare fired in an arbitrary order until the only enabled elements are activities. Secondly, one of theenabled activities is selected randomly and fired. This ensures equal probability of firing of eachenabled activity at each step. Moreover, the choice of one or another process model branch is alsomade randomly.The generation of a trace terminates when one of two following situations occurs:1. there are no more tokens in the model,2. execution exceeded the specified maximal number of firings.In the former case, the replay finished successfully (process instance is completed), and thegenerated trace is added to the event log. In the latter case, the replay did not terminate properly,and the trace will not be added to the event log.
Forced termination is supported to deal withvery large or live-locking models.Algorithm 7 Algorithm 6 continued — the EXECUTE procedure41:42:43:44:45:46:47:48:49:50:Procedure execute(, BPMNmodel , , = ( , , , )) ← (,,BPMNmodel ) ← () ← ∪ {} ← + ← ∪ {(, ())}If () is defined for then ← ∪ {(, (, ())}EndIfEndProcedureGenerating Event Logs for BPMN Models with DataIn contrast to the simulation of hierarchical and interacting BPMN models, which haveadditional firing rules and thus extend the basic log generation algorithm in a natural way,simulation of a BPMN model with data should be described separately.Algorithm 8 extends the basic Algorithm 6 with a modified procedure of activity execution:each firing of an activity not only changes the marking, but assigns novel values to data objects.The values of data objects are written to the log in a form of event attributes.Additionally, as it follows from the definition of BPMN models with data, during the executionof an exclusive gateway, a token is added to one of the outgoing sequence flows, for which thevalue of a special assigned function is true.
If the values of functions for all outgoing sequenceflows are false, a token is added to the default outgoing sequence flow.105Algorithm 8 Event generation with data — modified procedure of event executionInput:– an activity ,– a BPMN model with data BPMN = (BPMNℎ ,DO,DA, ,SF ,default, ), (,((do1 ,val1 ),...,(do ,val ))),– an event log = ( , , , ).1:2:3:4:5:6:7:8:9:10:11:12:13:14:15:Procedure execute(, BPMN , ) ← (,,BPMN ) ▷ , , ref are functions defined by BPMN models, which contain activity If ref() is not defined then ← () ← ∪ {} ← + ← ∪ {(, ())}If res (a) is defined for then ← ∪ {(, (, ())}EndIfFor do ∈ DO do ← ∪ {(, ( (do), ()((do1 ,val1 ),...,(do ,val ))(do ))}EndForEndIfEndProcedureSimulating BPMN Models With PreferencesIn order to make simulation more realistic, we introduce a notion of so-called preferences whichare used to modify the choice between the conflicting activities. For the BPMN language that isthe case, when dealing with exclusive gateways.Figure 3.16: Model fragment with an exclusive gatewayA typical scenario is shown in Figure 3.16, which is also a fragment of Figure 3.11.
Obviously,in a real-life setting, rejections and approvals happen with different frequencies. Thus, sometimesit seems rational to set one activity as more frequent than the other when generating an event log.For example, one may want to simulate the situation, when almost all proposals are approved.A preference is a non-negative integer value within some range. Each preference correspondsto exactly one outgoing sequence flow.
The higher a preference is, the higher possibility to adda token to a certain sequence flow is. The precise formula for the probability of a sequence flowto get a token is ( ) =pref (sj )∑=1⋃︀OSF⋃︀pref (si ). Where OSF is a set of outgoing sequence flows from a106specific exclusive gateway; , ∈ OSF are two outgoing sequence flows, and pref (s), ∈ OSF is apreference of the particular sequence flow from the set OSF.For the case shown in Figure 3.16 OSF contains two sequence flow to activities ApproveChanges and Proposal Rejected. For example, one can set pref (sApproveChanges ) = 10 andpref (sProposalRejected ) = 1 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
