Диссертация (1137084), страница 19
Текст из файла (страница 19)
Thecurrent version of the Bizagi engine can not simulate sub-processes with cancellations and is not anopen source tool, thus, it can not be modified. iGrafx5 is a set of solutions for process management,analysis, and collaborative process design. Among others it has a simulation functionality. Thenotation used in it is a similar to BPMN, but formal translation rules are not presented.
Thesimulator fits to goals of statistical analysis, but has no functions for flexible event log generation.Obviously, the scope of process simulation in the context of process mining is much broaderthan has been described in this section. Yet another tool to generate artificial event logs hasbeen developed by T. Jouck et al. [158, 159] There are approaches that aim at transforming eventdata into simulation models.
A. Rozinat et al. [160] proposed a method to do that. Workflowsimulation in the field of process mining has also been investigated by A. Rozinat et al. [161]K. van Hee et al. [162] investigated characteristics of generated event logs. A method for on-linestreaming of artificial event logs has been proposed by B. Yahya et al. [163] Developed algorithms— which need to be evaluated and tested — have a variety of specific characteristics and features.This explains a constant stream of new algorithms aiming at event log generation in spite of manyexisting techniques.As we’ve seen, all of the considered tools have specific characteristics which make them bestsuitable for particular tasks.
The same is true for our approach and supporting tools. It is suitablefor Petri nets and BPMN 2.0 models. The latest version of the approach is able to simulate basicPetri nets or model in a well-defined subset of the BPMN standard. A user may generate logsin a flexible manner using any BPMN model containing the core modelling elements: activities,gateways, cancellations, message flows, and nested processes. One can fine-tune the experimentby using a predefined process model. Another significant feature of the approach is its ability tosimulate models with a rich data-flow.
The user may specify the behaviour of each particular nodeconnected with data objects by assigning a script written in Python programming language.In contrast to the log generators considered above, the presented tool supports:1. generation of event logs using Petri nets and (possibly non-block-structured) BPMN 2.0models made by experts in any modelling tool;2. cancellation events and message flows;3.
data-driven gateways with assigned scripts;4. BPMN pools and lanes considered as process roles;5iGrafx Platform: http://www.igrafx.com805. time extensions of process models (for both Petri nets and BPMN models);6. fine-tuning of control-flow choices via so-called preferences.3.2Generating Event Logs for Petri netsThis section presents an approach for generation of a set of event logs for a basic Petri netmodel.
Petri nets were introduced in Section 1.1. We just shortly recall the basic elements of thenotation. A Petri net is a directed bipartite graph constructed from transitions and places, whichare interconnected with arcs. Considered tool uses a Petri net as a process model to generate eventlogs via model simulation.Section 1.1.3 already has introduced the event logs. The same notion is used in this section.That is, an event log is a multiset of traces, in which each trace is a sequence of events describingthe life-cycle of a particular process instance [5]. However, we extend this notion of event logwith several concepts in several parts of this chapter, when it is needed. In particular, when thealgorithm is described that generates an event log with time, an extend event log notion is used.From the software viewpoint, generated event logs are being recorded in XES format that hasbeen described in Section 1.1.3.Recall the example Petri net from Figure 1.2, which is a workflow net.
It is shown in Figure 3.2.ht8asourcet1bc1t2c2cft3t6det5c3gc4t4sinkt7Figure 3.2: Example Petri net from Figure 1.2This model can be executed based on standard semantics for basic Petri nets described inSection 1.1.2. Places in a Petri net may contain a number of tokens. A marking of a net is adistribution of tokens over the places. It represents a current state of a Petri net. Any transitionin a Petri net may fire if it is enabled, i.e. there are sufficient tokens in all of its input places. Afiring of a transition is a single step in a modelled process, i.e.
an execution of activity. When atransition fires, it consumes tokens from the input places, and produces token in its output places.Each execution begins from initial marking (a single token in place for the net shownin Figure 3.2) with firing of transition 1 .
It takes a token from the place and puts a newtoken to the place 1 . Then, 2 fires. It consumes a token from 1 and produces a token to 2 . A12357complete run through the model can be as follows: → 1 → 2 → 3 → 4 → , where =(︀1, 0, 0, 0, 0, 0⌋︀, 1 = (︀0, 1, 0, 0, 0, 0⌋︀, 2 = (︀0, 0, 1, 0, 0, 0⌋︀, 3 = (︀0, 0, 0, 1, 0, 0⌋︀, 4 = (︀0, 0, 0, 0, 1, 0⌋︀,81 = (︀0, 0, 0, 0, 0, 1⌋︀, and (1 ) = , (2 ) = , (3 ) = , (5 ) = , (7 ) = . Such an executiondetermines a trace in the obvious manner.
It is a sequential recording of labels of fired transitions.Table 3.1 shows an event log that consists of traces, which can be generated using a simulationof the model shown in Figure 3.2. In particular, a sequence of transition firings ∐︀1 , 2 , 3 , 5 , 7 ̃︀generates the second trace of this log.Table 3.1: Example event logTrace01234567...Events∐︀, , , , ̃︀∐︀, , , , ̃︀∐︀, , , , ̃︀∐︀, , , , ℎ, , , , ℎ, , , , ̃︀∐︀, , , , ℎ, , , , ̃︀∐︀, , , , ̃︀∐︀, , , , ℎ, , , , ̃︀∐︀, , , , ℎ, , , , ̃︀...This table can be continued with other traces. Note that each sequence of events may berepeated many times in the same log. An approach described in this section generates event logsof that type using a given basic Petri net.3.2.1Algorithms for Event Log GenerationA description of the approach for event log generation consists of three main parts: (1) simplelog generation, (2) generation of a set of event logs, (3) adding artificial noise to the event log.
Inthe following all these parts are considered.Generation of an Event LogIn order to generate a trace of an event log using our approach the following steps are performed:I. The algorithm adds tokens to all places from the initial marking.II. An empty set is created and used to store the places with tokens. At this step, only placesfrom the initial marking have already obtained a token, so they are added to this set.III.
The next step is to select from which place we will try to fire a transition. It is handled byrandomly picking a place from the set of places with tokens. The algorithm does it withoutlooking whether this place has outputs which could be fired or not. This is done in a waythat prevents looping in a situation when a place has a token and available outputs, butthese outputs eventually lead to the same place without any other possible choices.IV. The algorithm checks whether chosen place has available outputs. If this is the case, an outputtransition will be chosen and fired according to preferences (see details in the remainder of82this section) of available outputs. Looking for the place available is done in the followingway:(1) the algorithm iterates through inputs and tries to hold one token from every input;(2.1) if we meet an input from which we cannot hold a token, it means that this output isnot available;(2.2) otherwise, an output is available;(3) in both cases we release held tokens.V.
Firing of a transition implies the following steps:(1) information about the event is recorded into an event log (according to the chosensettings of noise generation and timing mode);(2) tokens are added to all places which are located as outputs for this transition;(3) a set of places which got tokens is returned.VI. Then the check is made if any of final places got a token. In this case, we finish the evaluation,otherwise we do the next two steps:(1) places from the original set which have no more tokens are eliminated, and(2) two sets of places are joined.VII.
Evaluation ends with removing (consuming) tokens from places which have them.A more formal and precise description of the event log generation method is shown in Algorithm 3.An outer while loop repeats as many times as traces are needed (. ).In this loop there are three loops executed in sequence. The first for_all loop traverse allplaces marked in the initial marking (all places of a net in the worst case). Then, a whileloop is executed.
It repeats until either a number of transition firings has led to the finalmarking, or a number of transition firings has reached an artificial limit . specified by a user. The second alternative is the worst case. Without this artificial limita Petri net may be executed infinitely, if it has loops in the control-flow. This while loopcontains a nested for_all loop, that makes ⋃︀ ⋃︀ operations in the worst case(potentially, all places of a net may be final places).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
