Performance of an automated process model discovery – the logistics process of a manufacturing company

Throughout the process mining literature, out of the previously mentioned areas, the automated process discovery is the most widely researched. As input, automated process discovery techniques take an event log containing the information about the behaviour of the analysed process, and then produce a process model representing control-flow containing relations between tasks observed or implied in the event log (Aalst, Weijters & Maruster, 2004). However, for discovered process models to be useful, they have to find an appropriate balance between several properties (Aalst, 2016; Buijs, Dongen & Aalst, 2014), such as fitness, precision, generalisation and simplicity. The fitness quality dimension describes the fraction of the behaviour in the event log that can be replayed by the process model, essentially meaning that the discovery method generates traces that are present in the log or are similar to a trace in the log. On the other hand, the precision quality dimension estimates the behaviour unseen in the event log but allowed by the process model, essentially meaning that the discovered model should not generate traces that are too different from the behaviour seen in the log. The generalisation quality dimension is indicated if the event log is not overfitting the behaviour present in the event log as the event log itself may contain only partial behaviour of the analysed system, essentially meaning that the discovery method generates traces not seen in the model which have similar behaviour to the traces seen in the event log. Finally, the simplicity quality dimension states that the discovered process model should be as simple as possible. As criteria go against each other, it is necessary to find the appropriate balance between them; however, this is not an easy task, especially considering real-life event logs. Thus, according to Augusto et al. (2018), there are two major problems which occur during the application of automated process discovery methods on real-life event logs: 1) the discovery method produces large spaghetti-like models (Fig. 1), which are incomprehensible, unstructured and very hard to analyse and work with (Aalst, 2016; Aalst, 2011); and 2) they produce models with unsatisfactory quality dimensions, be it poor fit of the log or ever-generalised model.

Fig. 1

According to Tiwari, Turner & Majeed (2008), pioneering work in the area of the automated process discovery and process mining discipline, in general, was done by Agrawal, Gunopulos & Leymann (1998) and Cook & Wolf (1998) and their foundational approaches. Agrawal, Gunpulos & Leymann (1998) focused on mining models from workflow systems with the main focus on the appropriate ordering of activities and the successful termination of the process. Cook & Wolf (1998) described the application of Markov method within the process mining domain in addition to RNet and Ktail methods and evaluated the three proposed approaches to the automated process discovery: algorithmic, statistical and probabilistic. As was predicted by Cook & Wolf (1998), the most popular approach to the automated process discovery will be the algorithmic approach. This prediction turns out to be true and algorithmic approach to the automated process discovery is by far the most popular approach among researchers of the field (Tiwari, Turner & Majeed, 2008; Augusto et al., 2018).

One of the most influential techniques of the automated process discovery was introduced by Aalst, Weijters & Maruster (2003) and called α-algorithm. In their work, Aalst, Weijters & Maruster proved that α-algorithm is capable of discovering structured workflow-nets, which are an important class of Petri nets in the area of business processes, from complete event logs, assuming that they do not contain any noise. However, the original α-algorithm had several shortcomings in the form of short loops, invisible, duplicate or implicit tasks and non-free-choice constructs (Medeiros, Aalst & Weijters, 2003). Thus, the α-algorithm was extended several times. Firstly, Medeiros et al. (2005) introduced so-called α+-algorithm, so it was able to deal with short loops using the pre-processing of patterns specific to short loops. Next, Wen et al. (2007) and Wen, Wang & Sun (2006) introduced α++-algorithm that was able to detect non-free-choice constructs by considering a new relation called the implicit dependency. Wen et al. (2010) introduced α#-algorithm, capable of mining invisible tasks by considering the relation called the mendacious dependency. The latest version of an α-algorithm, so-called α$-algorithm was introduced by Guo et al. (2015). The algorithm uses improved mendacious and implicit dependency relations, and besides invisible and non-free-choice constructs, it is also able to mine invisible tasks in non-free-choice constructs.

