IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v47y2022i1p232-258.html

Large Deviations for the Single-Server Queue and the Reneging Paradox

Author

Listed:
  • Rami Atar

    (Viterbi Faculty of Electrical Engineering, Technion, Haifa 32000, Israel)

  • Amarjit Budhiraja

    (Department of Statistics and Operations Research, University of North Carolina at Chapel Hill, Chapel Hill, North Carolina 27599)

  • Paul Dupuis

    (Division of Applied Mathematics, Brown University, Providence, Rhode Island 02906)

  • Ruoyu Wu

    (Department of Mathematics, Iowa State University, Ames, Iowa 50011)

Abstract

For the M/M/1+M model at the law-of-large-numbers scale, the long-run reneging count per unit time does not depend on the individual (i.e., per customer) reneging rate. This paradoxical statement has a simple proof. Less obvious is a large deviations analogue of this fact, stated as follows: the decay rate of the probability that the long-run reneging count per unit time is atypically large or atypically small does not depend on the individual reneging rate. In this paper, the sample path large deviations principle for the model is proved and the rate function is computed. Next, large time asymptotics for the reneging rate are studied for the case when the arrival rate exceeds the service rate. The key ingredient is a calculus of variations analysis of the variational problem associated with atypical reneging. A characterization of the aforementioned decay rate, given explicitly in terms of the arrival and service rate parameters of the model, is provided yielding a precise mathematical description of this paradoxical behavior.

