Ant-Colony Optimisation for Path Recommendation in Business Process Execution

Journal on Data Semantics - Tập 8 Số 2 - Trang 113-128 - 2019
Comuzzi, Marco1
1Ulsan National Institute of Science and Technology, Ulsan, Republic of Korea

Tóm tắt

In business process management, operational support concerns methods and tools to support users during the execution of business processes. One possible way of supporting users is to suggest the optimal way to complete the execution of a business process instance given the set of activities executed thus far and a notion of utility associated with the execution of possible remaining activities. This problem goes also under the label of process navigation. This paper proposes a novel technique to implement process navigation based on the innovative abstraction of business process models as a restricted class of directed hypergraphs, i.e. WF-hypergraphs. In our approach, workflow net process models are first transformed into WF-hypergraphs. Using this abstraction, finding the optimal way to complete a business process becomes a generalised hypergraph shortest path problem, which is NP-hard. To solve this problem, we propose a solution based on the ant-colony meta-heuristic specifically customised to the case of hypergraph traversal. The paper presents an experimental evaluation of the proposed optimisation heuristic and discusses how the proposed approach can be integrated into modern business process management systems.

Tài liệu tham khảo

citation_journal_title=Int J Inf Process Manag; citation_title=Simple additive weighting methods of multi criteria decision making and applications: a decade review; citation_author=L Abdullah, CR Adawiyah; citation_volume=5; citation_issue=1; citation_publication_date=2014; citation_pages=39; citation_id=CR1 citation_journal_title=IEEE Trans Softw Eng; citation_title=Adaptive service composition in flexible processes; citation_author=D Ardagna, B Pernici; citation_volume=33; citation_issue=6; citation_publication_date=2007; citation_pages=369-384; citation_doi=10.1109/TSE.2007.1011; citation_id=CR2 citation_journal_title=Math Found Comput Sci; citation_title=Hypergraph traversal revisited: cost measures and dynamic algorithms; citation_author=G Ausiello, G Italiano, U Nanni, L Brim; citation_volume=1450; citation_publication_date=1998; citation_pages=1-16; citation_id=CR3 citation_journal_title=Inf Sci; citation_title=Planning of business process execution in business process management environments; citation_author=H Bae, S Lee, I Moon; citation_volume=268; citation_publication_date=2014; citation_pages=357-369; citation_doi=10.1016/j.ins.2013.12.061; citation_id=CR4 citation_journal_title=Manag Sci; citation_title=Modeling data and process quality in multi-input, multi-output information systems; citation_author=DP Ballou, HL Pazer; citation_volume=31; citation_issue=2; citation_publication_date=1985; citation_pages=150-162; citation_doi=10.1287/mnsc.31.2.150; citation_id=CR5 citation_journal_title=Data Knowl Eng; citation_title=User recommendations for the optimized execution of business processes; citation_author=I Barba, B Weber, C Valle, A Jiménez-Ramírez; citation_volume=86; citation_publication_date=2013; citation_pages=61-84; citation_doi=10.1016/j.datak.2013.01.004; citation_id=CR6 citation_journal_title=Comput Oper Res; citation_title=Beam-ACO—hybridizing ant colony optimization with beam search: an application to open shop scheduling; citation_author=C Blum; citation_volume=32; citation_publication_date=2005; citation_pages=1565-1591; citation_doi=10.1016/j.cor.2003.11.018; citation_id=CR7 citation_journal_title=Int J Web Serv Res; citation_title=Business process control-flow complexity: metric, evaluation, and validation; citation_author=J Cardoso; citation_volume=5; citation_issue=2; citation_publication_date=2008; citation_pages=49-76; citation_doi=10.4018/jwsr.2008040103; citation_id=CR8 Cardoso J, Jablonski S, Volz B (2013) A navigation metaphor to support mobile workflow systems. In: International conference on business process management, Springer, pp 537–548 citation_journal_title=Inf Softw Technol; citation_title=Critical path identification in the context of a workflow; citation_author=D-H Chang, JH Son, MH Kim; citation_volume=44; citation_issue=7; citation_publication_date=2002; citation_pages=405-417; citation_doi=10.1016/S0950-5849(02)00025-3; citation_id=CR10 Comuzzi M (2017) Optimal paths in business processes: framework and applications. In: Business process management workshops citation_journal_title=Inf Sci; citation_title=Optimized cross-organizational business process monitoring: design and enactment; citation_author=M Comuzzi, ITP Vanderfeesten, T Wang; citation_volume=244; citation_publication_date=2013; citation_pages=107-118; citation_doi=10.1016/j.ins.2013.04.036; citation_id=CR12 Conforti R, Augusto A, La Rosa M, Dumas M, Garcia-Banuelos L (2016) BPMN miner 2.0: discovering hierarchical and block-structured BPMN process models. In: International conference on business process management. Springer, pp 328–343 citation_journal_title=Decis Support Syst; citation_title=A recommendation system for predicting risks across multiple business process instances; citation_author=R Conforti, M Leoni, M Rosa, WM Aalst, AH Hofstede; citation_volume=69; citation_publication_date=2015; citation_pages=1-19; citation_doi=10.1016/j.dss.2014.10.006; citation_id=CR14 Di Francescomarino C, Dumas M, Federici M, Ghidini C, Maggi FM, Rizzi W (2016) Predictive business process monitoring framework with hyperparameter optimization. In: International conference on advanced information systems engineering, pp 361–376 citation_journal_title=Theor Comput Sci; citation_title=Ant colony optimization theory: a survey; citation_author=M Dorigo, C Blum; citation_volume=344; citation_publication_date=2005; citation_pages=243-278; citation_doi=10.1016/j.tcs.2005.05.020; citation_id=CR16 citation_title=Fundamentals of business process management; citation_publication_date=2013; citation_id=CR17; citation_author=M Dumas; citation_author=M Rosa; citation_author=J Mendling; citation_author=HA Reijers; citation_publisher=Springer citation_title=Process-aware information systems: bridging people and software through process technology; citation_publication_date=2005; citation_id=CR18; citation_author=M Dumas; citation_author=WM Aalst; citation_author=AH Ter Hofstede; citation_publisher=Wiley citation_journal_title=Adv Eng Inform; citation_title=Comparison among five evolutionary-based optimization algorithms; citation_author=E Elbeltagi, T Hegazy, D Grierson; citation_volume=19; citation_publication_date=2005; citation_pages=43-53; citation_doi=10.1016/j.aei.2005.01.004; citation_id=CR19 citation_journal_title=Inf Syst; citation_title=Model repair—aligning process models to reality; citation_author=D Fahland, WMP Aalst; citation_volume=47; citation_publication_date=2015; citation_pages=220-243; citation_doi=10.1016/j.is.2013.12.007; citation_id=CR20 citation_journal_title=Int J Adv Manuf Technol; citation_title=Industrial applications of the ant colony optimization algorithm; citation_author=B Fox, W Xiang, H Lee; citation_volume=31; citation_publication_date=2007; citation_pages=805-814; citation_doi=10.1007/s00170-005-0254-z; citation_id=CR21 citation_journal_title=Discrete Appl Math; citation_title=Directed hypergraphs and applications; citation_author=G Gallo, G Longo, S Pallottino, S Nguyen; citation_volume=42; citation_issue=2–3; citation_publication_date=1993; citation_pages=177-201; citation_doi=10.1016/0166-218X(93)90045-P; citation_id=CR22 citation_journal_title=Decis Support Syst; citation_title=Improving business process decision making based on past experience; citation_author=J Ghattas, P Soffer, M Peleg; citation_volume=59; citation_publication_date=2014; citation_pages=93-107; citation_doi=10.1016/j.dss.2013.10.009; citation_id=CR23 citation_journal_title=Int J Qual Reliab Manag; citation_title=Service quality: concepts and models; citation_author=A Ghobadian, S Speller, M Jones; citation_volume=11; citation_issue=9; citation_publication_date=1994; citation_pages=43-66; citation_doi=10.1108/02656719410074297; citation_id=CR24 citation_title=Essentials of artificial intelligence; citation_publication_date=1993; citation_id=CR25; citation_author=M Ginsberg; citation_publisher=Morgan Kaufmann Publishers Günther CW, Van Der Aalst WM (2007) Fuzzy mining-adaptive process simplification based on multi-perspective metrics. In: International conference on business process management, Springer, pp 328–343 Haisjackl C, Weber B (2010) User assistance during process execution-an experimental evaluation of recommendation strategies. In: International conference on business process management, pp 134–145 citation_journal_title=J Med Syst; citation_title=Using recommendation to support adaptive clinical pathways; citation_author=Z Huang, X Lu, H Duan; citation_volume=36; citation_issue=3; citation_publication_date=2012; citation_pages=1849-1860; citation_doi=10.1007/s10916-010-9644-3; citation_id=CR28 citation_title=Business process modeling, simulation and design; citation_publication_date=2013; citation_id=CR29; citation_author=M Laguna; citation_author=J Marklund; citation_publisher=CRC Press citation_journal_title=Knowl Inf Syst; citation_title=A markov prediction model for data-driven semi-structured business processes; citation_author=GT Lakshmanan, D Shamsi, YN Doganata, M Unuvar, R Khalaf; citation_volume=42; citation_issue=1; citation_publication_date=2015; citation_pages=97-126; citation_doi=10.1007/s10115-013-0697-8; citation_id=CR30 Leemans SJ, Fahland D, van der Aalst WM (2013) Discovering block-structured process models from event logs containing infrequent behaviour. In: International conference on business process management, Springer, pp 66–78 Maggi FM, Di Francescomarino C, Dumas M, Ghidini C (2014) Predictive monitoring of business processes. In: International conference on advanced information systems engineering, pp 457–472 citation_journal_title=IEEE Trans Serv Comput; citation_title=Predictive monitoring of business processes: a survey; citation_author=AE Mrquez-Chamorro, M Resinas, A Ruiz-Cortes; citation_volume=1; citation_publication_date=2017; citation_pages=1-1; citation_id=CR33 citation_journal_title=Inf Sci; citation_title=Dynamic execution planning for reliable collaborative business processes; citation_author=J Oh, NW Cho, H Kim, Y Min, S-H Kang; citation_volume=181; citation_issue=2; citation_publication_date=2011; citation_pages=351-361; citation_doi=10.1016/j.ins.2010.09.019; citation_id=CR34 Polyvyabyy A, Weske M (2009) Hypergraph-based modeling of ad-hoc business processes. In: BPM workshops 2008, pp 278–289. Springer citation_title=Business process model abstraction; citation_inbook_title=Handbook on business process management; citation_publication_date=2015; citation_pages=147-165; citation_id=CR36; citation_author=A Polyvyanyy; citation_author=S Smirnov; citation_author=M Weske; citation_publisher=Springer citation_journal_title=Inf Syst; citation_title=Prediction of business process durations using non-Markovian stochastic Petri nets; citation_author=A Rogge-Solti, M Weske; citation_volume=54; citation_publication_date=2015; citation_pages=1-14; citation_doi=10.1016/j.is.2015.04.004; citation_id=CR37 Schonenberg H, Weber B, Van Dongen B, Van der Aalst W (2008) Supporting flexible processes through recommendations based on history. In: International conference on business process management. Springer, pp 51–66 citation_journal_title=IEEE Trans Syst Sci Cybern Part A; citation_title=Ant colony optimization for routing and load-balancing: survey and new directions; citation_author=K Sim, W Sun; citation_volume=33; citation_publication_date=2003; citation_pages=560-572; citation_doi=10.1109/TSMCA.2003.817391; citation_id=CR39 citation_journal_title=IEEE Trans Serv Comput; citation_title=Efficient alignment between event logs and process models; citation_author=W Song, X Xia, H-A Jacobsen, P Zhang, H Hu; citation_volume=10; citation_issue=1; citation_publication_date=2017; citation_pages=136-149; citation_doi=10.1109/TSC.2016.2601094; citation_id=CR40 citation_journal_title=Theor Comput Sci; citation_title=Linear connectivity problems in directed hypergraphs; citation_author=M Thakur, R Tripathi; citation_volume=410; citation_publication_date=2009; citation_pages=2592-2618; citation_doi=10.1016/j.tcs.2009.02.038; citation_id=CR41 citation_journal_title=Computer; citation_title=Auditing 2.0: using process mining to support tomorrow’s auditor; citation_author=WM Aalst, KM Hee, JM Werf, M Verdonk; citation_volume=43; citation_issue=3; citation_publication_date=2010; citation_pages=90-93; citation_doi=10.1109/MC.2010.61; citation_id=CR42 citation_journal_title=ACM Trans Manag Inf Syst; citation_title=Process mining: overview and opportunities; citation_author=W Aalst; citation_volume=3; citation_issue=2; citation_publication_date=2012; citation_pages=7; citation_id=CR43 van der Aalst WM (2009) Tomtom for business process management (tomtom4bpm). In: International conference on advanced information systems engineering, pp 2–5 citation_journal_title=Inf Syst; citation_title=Time prediction based on process mining; citation_author=WM Aalst, MH Schonenberg, M Song; citation_volume=36; citation_issue=2; citation_publication_date=2011; citation_pages=450-475; citation_doi=10.1016/j.is.2010.09.001; citation_id=CR45 citation_journal_title=Form Asp Comput; citation_title=Soundness of workflow nets: classification, decidability, and analysis; citation_author=WMP Aalst, KM Hee, AHM Hofstede, N Sidorova, HMW Verbeek, M Voorhoeve, MT Wynn; citation_volume=23; citation_issue=3; citation_publication_date=2010; citation_pages=333-363; citation_doi=10.1007/s00165-010-0161-4; citation_id=CR46 citation_journal_title=Form Asp Comput; citation_title=Soundness of workflow nets: classification, decidability, and analysis; citation_author=WMP Aalst, KM Hee, AHM Hofstede, N Sidorova, HMW Verbeek, M Voorhoeve, MT Wynn; citation_volume=23; citation_publication_date=2011; citation_pages=333-363; citation_doi=10.1007/s00165-010-0161-4; citation_id=CR47 citation_journal_title=Inf Syst; citation_title=Product-based workflow support; citation_author=I Vanderfeesten, HA Reijers, WM Aalst; citation_volume=36; citation_issue=2; citation_publication_date=2011; citation_pages=517-535; citation_doi=10.1016/j.is.2010.09.008; citation_id=CR48 citation_journal_title=Manag Sci; citation_title=A theoretical extension of the technology acceptance model: four longitudinal field studies; citation_author=V Venkatesh, FD Davis; citation_volume=46; citation_issue=2; citation_publication_date=2000; citation_pages=186-204; citation_doi=10.1287/mnsc.46.2.186.11926; citation_id=CR49 citation_journal_title=IEEE Trans Knowl Data Eng; citation_title=Efficient recovery of missing events; citation_author=J Wang, S Song, X Zhu, X Lin, J Sun; citation_volume=28; citation_issue=11; citation_publication_date=2016; citation_pages=2943-2957; citation_doi=10.1109/TKDE.2016.2594785; citation_id=CR50 citation_title=Operations research: applications and algorithms; citation_publication_date=2004; citation_id=CR51; citation_author=WL Winston; citation_author=JB Goldberg; citation_publisher=Duxbury Press