IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2020i1p42-d469068.html
   My bibliography  Save this article

Facilitating Numerical Solutions of Inhomogeneous Continuous Time Markov Chains Using Ergodicity Bounds Obtained with Logarithmic Norm Method

Author

Listed:
  • Alexander Zeifman

    (Institute of Informatics Problems, Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, Vavilova 44-2, 119333 Moscow, Russia
    Department of Applied Mathematics, Vologda State University, Lenina 15, 160000 Vologda, Russia
    Moscow Center for Fundamental and Applied Mathematics, Moscow State University, Leninskie Gory 1, 119991 Moscow, Russia; vkorolev@cs.msu.ru)

  • Yacov Satin

    (Department of Applied Mathematics, Vologda State University, Lenina 15, 160000 Vologda, Russia)

  • Ivan Kovalev

    (Department of Applied Mathematics, Vologda State University, Lenina 15, 160000 Vologda, Russia)

  • Rostislav Razumchik

    (Institute of Informatics Problems, Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, Vavilova 44-2, 119333 Moscow, Russia
    Moscow Center for Fundamental and Applied Mathematics, Moscow State University, Leninskie Gory 1, 119991 Moscow, Russia; vkorolev@cs.msu.ru)

  • Victor Korolev

    (Institute of Informatics Problems, Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, Vavilova 44-2, 119333 Moscow, Russia
    Moscow Center for Fundamental and Applied Mathematics, Moscow State University, Leninskie Gory 1, 119991 Moscow, Russia; vkorolev@cs.msu.ru
    Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, 119991 Moscow, Russia)

Abstract

The problem considered is the computation of the (limiting) time-dependent performance characteristics of one-dimensional continuous-time Markov chains with discrete state space and time varying intensities. Numerical solution techniques can benefit from methods providing ergodicity bounds because the latter can indicate how to choose the position and the length of the “distant time interval” (in the periodic case) on which the solution has to be computed. They can also be helpful whenever the state space truncation is required. In this paper one such analytic method—the logarithmic norm method—is being reviewed. Its applicability is shown within the queueing theory context with three examples: the classical time-varying M / M / 2 queue; the time-varying single-server Markovian system with bulk arrivals, queue skipping policy and catastrophes; and the time-varying Markovian bulk-arrival and bulk-service system with state-dependent control. In each case it is shown whether and how the bounds on the rate of convergence can be obtained. Numerical examples are provided.

