IMPROVED MULTI-OBJECTIVE OPTIMIZATION IN BUSINESS PROCESS MANAGEMENT USING R-NSGA-II
DOI:
https://doi.org/10.15588/1607-3274-2023-3-18Keywords:
business process, genetic algorithm, reference points, multi-objective optimization, spacingAbstract
Context. Business process management is a critical component in contemporary organizations for maintaining efficiency and achieving operational objectives. Optimization of these processes in terms of time and cost can lead to significant improvements in overall business performance. However, traditional optimization techniques often face challenges in handling multi-objective problems with a known time-cost trade-off, necessitating more effective solutions. The integration of a business process model and notation for a stochastic process simulation provides a robust foundation for analyzing these business processes and complies with stateof-the-art business process management. In prior studies, we applied several heuristic algorithms, including the evolutionary NSGAII, to find a Pareto-optimal set of solutions. We defined a solution as a pair of cost and time associated with a specific resource allocation. For one of the selected processes, the performance of NSGA-II was subpar compared to other techniques.
Objective. The goal of this study is to improve upon the NSGA-II’s performance and, in turn, enhance the efficiency of multiobjective business process optimization. Specifically, we aim to incorporate reference points into NSGA-II. Our goal is to identify an optimized set of solutions that represent a trade-off between process execution time and the associated cost. We expect this set to have a higher spread and other quality metrics, compared to the prior outputs.
Method. To accomplish our objective, we adopted a two-step approach. Firstly, we modified the original genetic algorithm by selecting and integrating the reference points that served to guide the search towards the Pareto-optimal front. This integration was designed to enhance the exploration and exploitation capabilities of the algorithm. Secondly, we employed the improved algorithm, namely R-NSGA-II, in the stochastic simulations of the business processes. The BPMN provided the input for these simulations, wherein we altered the resource allocation to observe the impact on process time and cost.
Results. Our experimental results demonstrated that the R-NSGA-II significantly outperformed the original NSGA-II algorithm for the given process model, derived from the event log. The modified algorithm was able to identify a wider and more diverse Pareto-optimal front, thus providing a more comprehensive set of optimal solutions concerning cost and time.
Conclusions. The study confirmed and underscored the potential of integrating the reference points into NSGA-II for optimizing business processes. The improved performance of R-NSGA-II, evident from the better Pareto-optimal front it identified, highlights its efficacy in multi-objective optimization problems, as well as the simplicity of the reference-based approaches in the scope of BPM. Our research poses the direction for the further exploration of the heuristics to improve the outcomes of the optimization techniques or their execution performance.
References
Qin J., Zhao N., Xie Z. et al. Business Process Modelling based on Petri nets, MATEC Web of Conference, 2017, Vol. 139, № 1, pp. 105–113.
Shoylekova K., Grigorova K. Methods for Business Process Simulation Based on Petri Nets, International Journal of Industrial and Systems Engineering, 2015, Vol. 9, Issue 12, pp. 4148–4153.
Umair M. M., Barkaoui K., Li Z. et al. Transformation of Business Process Model and Notation models onto Petri nets and their analysis, Advances in Mechanical Engineering, 2018, Vol. 10, № 12, pp. 168–188.
De Backer M., Snoeck M. Deterministic Petri Net Languages as Business Process Specification Language [Electronic resource], SSRN Electronic Journal, 2006. Access mode: http://dx.doi.org/10.2139/ssrn.876906
Zeigler B. Praehofer H., Gon Kim T. Theory of Modeling and Simulation. Cambridge, Academic Press, 2018, Discrete Event & Iterative System Computational Foundations, pp. 567–599.
Raedts I., Petkovic M., Usenko Y. et al. Transformation of BPMN Models for Behaviour Analysis, 5th International Workshop on Modelling, Simulation, Verification and Validation of Enterprise Information Systems, MSVVEIS-2007, Funchal, June 2007, proceedings, 2007, pp. 126–137.
Li Z., Ye Z. A Petri Nets Evolution Method that Supports BPMN Model Changes, Scientific Programming, 2021, Vol. 2021, Issue 3, pp. 1–16.
Pintado O. L., Dumas M., Yerokhin M. et al. Silhouetting the Cost-Time Front: Multi-objective Resource Optimization in Business Processes, Business Process Management Forum, Rome, 6–10 September 2021: proceedings. Berlin, Springer, 2021, pp. 92–108.
Durán F., Rocha C., Salaün G. Analysis of Resource Allocation of BPMN Processes, 17th International Conference on Service-Oriented Computing, Toulouse, 28–31 October 2019, proceedings. Berlin, Springer, 2019, pp. 452–457.
Rizk-Allah R. M. A Novel Multi-Ant Colony Optimization For Multi-Objective Resource Allocation Problems, International Journal of Mathematical Archive, 2014, Vol. 5, № 9, pp. 183–192.
Couckuyt I., Deschrijver D., Dhaene T. Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization, Journal of Global Optimization, 2013, Vol. 60, №3, pp. 575–594.
Cheng R., Jin Y., Olhofer M. et al. A Reference Vector Guided Evolutionary Algorithm for Many-Objective Optimization. IEEE transactions on neural networks, IEEE Transactions on Evolutionary Computation, 2016, Vol. 20, № 5, pp. 773–791.
Tong L., Du B. Neural architecture search via reference point based multi-objective evolutionary algorithm, Pattern Recognition, 2022, Vol. 132, № 11.
Lárraga G., Saini B. S., Miettinen K. Incorporating Preference Information Interactively in NSGA-III by the Adaptation of Reference Vectors, Evolutionary Multi-Criterion Optimization, Hannover, 18–23 September 2023, proceedings. Berlin, Springer, 2023, pp. 578–592.
Vargas D., Lemonge A. C. C., Barbosa H. et al. Solving multi-objective structural optimization problems using GDE3 and NSGA-II with reference points, Engineering Structures, 2021, Vol. 239, № 3.
Deb K., Jayavelmurugan S. Reference Point Based MultiObjective Optimization Using Evolutionary Algorithms, International Journal of Computational Intelligence Research, 2006, Vol. 2, № 3, pp. 635–642.
Dumas M., La Rosa M., Mendling J. et al. Fundamentals of Business Process Management. Berlin, Springer, 2018, 527 p.
Estrada-Torres B., Camargo M., Dumas M. et al. Discovering business process simulation models in the presence of multitasking and availability constraints, Data & Knowledge Engineering, 2021, Vol. 134, № 1.
Camargo M., Dumas M., González-Rojas O. Automated discovery of business process simulation models from event logs, Decision Support Systems, 2020, Vol. 134, № 1.
Audet C., Bigeon J., Cartier D. Et al.Performance indicators in multiobjective optimization, European Journal of Operational Research, 2021, Vol. 292, № 2, pp. 397–422.
Blank J., Deb K. Pymoo: Multi-Objective Optimization in Python, IEEE Access, 2020, Vol. 8, № 1, pp. 89497–89509.
Tanabe R., Oyama A. The Impact of Population Size, Number of Children, and Number of Reference Points on the Performance of NSGA-III, International Conference on Evolutionary Multi-Criterion Optimization, Münster, 19–22 March 2017: proceedings. Berlin, Springer, 2017, pp. 606– 621.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 В. О. Філатов, М. А. Єрохін
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
