Microsoft Word - tpel.doc Mathematical Problems of Computer Science 36, 28—40, 2012. 28 Analysis of Characteristics for Cyclic Business Processes Lusine S. Tarumyan IT Educational and Research Center, Yerevan State University Abstract A new method for evaluation of business process characteristics is proposed, which is applicable at design stage when probabilities of process transitions are unknown. Among a variety of publications on the process analysis, only a few address processes under unknown probabilities of transitions. The latter consider only acyclic processes, which restricts their application scope. The suggested method is based on a transformation of unstructured cycles into LOOP cycles. It gives an opportunity to represent a process via a hierarchy of LOOPs and to apply dynamic programming methodology for characteristics analysis. It allows to extend the algorithms, initially developed for acyclic processes, for the analysis of cyclic processes, preserving at the same time the polynomial complexity of source algorithms. The introduced method has been used to develop effective algorithms for determination of the main characteristics of a business process (including time, cost, revenue, and profit). References [1] W. van der Aalst, M. van H. Kees, Workflow Management, Models, Methods and Systems, The MIT Press Cambridge, 2002. [2] H. Jonkers, H.M. Franken, “Quantitative modeling and analysis of business processes”, Simulation in Industry, 8th European Simulation Symposium, vol.I, pp.175-179, 1996. [3] L. Tarumyan, “Timing analysis for workflow processes”, 17th European Simulation Symposium and Exhibition Within I3M'05 International Mediterranean Modeling Multiconference, pp. 51-57, 2005. [4] W. van der Aalst, J. Desel, E. Kindler, “On the semantics of EPCs: A vicious circle”, Workshop on EPK, pp 7-18, 2003. [5] J. Koehler, R. Hauser, “Untangling unstructured cyclic flows - a solution based on continuations”, 6th Int. Conference on Cooperative Information Systems CoopIs, Springer LNCS 3290, pp. 121-138, 2004. [6] L. Tarumyan, “A System of performance characteristics analysis for business processes”, CSIT2011 Eighth International Conference on Computer Science and Information technologies, pp. 198-201, 2011. [7] F. Dirk, C. Favre, B. Jobstmann, J. Koehler, N. Lohmann, H. Völzer, K. Wolf, “Instantaneous soundness checking of industrial business process models”, 7th Int. Conference on Business Process Management, Springer LNCS 5701, pp. 278-293, 2009. [8] J. Cardoso, A. Sheth, J. Miller, “Workflow quality of service”, International Conference on Enterprise Integration and Modeling Technology and International Enterprise Modeling Conference (ICEIMT/IEMC’02), 2002. [9] J. H. Son, M. H. Kim, “Analyzing the critical path for the well-formed workflow schema”, Seventh International Conference on Database Systems for Advanced Applications DASFAA, pp.146-147, 2001. [10] J. Eder, E. Panagos, “Managing time in workflow systems”, Workflow Handbook 2001, Layne Fischer ed., ISBN 0-9703509-0-2, pp. 109-132, 2001. L. Tarumyan 29 [11] F.E. Allen, J. Cocke, “A program data flow analysis procedure”, IBM Thomas J. Watson Research Center, 1971. [12] J. Vanhatalo, H. Volzer, F. Leymann, “Faster and more focused control-flow analysis for business process models though SESE decomposition”, ICSOC, Vol. 4749, pp. 43–55, 2007. [13] J. Vanhatalo, H. Völzer, J. Koehler, “The refined process structure tree”, Data & Knowledge Engineering, v.68 n.9, pp.793-818, 2009. [14] R. Bellman. Dynamic Programming, Princeton University Press, 1957. [15] Workflow Management Coalition (WfMC), Workflow Standard – Process Definition Interchange, Process Model. WfMC TC-1016-P.Version 1.1, 1999. [16] F. Leymann, D. Roller, Production Workflow: concepts and techniques. Prentice Hall, 2000. [17] M. A Schaefer, Mathematical Theory of Global Program Optimization. Prentice-Hall,1973. [18] P. Raulefs, S. Shoukourian, L. Tarumyan, V Matevosyan, “Determination of critical paths in hammock type processes”, HPC‘2003, SCS International Advanced Simulation Technologies Conference ASTC’2003, pp. 241-246, 2003. ´Ýáõó·ñÇãÝ»ñÇ í»ñÉáõÍáõÃÛáõÝÁ óÇÏÉÇÏ µÇ½Ý»ë åñáó»ëÝ»ñÇ Ñ³Ù³ñ È. ³éáõÙÛ³Ý ²Ù÷á÷áõÙ ²é³ç³ñÏí³Í ¿ µÇ½Ý»ë åñáó»ëÝ»ñÇ µÝáõó·ñÇãÝ»ñÇ ·Ý³Ñ³ïÙ³Ý Ýáñ Ù»Ãá¹, áñÁ ÏÇñ³é»ÉÇ ¿ ݳ˳·ÍÙ³Ý ÷áõÉáõÙ` »ñµ åñáó»ëÇ Õ»Ï³í³ñÙ³Ý ³ÝóáõÙÝ»ñÇ Ñ³í³Ý³Ï³ÝáõÃÛáõÝÝ»ñÁ ³ÝѳÛï »Ý: äñáó»ëÝ»ñÇ í»ñÉáõÍáõÃÛ³ÝÁ í»ñ³µ»ñíáÕ ³éϳ Ññ³å³ñ³ÏáõÙÝ»ñÇó Áݹ³Ù»ÝÁ ÙÇ ù³ÝÇëÝ »Ý ³Ý¹ñ³¹³éÝáõ٠ջϳí³ñÙ³Ý ³ÝóáõÙÝ»ñÇ ³ÝѳÛï ѳí³Ý³Ï³ÝáõÃÛáõÝÝ»ñáí åñáó»ëÝ»ñÇÝ: ì»ñçÇÝÝ»ñë ¹Çï³ñÏáõÙ »Ý ÙdzÛÝ ³óÇÏÉÇÏ åñáó»ëÝ»ñÁ, áñÁ ë³Ñٳݳ÷³ÏáõÙ ¿ Ýñ³Ýó ÏÇñ³éÙ³Ý áÉáñïÁ: ²é³ç³ñÏí³Í Ù»Ãá¹Á Ñ»Ýí³Í ¿ óÇÏÉ»ñÇ áã ëïñáõÏïáõñǽ³óí³ÍÇó LOOP Ó¨³÷áËÙ³Ý íñ³: ¸³ Ñݳñ³íáñáõÃÛáõÝ ¿ ï³ÉÇë åñáó»ëÁ Ý»ñϳ۳óÝ»É LOOP-»ñÇ ÑÇ»ñ³ñËdzÛÇ ï»ëùáí ¨ µÝáõó·ñÇãÝ»ñÇ í»ñÉáõÍáõÃÛ³Ý Ñ³Ù³ñ ÏÇñ³é»É ¹ÇݳÙÇÏ Íñ³·ñ³íáñÙ³Ý Ù»Ãá¹Á: ¸³ Ñݳñ³íáñáõÃÛáõÝ ¿ ï³ÉÇë ³óÇÏÉÇÏ åñáó»ëÝ»ñÇ Ñ³Ù³ñ Ùß³Ïí³Í í»ÉáõÍáõÃÛ³Ý ³É·áñÇÃÙÝ»ñÁ ÁݹɳÛÝ»É óÇÏÉÇÏ åñáó»ëÝ»ñÇ Ñ³Ù³ñ` ÙǨÝáõÛÝ Å³Ù³Ý³Ï å³Ñå³Ý»Éáí ݳËÝ³Ï³Ý ³É·áñÇÃÙÝ»ñÇ µ³½Ù³Ý¹³Ù³ÛÇÝ µ³ñ¹áõÃÛáõÝÁ: Ü»ñϳ۳óí³Í Ù»Ãá¹Á û·ï³·áñÍí³Í ¿ µÇ½Ý»ë åñáó»ëÝ»ñÇ ³é³çݳÛÇÝ µÝáõó·ñÇãÝ»ñÇ áñáßÙ³Ý ¿ý»ÏïÇí ³É·áñÇÃÙÝ»ñÇ Ùß³ÏÙ³Ý Ñ³Ù³ñ (ųٳݳÏ, ͳËë, »Ï³Ùáõï, ß³ÑáõÛÃ): Analysis of Characteristics for Cyclic Business Processes 30 Àíàëèç õàðàêòåðèñòèê öèêëè÷åñêèõ áèçíåñ-ïðîöåññîâ Ë. Òàðóìÿí Àííîòàöèÿ Ïðåäëîæåí íîâûé ìåòîä îöåíêè õàðàêòåðèñòèê áèçíåñ-ïðîöåññîâ, êîòîðûé ïðèìåíèì íà ýòàïå ïðîåêòèðîâàíèÿ, êîãäà âåðîÿòíîñòè ïåðåõîäîâ ïðîöåññà íåèçâåñòíû. Ñðåäè ìíîæåñòâà ïóáëèêàöèé, ïîñâÿùåííûõ àíàëèçó ïðîöåññîâ, ëèøü íåìíîãèå ðàññìàòðèâàþò ïðîöåññû ñ íåèçâåñòíûìè âåðîÿòíîñòÿìè ïåðåõîäîâ. Íî â ýòèõ ðàáîòàõ ðàññìàòðèâàþòñÿ òîëüêî àöèêëè÷åñêèå ïðîöåññû, ÷òî îãðàíè÷èâàåò îáëàñòü èõ ïðèìåíåíèÿ. Ïðåäëàãàåìûé ìåòîä îñíîâàí íà ïðåîáðàçîâàíèè íåñòðóêòóðèðîâàííûõ öèêëîâ â LOOP öèêëû. Ýòî äàåò âîçìîæíîñòü ïðåäñòàâèòü ïðîöåññ â âèäå èåðàðõèè LOOP öèêëîâ è ïðèìåíèòü ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ äëÿ àíàëèçà õàðàêòåðèñòèê. Ìåòîä ïîçâîëÿåò ðàñøèðèòü àíàëèòè÷åñêèå àëãîðèòìû, êîòîðûå ïåðâîíà÷àëüíî ðàçðàáîòàíû äëÿ àöèêëè÷åñêèõ ïðîöåññîâ, äëÿ öèêëè÷åñêèõ áèçíåñ-ïðîöåññîâ, ïðè ýòîì ñîõðàíÿÿ ïîëèíîìèàëüíóþ ñëîæíîñòü íà÷àëüíûõ àëãîðèòìîâ. Ïðåäëîæåííûé ìåòîä áûë èñïîëüçîâàí äëÿ ðàçðàáîòêè ýôôåêòèâíûõ àëãîðèòìîâ îïðåäåëåíèÿ êëþ÷åâûõ õàðàêòåðèñòèê áèçíåñ- ïðîöåññîâ (âðåìÿ, çàòðàòû, äîõîäû, ïðèáûëü).