HeuristicsMiner is another influential approach to the automated process discovery, which was introduced by Weijters, Aalst & Medeiros (2006). HeuristicsMiner was introduced to deal with noise and incompletion of event logs, where noise means events recorded in the log that are not supposed to be there and that do not represent the behaviour of the analysed process. On the other hand, an incomplete event log means missing data. It is an extension of α-algorithm in a sense that it considers frequencies, by which activity relationships occur (Aalst, Weijters & Medeiros, 2003) in the event log. In addition to robustness of an event log, HeuristicsMiner is also capable of dealing with short loops and non-local dependencies. Broucke & Weerdt (2017) introduced the discovery technique Fodina that is based on HeuristicsMiner and which handles the noise in the log and discover duplicate activities. Flexible Heuristics Miner (Weijters & Ribeiro, 2011) is yet another discovery technique based on HeristicsMiner. Similarly to previous techniques, Flexible Heuristics Miner can also deal well with noise in event logs.

In a series of papers, Leemans et al. (2013a, b; 2014) introduced the so-called inductive mining. Later versions focused on infrequency and incompleteness. Inductive mining produces process models in the form of process trees. The advantage of inductive mining is that it does provide guarantees in terms of soundness and re-discoverability of discovered process models. Leemans, Fahland & Aalst (2015; 2016) introduced the framework based on inductive mining that adds the advantage of scalability, while still guaranteeing the soundness and re-discoverability. Evolutionary Tree Miner introduced by Buijs, Dongen and Aalst (2012; 2014) belongs to the group of genetic algorithms and extracts process models from event logs in the form of a process tree.

Split Miner proposed by Augusto et al. (2017) is a technique with consistently high and balanced fitness, precision and generalisation that guarantees the deadlock-freedom for cyclic process models and the soundness for the acyclic. It merges an innovative approach to filter the directly-follows graph induced by an event log, with an approach to identify combinations of split gateways that accurately capture the concurrency, conflict and causal relations between neighbours in the directly-follows graph.

Günther & Aalst (2007) introduced Fuzzy Miner to tackle with unstructured processes. Fuzzy Miner is an adaptive simplification and visualisation technique based on significance and correlation measures to visualise the behaviour in event logs at various levels of abstraction (Weerdt et al., 2012). Previously mentioned algorithms use Petri nets as a representation of discovered process models. However, the discovered fuzzy model cannot be translated to the Petri net, which is a severe disadvantage to the Fuzzy Miner approach as it limits the comparability of Fuzzy Miner to other techniques. The same problem is characteristic of many more techniques.

Applying the genetic algorithm to process discovery, Medeiros, Weijters & Aalst (2007) introduced the so-called genetic process mining. An effort of the genetic process mining was to overcome problems related to non-free-choice constructs, and furthermore, invisible and duplicate task. Previously mentioned discovery techniques are limited by a local search, which is causing problems in discovering non-free-choice constructs or invisible and duplicate task. Thus, the global approach of genetic process mining comes into play, enabling the discovery of non-local behaviour (Weerdt et al., 2012). The advantage of the genetic process mining is that while most of other process discovery techniques focus only on one or two quality dimensions at the same time (Buijs, Dongen & Aalst, 2012), the genetic process mining can address all four quality dimensions.

Furthermore, several authors, for example, Werf et al. (2009), Aalst et al. (2010), based their automated discovery techniques on the principles of the theory of regions and integer linear programming (ILP). One of the main goals of automated discovery algorithms based on the theory of regions and ILP was to address the issue related to the assumption of completeness of the event log and the related problem of overfitting or underfitting the discovered process model by solving a series of ILPs. ILP was also used by Zelst et al. (2018) in their approach to automated process discovery. HybridILPMiner by Zelst et al. (2018)’s is based on the theory of regions and discovers relaxed sound workflow nets built on hybrid variable-based regions. Dongen & Aalst (2004) introduced the multi-phase process mining to mine instances of processes that can be later translated into other models, such as Petri nets of Event-driven Process Chains (EPCs). Correspondingly to techniques based on the theory of regions, the multi-phase process mining addresses the assumption of completeness of the log. The divide and conquer framework (Verbeek, Aalst & Munoz-Gama; 2017, Verbeek & Aalst, 2015) decomposes the process model discovery into smaller parts working with discovery techniques, and in this study, with ILP.

To evaluate different automated process discovery techniques and assess their performance with ABS, a hybrid simulation was chosen from the Any-Logic framework (2019), based on which synthetic event logs were generated by replaying the process model. Hybrid simulation means that the simulation model consists of two or more approaches, meaning that the simulation model combines characteristics of two approaches, for example, ABS and discrete-event simulation, which was also used for the purpose of this study. The AnyLogic framework does not directly produce event logs needed for the process mining analysis. Thus, first, it is necessary to acquire such event logs. For this purpose, the BPMN 2.0 notation and the business process simulator (BIMP, 2019) were used. First, based on flowcharts and statecharts of business processes contained in the chosen hybrid simulation, models were transformed into BPMN process models. Then, the BPMN process models were simulated using the BIMP software that can produce an event log in the form of an MXML file. The BPMN notation is expressive enough to reproduce the control flow of a hybrid simulation model without any sacrifices (Fig. 2).

