IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v43y2018i3p867-886.html
   My bibliography  Save this article

Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics

Author

Listed:
  • Patrick Eschenfeldt

    (Massachusetts Institute of Technology Operations Research Center, Cambridge, Massachusetts, 02139)

  • David Gamarnik

    (Massachusetts Institute of Technology Sloan School of Management and Operations Research Center, Cambridge, Massachusetts 02139)

Abstract

We consider queueing systems with n parallel queues under a Join the Shortest Queue (JSQ) policy in the Halfin-Whitt heavy-traffic regime. We use the martingale method to prove that a scaled process counting the number of idle servers and queues of length exactly two weakly converges to a two-dimensional reflected Ornstein-Uhlenbeck process, while processes counting longer queues converge to a deterministic system decaying to zero in constant time. This limiting system is comparable to that of the traditional Halfin-Whitt model, but there are key differences in the queueing behavior of the JSQ model. In particular, only a vanishing fraction of customers will have to wait, but those who do incur a constant order waiting time.

Suggested Citation

  • Patrick Eschenfeldt & David Gamarnik, 2018. "Join the Shortest Queue with Many Servers. The Heavy-Traffic Asymptotics," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 867-886, August.
    • Handle: RePEc:inm:ormoor:v:43:y:2018:i:3:p:867-886
    DOI: 10.1287/moor.2017.0887
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2017.0887
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2017.0887?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. Shlomo Halfin & Ward Whitt, 1981. "Heavy-Traffic Limits for Queues with Many Exponential Servers," Operations Research, INFORMS, vol. 29(3), pages 567-588, June.
    2. J. G. Dai & Tolga Tezcan, 2011. "State Space Collapse in Many-Server Diffusion Limits of Parallel Server Systems," Mathematics of Operations Research, INFORMS, vol. 36(2), pages 271-320, May.
    3. Tolga Tezcan, 2008. "Optimal Control of Distributed Parallel Server Systems Under the Halfin and Whitt Regime," Mathematics of Operations Research, INFORMS, vol. 33(1), pages 51-90, February.
    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. Danielle Tibi, 2019. "Martingales and buffer overflow for the symmetric shortest queue model," Queueing Systems: Theory and Applications, Springer, vol. 93(1), pages 153-190, October.
    2. Daniela Hurtado-Lange & Siva Theja Maguluri, 2022. "A load balancing system in the many-server heavy-traffic asymptotics," Queueing Systems: Theory and Applications, Springer, vol. 101(3), pages 353-391, August.
    3. Debankur Mukherjee, 2022. "Rates of convergence of the join the shortest queue policy for large-system heavy traffic," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 317-319, April.
    4. Anton Braverman, 2020. "Steady-State Analysis of the Join-the-Shortest-Queue Model in the Halfin–Whitt Regime," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 1069-1103, August.
    5. Varun Gupta & Neil Walton, 2019. "Load Balancing in the Nondegenerate Slowdown Regime," Operations Research, INFORMS, vol. 67(1), pages 281-294, January.
    6. Debankur Mukherjee & Sem C. Borst & Johan S. H. van Leeuwaarden & Philip A. Whiting, 2020. "Asymptotic Optimality of Power-of- d Load Balancing in Large-Scale Systems," Mathematics of Operations Research, INFORMS, vol. 45(4), pages 1535-1571, November.
    7. Rami Atar & David Lipshutz, 2021. "Heavy Traffic Limits for Join-the-Shortest-Estimated-Queue Policy Using Delayed Information," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 268-300, February.

    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. Fiona Sloothaak & James Cruise & Seva Shneer & Maria Vlasiou & Bert Zwart, 2021. "Complete resource pooling of a load-balancing policy for a network of battery swapping stations," Queueing Systems: Theory and Applications, Springer, vol. 99(1), pages 65-120, October.
    2. Zhong, Zhiheng & Cao, Ping, 2023. "Balanced routing with partial information in a distributed parallel many-server queueing system," European Journal of Operational Research, Elsevier, vol. 304(2), pages 618-633.
    3. Leon Cui & Tolga Tezcan, 2016. "Approximations for Chat Service Systems Using Many-Server Diffusion Limits," Mathematics of Operations Research, INFORMS, vol. 41(3), pages 775-807, August.
    4. Jinsheng Chen & Jing Dong & Pengyi Shi, 2020. "A survey on skill-based routing with applications to service operations management," Queueing Systems: Theory and Applications, Springer, vol. 96(1), pages 53-82, October.
    5. Cao, Ping & Zhong, Zhiheng & Huang, Junfei, 2021. "Dynamic routing in a distributed parallel many-server service system: The effect of ξ-choice," European Journal of Operational Research, Elsevier, vol. 294(1), pages 219-235.
    6. Arka Ghosh & Keguo Huang, 2017. "Asymptotically optimal control of N-systems with $$H_2^*$$ H 2 ∗ service times under many-server heavy traffic," Queueing Systems: Theory and Applications, Springer, vol. 86(1), pages 35-60, June.
    7. J. G. Dai & Tolga Tezcan, 2011. "State Space Collapse in Many-Server Diffusion Limits of Parallel Server Systems," Mathematics of Operations Research, INFORMS, vol. 36(2), pages 271-320, May.
    8. Sunil Kumar & Ramandeep S. Randhawa, 2010. "Exploiting Market Size in Service Systems," Manufacturing & Service Operations Management, INFORMS, vol. 12(3), pages 511-526, September.
    9. Avishai Mandelbaum & Petar Momčilović, 2008. "Queues with Many Servers: The Virtual Waiting-Time Process in the QED Regime," Mathematics of Operations Research, INFORMS, vol. 33(3), pages 561-586, August.
    10. Avishai Mandelbaum & Petar Momčilović & Yulia Tseytlin, 2012. "On Fair Routing from Emergency Departments to Hospital Wards: QED Queues with Heterogeneous Servers," Management Science, INFORMS, vol. 58(7), pages 1273-1291, July.
    11. Daniela Hurtado-Lange & Siva Theja Maguluri, 2022. "A load balancing system in the many-server heavy-traffic asymptotics," Queueing Systems: Theory and Applications, Springer, vol. 101(3), pages 353-391, August.
    12. Ragavendran Gopalakrishnan & Sherwin Doroudi & Amy R. Ward & Adam Wierman, 2016. "Routing and Staffing When Servers Are Strategic," Operations Research, INFORMS, vol. 64(4), pages 1033-1050, August.
    13. Anton Braverman, 2020. "Steady-State Analysis of the Join-the-Shortest-Queue Model in the Halfin–Whitt Regime," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 1069-1103, August.
    14. Petar Momčilović & Amir Motaei, 2018. "QED limits for many-server systems under a priority policy," Queueing Systems: Theory and Applications, Springer, vol. 90(1), pages 125-159, October.
    15. 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.
    16. Itay Gurvich & Ward Whitt, 2009. "Queue-and-Idleness-Ratio Controls in Many-Server Service Systems," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 363-396, May.
    17. Rami Atar & Adam Shwartz, 2008. "Efficient Routing in Heavy Traffic Under Partial Sampling of Service Times," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 899-909, November.
    18. Avishai Mandelbaum & Petar Momčilović, 2017. "Personalized queues: the customer view, via a fluid model of serving least-patient first," Queueing Systems: Theory and Applications, Springer, vol. 87(1), pages 23-53, October.
    19. Tolga Tezcan & Banafsheh Behzad, 2012. "Robust Design and Control of Call Centers with Flexible Interactive Voice Response Systems," Manufacturing & Service Operations Management, INFORMS, vol. 14(3), pages 386-401, July.
    20. Amy R. Ward & Mor Armony, 2013. "Blind Fair Routing in Large-Scale Service Systems with Heterogeneous Customers and Servers," Operations Research, INFORMS, vol. 61(1), pages 228-243, February.

    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:43:y:2018:i:3:p:867-886. 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.