Safety and Soundness for Priced Resource : Constrained Workflow Nets

• Autorzy: Martos-Salgado M. , Rosa-Velardo F.

Identyfikatory

DOI

10.3233/FI-2014-1004

• Języki publikacji: EN

Abstrakty

EN

We extend workflow Petri nets (wf-nets) with discrete prices, by associating a price to the execution of a transition and to the storage of tokens. We first define the safety and the soundness problems for priced wf-nets. A priced wf-net is safe if no execution costs more than a given budget. The soundness problem is that of deciding whether the workflow can always terminate properly, where in the priced setting “properly” also means that the execution does not cost more than a given threshold. Then, we study safety and soundness of resource-constrained workflow nets (rcwf-nets), an extension of wf-nets for the modeling of concurrent executions of a workflow, sharing some global resources. We develop a framework in which to study safety and soundness for priced rcwf-nets, that is parametric on the cost model. Then, that framework is instantiated, obtaining the cases in which the sum, the maximum, the average and the discounted sum of the prices of all instances are considered. We study the decidability and the complexity of these properties, together with their relation.

Słowa kluczowe

EN

workflow; Petri nets; discrete systems; computational complexity; pricing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 131, nr 1
• Strony: 55--80
• Opis fizyczny: Bibliogr. 31 poz., rys., tab.

Twórcy

autor

Martos-Salgado M.

• Facultad de Informática, Universidad Complutense de Madrid, Spain

autor

Rosa-Velardo F.

• Facultad de Informática, Universidad Complutense de Madrid, Spain

Bibliografia