Suggested Citation

  • Alexander Zeifman & Yacov Satin & Ivan Kovalev & Rostislav Razumchik & Victor Korolev, 2020. "Facilitating Numerical Solutions of Inhomogeneous Continuous Time Markov Chains Using Ergodicity Bounds Obtained with Logarithmic Norm Method," Mathematics, MDPI, vol. 9(1), pages 1-20, December.
    • Handle: RePEc:gam:jmathe:v:9:y:2020:i:1:p:42-:d:469068
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/1/42/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/1/42/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Linda Green & Peter Kolesar, 1991. "The Pointwise Stationary Approximation for Queues with Nonstationary Arrivals," Management Science, INFORMS, vol. 37(1), pages 84-97, January.
    2. Anyue Chen & Xiaohan Wu & Jing Zhang, 2020. "Markovian bulk-arrival and bulk-service queues with general state-dependent control," Queueing Systems: Theory and Applications, Springer, vol. 95(3), pages 331-378, August.
    3. Liu, Yunan & Whitt, Ward, 2017. "Stabilizing performance in a service system with time-varying arrivals and customer feedback," European Journal of Operational Research, Elsevier, vol. 256(2), pages 473-486.
    4. Armann Ingolfsson & Elvira Akhmetshina & Susan Budge & Yongyue Li & Xudong Wu, 2007. "A Survey and Experimental Comparison of Service-Level-Approximation Methods for Nonstationary M(t)/M/s(t) Queueing Systems with Exhaustive Discipline," INFORMS Journal on Computing, INFORMS, vol. 19(2), pages 201-214, May.
    5. Ward Whitt & Wei You, 2019. "Time-Varying Robust Queueing," Operations Research, INFORMS, vol. 67(6), pages 1766-1782, November.
    6. Peter J. Kolesar & Kenneth L. Rider & Thomas B. Crabill & Warren E. Walker, 1975. "A Queuing-Linear Programming Approach to Scheduling Police Patrol Cars," Operations Research, INFORMS, vol. 23(6), pages 1045-1062, December.
    7. Schwarz, Justus Arne & Selinka, Gregor & Stolletz, Raik, 2016. "Performance analysis of time-dependent queueing systems: Survey and classification," Omega, Elsevier, vol. 63(C), pages 170-189.
    8. Soongeol Kwon & Natarajan Gautam, 2016. "Guaranteeing performance based on time-stability for energy-efficient data centers," IISE Transactions, Taylor & Francis Journals, vol. 48(9), pages 812-825, September.
    9. M. Arns & P. Buchholz & A. Panchenko, 2010. "On the Numerical Analysis of Inhomogeneous Continuous-Time Markov Chains," INFORMS Journal on Computing, INFORMS, vol. 22(3), pages 416-432, August.
    10. Pier Conti, 1997. "An asymptotic test for a geometric process against a lattice distribution with monotone hazard," Statistical Methods & Applications, Springer;Società Italiana di Statistica, vol. 6(3), pages 213-231, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yongkyu Cho & Young Myoung Ko, 2020. "Stabilizing the virtual response time in single-server processor sharing queues with slowly time-varying arrival rates," Annals of Operations Research, Springer, vol. 293(1), pages 27-55, October.
    2. Schwarz, Justus Arne & Selinka, Gregor & Stolletz, Raik, 2016. "Performance analysis of time-dependent queueing systems: Survey and classification," Omega, Elsevier, vol. 63(C), pages 170-189.
    3. Yacov Satin & Rostislav Razumchik & Ilya Usov & Alexander Zeifman, 2023. "Numerical Computation of Distributions in Finite-State Inhomogeneous Continuous Time Markov Chains, Based on Ergodicity Bounds and Piecewise Constant Approximation," Mathematics, MDPI, vol. 11(20), pages 1-12, October.
    4. William A. Massey & Jamol Pender, 2018. "Dynamic rate Erlang-A queues," Queueing Systems: Theory and Applications, Springer, vol. 89(1), pages 127-164, June.
    5. Pei, Zhi & Dai, Xu & Yuan, Yilun & Du, Rui & Liu, Changchun, 2021. "Managing price and fleet size for courier service with shared drones," Omega, Elsevier, vol. 104(C).
    6. Niyirora, Jerome & Zhuang, Jun, 2017. "Fluid approximations and control of queues in emergency departments," European Journal of Operational Research, Elsevier, vol. 261(3), pages 1110-1124.
    7. Yacov Satin & Rostislav Razumchik & Ivan Kovalev & Alexander Zeifman, 2023. "Ergodicity and Related Bounds for One Particular Class of Markovian Time—Varying Queues with Heterogeneous Servers and Customer’s Impatience," Mathematics, MDPI, vol. 11(9), pages 1-15, April.
    8. Ran Liu & Xiaolan Xie, 2018. "Physician Staffing for Emergency Departments with Time-Varying Demand," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 588-607, August.
    9. Defraeye, Mieke & Van Nieuwenhuyse, Inneke, 2016. "Staffing and scheduling under nonstationary demand for service: A literature review," Omega, Elsevier, vol. 58(C), pages 4-25.
    10. Linda V. Green & Peter J. Kolesar, 1998. "A Note on Approximating Peak Congestion in Mt/G/\infty Queues with Sinusoidal Arrivals," Management Science, INFORMS, vol. 44(11-Part-2), pages 137-144, November.
    11. Ad Ridder, 2022. "Rare-event analysis and simulation of queues with time-varying rates," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 545-547, April.
    12. Yue Zhang & Martin L. Puterman & Matthew Nelson & Derek Atkins, 2012. "A Simulation Optimization Approach to Long-Term Care Capacity Planning," Operations Research, INFORMS, vol. 60(2), pages 249-261, April.
    13. Eugene Furman & Adam Diamant & Murat Kristal, 2021. "Customer Acquisition and Retention: A Fluid Approach for Staffing," Production and Operations Management, Production and Operations Management Society, vol. 30(11), pages 4236-4257, November.
    14. Hu, Lu & Zhao, Bin & Zhu, Juanxiu & Jiang, Yangsheng, 2019. "Two time-varying and state-dependent fluid queuing models for traffic circulation systems," European Journal of Operational Research, Elsevier, vol. 275(3), pages 997-1019.
    15. J. G. Dai & Pengyi Shi, 2017. "A Two-Time-Scale Approach to Time-Varying Queues in Hospital Inpatient Flow Management," Operations Research, INFORMS, vol. 65(2), pages 514-536, April.
    16. Ward Whitt & Wei You, 2019. "Time-Varying Robust Queueing," Operations Research, INFORMS, vol. 67(6), pages 1766-1782, November.
    17. Gabriel Zayas-Cabán & Mark E. Lewis, 2020. "Admission control in a two-class loss system with periodically varying parameters and abandonments," Queueing Systems: Theory and Applications, Springer, vol. 94(1), pages 175-210, February.
    18. Zeifman, A.I. & Razumchik, R.V. & Satin, Y.A. & Kovalev, I.A., 2021. "Ergodicity bounds for the Markovian queue with time-varying transition intensities, batch arrivals and one queue skipping policy," Applied Mathematics and Computation, Elsevier, vol. 395(C).
    19. Linda V. Green & Peter J. Kolesar & João Soares, 2001. "Improving the Sipp Approach for Staffing Service Systems That Have Cyclic Demands," Operations Research, INFORMS, vol. 49(4), pages 549-564, August.
    20. Narayanan C. Viswanath, 2022. "Transient study of Markov models with time-dependent transition rates," Operational Research, Springer, vol. 22(3), pages 2209-2243, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:9:y:2020:i:1:p:42-:d:469068. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.