IDEAS home Printed from https://ideas.repec.org/a/spr/queues/v94y2020i3d10.1007_s11134-020-09649-9.html
   My bibliography  Save this article

Algorithms for the upper bound mean waiting time in the GI/GI/1 queue

Author

Listed:
  • Yan Chen

    (Columbia University)

  • Ward Whitt

    (Columbia University)

Abstract

It has long been conjectured that the tight upper bound for the mean steady-state waiting time in the GI/GI/1 queue given the first two moments of the interarrival-time and service-time distributions is attained asymptotically by two-point distributions. The two-point distribution for the interarrival time has one mass point at 0, but the service-time distribution involves a limit; there is one mass point at a high value, but that upper mass point must increase to infinity while the probability on that point must decrease to 0 appropriately. In this paper, we develop effective numerical and simulation algorithms to compute the value of this conjectured tight bound. The algorithms are aided by reductions of the special queues with extremal interarrival-time and extremal service-time distributions to D/GI/1 and GI/D/1 models. Combining these reductions yields an overall representation in terms of a D/RS(D)/1 discrete-time model involving a geometric random sum of deterministic random variables (the RS(D)), where the two deterministic random variables in the model may have different values, so that the extremal steady-state waiting time need not have a lattice distribution. Efficient computational methods are developed. The computational results show that the conjectured tight upper bound offers a significant improvement over established bounds.

