Resumen de Light methods for conformance checking of business processes
Farbod Taymouri
Conformance Checking is a new research discipline devoted to identify deviations between business process models and their real executions. Identifying deviations boils down to the notion of alignment conceptually. An alignment quantifies to what degree a process model can imitate what happened in its observed behavior, i.e., an event log. Accordingly, an optimal alignment is the best combination by which the process model can imitate the corresponding observed behavior. The state of the art technique for alignment computation has exponential time and space complexity, hindering its applicability for medium and large instances.
The main aim of this thesis is to propose light and efficient methods for alignment computation. By finding a suitable trade-off between computation time, memory consumption and optimality, a familly of techniques is proposed such that depending on the input assumptions and required guarantees, a user can select the right technique for her particular problem.
Generally speaking, the methods presented in this thesis can be categorized as:
Classical approaches: These techniques exploit Integer Linear Programming (ILP), as well as structural theory of Petri nets, to formulate alignment computation as an optimization of a set of linear equations. A modification to this strategy which trades-off between complexity and quality is to integrate it with state of the art approach.
Heuristic approaches: These techniques take advantages of heuristic functions to explore the search space of alignments, to find the optimal one(s). This can be done by obtaining an initial solution, and iteratively improving it until saturation or reaching a certain criterion. Another contribution is by adopting a Genetic Algorithm with well specific designed operators, by which exploration of the corresponding search space can be speed up toward the best solution(s).
Model reduction: An alternative way to boost the effectiveness of alignment computation is by reducing model and observed behavior without loosing alignment information. This structure reduction not only boosts the alignment computation, but also provides a big picture of detected deviations. Above that, a divide-and-conquer strategy will be provided for the ILP approach, such that it breaks the original problem into a set of smaller independent problems that can be solved independently.
Experiments witness the merit of proposed approaches with respect to state of the art technique in different perspectives, such as resource consumption, execution time, quality and accuracy of the solutions found. All methods have been implemented as a stand-alone tool box called ALI.
