Research Journal of Recent Sciences _________________________________________________ ISSN 2277-2502 Vol. 2(12), 74-79, December (2013) Res.J.Recent Sci. International Science Congress Association 74 Customizing NSGAII to Optimize Business Processes DesignsShirin Torabi Farsani, Majid Aboutalebi and Homaun MotameniSari Branch, Islamic Azad University, Sari, IRANAvailable online at: www.isca.in, www.isca.me Received 13th May 2013, revised 10th June 2013, accepted 3rd July 2013Abstract Nowadays, business processes of firms and organizations have encountered many complications. On the other hand, business owners tend to maintain competitive market and increase profitability of their businesses. Therefore, they put the efforts to improve their business processes in the form of decreased costs and increased quality of product and customer satisfaction. Thus, business owners try to consider the optimization of business processes using suitable methods for a continuous and structured improvement of business processes. There are many methods most of which based on complicated mathematical relationships; evolutionary algorithms have become more popular. Hence, the present study attempts to optimize the process using an evolutionary method based on non-dominated sorting genetic evolutionary algorithms. However, the objective here is to customize the algorithm properly in order to achieve efficient and reasonable results. Keywords: Business processes, optimization, evolutionary algorithms, evolutionary operators, evolutionary optimization, non-dominated sorting genetic algorithm, qualitative parameters, quantitative parameters Introduction Due to increasingly expanded utilization of information systems, business architecture and modelling have been considerably interested. During recent fifteen years, many authors studied business area2-4. Changes in organization make it necessary to make changes in modelling business processes over time2,5,6. Extraction of AS-IS model and development of information systems based on them is ineffective; because these systems often need changes and system will encounter many challenges or breakdowns, if implemented. Extraction of TO-BE model is often time consuming and in cases completely impossible6-8. A proper solution to achieve a developable business process model (BPM) is to optimize AS-IS model9-11. The present study provides and examines proper algorithmic methods to extract an optimized model from AS-IS model of organization. An optimized model involves feasibility and optimality of internal and external efficiency. Internal efficiency of a business process can be measured by measuring parameters such as resource consumption (cost) and external efficiency is measured by criteria such as response time, operational power etc.12,13. The present study considers an algorithm to find optimal designs of business process as evolutionary double-objective optimization algorithm which randomly produces possible states of business process and then finds optimal states among them. Generally, evolutionary optimization is helpful because it can discover process designs which may have been ignored. These methods are able to evaluate alternative designs and determine the best and most proper one based on particular goals12. Literature ReviewOptimization of business process is conducted to decrease run time and cost, improve quality of product and promote satisfactory of customers and personnel10,14. In relation to optimizing business processes, a business process is considered as a series of tasks when correctly connected a correct business operation is conducted6,16,17. Although there are many methods for modelling business processes, only few can optimize business processes; since, they mostly either use complicated mathematical models or consider a fixed design for the process which only tasks participating in the design are optimized13,14,18,19. Optimization of business processes have a more formal landscape compared to other business areas10,13. Hofacker et al.12 worked on optimizing business processes by a genetic algorithm (GA); however, their work did not provide satisfactory results. Their developed model was highly complicated due to numerous mathematical formula and limitations; hence, GA hardly can generate optimal solutions. Tiwari et al.18 developed their mathematical model and used multi-objective optimization algorithms such as NSGA2 and SPEA2 reporting satisfactory results. Tiwari et al. initially graphically modeled a pilot business process and formulated its formal (mathematical) model considering total constraints and essential variables. The formulation was based on minimizing two objectives: cost and run time. Then to find optimal solution from their own model, they used three evolutionary algorithms including NSGAII, SPEAII and MOPSO. They finally compared solutions of three algorithms using efficiency index. Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 2(12), 74-79, December (2013) Res. J. Recent Sci. International Science Congress Association 75 Vergidis et al.20 initially developed a schematic model of a general process by total input and output resources and its activities; theydetermined activities and their related costs as well as objective functions required for minimizing cost and run time and maximizing productivity of resources using mathematical modelling. Then, they determined required parameters for three developed evolutionary algorithms and compared them to find optimal solutions. A breakdown for most of these methods is to use complicated mathematical modellings as well as evolutionary algorithms in their traditional form. The present study tries to overcome more effectively on these breakdowns. Moreover, current study is different from other ones on that how internal and external parameters are organized and used to analyze alternative optimal processes. The proposed Algorithm to Find Optimal Designs of Business Process: Those elements which participate in the process include tasks participating in the process, characteristics and properties of tasks and resources needed to fulfill tasks as well as external resources for process of same products generated by the process. Sorting input and output resources of tasks can determine how tasks are interconnected in the process. Characteristics and properties of a process totally can be achieved by characteristics and properties of tasks. Generally, characteristics and properties of tasks are used to analyze quantitative (time, cost …) and qualitative (satisfaction of customers, quality of product and etc.) parameters13. The proposed method considered several alternatives for total tasks. There are particular resources and properties for each alternative; this varies designs. The figure 1 shows the proposed algorithm to find optimal designs of business process.  \n \r Figure-1The proposed algorithm to find optimal designs of business process The first part of algorithm needs to evaluate input parameters and variables used for (some notations are derived from 10,13): is number of tasks available in task library participating in the process and represented as Tlibrary={t,t,t,…,t}. is number of tasks belonged to a particular design represented as design={t,t,t,…,t }, Tdesignlibrary. k is number of available resources and represented as R={r, r2 , r3 , r}(Tasks need to resources to perform their jobs). Subseries RGIN and RGOUT are total input and output resources for the process by which feasibility of a process can be evaluated. In fact, a business process design needs to consume total resources available in GIN and produce total resources available in RGout. Input and output resources of the task i available in the library are represented as the series R={{Rin},{Rout}}, RinR and RoutR (resources needed for tasks need to be available in resource list). Each task has i characteristics which are maximally p represented as a={ai1,ai2,…,aip}. The proposed algorithm considers two matrices for each process design: one holds sequence of tasks (process design) and the other maintains characteristics of tasks. The former is a two-dimensional matrix called as Task-Resource (TR) matrix and holds input and output resources of a task. TR is an×k matrix representing ,”n” rows which show number of tasks available in process design and “k” as columns which show number of resources needed for a task. Then, the matrix shows total input and output resources available in the design. Followings are considered to develop the matrix: i. Resource j given that j R and task i given that idesign. ii. Let resource j be neither an input nor an output resource for task i; then TRij=0. TR is able to hold business process and form basis of new designs. The matrix TA is the same as TR. TA maintains values for characteristics of tasks participating in the process used for evaluating business process based on properties and characteristics of the task. TA is n×p matrix representing “n” rows which show number of tasks and “p” as columns which show number of characteristics considered in the process. Then, we have: TAi1= {ai1}, TAi2= {ai2}… TAip = {aip} Value of characteristic j for the process can be calculated by total values corresponding to that characteristic for n tasks. Thus, we have: pA j = (1) In general, performance of the process is evaluated by TR and TA matrices. According to figure 1, inputs of the algorithm include one-dimensional array of a task library, chromosome size, available Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 2(12), 74-79, December (2013) Res. J. Recent Sci. International Science Congress Association 76 resources, resource vector (containing input and output resources needed for a task), characteristic vector (containing values for time and cost of a task) and conditions for feasibility of a design (total input and output resources). By input information, the first part of algorithm starts to produce random solutions followed by developing TR and TA matrices for solutions). Feasibility conditions can determine unfeasible solutions and repair them as much as possible; then some penalties are considered for their occurrence (next section discusses their repair and estimation of penalty function). Penalty Function: For each condition of unfeasibility in random solutions, some penalties are considered which are added to objective function. Conditions of unfeasibility are initially considered and value of their penalties is determined as follows: i. One or more output resources are not generated (% penalty). ii. One or more input resources are not consumed by tasks available in TR (% penalty). iii. There is a disconnection in the design which can not be alternated by tasks based on available resources (% penalty). To obtain penalty function needs estimation of exact value for , and as well as number of occurrences of these conditions representing as n, m and k, respectively. Then, penalty function is: penalty × n + × m + × k, (2) As noted above, when feasibility random solutions generated by the first part of the proposed algorithm is evaluated, best solutions are selected by the proposed evolutionary algorithm to generate population and next generation. As required generations are iterated, a series of optimal solutions can be obtained based on optimization purposes. To perform second part of the algorithm correctly, it is required that evolutionary operators can be customized efficiently. Customized Crossover Operator: Since genetic operators are used to diverse solutions available in population and to expand query space, this section addresses how these operators are customized. First, customization of crossover operator is studied. Two random members are initially selected from population; then, two random numbers are selected between 1 and nd and total tasks between these two random numbers are paired compared according to optimization purposes. Two sequential tasks with timeless than or equal to a minimum time and implementation cost greater than or equal to a minimum cost are selected and combined in a task; combined task is entitled from two tasks prior to attachment. Then, time, cost and resources of combined task are considered as figure 2. Figure-2Code for customized crossover operatorAccording to above conditions, TAi1 is time and TAi2 is cost of implementing taski (instead of i, any task can be used). K represents name of combined task. Customized Mutation Operator: To customize mutation operator, a member of population is randomly selected; then a random number is selected between 1 and nd and corresponding task is evaluated in terms of both optimization purposes. Under this condition, it is evaluated that whether selected task time is greater than or equal to maximum time and its cost is greater than or equal to minimum cost and less than or equal to maximum cost. If so, considered task is divided to two tasks running parallel to each other. Then, time, cost and resources of parallel task are considered as figure 3. Figure-3Code for customized mutation operator Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 2(12), 74-79, December (2013) Res. J. Recent Sci. International Science Congress Association 77 The proposed Evolutionary Algorithms: A NSGAII evolutionary algorithm is used to find Pareto optimal solutions. However, some changes are made for multi-objective optimization of business processes. NSGAII is derived from GA; however, NSGAII is able to run multi-objective optimization in more efficient way than GA. NSGAII can well perform in discrete optimization settings; however, the only breakdown to NSGAII is its low rate in finding optimal solutions. This is because each step to generate new population needs to find optimal solutions of Pareto population and determine priority or rank of each solution; this is time-consuming. Despite this fact, NSGAII is highly efficient and its performance is improved by adding crossover and mutation operators. Table 1 shows tuning of parameters in evolutionary algorithms. Table-1Parameters available in evolutionary algorithmsNSGA2 Population size: 100 Number of generations:250 Probable mutation: 0.7 Probable crossover: 0.9 Real Studied Case: To run proposed algorithm on a real-world process, reservation process of a tourism agency is considered [3]. There are four tasks in this process; two alternatives with different time and cost are developed for each task. There are also four resources. Then, we have: design = {t, t2 , t,t}, Tlibrary = {t, t2 , … , t}, Rdesign={r1 , r, ,r} (3) Results and Discussion Here, results from running the proposed algorithm on considered process are run and derived results are compared to NSGAII proposed by Vergidis. Values for parameters of NSGAII are considered as follows: Figure 4 shows the results from running algorithms proposed by Vergidis. According to the table 2, three optimal processes can be listed from different values of time and cost. Figure 5 shows results for running the proposed optimization algorithm on NSGA. Table-2Values for time and cost of optimal process in NSGAProcess Time Cost 1 8 34 2 12 23 3 16 16 Figure-4Result from running NSGA on reservation process of a tourism agency 8 10 12 14 16 18 20 22 12 14 16 18 20 22 24 26 28 Duration CostFigure-5Result from running proposed algorithm on customized NSGAAs figure 5 shows, six optimal processes are generated with different time and cost. Values for each process are listed in table 3. Table-3Time and cost of optimal process in the proposed NSGAProcess Time Cost 1 8 28 2 12 22 3 15 19 4 16 17 5 19 16 6 22 8 Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 2(12), 74-79, December (2013) Res. J. Recent Sci. International Science Congress Association 78 As results of the proposed algorithm shows, number of optimal processes increased and their values became better. It is noteworthy that most tasks are different from tasks available in primary population; this is because of running attachment and parallel operators on qualified tasks of feasible solutions in the population (all attachments and parallelisms of tasks can be observed by running algorithm). To run such operators on population of solutions can improve time, cost and number of customers available in the process in an efficient way; in a broader sense, the process can be optimized in terms of objective parameters. Discussion: According to presented figures, this is possible to evaluate optimal business processes in terms of qualitative parameters of time and cost. Additionally, alternative process designs can be evaluated and analyzed in terms of qualitative parameter of customer satisfaction. To do so, customers’ satisfaction can be defined as formula below (number of waiting customers is 1000): (4) where, number of progressing customers is equal to number of customers who serviced by the process at the end of a complete cycle (even though services are not completed). The more customers supported in each full cycle of process the more satisfaction for the process. The more satisfaction the higher quality process is. As noted above, time and cost are quantitative criteria of a business process. Now, another quantitative criterion called as operational power is calculated here: (5) Here, productivity index is analyzed. Performance of business process can be analyzed by estimating value of the index for running each evolutionary algorithm on considered process. The index is formulated as follows22: (6) Accordingly, the more useful process has more productivity. Table 6 lists values for time, cost, customer satisfaction, operational power and productivity of NSGA. ConclusionThe present study developed an efficient and structured method to optimize business process using NSGA. The algorithm was modified so that it was able to optimize business processes in discrete settings in an efficient way. To do so, considered algorithm was customized. By developing the proposed algorithm, requisites were provided to implement a real-world example on the proposed optimization algorithm of business process. Then, reservation process of a tourism agency was implemented on the algorithm and its results were compared to reported results in Vergidis et al.. The present study provided an opportunity to evaluate optimal processes using quantitative criteria including time, cost, operational power and qualitative criteria including satisfaction and productivity and analyze them in terms of internal and external criteria. Success of used method was related to analysis of quantitative and qualitative parameters in discrete setting of business processes compared to previous studies in terms of efficiency of the proposed algorithm. Previous studies put no effort on customizing evolutionary algorithms for optimizing business processes. However, current study combined evolutionary operators and modified NSGA to use efficiently business processes. The proposed method allows using more evolutionary algorithms; to do so, a tree genetic algorithm, a gravitation search algorithm and a raindrop algorithm can be used. More quantitative and qualitative parameters can also be considered to find alternative designs. However, authors will use more parameters to optimize business processes in the future. Table-6 Values for characteristics of NSGAproductivity Operational Power Customer ’s Satisfaction Number Customers Cost Time Property Process 0.5581250.0030281 0.172245.45450.008022122 0.55801250.005019153 0.172245.45450.008017164 0.5581250.004016195 0.55801250.0050226 Research Journal of Recent Sciences ______________________________________________________________ ISSN 2277-2502Vol. 2(12), 74-79, December (2013) Res. J. Recent Sci. International Science Congress Association 79 References1.Wolfenden P.J. and Welch D.E. Business Architecture: A Holistic Approach to Defining the Organization Necessary to Deliver a Strategy, Knowledge and Process Management, 7(2), 97–106 (2000)2.Van der Aalst, W.M.P., Van Hee K.M. and Houben G.J., Modelling and analysing workflow using a Petri-net based approach, In Proceedings of the second Workshop on Computer-Supported Cooperative Work, Petri nets and related formalisms (1994)3.Vergidis K., Tiwari A., Majeed B. and Roy R., Optimisation of business process designs: an algorithmic approach with multiple objectives, International Journal of Production Economics, 109(1), 105-121 (2007)4.Tiwari A. and Vergidis K., Evolutionary Multi-objective Optimization of Business Processes, IEEE Comouter Society, 3091–3097, (2006)5.Van Der Aalst W.M., Ter Hofstede A.H., Kiepuszewski B. and Barros A.P., Workflow patterns, Distributed and parallel databases, 14(1), 5-51 (2003)6.Van Der Aalst W. and K. Van Hee, Workflow Management Models, Methods , and Systems, Second edi. London: Academic Service, (2002)7.Ortiz-Hernández J. and Nieto-Ariza E.M., Estrada-Esquivel H., Rodríguez-Ortiz G. and Montes-Rendon A., A theoretical evaluation for assessing the relevance of modeling techniques in business process modeling, In Fourth international workshop on Software quality assurance: in conjunction with the 6th ESEC/FSE joint meeting, 102-107 (2007)8.Emiris D.M., Koulouriotis D.E. and Matsatsinis N.F., Modeling of business processes and functions of an industrial unit for ERP system application, Operational Research, (2), 181-195, (2001)9.Vergidis K., Tiwari A., Majeed B. and Roy R., Optimisation of business process designs: an algorithmic approach with multiple objectives, International Journal of Production Economics, 109(1), 105-121 (2007)10.Vergidis K., Saxena D. and Tiwari A., An evolutionary multi-objective framework for business process optimization, Applied Soft Computing, 12(8), 2638–2653 (2012)11.Shraideh A., Yim P., Business process optimization by workflow analysis, Springer Berlin, (2010)12.Vergidis K., Tiwari A. and Majeed B., Business process analysis and optimization: beyond reengineering, Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 38(1), 69-82 (2008)13.Vergidis K. and Tiwari A., Business Process Design and Attribute Optimization within an Evolutionary Frammework, IEEE Congress on Evolutionary Computation, 668–675 (2008)14.Ahmadikatouli A. and Aboutalebi M., New Evolutionary Approach to Business Process Model Optimization, In Proceedings of the International MultiConference of Engineers and Computer Scientists, (2011)15.Vanderfeesten I., Reijers H.A. and Van der Aalst W.M., Product-based workflow support, Information Systems, 36(2), 517-535 (2011)16.Damij N., Damij T., Grad J. and Jelenc F., A methodology for business process improvement and IS development, Information and software technology, 50(11), 1127-1141 (2008)17.Dayal, U., Hsu, M., & Ladin, R. Business process coordination: State of the art, trends, and open issues. In Proceedings of the 27th International Conference on Very Large Data Bases, (2001)18.Tiwari A., Vergidis K. and Roy R., Evolutionary Optimization of Business Process Designs, In Evolutionary Scheduling, 513-541). Springer Berlin Heidelberg (2007)19.Völkner P. and Werners B., A decision support system for business process planning, European Journal of Operational Research, 125(3), 633-647 (2000)20.Vergidis K. and Tiwari A., Composite Business Process: An Evolutionary Multi-objective Optimization Approach, IEEE World Congress on Computational Intelligence, 2672–2678 (2007)21.Van Hee K.M. and Reijers H.A., Using formal analysis techniques in business process redesign, In Business process management (142-160), Springer Berlin Heidelberg (2000)22.Valenti S. and Cucchiarelli A., Computer Based Assessment Systems Evaluation via the ISO9126 Quality Model, Journal of Information Technology Education 1(3), 158–175 (2002)