Inferring Unobserved Events in Systems with Shared Resources and Queues

• Autorzy: Fahland Dirk , Denisov Vadim , van der Aalst Wil. M.P.

Identyfikatory

DOI

10.3233/FI-2021-2087

• Języki publikacji: EN

Abstrakty

EN

To identify the causes of performance problems or to predict process behavior, it is essential to have correct and complete event data. This is particularly important for distributed systems with shared resources, e.g., one case can block another case competing for the same machine, leading to inter-case dependencies in performance. However, due to a variety of reasons, real-life systems often record only a subset of all events taking place. To understand and analyze the behavior and performance of processes with shared resources, we aim to reconstruct bounds for timestamps of events in a case that must have happened but were not recorded by inference over events in other cases in the system. We formulate and solve the problem by systematically introducing multi-entity concepts in event logs and process models. We introduce a partial-order based model of a multi-entity event log and a corresponding compositional model for multi-entity processes. We define PQR-systems as a special class of multi-entity processes with shared resources and queues. We then study the problem of inferring from an incomplete event log unobserved events and their timestamps that are globally consistent with a PQR-system. We solve the problem by reconstructing unobserved traces of resources and queues according to the PQR-model and derive bounds for their timestamps using a linear program. While the problem is illustrated for material handling systems like baggage handling systems in airports, the approach can be applied to other settings where recording is incomplete. The ideas have been implemented in ProM and were evaluated using both synthetic and real-life event logs.

Słowa kluczowe

EN

log repair; process mining; performance analysis; multi-entity modeling; multientity event logs; conformance checking; material handling systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 183, nr 3-4
• Strony: 203--242
• Opis fizyczny: Bibliogr. 35 poz., tab., rys., wykr.

Twórcy

autor

Fahland Dirk

• Eindhoven University of Technology Eindhoven, the Netherlands

autor

Denisov Vadim

• Eindhoven University of Technology Eindhoven, the Netherlands

autor

van der Aalst Wil. M.P.

• Process and Data Science (Informatik 9) RWTH Aachen University, Aachen, Germany

Bibliografia

