IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v67y2019i1p281-294.html
   My bibliography  Save this article

Load Balancing in the Nondegenerate Slowdown Regime

Author

Listed:
  • Varun Gupta

    (Booth School of Business, University of Chicago, Chicago, Illinois 60637)

  • Neil Walton

    (Alan Turing Building, University of Manchester, Manchester M13 9PL, United Kingdom)

Abstract

We analyze join-the-shortest-queue (JSQ) in a contemporary scaling regime known as the nondegenerate slowdown (NDS) regime. Join-the-shortest-queue is a classical load-balancing policy for queueing systems with multiple parallel servers. Parallel server queueing systems are regularly analyzed and dimensioned by diffusion approximations achieved in the Halfin–Whitt scaling regime. However, when jobs must be dispatched to a server upon arrival, we advocate the nondegenerate slowdown regime to compare different load-balancing rules. In this paper we identify novel diffusion approximation and timescale separation that provides insights into the performance of JSQ. We calculate the price of irrevocably dispatching jobs to servers and prove this to be within 15% (in the NDS regime) of the rules that may maneuver jobs between servers. We also compare our results for the JSQ policy with the NDS approximations of many modern load-balancing policies such as idle-queue-first and power-of-d-choices policies that act as low information proxies for the JSQ policy. Our analysis leads us to construct new rules that have identical performance to JSQ but require less communication overhead than power of two choices.

Suggested Citation

  • Varun Gupta & Neil Walton, 2019. "Load Balancing in the Nondegenerate Slowdown Regime," Operations Research, INFORMS, vol. 67(1), pages 281-294, January.
    • Handle: RePEc:inm:oropre:v:67:y:2019:i:1:p:281-294
    DOI: 10.1287/opre.2018.1768
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/opre.2018.1768
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2018.1768?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. Rami Atar, 2012. "A Diffusion Regime with Nondegenerate Slowdown," Operations Research, INFORMS, vol. 60(2), pages 490-500, April.
    2. Hunt, P. J. & Kurtz, T. G., 1994. "Large loss networks," Stochastic Processes and their Applications, Elsevier, vol. 53(2), pages 363-378, October.
    3. 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.
    4. Ward Whitt, 2003. "How Multiserver Queues Scale with Growing Congestion-Dependent Demand," Operations Research, INFORMS, vol. 51(4), pages 531-542, August.
    5. Shlomo Halfin & Ward Whitt, 1981. "Heavy-Traffic Limits for Queues with Many Exponential Servers," Operations Research, INFORMS, vol. 29(3), pages 567-588, June.
    6. Lawrence Brown & Noah Gans & Avishai Mandelbaum & Anat Sakov & Haipeng Shen & Sergey Zeltyn & Linda Zhao, 2005. "Statistical Analysis of a Telephone Call Center: A Queueing-Science Perspective," Journal of the American Statistical Association, American Statistical Association, vol. 100, pages 36-50, March.
    7. Sem Borst & Avi Mandelbaum & Martin I. Reiman, 2004. "Dimensioning Large Call Centers," Operations Research, INFORMS, vol. 52(1), pages 17-34, 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. Sem Borst, 2022. "Load balancing in large-scale heterogeneous systems," Queueing Systems: Theory and Applications, Springer, vol. 100(3), pages 397-399, April.
    2. Jonatha Anselmi & Francois Dufour, 2020. "Power-of- d -Choices with Memory: Fluid Limit and Optimality," Mathematics of Operations Research, INFORMS, vol. 45(3), pages 862-888, August.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.

    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. Shuangchi He, 2020. "Diffusion Approximation for Efficiency-Driven Queues When Customers Are Patient," Operations Research, INFORMS, vol. 68(4), pages 1265-1284, July.
    2. Jayakrishnan Nair & Adam Wierman & Bert Zwart, 2016. "Provisioning of Large-Scale Systems: The Interplay Between Network Effects and Strategic Behavior in the User Base," Management Science, INFORMS, vol. 62(6), pages 1830-1841, June.
    3. 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.
    4. Rouba Ibrahim & Mor Armony & Achal Bassamboo, 2017. "Does the Past Predict the Future? The Case of Delay Announcements in Service Systems," Management Science, INFORMS, vol. 63(6), pages 1762-1780, June.
    5. Achal Bassamboo & Assaf Zeevi, 2009. "On a Data-Driven Method for Staffing Large Call Centers," Operations Research, INFORMS, vol. 57(3), pages 714-726, June.
    6. Ramandeep S. Randhawa & Sunil Kumar, 2008. "Usage Restriction and Subscription Services: Operational Benefits with Rational Users," Manufacturing & Service Operations Management, INFORMS, vol. 10(3), pages 429-447, December.
    7. Li Xiao & Susan H. Xu & David D. Yao & Hanqin Zhang, 2022. "Optimal staffing for ticket queues," Queueing Systems: Theory and Applications, Springer, vol. 102(1), pages 309-351, October.
    8. Mor Armony & Constantinos Maglaras, 2004. "On Customer Contact Centers with a Call-Back Option: Customer Decisions, Routing Rules, and System Design," Operations Research, INFORMS, vol. 52(2), pages 271-292, April.
    9. Costis Maglaras & John Yao & Assaf Zeevi, 2018. "Optimal Price and Delay Differentiation in Large-Scale Queueing Systems," Management Science, INFORMS, vol. 64(5), pages 2427-2444, May.
    10. Sunil Kumar & Ramandeep S. Randhawa, 2010. "Exploiting Market Size in Service Systems," Manufacturing & Service Operations Management, INFORMS, vol. 12(3), pages 511-526, September.
    11. 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.
    12. 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.
    13. Itai Gurvich & Junfei Huang & Avishai Mandelbaum, 2014. "Excursion-Based Universal Approximations for the Erlang-A Queue in Steady-State," Mathematics of Operations Research, INFORMS, vol. 39(2), pages 325-373, May.
    14. Jing Dong & Rouba Ibrahimb, 2020. "Managing Supply in the On-Demand Economy: Flexible Workers, Full-Time Employees, or Both?," Operations Research, INFORMS, vol. 68(4), pages 1238-1264, July.
    15. Constantinos Maglaras & Assaf Zeevi, 2004. "Diffusion Approximations for a Multiclass Markovian Service System with “Guaranteed” and “Best-Effort” Service Levels," Mathematics of Operations Research, INFORMS, vol. 29(4), pages 786-813, November.
    16. Tolga Tezcan & J. G. Dai, 2010. "Dynamic Control of N -Systems with Many Servers: Asymptotic Optimality of a Static Priority Policy in Heavy Traffic," Operations Research, INFORMS, vol. 58(1), pages 94-110, February.
    17. Eugene Furman & Adam Diamant & Murat Kristal, 2021. "Customer Acquisition and Retention: A Fluid Approach for Staffing," Production and Operations Management, Production and Operations Management Society, vol. 30(11), pages 4236-4257, November.
    18. 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.
    19. 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.
    20. Hassan Hmedi & Ari Arapostathis & Guodong Pang, 2022. "Uniform stability of some large-scale parallel server networks," Queueing Systems: Theory and Applications, Springer, vol. 102(3), pages 509-552, December.

    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:oropre:v:67:y:2019:i:1:p:281-294. 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.