Discovering Reference Models by Mining Process Variants Using a Heuristic Approach #BPM2009

Chen Li of University of Twente gave the last presentation of the conference on process variant mining. We heard yesterday in the tutorial on flexibility about process variants; one issue with process variants is that there needs to be some way to identify which of the variants are important enough to update the original process model. The paper describes a heuristic search algorithm for determining which of the variants are important, by considering both the similarity to the original process model and the most common changes amongst the variants, e.g., the same new step is added to almost all process variants.

Since the process can be varied at runtime, the new process model doesn’t have to be perfect, it just has to be better than the original one. In general, the more activities contained in a candidate model and the more that its structure matches that of the variants, the better it is: they have created a fitness function that combines these two parameters and calculates how good a specific candidate model is. The search tree used to find the optimal candidate process model generates all potential candidates by changing one activity at a time, calculating the best fit, then replacing the original with the candidate if it is better than the original. This continues until no better candidate model can be calculated, or until you reach your maximum search distance (which would be set in order to bound computations).

The algorithm was evaluated with simulations, indicating that the most important changes tend to be performed at the beginning of the search.