In a highly competitive environment, enterprises success depends on the efectiveness of their business processes, which leads to the search of a continuous improvement in the time. This kind of improvement is called business process optimization. Yet, two major challenges often prevent processes optimization. First, the skills of the analysts to choose the right process among a number of propositions. Second, the techniques applied to generate and evaluate solutions during optimization process are poor and do not include all relevant data. Our Evolutionary Business Process Optimization approach addresses these challenges through a well-defined mathematical representation and a novel evolutionary algorithm as optimization facilities. In this paper, we focus to use of a formalized process optimization approach for generating and improving business process designs
A business process (BP) can be defined as a set of tasks that when properly connected perform
a business operation, e.g. a service or a product with benefit for the enterprise [
Coello Coello in [
This article explores a way to build satisfactory BP designs in an evolutionary multi-criteria
optimization problem. What authors mean by a BP design (as defined by Adamo in [
The result is an approach dealing with an evolutionary multi-criteria business process optimization (BPO) issue by minimizing cost and duration. The approach utilizes a multiple population GA adapted for the stated problem. The rest of the paper is organized as follows. Section 2 presents a state of the art on BPO with evolutionary algorithms (EA). Section 3 presents the optimization approach with the mathematical representation of BP designs and introduces properly the proposed multi-population GA. Experimental results are presented in section 4. Finally, section 5 summarizes the paper with conclusion and directions for future work.
The work of Hofacker [
Georgoulakos in [11] resumed [9] proposal and added a pre-processing stage to categorize
Web services for the working optimization framework. Thereafter, the work of Tsakalidis [12]
summarizes Vergidis’ work on BPO with evolutionary computing. In Si [13], the BPO is
discussed in regards to resources allocation. A GA is used with color Petri nets to reach desired
results. The authors of [
This article describes authors’ investigation and experimentation on the benefit from using a multiple population GA in BPO. The idea to propose the use of a multiple population within a GA comes from authors previous successful work which implied using a modified GA but still with a unique population. The authors are working to demonstrate that applying a multiple population approach in such issue can lead to explore more search space and in a shorter execution duration, at the same time.
The development of a functional and eficient optimization approach needs to overcome a number of variant challenges: 1. A simple representation technique able to capture the main features of a solution and easily used by optimization methods (e.g. GA). 2. An algorithmic approach for the composition of new solutions and evaluating them in a good manner.
During the optimization process, the authors work on the appended value by using a multiple population GA with the aim of reducing execution constraints such as calculation duration, and improve execution results.
A solution is defined by authors as a BP design has a mathematical representation (Table 1) which results to a graphical representation: a Task Task Matrix (TTM) (see figure 1) and its calculated attributes values. In order to represent a BP design, two nodes are added StarT and EnD, which represent the beginning and the end of a design, respectively. Each design has tasks ( ) that consumes and produces one or more resources ( ).
• If • If =
then ∩T = = {} then ∩
T = {}
Non-dominated sorting genetic algorithm II or NSGA-II is an EA that helps to solve this category of problems. It conducts the non-dominated sorting of the initial population, then applies genetic operators to obtain a brand-new population, merges the parent population with the resulting population, and conducts a non-dominated sorting to obtain a nondominated solutions front.
In former version of NSGA-II, a single population is maintained during the algorithm execution. A consequence of such choice is that population diversity may be poor as many local optima in some multi-objective optimization issues. Using a multiple population method with an EA helps to accelerate the convergence and because it uses multiple sub-populations, it accelerates individuals’ migration too, compared to a simple and unique population, which leads, to improve the results quantity.
Tanese [21] and Pettey [22] were the first to add a multiple population aspect with a GA based on the parallel computing paradigm. Chen in [23] describes two manners in which individuals are selected to migrate: • Uniform selection chooses individuals and replaces them in a sub-population with individuals randomly. • Selection based on Fitness picks individuals with high Fitness level and replaces them in a sub-population uniformly at random.
Chen in [23] proposed three migration manners between sub-populations of those being selected individuals.
• Adjacent migration: When individuals are allowed to transfer between adjacent subpopulations unidirectional. • Neighborhood migration: When individuals are allowed to transfer between nearest subpopulations in either direction. • Free migration: When individuals are allowed to transfer from any sub-population to another.
The authors have developed a novel multiple population GA based on NSGA-II which called MP-NSGA-II. The core functioning in figure 2: 1. An initial population of individuals is randomly generated. 2. The population is sorted in sub-population based on the crowding distant of NSGA-II. 3. The population is decomposed in sub-population based on the sorting result. 4. NSGA-II is applied separately on each population. 5. After a defined number of iterations all sub-populations share their information (Figure 2): • Best individuals of each sub-population are chosen to migrate. • A new main population is formed by the combination of best individuals (Fitnessbased) of each sub-population using a migration rate. 6. The best individuals are kept to form the new parent population.
7. Steps 2 to 6 are repeated for a number of iterations.
The proposed approach generates a set of optimized BP designs from an initial BP model. Its inputs and its outputs resources primarily define the model. Figure 3 outlines the steps making up the approach.
1. Perform MP-NSGA-II. The approach begins with the production of a set of populations of BP designs randomly. Which happens once during the approach execution. The population is not assessed until the evaluation stage (step 4). During the future iterations, MP-NSGA-II is applied rigorously. 2. Create mathematical representation. After the generation of a population of BP designs, each individual is represented by its (Table 1). Each matrix represents the relationship between the tasks composing a design using resources. 3. Apply and verify a set of restraints. During the approach course, a set of requirements needs to be examined regarding to the input and output resources, used and produced by each solution, respectively. Then, checks a set of constraints regarding the design itself. 4. The evaluation consists of calculating the attributes of each individual created and on which diferent constraints have been applied. The attributes of a BP design are calculated based on the tasks’ attributes composing it. Subsequently, these attributes are the objective values used to calculate the Fitness function of each solution which used later by MP-NSGA-II. 5. Apply Steps 1 to 4 are repeated for a number of iterations defines by the experimenters.
It would be advisable to specify that the execution of the first step difers after the first iteration.
• MP-NSGA-II generates the first population randomly from scratch during the first iteration. • MP-NSGA-II generates the new population (always) randomly but from the ofspring of the first iteration results, during all of the following iterations.
The proposed optimization approach aim is to generate a set of optimized feasible BP designs. A feasible solution is a BP design which: 1. Consumes all input resources of the original BP model, 2. Produces all output resources of the original BP model. 3. With limited length. 4. It leads to define the features and summarizes what is expected from the approach as: • The amount of feasible non-dominated solutions. • The solutions with diferent sizes and diferent solutions with same size i.e. solutions variety
The present work focuses on a combinatorial multi-criteria BPO and seeks to minimize two criteria. These two criteria’ units of measure are not specified. As example, criteria can be assumed as cost and duration, and the aim is to minimize them on a design as studied in [24].
The authors assumed that tasks composing a solution are in sequential order. So, the calculation of a BP design attributes (objective values) for the tasks is shown in equation (1): ( ) = ∑ =1 (1) • : BP design. • : Tasks’ number composing
. • : Objective value. •
: Value of for a task . equation (2):
The Fitness function used by MP-NSGA-II where k the number of criteria to optimize is in ( ) = ∑
( ) =1 (2)
To explore the influence of the multiple sub-population feature on the performance of MPNSGAII, it seems necessary to know how to measure it. Therefore, as described in [25], an average optimal value (
) and a success rate ( ) are used in this study to measure the performance of MP-NSGA-II. For a given population size, the algorithm runs several times. Table 2 summarizes the optimization approach parameters. It itemizes also the genetic operators features used within MP-NSGA-II.
First, the impact of the sub-population size, and the sub-population number, afect the performance of MP-NSGA-II is studied. The results are shown in figure 4 for the sub-population number experiments and figure 5 for the sub-population size experiments.
The experiment results of the optimization approach are presented then analyzed using five (05) diferent scenarios borrowed from [9] and [11]. The scenarios gather a diferent tasks library size (set of tasks used to generate solutions).
Tables ?? and ?? show computational results where all tests were performed using the settings summarized in Table 2. For the purpose of comparison, the authors conducted experiments on two axes, with one hundred (100) iterations each: • Diversifying used GAs: Simple genetic algorithm (SGA), NSGA-II, MP-SGA and MP
NSGA-II.
The influence of the sub-populations size on the performance of MP-NSGA-II is studied (likewise for the sub-population number). The size is changed from 0 to 450 with a step size of 50. Figure 4 presents the experiments results. The algorithm runs 50 times, and the average of the values of these runs are used to measure the performance of MP-NSGAII.
In figure 4, the X-axis, Y-axis (left), and Y-axis (right) represent sub-population size ( ), , and , respectively. For <50, the performance of the algorithm is extremely poor ( <10 and =20). For increasing , the performance of MP-NSGA-II improved rapidly. For = 200, MP-NSGA-II shows an improved performance with an of 73, and is 90%. At this level, MP-NSGA-II performs best. However, as continues to increase, the performance of MP-NSGA-II slowly decreases. Therefore, it can be concluded that, the performance of proposed algorithm improves rapidly with increasing , and then decreases slowly. To obtain an improved approach, the value of the size of sub-populations cannot be too small, specifically, a value around 200 is a good choice.
Second, the influence of the sub-population number on the performance of MP-NSGA-II is studied. The number is changed from 0 to 25 with a step size of 5. Figure 5 presents the obtained results. In figure 5, the X-axis, Y-axis (left), and Y-axis (right) represent number of subpopulations, , and , respectively. For <20, the performance of MP-NSGA-II is poor and is less than 20, and is 20%. The performance of MP-NSGA-II increases slowly with increasing of the number of sub-populations ( ). For = 5, MP-NSGA-II performs the best, =75, and =79%. As continues to increase, the performance of MP-NSGA-II rapidly decreases. Therefore, it can be concluded that, the performance of MP-NSGA-II first improves slowly and then decreases rapidly with increasing . To obtain an improved optimization approach, the value of sub-populations should be a value around 5, for the present issue. These values ( =200, =5) is used later on the forthcoming experiments as shown in the approach parameters (Table 2).
The number of non-dominated solutions by scenario with the optimization approach using multiple population GAs with diferent migration processes is summarized in figure 6. The amount of solutions obtained difers between the diferent GAs can be observed evidently. Among the four tested GAs, MP-NSGA-II outperforms on each scenario and with every migration process applied. Even if the values are close (by migration process) for each scenario, which can be explained by the discrete nature of values used in diferent scenarios (tasks library and available resources). But, if the comparison in done by focusing on the GA instead of diferent migration process, the obtained results difer significantly.
Figure 6 presents the increase rate (%) of number of solutions generated compared to a simple GA. Figure 7 depicts the eficiency of the proposed multiple population GA for diferent scenarios. It summarizes the average results classified by scenario. It clearly highlight and confirms that the diferent versions of the approach with multiple population GAs obtain the best overall results compared with a simple GA or NSGA-II. It is clear that for scenarios sample in the experiments, the performance of MP-NSGA-II is significantly better than the singlepopulation GA not only in the number of results, the execution time but also in the convergent speed of searching. In addition, since the multi-population GA let the sub-populations evolve separately, it might be able to explore more extreme solutions.
A GA based on multi-population (MP-NSGA-II) is presented in this study for solving a multiobjective BP designs problem. The algorithm can be summarized as follow: First, sub-populations are created from a unique initial population, using a crowding distance sorting. Then, in order to prevent the premature convergence of all individuals into a local optimal, NSGA-II is applied separately on each sub-population. Finally, sub-populations are regrouped (by migration) as a single population. To do so, each individual in the final population is chosen based on a non-dominated sorting randomly which may help to explore for more solution spaces next iterations.
So, this paper explores the idea of using MP-NSGA-II in a multiple objective problem of BPO. This work concretely aims at giving a tool capable to enhance the generated BP designs in quantity and diversity. Further investigations and experimentation would be welcomed to improve the proposed approach and its EA. In the future, tests with MP-NSGA-II can be further extended to a larger number of tasks to work with. Working with more optimization criteria is the next step to follow. It would be interesting to manipulate the number of sub-populations and population size within the chosen GA. [9] K. Vergidis, C. Turner, A. Alechnovic, A. Tiwari, An automated optimisation framework for the development of re-configurable business processes: a web services approach, Inter.
J. of Computer Integrated Manufacturing 28 (2015) 41–58. [10] N. Mahammed, S. M. Benslimane, An evolutionary algorithm based approach for business process multi-criteria optimization, Inter. J. of Organizational and Collective Intelligence (IJOCI) 7 (2017) 34–53. [11] K. Georgoulakos, K. Vergidis, G. Tsakalidis, N. Samaras, Evolutionary multi-objective optimization of business process designs with pre-processing, in: 2017 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2017, pp. 897–904. [12] G. Tsakalidis, K. Vergidis, Towards a comprehensive business process optimization framework, in: 2017 IEEE 19th Conf. on Business Informatics (CBI), volume 1, IEEE, 2017, pp. 129–134. [13] Y.-W. Si, V.-I. Chan, M. Dumas, D. Zhang, A petri nets based generic genetic algorithm framework for resource optimization in business processes, Simulation Modelling Practice and Theory 86 (2018) 72–101. [14] M. Comuzzi, Ant-colony optimization for path recommendation in business process execution, J. on Data Semantics 8 (2019) 113–128. [15] J. Kurniasih, E. Utami, S. Raharjo, Query optimization: A metaheuristics approach using modified memetics algorithm (mma), in: Journal of Physics: Conf. Series, volume 1254, IOP Publishing, 2019, p. 012011. [16] C. Shajahan, E. E. Subramanyan, S. Kumanan, N. Firoz, Design process sequencing in product development process using design structure matrix and particle swarm optimisation techniques, in: J. of Physics: Conf. Series, volume 1355, IOP Publishing, 2019, p. 012027. [17] M. Rekik, K. Boukadi, H. Ben-Abdallah, An end-to-end system to enhance business process performance through new outsourcing to the cloud strategies, Inter. J. of Business and Systems Research 13 (2019) 1–20. [18] R. C. G.-L. Neira-Tovar, Un enfoque para la optimizacion de procesos de negocio: Metodologia prototipo focus for the business processes optimization: A methodology prototype, Daena: Inter. Journal of Good Conscience 14 (2019) 364–383. [19] S. Deshmukh, M. Agarwal, S. Gupta, N. Kumar, Moea for discovering pareto-optimal process models: an experimental comparison, Inter. J. of Computational Science and Engineering 21 (2020) 446–456. [20] H. Li, S. Weng, J. Tong, T. He, W. Chen, M. Sun, Y. Shen, Composition of resource-service chain based on evolutionary algorithm in distributed cloud manufacturing systems, IEEE Access 8 (2020) 19911–19920. [21] R. Tanese, Parallel genetic algorithm for a hypercube, in: Genetic algorithms and their applications: proceedings of the second International Conference on Genetic Algorithms: July 28-31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA, Hillsdale, NJ: L. Erlhaum Associates, 1987., 1987. [22] C. B. Pettey, M. R. Leuze, J. J. Grefenstette, A parallel genetic algorithm, in: Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, 1987, pp. 155–161. [23] Y. Chen, Y. Zhong, Automatic path-oriented test data generation using a multi-population genetic algorithm, in: 2008 Fourth Inter. Conf. on Natural Computation, volume 1, IEEE, 2008, pp. 566–570. [24] A. Chassiakos, G. Rempis, Evolutionary algorithm performance evaluation in project time-cost optimization, J. of Soft Computing in Civil Engineering 3 (2019) 16–29. [25] X.-q. Shi, W. Long, Y.-y. Li, Y.-l. Wei, D.-s. Deng, Diferent performances of diferent intelligent algorithms for solving fjsp: A perspective of structure, Computational intelligence and neuroscience 2018 (2018).