• [1] Maruster L, van Beest NRTP. Redesigning business processes: a methodology based on simulation and process mining techniques. Knowl. Inf. Syst., 2009. 21(3):267-297. doi:10.1007/s10115-009-0224-0.
• [2] Marquez-Chamorro AE, Resinas M, Ruiz-Cort ´es A. Predictive Monitoring of Business Processes: A Survey. IEEE Transactions on Services Computing, 2018. 11(6):962-977. doi:10.1109/TSC.2017.2772256.
• [3] Denisov V, Fahland D, van der Aalst WMP. Unbiased, Fine-Grained Description of Processes Performance from Event Data. In: Weske M, Montali M, Weber I, vom Brocke J (eds.), Business Process Management. Springer International Publishing, Cham. 2018 pp. 139-157. ISBN:978-3-319-98648-7.
• [4] Ahmed T, Pedersen TB, Calders T, Lu H. Online Risk Prediction for Indoor Moving Objects. In: 2016 17th IEEE International Conference on Mobile Data Management (MDM), volume 1. 2016 pp. 102-111. doi:10.1109/MDM.2016.27.
• [5] Denisov V, Fahland D, van der Aalst WMP. Predictive Performance Monitoring of Material Handling Systems Using the Performance Spectrum. In: 2019 International Conference on Process Mining (ICPM). 2019 pp. 137-144. doi:10.1109/ICPM.2019.00029.
• [6] Fahland D. Describing Behavior of Processes with Many-to-Many Interactions. In: Donatelli S, Haar S (eds.), Application and Theory of Petri Nets and Concurrency. Springer International Publishing, Cham. 2019 pp. 3-24. ISBN:978-3-030-21571-2.
• [7] Jensen K, Kristensen LM. Colored Petri nets: a graphical language for formal modeling and validation of concurrent systems. Commun. ACM, 2015. 58(6):61-70. doi:10.1145/2663340.
• [8] Schrijver A. Theory of Linear and Integer Programming. John Wiley & Sons, Chichester, 1986.
• [9] van der Aalst WMP. Process Mining - Data Science in Action, Second Edition. Springer, 2016. ISBN-10:9783662498507, 13:978-3662498507.
• [10] Senderovich A, Francescomarino CD, Maggi FM. From knowledge-driven to data-driven inter-case feature encoding in predictive process monitoring. Inf. Syst., 2019. 84:255-264. doi:10.1016/j.is.2019.01.007.
• [11] Gans N, Koole G, Mandelbaum A. Telephone Call Centers: Tutorial, Review, and Research Prospects. Manufacturing & Service Operations Management, 2003. 5(2):79-141. doi:10.1287/msom.5.2.79.16071.
• [12] Brown L, Gans N, Mandelbaum A, Sakov A, Shen H, Zeltyn S, Zhao L. Statistical Analysis of a Telephone Call Center. Journal of the American Statistical Association, 2005. 100(469):36-50. doi:10.1198/016214504000001808.
• [13] Senderovich A, Weidlich M, Gal A, Mandelbaum A. Queue Mining - Predicting Delays in Service Processes. In: Advanced Information Systems Engineering - 26th International Conference, CAiSE 2014, Thessaloniki, Greece, June 16-20, 2014. Proceedings, volume 8484 of Lecture Notes in Computer Science. Springer, 2014 pp. 42-57. doi:10.1007/978-3-319-07881-6\_4.
• [14] Senderovich A, Beck J, Gal A, Weidlich M. Congestion Graphs for Automated Time Predictions. Proceedings of the AAAI Conference on Artificial Intelligence, 2019. 33:4854-4861. doi:10.1609/aaai.v33i01.33014854.
• [15] Suriadi S, Andrews R, ter Hofstede A, Wynn M. Event log imperfection patterns for process mining: Towards a systematic approach to cleaning event logs. Information Systems, 2017. 64:132 - 150. doi:https://doi.org/10.1016/j.is.2016.07.011.
• [16] Conforti R, La Rosa M, ter Hofstede A. Timestamp Repair for Business Process Event Logs. Technical report, 2018. URL http://hdl.handle.net/11343/209011.
• [17] Martin N, Depaire B, Caris A, Schepers D. Retrieving the resource availability calendars of a process from an event log. Information Systems, 2020. 88:101463. doi:https://doi.org/10.1016/j.is.2019.101463.
• [18] Carmona J, van Dongen B, Solti A, Weidlich M. Conformance Checking - Relating Processes and Models. Springer, 2018. ISBN:978-3-319-99414-7.
• [19] Pegoraro M, van der Aalst WMP. Mining Uncertain Event Data in Process Mining. In: International Conference on Process Mining, ICPM 2019, Aachen, Germany, June 24-26, 2019. IEEE, 2019 pp. 89-96. doi:10.1109/ICPM.2019.00023.
• [20] Pegoraro M, Uysal MS, van der Aalst WMP. Discovering Process Models from Uncertain Event Data. In: Di Francescomarino C, Dijkman R, Zdun U (eds.), Business Process Management Workshops. Springer International Publishing, Cham. 2019 pp. 238-249. ISBN:978-3-030-37453-2.
• [21] van der Aalst WMP, Barthelmess P, Ellis CA, Wainer J. Proclets: A Framework for Lightweight Interacting Workflow Processes. International Journal of Cooperative Information Systems, 2001. 10(04):443-481.
• [22] van der Aalst WMP, Berti A. Discovering Object-centric Petri Nets. Fundam. Informaticae, 2020. 175(1-4):1-40. doi:10.3233/FI-2020-1946.
• [23] Ghilardi S, Gianola A, Montali M, Rivkin A. Petri Nets with Parameterised Data - Modelling and Verification. In: Fahland D, Ghidini C, Becker J, Dumas M (eds.), Business Process Management - 18th International Conference, BPM 2020, Seville, Spain, September 13-18, 2020, Proceedings, volume 2168 of Lecture Notes in Computer Science. Springer, 2020 pp. 55-74. doi:10.1007/978-3-030-58666-9\_4.
• [24] Steinau S, Andrews K, Reichert M. Coordinating Large Distributed Process Structures. In: Reinhartz-Berger I, Zdravkovic J, Gulden J, Schmidt R (eds.), Enterprise, Business-Process and Information Systems Modeling - 20th International Conference, BPMDS 2019, 24th International Conference, EMMSAD 2019, Held at CAiSE 2019, Rome, Italy, June 3-4, 2019, Proceedings, volume 352 of Lecture Notes in Business Information Processing. Springer, 2019 pp. 19-34. doi:10.1007/978-3-030-20618-5\_2.
• [25] Popova V, Fahland D, Dumas M. Artifact Lifecycle Discovery. Int. J. Cooperative Inf. Syst., 2015. 24(1):1550001:1–1550001:44. doi:10.1142/S021884301550001X.
• [26] van der Aalst WMP. Object-Centric Process Mining: Dealing with Divergence and Convergence in Event Data. In: ¨Olveczky PC, Sala ¨un G (eds.), Software Engineering and Formal Methods - 17th International Conference, SEFM 2019, Oslo, Norway, September 18-20, 2019, Proceedings, volume 11724 of Lecture Notes in Computer Science. Springer, 2019 pp. 3-25. doi:10.1007/978-3-030-30446-1\_1.
• [27] Lu X, Nagelkerke M, van de Wiel D, Fahland D. Discovering Interacting Artifacts from ERP Systems. IEEE Trans. Serv. Comput., 2015. 8(6):861-873. doi:10.1109/TSC.2015.2474358.
• [28] Werner M, Gehrke N. Multilevel Process Mining for Financial Audits. IEEE Trans. Serv. Comput., 2015. 8(6):820-832. doi:10.1109/TSC.2015.2457907.
• [29] Esser S, Fahland D. Storing and Querying Multi-dimensional Process Event Logs Using Graph Databases. In: Francescomarino CD, Dijkman RM, Zdun U (eds.), Business Process Management Workshops -BPM 2019 International Workshops, Vienna, Austria, September 1-6, 2019, Revised Selected Papers, volume 362 of Lecture Notes in Business Information Processing. Springer, 2019 pp. 632-644. doi:10.1007/978-3-030-37453-2\_51.
• [30] Berti A, van der Aalst WMP. Extracting Multiple Viewpoint Models from Relational Databases. In: Ceravolo P, van Keulen M, L ´opez MTG (eds.), Data-Driven Process Discovery and Analysis - 8th IFIP WG 2.6 International Symposium, SIMPDA 2018, Seville, Spain, December 13-14, 2018, and 9th International Symposium, SIMPDA 2019, Bled, Slovenia, September 8, 2019, Revised Selected Papers, volume 379 of Lecture Notes in Business Information Processing. Springer, 2019 pp. 24-51. doi:10.1007/978-3-030-46633-6\_2.
• [31] Esser S, Fahland D. Multi-Dimensional Event Data in Graph Databases. J. Data Semant., 2021. 10(1):109-141. doi:10.1007/s13740-021-00122-1.
• [32] Denisov V, Fahland D, van der Aalst WMP. Repairing Event Logs with Missing Events to Support Performance Analysis of Systems with Shared Resources. In: Janicki R, Sidorova N, Chatain T (eds.), Application and Theory of Petri Nets and Concurrency - 41st International Conference, PETRI NETS 2020, Paris, France, June 24-25, 2020, Proceedings, volume 12152 of Lecture Notes in Computer Science. Springer, 2020 pp. 239-259. doi:10.1007/978-3-030-51831-8\_12.
• [33] Rosa-Velardo F, de Frutos-Escrig D. Name Creation vs. Replication in Petri Net Systems. Fundam. Inform., 2008. 88(3):329-356.
• [34] van der Aalst WMP, Weijters AJMM, Maruster L. Workflow mining: discovering process models from event logs. IEEE TKDE, 2004. 16:1128-1142. doi:10.1109/TKDE.2004.47.
• [35] van der Aalst WMP, Adriansyah A, Dongen B. Replaying History on Process Models for Conformance Checking and Performance Analysis. WIREs Data Mining and Knowledge Discovery, 2012. 2:182-192. doi:10.1002/widm.1045.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)