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

Asymptotic Optimality of Balanced Routing

Author

Listed:
  • Hong Chen

    (Shanghai Advanced Institute of Finance, Shanghai Jiaotong University, Shanghai, China)

  • Heng-Qing Ye

    (Faculty of Business, Hong Kong Polytechnic University, Hung Hom, Hong Kong)

Abstract

Consider a system with K parallel servers, each with its own waiting room. Upon arrival, a job is routed to the queue of one of the servers. Finding a routing policy that minimizes the total workload in the system is a known difficult problem in general. Even if the optimal policy is identified, the policy would require the full queue length information at the arrival of each job; for example, the join-the-shortest-queue policy (which is known to be optimal for identical servers with exponentially distributed service times) would require comparing the queue lengths of all the servers. In this paper, we consider a balanced routing policy that examines only a subset of c servers, with 1 (le) c (le) K : specifically, upon the arrival of a job, choose a subset of c servers with a probability proportional to their service rates, and then route the job to the one with the shortest queue among the c chosen servers. Under such a balanced policy, we derive the diffusion limits of the queue length processes and the workload processes. We note that the diffusion limits are the same for these processes regardless the choice of c , as long as c (ge) 2. We further show that the proposed balanced routing policy for any fixed c (ge) 2 is asymptotically optimal in the sense that it minimizes the workload over all time in the diffusion limit. In addition, the policy helps to distribute work among all the servers evenly.

