Computing Alignments of Well-Formed Process Models using Local Search

Abstract

The alignment of observed and modeled behavior is an essential element for organizations, since it opens the door for conformance checking and enhancement of processes. The state of the art technique for computing alignments has exponential time and space complexity, hindering its applicability for medium and large instances. In this paper a novel approach is presented to tackle the challenge of computing an alignment for large problem instances that correspond to well-formed process models. Given an observed trace, first it uses a novel replay technique to find an initial candidate trace in the model. Then a local search framework is applied to try to improve the alignment until no further ..