Piecewise Affine Dynamical Models of Petri Nets – Application to Emergency Call Centers

• Autorzy: Allamigeon Xavier , Boyet Marin , Gaubert Stéphane

Identyfikatory

DOI

10.3233/FI-2021-2086

• Języki publikacji: EN

Abstrakty

EN

We study timed Petri nets, with preselection and priority routing. We represent the behavior of these systems by piecewise affine dynamical systems. We use tools from the theory of nonexpansive mappings to analyze these systems. We establish an equivalence theorem between priority-free fluid timed Petri nets and semi-Markov decision processes, from which we derive the convergence to a periodic regime and the polynomial-time computability of the throughput. More generally, we develop an approach inspired by tropical geometry, characterizing the congestion phases as the cells of a polyhedral complex. We illustrate these results by a current application to the performance evaluation of emergency call centers in the Paris area. We show that priorities can lead to a paradoxical behavior: in certain regimes, the throughput of the most prioritary task may not be an increasing function of the resources.

Słowa kluczowe

EN

Timed Petri net; Performance evaluation; Markov decision process; tropical geometry; emergency call center

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 183, nr 3-4
• Strony: 169--201
• Opis fizyczny: Bibliogr 28 rys. wykr.

Twórcy

autor

Allamigeon Xavier

• INRIA and CMAP, CNRS, ´Ecole polytechnique IP Paris, France

autor

Boyet Marin

• INRIA and CMAP, CNRS, ´Ecole polytechnique IP Paris, France

autor

Gaubert Stéphane

• INRIA and CMAP, CNRS, ´Ecole polytechnique IP Paris, France

Bibliografia

• [1] Baccelli F, Cohen G, Olsder GJ, Quadrat JP. Synchronization and Linearity. Wiley, 1992. ISBN: 047193609X.
• [2] Heidergott G, Olsder GJ, van der Woude J. Max Plus at work. Princeton University Press, 2006. ISBN:9780691117638.
• [3] Komenda J, Lahaye S, Boimond JL, van den Boom T. Max-plus algebra in the history of discrete event systems. Annual Reviews in Control, 2018. 45:240–249. doi:10.1016/j.arcontrol.2018.04.004.
• [4] Cohen G, Gaubert S, Quadrat J. Asymptotic Throughput of Continuous Timed Petri Nets. In: Proceedings of the 34th Conference on Decision and Control. New Orleans, 1995. doi:10.1109/CDC.1995.480646.
• [5] Cohen G, Gaubert S, Quadrat J. Algebraic System Analysis of Timed Petri Nets. In: Gunawardena J (ed.), Idempotency, Publications of the Isaac Newton Institute, pp. 145–170. Cambridge University Press, 1998.
• [6] Gaujal B, Giua A. Optimal stationary behavior for a class of timed continuous Petri nets. Automatica, 2004. 40(9):1505–1516. doi:10.1016/j.automatica.2004.04.018.
• [7] Recalde L, Silva M. Petri net fluidification revisited: Semantics and steady state. European Journal of Automation, APII-JESA, 2001. 35(4):435–449.
• [8] Allamigeon X, Bœuf V, Gaubert S. Performance evaluation of an emergency call center: tropical polynomial systems applied to timed Petri nets. In: International Conference on Formal Modeling and Analysis of Timed Systems. Springer, 2015 pp. 10–26. doi:10.1007/978-3-319-22975-1_2.
• [9] L’Ecuyer P, Gustavsson K, Olsson L. Modeling bursts in the arrival process to an emergency call center. In: Rabe M, Juan AA, Mustafee N, Skoogh A, Jain S, Johansson B (eds.), Proceedings of the 2018 Winter Simulation Conference. 2018. doi:10.1109/WSC.2018.8632536.
• [10] Boeuf V, Robert P. A Stochastic Analysis of a Network with Two Levels of Service. Queueing Systems, 2019. 92(3-4):30. doi:10.1007/s11134-019-09617-y.
• [11] Puterman ML. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014. ISBN:978-1-118-62587-3.
• [12] Yushkevich A. On semi-Markov controlled models with an average reward criterion. Theory of Probability & Its Applications, 1982. 26(4):796–803. doi:10.1137/1126085.
• [13] Jianyong L, Xiaobo Z. On average reward semi-Markov decision processes with a general multichain structure. Mathematics of Operations Research, 2004. 29(2):339–352. doi:10.1287/moor.1030.0077.
• [14] Berman A, Plemmons RJ. Nonnegative matrices in the mathematical sciences. Academic Press, 1979.
• [15] Schweitzer PJ, Federgruen A. The Functional Equations of Undiscounted Markov Renewal Programming. Mathematics of Operations Research, 1978. 3(4):308–321. doi:10.1287/moor.3.4.308.
• [16] Denardo E, Fox B. Multichain Markov Renewal Programs. SIAM J.Appl.Math, 1968. 16:468–487. [17] Crandall M, Tartar L. Some relations between non expansive and order preserving maps. Proceedings of the AMS, 1980. 78(3):385–390. doi:10.2307/2042330.
• [18] Akian M, Gaubert S, Nussbaum R. Uniqueness of the fixed point of nonexpansive semidifferentiable maps. Trans. of AMS, 2016. 368(2):1271–1320. 1201.1536.
• [19] Kohlberg E. Invariant half-lines of nonexpansive piecewise-linear transformations. Math. Oper. Res., 1980. 5(3):366–372.
• [20] Martus P. Asymptotic properties of nonstationary operator sequences in the nonlinear case. Phd thesis, Friedrich-Alexander Universit¨at, Erlangen-N¨urnberg, 1989.
• [21] Lemmens B, Nussbaum RD. Nonlinear Perron-Frobenius theory, volume 189 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2012. ISBN:978-0-521-89881-2.
• [22] Lemmens B, Scheutzow M. On the dynamics of sup-norm non-expansive maps. Ergodic Theory Dynam. Systems, 2005. 25(3):861–871. doi:10.1017/S0143385704000665.
• [23] Akian M, Gaubert S. Spectral Theorem for Convex Monotone Homogeneous Maps, and ergodic Control. Nonlinear Analysis. Theory, Methods & Applications, 2003. 52(2):637–679. math.SP/0110108.
• [24] Gaubert S, Gunawardena J. The Perron-Frobenius Theorem for Homogeneous, Monotone Functions. Trans. of AMS, 2004. 356(12):4931–4950. math.FA/0105091.
• [25] Schweitzer P, Federgruen A. Geometric convergence of value-iteration in multichain Markov decision problems. Adv. Appl. Prob., 1979. 11:188–217. doi:10.2307/1426774.
• [26] De Loera JA, Rambau J, Santos F. Triangulations Structures for algorithms and applications. Springer, 2010. doi:10.1007/978-3-642-12971-1.
• [27] Ye HQ. A paradox for admission control of multiclass queueing network with differentiated service. Journal of applied probability, 2007. 44(2):321–331. doi:10.1239/jap/1183667404.
• [28] Schweitzer P, Federgruen A. The asymptotic behavior of undiscounted value iteration in Markov decision problems. Math. of O.R., 1978. 2:360–381. doi:10.1287/moor.2.4.360.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)