Light methods for conformance checking of business processes

Abstract

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.

Conformance checking és una nova disciplina dedicada a identificar desviacions entre els models de processos de negoci i les seves execucions reals. Identificar les desviacions porta directament al concepte d'alineament. Un alineament quantifica el grau en que un model de procés pot imitar el que va passar en el seu comportament observat, és a dir, un registre d'esdeveniments. En conseqüència, una alineament òptim és la millor combinació per la qual el model de procés pot imitar el comportament observat. La tècnica de referència per a la computació d'alineaments té una complexitat exponencial, el que dificulta la seva aplicabilitat per a casos mitjans o grans. L'objectiu principal d'aquesta tesi és proposar mètodes eficients per a la computació d'alineaments. En trobar un punt raonable entre el temps d'execució, el consum de memòria i la optimalitat, es proposa una família de tècniques de manera que, segons els supòsits d'entrada i les garanties requerides, un usuari pot seleccionar la tècnica adequada per al seu problema. En termes generals, els mètodes presentats en aquesta tesi es poden classificar com: Enfocaments clàssics: aquestes tècniques utilitzen la Programació Lineal Entera (anglès, ILP), així com la teoria estructural de les xarxes Petri, per realitzar la computació d'alineaments com una optimització d'un conjunt d'equacions lineals. Una modificació d'aquesta estratègia, que pondera la complexitat i la qualitat, és la d'integrar-la amb l'enfocament de referència. Aproximacions heurístiques: aquestes tècniques aprofiten funcions heurístiques per explorar l'espai de cerca d'alineaments, per trobar les solucions properes a l'òptim. Això es pot fer obtenint una solució inicial, que es millorarà iterativament fins a la saturació, o bé assolint un criteri determinat de convergència. Una altra contribució és l'adopció d'un algoritme evolutiu amb operadors específics, que permeten guiar l'exploració de l'espai de cerca corresponent cap a les millors solucions. Reducció de models: una forma alternativa de potenciar l'efectivitat de la computació d'alineaments és reduint el comportament modelat i observat sense perdre la informació d'alineaments. Aquesta reducció d'estructura no només alleugereix el problema, sinó que també proporciona una visió abstracta de les desviacions detectades. Addicionalment, es proposa una estratègia de divideix i vèncer per a l'enfocament de l'ILP, que trenca el problema original en un conjunt de problemes independents més petits que es poden resoldre de forma independent. Els experiments realitzats per cada tècnica demostren la capacitat dels algorismes proposats, en diferents perspectives, com ara el consum de recursos, el temps d'execució, la qualitat i la precisió de les solucions trobades. Tots els mètodes s'han implementat en el software open-source ALI.