IDEAS home Printed from https://ideas.repec.org/a/eee/apmaco/v395y2021ics0096300320307992.html
   My bibliography  Save this article

Ergodicity bounds for the Markovian queue with time-varying transition intensities, batch arrivals and one queue skipping policy

Author

Listed:
  • Zeifman, A.I.
  • Razumchik, R.V.
  • Satin, Y.A.
  • Kovalev, I.A.

Abstract

In this paper we revisit the Markovian queueing system with a single server, infinite capacity queue and one special queue skipping policy. Customers arrive in batches but are served one by one in any order. The size of the arriving batch becomes known upon its arrival and at any time instant the total number of customers in the system is also known. According to the adopted queue skipping policy if a batch, which size is greater than the current total number of customers in the system, arrives, all customers currently residing in the system are removed from it and the new batch is placed in the queue. Otherwise the new batch is lost and does not have effect on the system. The distribution of the total number of customers in the system is under consideration under assumption that the arrival intensity λ(t) and/or the service intensity μ(t) are non-random functions of time. We provide the method for the computation of the upper bounds for the rate of convergence of system size to the limiting regime, whenever it exists, for any bounded λ(t) and μ(t) (not necessarily periodic) and any distribution of the batch size. For periodic intensities λ(t) and/or μ(t) and light-tailed distribution of the batch size it is shown how the obtained bounds can be used to numerically compute the limiting distribution of the queue size with the given error. Illustrating numerical examples are provided.

Suggested Citation

  • 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).
    • Handle: RePEc:eee:apmaco:v:395:y:2021:i:c:s0096300320307992
    DOI: 10.1016/j.amc.2020.125846
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0096300320307992
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.amc.2020.125846?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. B. Pittel, 1979. "Closed Exponential Networks of Queues with Saturation: The Jackson-Type Stationary Distribution and Its Asymptotic Analysis," Mathematics of Operations Research, INFORMS, vol. 4(4), pages 357-378, November.
    3. Masayuki Matsui, 2009. "Stochastic Management Approach," International Series in Operations Research & Management Science, in: Manufacturing and Service Enterprise with Risks, chapter 0, pages 11-18, Springer.
    4. Masayuki Matsui, 2009. "Manufacturing and Service Enterprise with Risks," International Series in Operations Research and Management Science, Springer, number 978-0-387-84804-4, January.
    5. Ward Whitt & Wei You, 2019. "Time-Varying Robust Queueing," Operations Research, INFORMS, vol. 67(6), pages 1766-1782, November.
    6. Linus Schrage, 1968. "Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline," Operations Research, INFORMS, vol. 16(3), pages 687-690, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ilya Usov & Yacov Satin & Alexander Zeifman, 2023. "Estimating the Rate of Convergence of the PH/M/1 Model by Reducing to Quasi-Birth-Death Processes," Mathematics, MDPI, vol. 11(6), pages 1-11, March.
    2. Zeifman, Alexander, 2021. "Bounds on the rate of convergence for Markovian queuing models with catastrophes," Statistics & Probability Letters, Elsevier, vol. 176(C).
    3. 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.

    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. 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.
    2. Konstantin Avrachenkov & Patrick Brown & Natalia Osipova, 2009. "Optimal choice of threshold in Two Level Processor Sharing," Annals of Operations Research, Springer, vol. 170(1), pages 21-39, September.
    3. 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).
    4. Samuli Aalto & Ziv Scully, 2023. "Minimizing the mean slowdown in the M/G/1 queue," Queueing Systems: Theory and Applications, Springer, vol. 104(3), pages 187-210, August.
    5. Thomas Kittsteiner & Benny Moldovanu, 2005. "Priority Auctions and Queue Disciplines That Depend on Processing Time," Management Science, INFORMS, vol. 51(2), pages 236-248, February.
    6. Samuli Aalto & Urtzi Ayesta, 2009. "SRPT applied to bandwidth-sharing networks," Annals of Operations Research, Springer, vol. 170(1), pages 3-19, September.
    7. Azizoglu, Meral & Cakmak, Ergin & Kondakci, Suna, 2001. "A flexible flowshop problem with total flow time minimization," European Journal of Operational Research, Elsevier, vol. 132(3), pages 528-538, August.
    8. Ward Whitt & Wei You, 2022. "New decomposition approximations for queueing networks," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 365-367, April.
    9. Łukasz Kruk, 2017. "Edge minimality of EDF resource sharing networks," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 86(2), pages 331-366, October.
    10. Samuli Aalto, 2006. "M/G/1/MLPS compared with M/G/1/PS within service time distribution class IMRL," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 64(2), pages 309-325, October.
    11. Samuli Aalto & Ziv Scully, 2022. "On the Gittins index for multistage jobs," Queueing Systems: Theory and Applications, Springer, vol. 102(3), pages 353-371, December.
    12. Mor Harchol-Balter, 2021. "Open problems in queueing theory inspired by datacenter computing," Queueing Systems: Theory and Applications, Springer, vol. 97(1), pages 3-37, February.
    13. Yonatan Shadmi, 2022. "Fluid limits for shortest job first with aging," Queueing Systems: Theory and Applications, Springer, vol. 101(1), pages 93-112, June.
    14. Jonatha Anselmi & Bernardo D'Auria & Neil Walton, 2013. "Closed Queueing Networks Under Congestion: Nonbottleneck Independence and Bottleneck Convergence," Mathematics of Operations Research, INFORMS, vol. 38(3), pages 469-491, August.
    15. Nicole Megow & Tjark Vredeveld, 2014. "A Tight 2-Approximation for Preemptive Stochastic Scheduling," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 1297-1310, November.
    16. Douglas G. Down & H. Christian Gromoll & Amber L. Puha, 2009. "Fluid Limits for Shortest Remaining Processing Time Queues," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 880-911, November.
    17. Chengbin Chu, 1992. "A branch‐and‐bound algorithm to minimize total tardiness with different release dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(2), pages 265-283, March.
    18. 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.
    19. Dijk, N.M. van, 1989. "Product forms for queueing networks with limited clusters," Serie Research Memoranda 0029, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    20. Sitters, R.A., 2009. "Efficient algorithms for average completion time scheduling," Serie Research Memoranda 0058, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.

    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:eee:apmaco:v:395:y:2021:i:c:s0096300320307992. 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: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/applied-mathematics-and-computation .

    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.