Suggested Citation

  • Yan Chen & Ward Whitt, 2020. "Algorithms for the upper bound mean waiting time in the GI/GI/1 queue," Queueing Systems: Theory and Applications, Springer, vol. 94(3), pages 327-356, April.
    • Handle: RePEc:spr:queues:v:94:y:2020:i:3:d:10.1007_s11134-020-09649-9
    DOI: 10.1007/s11134-020-09649-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11134-020-09649-9
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11134-020-09649-9?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. Ward Whitt, 2005. "Engineering Solution of a Basic Call-Center Model," Management Science, INFORMS, vol. 51(2), pages 221-235, February.
    2. Teunis J. Ott, 1987. "Simple Inequalities for the D / G /1 Queue," Operations Research, INFORMS, vol. 35(4), pages 589-597, August.
    3. K. T. Marshall, 1968. "Some Inequalities in Queuing," Operations Research, INFORMS, vol. 16(3), pages 651-668, June.
    4. Ward Whitt, 1986. "Deciding Which Queue to Join: Some Counterexamples," Operations Research, INFORMS, vol. 34(1), pages 55-62, February.
    5. A. E. Eckberg, 1977. "Sharp Bounds on Laplace-Stieltjes Transforms, with Applications to Various Queueing Problems," Mathematics of Operations Research, INFORMS, vol. 2(2), pages 135-142, May.
    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. Yan Chen & Ward Whitt, 2022. "Applying optimization theory to study extremal GI/GI/1 transient mean waiting times," Queueing Systems: Theory and Applications, Springer, vol. 101(3), pages 197-220, August.
    2. van Eekelen, Wouter, 2023. "Distributionally robust views on queues and related stochastic models," Other publications TiSEM 9b99fc05-9d68-48eb-ae8c-9, Tilburg University, School of Economics and Management.
    3. Wouter van Eekelen & Dick den Hertog & Johan S.H. van Leeuwaarden, 2022. "MAD Dispersion Measure Makes Extremal Queue Analysis Simple," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1681-1692, May.
    4. Filip Lindskog & Mario V. Wuthrich, 2024. "Claims processing and costs under capacity constraints," Papers 2409.09091, arXiv.org.

    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. Yan Chen & Ward Whitt, 2021. "Extremal GI/GI/1 queues given two moments: exploiting Tchebycheff systems," Queueing Systems: Theory and Applications, Springer, vol. 97(1), pages 101-124, February.
    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. Plinio S. Dester & Christine Fricker & Danielle Tibi, 2017. "Stationary analysis of the shortest queue problem," Queueing Systems: Theory and Applications, Springer, vol. 87(3), pages 211-243, December.
    4. Rouba Ibrahim & Ward Whitt, 2011. "Wait-Time Predictors for Customer Service Systems with Time-Varying Demand and Capacity," Operations Research, INFORMS, vol. 59(5), pages 1106-1118, October.
    5. Josh Reed & Yair Shaki, 2015. "A Fair Policy for the G / GI / N Queue with Multiple Server Pools," Mathematics of Operations Research, INFORMS, vol. 40(3), pages 558-595, March.
    6. Parlakturk, Ali & Kumar, Sunil, 2004. "Self-Interested Routing in Queueing Networks," Research Papers 1782r, Stanford University, Graduate School of Business.
    7. 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.
    8. Xi Chen & Dave Worthington, 2017. "Staffing of time-varying queues using a geometric discrete time modelling approach," Annals of Operations Research, Springer, vol. 252(1), pages 63-84, May.
    9. Odysseas Kanavetas & Barış Balcıog̃lu, 2022. "The “Sensitive” Markovian queueing system and its application for a call center problem," Annals of Operations Research, Springer, vol. 317(2), pages 651-664, October.
    10. Legros, Benjamin & Fransoo, Jan C., 2023. "Admission and pricing optimization of on-street parking with delivery bays," Other publications TiSEM 6d41ee5c-27dc-4d34-aff1-4, Tilburg University, School of Economics and Management.
    11. Freeman, Mark C. & Groom, Ben, 2016. "How certain are we about the certainty-equivalent long term social discount rate?," Journal of Environmental Economics and Management, Elsevier, vol. 79(C), pages 152-168.
    12. Yunan Liu & Ward Whitt, 2012. "Stabilizing Customer Abandonment in Many-Server Queues with Time-Varying Arrivals," Operations Research, INFORMS, vol. 60(6), pages 1551-1564, December.
    13. Shenghai Zhou & Yichuan Ding & Woonghee Tim Huh & Guohua Wan, 2021. "Constant Job‐Allowance Policies for Appointment Scheduling: Performance Bounds and Numerical Analysis," Production and Operations Management, Production and Operations Management Society, vol. 30(7), pages 2211-2231, July.
    14. Athanasia Manou & Antonis Economou & Fikri Karaesmen, 2014. "Strategic Customers in a Transportation Station: When Is It Optimal to Wait?," Operations Research, INFORMS, vol. 62(4), pages 910-925, August.
    15. V.D. Dinopoulou & C. Melolidakis, 2001. "Asymptotically optimal component assembly plans in repairable systems and server allocation in parallel multiserver queues," Naval Research Logistics (NRL), John Wiley & Sons, vol. 48(8), pages 732-746, December.
    16. J. E. Reed & Amy R. Ward, 2008. "Approximating the GI/GI/1+GI Queue with a Nonlinear Drift Diffusion: Hazard Rate Scaling in Heavy Traffic," Mathematics of Operations Research, INFORMS, vol. 33(3), pages 606-644, August.
    17. Mor Armony & Erica Plambeck & Sridhar Seshadri, 2009. "Sensitivity of Optimal Capacity to Customer Impatience in an Unobservable M/M/S Queue (Why You Shouldn't Shout at the DMV)," Manufacturing & Service Operations Management, INFORMS, vol. 11(1), pages 19-32, June.
    18. 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.
    19. Opher Baron & Joseph Milner, 2009. "Staffing to Maximize Profit for Call Centers with Alternate Service-Level Agreements," Operations Research, INFORMS, vol. 57(3), pages 685-700, June.
    20. Whitt, Ward, 2012. "Fitting birth-and-death queueing models to data," Statistics & Probability Letters, Elsevier, vol. 82(5), pages 998-1004.

    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:spr:queues:v:94:y:2020:i:3:d:10.1007_s11134-020-09649-9. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.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.