• [1] van der Aalst, W. M. P.: Verification of Workflow Nets, ICATPN (P. Azéma, G. Balbo, Eds.), 1248, Springer, 1997, ISBN 3-540-63139-9.
• [2] van der Aalst,W. M. P., van Hee, K. M.: Workflow Management: Models, Methods, and Systems, MIT Press, 2002, ISBN 0-262-01189-1.
• [3] van der Aalst, W. M. P., van Hee, K. M., ter Hofstede, A. H. M., Sidorova, N., Verbeek, H. M. W., Voorhoeve, M., Wynn, M. T.: Soundness of workflow nets: classification, decidability, and analysis, Formal Asp. Comput., 23(3), 2011, 333–363.
• [4] Abdulla, P. A., Delzanno, G., Begin, L. V.: A classification of the expressive power of well-structured transition systems, Inf. Comput., 209(3), 2011, 248–279.
• [5] Abdulla, P. A., Mayr, R.: Minimal Cost Reachability/Coverability in Priced Timed Petri Nets, FOSSACS (L. de Alfaro, Ed.), 5504, Springer, 2009, ISBN 978-3-642-00595-4.
• [6] Abdulla, P. A., Mayr, R.: Computing Optimal Coverability Costs in Priced Timed Petri Nets, LICS, IEEE Computer Society, 2011, ISBN 978-0-7695-4412-0.
• [7] Alur, R., Torre, S. L., Pappas, G. J.: Optimal paths in weighted timed automata, Theor. Comput. Sci., 318(3), 2004, 297–322.
• [8] Bouyer, P., Brihaye, T., Bruyère, V., Raskin, J.-F.: On the optimal reachability problem of weighted timed automata, Formal Methods in System Design, 31(2), 2007, 135–175.
• [9] Bouyer, P., Fahrenberg, U., Larsen, K. G., Markey, N.: Timed automata with observers under energy constraints, HSCC (K. H. Johansson,W. Yi, Eds.), ACM ACM, 2010, ISBN 978-1-60558-955-8.
• [10] Chatterjee, K., Doyen, L., Henzinger, T. A.: Quantitative languages, ACM Trans. Comput. Log., 11(4), 2010.
• [11] Chatterjee, K., Doyen, L., Henzinger, T. A., Raskin, J.-F.: Generalized Mean-payoff and Energy Games, FSTTCS (K. Lodaya, M. Mahajan, Eds.), 8, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2010, ISBN 978-3-939897-23-1.
• [12] Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C.: Introduction to Algorithms, 2 edition, The MIT Press, 2001.
• [13] Cowell, F.: Measuring Inequality, Oxford University Press, 2011.
• [14] Desel, J., Erwin, T.: Modeling, Simulation and Analysis of Business Processes, Business Process Management (W. M. P. van der Aalst, J. Desel, A. Oberweis, Eds.), 1806, Springer, 2000, ISBN 3-540-67454-3.
• [15] Desel, J., Erwin, T.: Quantitative Engineering of Business Processes with VIP business, Petri Net Technology for Communication-Based Systems (H. Ehrig, W. Reisig, G. Rozenberg, H. Weber, Eds.), 2472, Springer, 2003, ISBN 3-540-20538-1.
• [16] Dickson, L. E.: Finiteness of the Odd Perfect and Primitive Abundant Number swith n Distinct Prime Factors, American Journal of Mathematics, 35(4), 1913, pp. 413–422, ISSN 00029327.
• [17] Fahrenberg, U., Juhl, L., Larsen, K. G., Srba, J.: Energy Games in Multiweighted Automata, ICTAC (A. Cerone, P. Pihlajasaari, Eds.), 6916, Springer, 2011, ISBN 978-3-642-23282-4.
• [18] Finkel, A., Schnoebelen, P.: Well-structured transition systems everywhere!, Theor. Comput. Sci., 256(1-2), 2001, 63–92.
• [19] van Hee, K.M., Serebrenik, A., Sidorova, N., Voorhoeve, M.: Soundness of Resource-Constrained Workflow Nets, ICATPN (G. Ciardo, P. Darondeau, Eds.), 3536, Springer, 2005, ISBN 3-540-26301-2.
• [20] Juhás, G., Kazlov, I., Juhásová, A.: Instance Deadlock: A Mystery behind Frozen Programs, Petri Nets (J. Lilius, W. Penczek, Eds.), 6128, Springer, 2010, ISBN 978-3-642-13674-0.
• [21] Lazic, R., Newcomb, T., Ouaknine, J., Roscoe, A. W., Worrell, J.: Nets with Tokens which Carry Data, Fundam. Inform., 88(3), 2008, 251–274.
• [22] Liu, K., Jin, H., Chen, J., Liu, X., Yuan, D., Yang, Y.: A Compromised-Time-Cost Scheduling Algorithm in SwinDeW-C for Instance-Intensive Cost-Constrained Workflows on a Cloud Computing Platform, IJHPCA, 24(4), 2010, 445–456.
• [23] Magnani, M., Montesi, D.: BPMN: How Much Does It Cost? An Incremental Approach, BPM (G. Alonso, P. Dadam, M. Rosemann, Eds.), 4714, Springer, 2007, ISBN 978-3-540-75182-3.
• [24] Martos-Salgado, M., Rosa-Velardo, F.: Dynamic Soundness in Resource-Constrained Workflow Nets, FMOODS/FORTE (R. Bruni, J. Dingel, Eds.), 6722, Springer, 2011, ISBN 978-3-642-21460-8.
• [25] Martos-Salgado, M., Rosa-Velardo, F.: Cost Soundness for Priced Resource-Constrained Workflow Nets, Petri Nets (S. Haddad, L. Pomello, Eds.), 7347, Springer, 2012, ISBN 978-3-642-31130-7.
• [26] Mukherjee, D.: QoS in WS-BPEL Processes, Ph.D. Thesis, Indian Institute Of Technology, 2008.
• [27] Rosa-Velardo, F., de Frutos-Escrig, D.: Name Creation vs. Replication in Petri Net Systems, Fundam. Inform., 88(3), 2008, 329–356.
• [28] Rosa-Velardo, F., de Frutos-Escrig, D.: Decidability and complexity of Petri nets with unordered data, Theor. Comput. Sci., 412(34), 2011, 4439–4451.
• [29] Sampath, P., Wirsing, M.: Computing the Cost of Business Processes, UNISCON (J. Yang, A. Ginige, H. C. Mayr, R.-D. Kutsche, Eds.), 20, Springer, 2009, ISBN 978-3-642-01111-5.
• [30] Tahamtan, A., Oesterle, C., Tjoa, A. M., Hameurlain, A.: BPEL-TIME - WS-BPEL Time Management Extension, ICEIS (3) (R. Zhang, J. Cordeiro, X. Li, Z. Zhang, J. Zhang, Eds.), SciTePress, 2011, ISBN 978-989-8425-55-3.
• [31] Valk, R., Jantzen, M.: The Residue of Vector Sets with Applications to Decidability Problems in Petri Nets, Acta Inf., 21, 1985, 643–674.