Suggested Citation

  • Rami Atar & Amarjit Budhiraja & Paul Dupuis & Ruoyu Wu, 2022. "Large Deviations for the Single-Server Queue and the Reneging Paradox," Mathematics of Operations Research, INFORMS, vol. 47(1), pages 232-258, February.
    • Handle: RePEc:inm:ormoor:v:47:y:2022:i:1:p:232-258
    DOI: 10.1287/moor.2021.1127
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2021.1127
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2021.1127?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
    ---><---

    References listed on IDEAS

    as
    1. Budhiraja, Amarjit & Chen, Jiang & Dupuis, Paul, 2013. "Large deviations for stochastic partial differential equations driven by a Poisson random measure," Stochastic Processes and their Applications, Elsevier, vol. 123(2), pages 523-560.
    2. Rami Atar & Haya Kaspi & Nahum Shimkin, 2014. "Fluid Limits for Many-Server Systems with Reneging Under a Priority Policy," Mathematics of Operations Research, INFORMS, vol. 39(3), pages 672-696, August.
    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. Chang Feng & John J. Hasenbein & Guodong Pang, 2025. "Sample-path moderate deviation principle for GI/GI/1+GI queues in the nearly critically loaded regime," Queueing Systems: Theory and Applications, Springer, vol. 109(2), pages 1-37, June.
    2. Angelos Aveklouris & Levi DeValve & Maximiliano Stock & Amy Ward, 2025. "Matching Impatient and Heterogeneous Demand and Supply," Operations Research, INFORMS, vol. 73(3), pages 1637-1658, May.

    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. Ma, Xiaocui & Xi, Fubao, 2017. "Moderate deviations for neutral stochastic differential delay equations with jumps," Statistics & Probability Letters, Elsevier, vol. 126(C), pages 97-107.
    2. Rami Atar & Anup Biswas & Haya Kaspi, 2015. "Fluid Limits of G / G /1+ G Queues Under the Nonpreemptive Earliest-Deadline-First Discipline," Mathematics of Operations Research, INFORMS, vol. 40(3), pages 683-702, March.
    3. Zhiheng Zhong & Ping Cao & Junfei Huang & Sean X. Zhou, 2024. "Capacity Allocation and Scheduling in Two-Stage Service Systems with Multiclass Customers," Manufacturing & Service Operations Management, INFORMS, vol. 26(5), pages 1842-1859, September.
    4. Zhenghua Long & Nahum Shimkin & Hailun Zhang & Jiheng Zhang, 2020. "Dynamic Scheduling of Multiclass Many-Server Queues with Abandonment: The Generalized cμ / h Rule," Operations Research, INFORMS, vol. 68(4), pages 1128-1230, July.
    5. Jing Dong & Rouba Ibrahim, 2025. "Shortest-Job-First Scheduling in Many-Server Queues with Impatient Customers and Noisy Service-Time Estimates," Operations Research, INFORMS, vol. 73(6), pages 3139-3155, November.
    6. Atar, Rami & Biswas, Anup & Kaspi, Haya, 2018. "Law of large numbers for the many-server earliest-deadline-first queue," Stochastic Processes and their Applications, Elsevier, vol. 128(7), pages 2270-2296.
    7. Weina Wu & Jianliang Zhai & Jiahui Zhu, 2025. "Large Deviations for Locally Monotone Stochastic Partial Differential Equations Driven by Lévy Noise," Journal of Theoretical Probability, Springer, vol. 38(4), pages 1-33, December.
    8. Antoine Jacquier & Alexandre Pannier, 2020. "Large and moderate deviations for stochastic Volterra systems," Papers 2004.10571, arXiv.org, revised Apr 2022.
    9. Philipp Afèche & Adam Diamant & Joseph Milner, 2014. "Double-Sided Batch Queues with Abandonment: Modeling Crossing Networks," Operations Research, INFORMS, vol. 62(5), pages 1179-1201, October.
    10. Achal Bassamboo & Ramandeep Singh Randhawa, 2016. "Scheduling Homogeneous Impatient Customers," Management Science, INFORMS, vol. 62(7), pages 2129-2147, July.
    11. Zhenghua Long & Jiheng Zhang, 2019. "Virtual allocation policies for many-server queues with abandonment," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 90(3), pages 399-451, December.
    12. Hu, Shulan & Wang, Ran, 2020. "Asymptotics of stochastic Burgers equation with jumps," Statistics & Probability Letters, Elsevier, vol. 162(C).
    13. Huang, Zaitang & Lu, Yumei & Li, Qi & Huang, Yousu, 2025. "Dynamics of fractional stochastic diffusive SIRS epidemic model with Lévy noise," Chaos, Solitons & Fractals, Elsevier, vol. 200(P1).
    14. Samuli Aalto, 2024. "Whittle index approach to multiserver scheduling with impatient customers and DHR service times," Queueing Systems: Theory and Applications, Springer, vol. 107(1), pages 1-30, June.
    15. Maroulas, Vasileios & Pan, Xiaoyang & Xiong, Jie, 2020. "Large deviations for the optimal filter of nonlinear dynamical systems driven by Lévy noise," Stochastic Processes and their Applications, Elsevier, vol. 130(1), pages 203-231.
    16. Zhenghua Long & Hailun Zhang & Jiheng Zhang & Zhe George Zhang, 2024. "The Generalized c / μ Rule for Queues with Heterogeneous Server Pools," Operations Research, INFORMS, vol. 72(6), pages 2488-2506, November.
    17. Anugu, Sumith Reddy & Pang, Guodong, 2024. "Sample path moderate deviations for shot noise processes in the high intensity regime," Stochastic Processes and their Applications, Elsevier, vol. 176(C).
    18. Atar, Rami & Shadmi, Yonatan, 2023. "Fluid limits for earliest-deadline-first networks," Stochastic Processes and their Applications, Elsevier, vol. 157(C), pages 279-307.
    19. Ruinan Li & Ran Wang & Beibei Zhang, 2024. "A Large Deviation Principle for the Stochastic Heat Equation with General Rough Noise," Journal of Theoretical Probability, Springer, vol. 37(1), pages 251-306, March.
    20. Deugoué, G. & Tachim Medjo, T., 2023. "Large deviation for a 3D globally modified Cahn–Hilliard–Navier–Stokes model under random influences," Stochastic Processes and their Applications, Elsevier, vol. 160(C), pages 33-71.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;
    ;

    JEL classification:

    Statistics

    Access and download statistics

    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:inm:ormoor:v:47:y:2022:i:1:p:232-258. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.