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

Load Balancing Under Strict Compatibility Constraints

Author

Listed:
  • Daan Rutten

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Debankur Mukherjee

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

Abstract

Consider a system with N identical single-server queues and a number of task types, where each server is able to process only a small subset of possible task types. Arriving tasks select d ≥ 2 random compatible servers and join the shortest queue among them. The compatibility constraints are captured by a fixed bipartite graph between the servers and the task types. When the graph is complete bipartite, the mean-field approximation is accurate. However, such dense compatibility graphs are infeasible for large-scale implementation. We characterize a class of sparse compatibility graphs for which the mean-field approximation remains valid. For this, we introduce a novel notion, called proportional sparsity , and establish that systems with proportionally sparse compatibility graphs asymptotically match the performance of a fully flexible system. Furthermore, we show that proportionally sparse random compatibility graphs can be constructed, which reduce the server degree almost by a factor N / ln ( N ) compared with the complete bipartite compatibility graph.

Suggested Citation

  • Daan Rutten & Debankur Mukherjee, 2023. "Load Balancing Under Strict Compatibility Constraints," Mathematics of Operations Research, INFORMS, vol. 48(1), pages 227-256, February.
    • Handle: RePEc:inm:ormoor:v:48:y:2023:i:1:p:227-256
    DOI: 10.1287/moor.2022.1258
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2022.1258
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2022.1258?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. Alexander L. Stolyar, 2017. "Pull-based load distribution among heterogeneous parallel servers: the case of multiple routers," Queueing Systems: Theory and Applications, Springer, vol. 85(1), pages 31-65, February.
    2. Ari Arapostathis & Hassan Hmedi & Guodong Pang, 2021. "On Uniform Exponential Ergodicity of Markovian Multiclass Many-Server Queues in the Halfin–Whitt Regime," Mathematics of Operations Research, INFORMS, vol. 46(2), pages 772-796, May.
    3. James Cruise & Matthieu Jonckheere & Seva Shneer, 2020. "Stability of JSQ in queues with general server-job class compatibilities," Queueing Systems: Theory and Applications, Springer, vol. 95(3), pages 271-279, August.
    4. John N. Tsitsiklis & Kuang Xu, 2017. "Flexible Queueing Architectures," Operations Research, INFORMS, vol. 65(5), pages 1398-1413, October.
    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. Zhisheng Zhao & Debankur Mukherjee, 2026. "Optimal rate-matrix pruning for large-scale heterogeneous systems," Queueing Systems: Theory and Applications, Springer, vol. 110(1), pages 1-45, March.
    2. Ellen Cardinaels & Sem Borst & Johan S. H. van Leeuwaarden, 2024. "Heavy-Traffic Universality of Redundancy Systems with Assignment Constraints," Operations Research, INFORMS, vol. 72(4), pages 1539-1555, July.
    3. Cardinaels, Ellen & Borst, Sem & van Leeuwaarden, Johan S.H., 2024. "Heavy-traffic universality of redundancy systems with assignment constraints," Other publications TiSEM 1ab2791a-b085-466e-8ada-e, Tilburg University, School of Economics and Management.
    4. David Chen & Ruoran Chen & Rowan Wang & Xuan Wang, 2025. "Optimal Control of Service Systems with Heterogeneous Servers and Priority Customers," Management Science, INFORMS, vol. 71(8), pages 6559-6579, August.
    5. Kuang Xu & Yuan Zhong, 2020. "Information and Memory in Dynamic Resource Allocation," Operations Research, INFORMS, vol. 68(6), pages 1698-1715, November.
    6. Hassan Hmedi & Ari Arapostathis & Guodong Pang, 2023. "On System-Wide Safety Staffing of Large-Scale Parallel Server Networks," Operations Research, INFORMS, vol. 71(2), pages 415-432, March.
    7. Xinghu Jin & Guodong Pang & Lihu Xu & Xin Xu, 2025. "An Approximation to the Invariant Measure of the Limiting Diffusion of G / Ph / n + GI Queues in the Halfin–Whitt Regime and Related Asymptotics," Mathematics of Operations Research, INFORMS, vol. 50(2), pages 783-812, May.
    8. Danny Segev, 2025. "Near-Optimal Adaptive Policies for Serving Stochastically Departing Customers," Operations Research, INFORMS, vol. 73(5), pages 2744-2760, September.
    9. 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.
    10. Daan Rutten & Martin Zubeldia & Debankur Mukherjee, 2026. "Distributed Speed Scaling in Large-Scale Service Systems," Operations Research, INFORMS, vol. 74(2), pages 984-1004, March.
    11. Daniel Freund & Thodoris Lykouris & Wentao Weng, 2024. "Efficient Decentralized Multi-agent Learning in Asymmetric Bipartite Queueing Systems," Operations Research, INFORMS, vol. 72(3), pages 1049-1070, 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. Taha Ameen & Flore Sentenac & Sophie H. Yu, 2026. "A uniformity principle for spatial matching," Papers 2601.13426, arXiv.org, revised Feb 2026.
    14. 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.
    15. Ali Aouad & Ömer Sarıtaç, 2022. "Dynamic Stochastic Matching Under Limited Time," Operations Research, INFORMS, vol. 70(4), pages 2349-2383, July.
    16. 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.
    17. 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.
    18. Cong Shi & Yehua Wei & Yuan Zhong, 2019. "Process Flexibility for Multiperiod Production Systems," Operations Research, INFORMS, vol. 67(5), pages 1300-1320, September.
    19. Seva Shneer & Alexander L. Stolyar, 2021. "Large-scale parallel server system with multi-component jobs," Queueing Systems: Theory and Applications, Springer, vol. 98(1), pages 21-48, June.
    20. Diego Goldsztajn & Sem C. Borst & Johan S. H. van Leeuwaarden, 2025. "Learning and Balancing Unknown Loads in Large-Scale Systems," Mathematics of Operations Research, INFORMS, vol. 50(2), pages 1139-1172, May.

    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:48:y:2023:i:1:p:227-256. 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.