Fig. 2

Furthermore, as stated in the Introduction section, the main advantages of ABS are the autonomy of agents, the complexity of the models etc. The autonomy of agents allows them to make decisions and, thus, determine the control-flow in particular process instances through such decisions. However, automated process discovery techniques are mainly focused on relations between occurring events and their sequence, and not necessarily on the reasons why the behaviour occurred. Thus, by expressing the behaviour of the modelled system using the BPMN notation, all the information relevant to automated process discovery techniques is preserved. While simulating the BPMN model in the business process simulator BIMP to acquire an event log, each event has to have a timestamp, so it can be ordered within the trace and, thus, processing times and arrival distributions of process tasks have to be defined for the purpose of generating an event log in the BIMP simulator. Where possible, parameters were used from the hybrid simulation model; otherwise, they were made artificially. However, it is necessary to keep in mind that this does not pose a problem to the validity of the event log because the interest is not in the performance of the process itself and, thus, particular timestamps, but rather in the control flow of the process.

A simulation model simulates the logistic process in a small job shop. Specifically, it is a logistics process describing the import of raw material, its storage, transformation into a product and its export. The overall process of the job shop simulation is as follows: the raw material is delivered to the receiving dock, where it is placed into storage until the processing occurs at the machine. Finished products are palletised and then moved to storage at s shipping dock until the completed pallets can be loaded on a truck.

The BPMN process model of the hybrid simulation is provided in Fig. 3 and is as follows: the start event in the business model is represented by the arrival of a truck with raw material. When the truck arrives at the docks, the system checks if the forklift is available. In the case that a forklift is available, it is assigned, pallets are unloaded from the truck and simultaneously assigned. In another case, the system automatically checks for an available forklift again until the forklift is assigned. After the pallets are unloaded, they are transferred into docks and stored. When the time comes, the pallets are assigned to particular machines for processing and transported to the assigned machines. This job used the second group of forklifts. Once the pallets are transferred to the machines, the raw material is processed. After the processing, the finished products are collected and put into storage. This processing part of the logistics process lies inside the big XOR gate. When the time comes, the system schedules a truck and finished products are prepared for export. When the truck arrives, the finished products are loaded, and the process ends when the loaded truck leaves. Fig. 4 basically represents the same model, but with 4 added machines (red rectangle in Fig. 4) and one additional input of raw material (blue rectangles in Fig. 4) per each work line as parallel work lines are common in manufacturing. Finally, particular products made in the job shop were chosen as the case identifier for the simulation. The idea behind the case identifier being equal to a particular manufactured product is based on one of the pillars of Industry 4.0, where the product and even material are equipped with chips and thus, trackable in the cyber-physical environment.

Fig. 3

Fig.4

The focus regarding the evaluation of automated process discovery techniques is mainly on two previously mentioned quality dimensions: fitness and precision. Simply put, fitness measures the ability of the model to reproduce behaviour contained in the log. The range of the fitness function is the interval [0,1], where the value of fitness equal to 1 means that the process model can replay every trace in the event log. Precision, on the other hand, measures the ability of a model to generate the behaviour present in the event log. Similarly to fitness, the range of the precision function is the interval [0,1], where the value of precision equal to 1 means that any trace produced by the process model is found in the event log. Both quality dimensions can be combined into one index called the F-score, which is the harmonic mean of the two measures. For the purpose of this study, Markovian fitness and precision are used (Augusto et al., 2019).

It is necessary that the used modelling language has executable semantics so the quality dimension of fitness and precision are computable. Petri nets are popular in many different areas of system modelling, while simultaneously having executable semantics. Furthermore, Petri nets are used by a relatively large number of automated process discovery techniques for representation of discovered process models. Thus, it is required that discovery techniques selected for the benchmark use Petri nets for the representation of the discovered process model. Also, those techniques were included that produce models which are convertible into Petri nets (Process Trees, BPMN models). Secondary criteria for the selection of the automated process discovery technique was the accessibility of the technique itself. The selected techniques can be found in Tab. 1.