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

Heavy-Traffic Analysis of Queueing Systems with No Complete Resource Pooling

Author

Listed:
  • Daniela Andrea Hurtado Lange

    (The College of William and Mary, Williamsburg, Virginia 23187)

  • Siva Theja Maguluri

    (Georgia Institute of Technology, Atlanta, Georgia 30332)

Abstract

We study the heavy-traffic limit of the generalized switch operating under MaxWeight, without assuming that the complete resource pooling condition is satisfied and allowing for correlated arrivals. The main contribution of this paper is the steady-state mean of linear combinations of queue lengths in heavy traffic. We showcase the generality of our result by presenting various stochastic networks as corollaries, each of which is a contribution by itself. In particular, we study the input-queued switch with correlated arrivals, and we show that, if the state space collapses to a full-dimensional subspace, the correlation among the arrival processes does not matter in heavy traffic. We exemplify this last case with a parallel-server system, an N -system, and an ad hoc wireless network. Whereas these results are obtained using the drift method, we additionally present a negative result showing a limitation of the drift method. We show that it is not possible to obtain the individual queue lengths using the drift method with polynomial test functions. We do this by presenting an alternate view of the drift method in terms of a system of linear equations, and we use this system of equations to obtain bounds on arbitrary linear combinations of the queue lengths.

Suggested Citation

  • Daniela Andrea Hurtado Lange & Siva Theja Maguluri, 2022. "Heavy-Traffic Analysis of Queueing Systems with No Complete Resource Pooling," Mathematics of Operations Research, INFORMS, vol. 47(4), pages 3129-3155, November.
    • Handle: RePEc:inm:ormoor:v:47:y:2022:i:4:p:3129-3155
    DOI: 10.1287/moor.2021.1248
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2021.1248
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2021.1248?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. Samim Ghamami & Amy R. Ward, 2013. "Dynamic Scheduling of a Two-Server Parallel Server System with Complete Resource Pooling and Reneging in Heavy Traffic: Asymptotic Optimality of a Two-Threshold Policy," Mathematics of Operations Research, INFORMS, vol. 38(4), pages 761-824, November.
    2. Weina Wang & Siva Theja Maguluri & R. Srikant & Lei Ying, 2022. "Heavy-Traffic Insensitive Bounds for Weighted Proportionally Fair Bandwidth Sharing Policies," Mathematics of Operations Research, INFORMS, vol. 47(4), pages 2691-2720, November.
    3. Cong Shi & Yehua Wei & Yuan Zhong, 2019. "Process Flexibility for Multiperiod Production Systems," Operations Research, INFORMS, vol. 67(5), pages 1300-1320, September.
    4. Siva Theja Maguluri & Sai Kiran Burle & R. Srikant, 2018. "Optimal heavy-traffic queue length scaling in an incompletely saturated switch," Queueing Systems: Theory and Applications, Springer, vol. 88(3), pages 279-309, April.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. Maria Vlasiou & Jiheng Zhang & Bert Zwart, 2026. "Insensitivity of proportional fairness in critically loaded bandwidth sharing networks," Queueing Systems: Theory and Applications, Springer, vol. 110(1), pages 1-39, March.
    3. Jiashuo Jiang & Shixin Wang & Jiawei Zhang, 2023. "Achieving High Individual Service Levels Without Safety Stock? Optimal Rationing Policy of Pooled Resources," Operations Research, INFORMS, vol. 71(1), pages 358-377, January.
    4. Haiyue Yu & Ting Shen & Liwei Zhong, 2024. "Optimizing hospital bed allocation for coordinated medical efficiency and quality improvement," Journal of Combinatorial Optimization, Springer, vol. 48(4), pages 1-20, November.
    5. Heng-Li Liu & Quan-Lin Li, 2023. "Matched Queues with Flexible and Impatient Customers," Methodology and Computing in Applied Probability, Springer, vol. 25(1), pages 1-26, March.
    6. Baris Ata & Mustafa H. Tongarlak & Deishin Lee & Joy Field, 2024. "A Dynamic Model for Managing Volunteer Engagement," Operations Research, INFORMS, vol. 72(5), pages 1958-1975, September.
    7. Rujeerapaiboon, Napat & Zhong, Yuanguang & Zhu, Dan, 2023. "Resilience of long chain under disruption," European Journal of Operational Research, Elsevier, vol. 309(2), pages 597-615.
    8. Dongyuan Zhan & Gideon Weiss, 2018. "Many-server scaling of the N-system under FCFS–ALIS," Queueing Systems: Theory and Applications, Springer, vol. 88(1), pages 27-71, February.
    9. Adan, Ivo J.B.F. & Boon, Marko A.A. & Weiss, Gideon, 2019. "Design heuristic for parallel many server systems," European Journal of Operational Research, Elsevier, vol. 273(1), pages 259-277.
    10. Rami Atar & Anat Lev-Ari, 2018. "Workload-Dependent Dynamic Priority for the Multiclass Queue with Reneging," Mathematics of Operations Research, INFORMS, vol. 43(2), pages 494-515, May.
    11. René Caldentey & Lisa Aoki Hillas & Varun Gupta, 2025. "Designing Service Menus for Bipartite Queueing Systems," Operations Research, INFORMS, vol. 73(3), pages 1496-1534, May.
    12. Philipp Afèche & René Caldentey & Varun Gupta, 2022. "On the Optimal Design of a Bipartite Matching Queueing System," Operations Research, INFORMS, vol. 70(1), pages 363-401, January.
    13. Arash Asadpour & Xuan Wang & Jiawei Zhang, 2020. "Online Resource Allocation with Limited Flexibility," Management Science, INFORMS, vol. 66(2), pages 642-666, February.
    14. Perraudat, Antoine & Dauzère-Pérès, Stéphane & Vialletelle, Philippe, 2022. "Robust tactical qualification decisions in flexible manufacturing systems," Omega, Elsevier, vol. 106(C).
    15. Yifan Feng & René Caldentey & Linwei Xin & Yuan Zhong & Bing Wang & Haoyuan Hu, 2024. "Designing Sparse Graphs for Stochastic Matching with an Application to Middle-Mile Transportation Management," Management Science, INFORMS, vol. 70(12), pages 8988-9013, December.
    16. Yash Kanoria & Pengyu Qian, 2024. "Blind Dynamic Resource Allocation in Closed Networks via Mirror Backpressure," Management Science, INFORMS, vol. 70(8), pages 5445-5462, August.
    17. David A. Goldberg & Martin I. Reiman & Qiong Wang, 2021. "A Survey of Recent Progress in the Asymptotic Analysis of Inventory Systems," Production and Operations Management, Production and Operations Management Society, vol. 30(6), pages 1718-1750, June.
    18. Zhen Xu & Hailun Zhang & Jiheng Zhang & Rachel Q. Zhang, 2020. "Online Demand Fulfillment Under Limited Flexibility," Management Science, INFORMS, vol. 66(10), pages 4667-4685, October.
    19. Brett Alan Hathaway & Seyed Morteza Emadi & Vinayak Deshpande, 2022. "Personalized Priority Policies in Call Centers Using Past Customer Interaction Information," Management Science, INFORMS, vol. 68(4), pages 2806-2823, April.
    20. Yuval Nov & Gideon Weiss & Hanqin Zhang, 2022. "Fluid Models of Parallel Service Systems Under FCFS," Operations Research, INFORMS, vol. 70(2), pages 1182-1218, March.

    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:4:p:3129-3155. 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.