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, December.
    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. 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.
    2. 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.
    3. Zeifman, Alexander, 2021. "Bounds on the rate of convergence for Markovian queuing models with catastrophes," Statistics & Probability Letters, Elsevier, vol. 176(C).

    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. 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).
    3. 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.
    4. Ward Whitt & Wei You, 2022. "New decomposition approximations for queueing networks," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 365-367, April.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Luca Becchetti & Stefano Leonardi & Alberto Marchetti-Spaccamela & Guido Schäfer & Tjark Vredeveld, 2006. "Average-Case and Smoothed Competitive Analysis of the Multilevel Feedback Algorithm," Mathematics of Operations Research, INFORMS, vol. 31(1), pages 85-108, February.
    11. Andersen, Anders Reenberg & Nielsen, Bo Friis & Reinhardt, Line Blander & Stidsen, Thomas Riis, 2019. "Staff optimization for time-dependent acute patient flow," European Journal of Operational Research, Elsevier, vol. 272(1), pages 94-105.
    12. Dijk, N.M. van, 1991. "Product forms for queueing networks with limited clusters," Serie Research Memoranda 0013, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    13. Ansari, Sardar & Yoon, Soovin & Albert, Laura A., 2017. "An approximate hypercube model for public service systems with co-located servers and multiple response," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 103(C), pages 143-157.
    14. Yacov Satin & Alexander Zeifman & Alexander Sipin & Sherif I. Ammar & Janos Sztrik, 2020. "On Probability Characteristics for a Class of Queueing Models with Impatient Customers," Mathematics, MDPI, vol. 8(4), pages 1-15, April.
    15. Samuli Aalto & Pasi Lassila & Prajwal Osti, 2016. "Whittle index approach to size-aware scheduling for time-varying channels with multiple states," Queueing Systems: Theory and Applications, Springer, vol. 83(3), pages 195-225, August.
    16. Nikhil Bansal & Bart Kamphorst & Bert Zwart, 2018. "Achievable Performance of Blind Policies in Heavy Traffic," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 949-964, August.
    17. Boucherie, R.J. & Dijk, N.M. van, 1988. "Spatial birth-death processes with multiple changes and applications to batch service networks and clustering processes," Serie Research Memoranda 0055, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    18. Tsiligianni, Christiana & Tsiligiannis, Aristeides & Tsiliyannis, Christos, 2023. "A stochastic inventory model of COVID-19 and robust, real-time identification of carriers at large and infection rate via asymptotic laws," European Journal of Operational Research, Elsevier, vol. 304(1), pages 42-56.
    19. Zeifman, A. & Satin, Y. & Kiseleva, K. & Korolev, V. & Panfilova, T., 2019. "On limiting characteristics for a non-stationary two-processor heterogeneous system," Applied Mathematics and Computation, Elsevier, vol. 351(C), pages 48-65.
    20. Kerry Fendick & Ward Whitt, 2022. "Heavy traffic limits for queues with non-stationary path-dependent arrival processes," Queueing Systems: Theory and Applications, Springer, vol. 101(1), pages 113-135, June.

    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.