Suggested Citation

  • Hong Chen & Heng-Qing Ye, 2012. "Asymptotic Optimality of Balanced Routing," Operations Research, INFORMS, vol. 60(1), pages 163-179, February.
    • Handle: RePEc:inm:oropre:v:60:y:2012:i:1:p:163-179
    DOI: 10.1287/opre.1110.0998
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1110.0998
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1110.0998?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. Ward Whitt, 1980. "Some Useful Functions for Functional Limit Theorems," Mathematics of Operations Research, INFORMS, vol. 5(1), pages 67-85, February.
    2. Avishai Mandelbaum & Alexander L. Stolyar, 2004. "Scheduling Flexible Servers with Convex Delay Costs: Heavy-Traffic Optimality of the Generalized cμ-Rule," Operations Research, INFORMS, vol. 52(6), pages 836-855, December.
    3. Bruce Hajek, 1985. "Extremal Splittings of Point Processes," Mathematics of Operations Research, INFORMS, vol. 10(4), pages 543-556, November.
    4. Heng-Qing Ye & David D. Yao, 2008. "Heavy-Traffic Optimality of a Stochastic Network Under Utility-Maximizing Resource Allocation," Operations Research, INFORMS, vol. 56(2), pages 453-470, April.
    5. Ward Whitt, 1986. "Deciding Which Queue to Join: Some Counterexamples," Operations Research, INFORMS, vol. 34(1), pages 55-62, 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. Jazeem Abdul Jaleel & Sherwin Doroudi & Kristen Gardner & Alexander Wickeham, 2022. "A general “power-of-d” dispatching framework for heterogeneous systems," Queueing Systems: Theory and Applications, Springer, vol. 102(3), pages 431-480, December.
    2. Rami Atar & Isaac Keslassy & Gal Mendelson, 2019. "Replicate to the shortest queues," Queueing Systems: Theory and Applications, Springer, vol. 92(1), pages 1-23, June.
    3. 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.
    4. Chihoon Lee & Amy R. Ward & Heng-Qing Ye, 2021. "Stationary distribution convergence of the offered waiting processes in heavy traffic under general patience time scaling," Queueing Systems: Theory and Applications, Springer, vol. 99(3), pages 283-303, December.
    5. Rami Atar & Isaac Keslassy & Gal Mendelson, 2019. "Subdiffusive Load Balancing in Time-Varying Queueing Systems," Operations Research, INFORMS, vol. 67(6), pages 1678-1698, November.
    6. Dinard van der Laan, 2015. "Assigning Multiple Job Types to Parallel Specialized Servers," Tinbergen Institute Discussion Papers 15-102/III, Tinbergen Institute.
    7. 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.
    8. Cardinaels, Ellen & Borst, Sem & van Leeuwaarden, Johan S.H., 2022. "Heavy-traffic universality of redundancy systems with assignment constraints," Other publications TiSEM 1ab2791a-b085-466e-8ada-e, Tilburg University, School of Economics and Management.
    9. 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.
    10. Chihoon Lee & Amy R. Ward & Heng-Qing Ye, 2020. "Stationary distribution convergence of the offered waiting processes for $$GI/GI/1+GI$$GI/GI/1+GI queues in heavy traffic," Queueing Systems: Theory and Applications, Springer, vol. 94(1), pages 147-173, 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. Wanyang Dai, 2013. "Optimal Rate Scheduling via Utility-Maximization for J -User MIMO Markov Fading Wireless Channels with Cooperation," Operations Research, INFORMS, vol. 61(6), pages 1450-1462, December.
    2. Erhun Özkan & Amy R. Ward, 2019. "On the Control of Fork-Join Networks," Mathematics of Operations Research, INFORMS, vol. 44(2), pages 532-564, 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.
    4. 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.
    5. Heng-Qing Ye & David D. Yao, 2016. "Diffusion Limit of Fair Resource Control—Stationarity and Interchange of Limits," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1161-1207, November.
    6. P S Ansell & K D Glazebrook & C Kirkbride, 2003. "Generalised ‘join the shortest queue’ policies for the dynamic routing of jobs to multi-class queues," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(4), pages 379-389, April.
    7. Heng-Qing Ye & David D. Yao, 2012. "A Stochastic Network Under Proportional Fair Resource Control---Diffusion Limit with Multiple Bottlenecks," Operations Research, INFORMS, vol. 60(3), pages 716-738, June.
    8. Heng-Qing Ye & David D. Yao, 2010. "Utility-Maximizing Resource Control: Diffusion Limit and Asymptotic Optimality for a Two-Bottleneck Model," Operations Research, INFORMS, vol. 58(3), pages 613-623, June.
    9. Stilian A. Stoev & Murad S. Taqqu, 2007. "Limit Theorems for Sums of Heavy-tailed Variables with Random Dependent Weights," Methodology and Computing in Applied Probability, Springer, vol. 9(1), pages 55-87, March.
    10. 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.
    11. Achal Bassamboo & J. Michael Harrison & Assaf Zeevi, 2006. "Design and Control of a Large Call Center: Asymptotic Analysis of an LP-Based Method," Operations Research, INFORMS, vol. 54(3), pages 419-435, June.
    12. Furrer, Hansjorg & Michna, Zbigniew & Weron, Aleksander, 1997. "Stable Lévy motion approximation in collective risk theory," Insurance: Mathematics and Economics, Elsevier, vol. 20(2), pages 97-114, September.
    13. 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.
    14. Anatolii A. Puhalskii, 2003. "On Large Deviation Convergence of Invariant Measures," Journal of Theoretical Probability, Springer, vol. 16(3), pages 689-724, July.
    15. 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.
    16. Parlakturk, Ali & Kumar, Sunil, 2004. "Self-Interested Routing in Queueing Networks," Research Papers 1782r, Stanford University, Graduate School of Business.
    17. Saulius Minkevičius & Igor Katin & Joana Katina & Irina Vinogradova-Zinkevič, 2021. "On Little’s Formula in Multiphase Queues," Mathematics, MDPI, vol. 9(18), pages 1-15, September.
    18. Doruk Cetemen & Can Urgun & Leeat Yariv, 2023. "Collective Progress: Dynamics of Exit Waves," Journal of Political Economy, University of Chicago Press, vol. 131(9), pages 2402-2450.
    19. Zhang, Tonglin, 2024. "Variables selection using L0 penalty," Computational Statistics & Data Analysis, Elsevier, vol. 190(C).
    20. Rami Atar & Subhamay Saha, 2017. "Optimality of the generalized $$\varvec{c\mu }$$ c μ rule in the moderate deviation regime," Queueing Systems: Theory and Applications, Springer, vol. 87(1), pages 113-130, October.

    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:60:y:2012:i:1:p:163-179. 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.