Ant-Colony Optimisation for Path Recommendation in Business Process Execution
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
