Scaling limits of queueing systems on graphs

排队系统网络在应用概率和运筹学中有着广泛的应用，例如在呼叫中心、工厂、商店、办公室、医院、公共交通服务和云计算系统的设计中。这个项目的目标是了解网络对大型交互排队系统性能的影响，无论是在典型情况下，还是在罕见和意外的情况下，都会产生显著的后果。这项研究将有助于系统管理者设计排队网络和排队策略，从而提高系统的效率和稳定性。该项目还将为相互作用的排队网络问题开发新的数学方法，其结果将有助于研究排队系统以外的领域，如社会科学和流行病学。本研究项目包括本科生、研究生和博士后研究人员，主要研究随机图上大规模负载均衡排队系统的渐近行为，包括加入最短队列、加入空闲队列和d的幂策略。将考虑三类图：经典完全图、具有齐次极限的随机图和异类随机图。研究的目的是通过获得各种尺度极限，包括大数定律、中心极限定理、长期稳定性、大偏差原理和中偏差原理，并分析相关的稀有事件概率数值估计的加速蒙特卡罗格式，来严格理解随机网络对系统性能的关键和具有挑战性的影响，特别是与经典完全图设置的显著偏差。对典型渐近行为的研究将需要弱相互作用粒子系统理论和随机图形/图形理论的工具组合。获得大偏差和中偏差原则的主要挑战来自无限维动力学、零转换率和不连续统计的系统特征。除了使用经典的大偏差方法和弱收敛方法外，研究非典型渐近行为还需要开发新的技术，涉及来自随机分析和微分方程式的工具的组合。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Networks of queueing systems have broad applications in applied probability and operations research, such as in the design of call centers, factories, shops, offices, hospitals, public transportation services, and cloud computing systems. The goal of this project is to understand the impact of the network on the performance of large interacting queueing systems, in both typical scenarios and rare and unexpected scenarios with significant consequences. This research will help system managers design the queueing network and queueing policies, which will lead to better system efficiency and stability. The project will also develop new mathematical techniques for problems of networks of interacting queues, and the results will be beneficial to the study of areas beyond queueing systems, such as social science and epidemiology. This research project includes training undergraduate students, graduate students, and postdoctoral researchers.This project focuses mainly on the analysis of asymptotic behavior of large-scale load balancing queueing systems on random graphs, including join-the-shortest-queue, join-the-idle-queue and power-of-d policies. Three classes of graphs will be considered: classic complete graphs, random graphs with homogeneous limits, and heterogeneous random graphs. The research objectives are to rigorously understand the crucial and challenging impacts of stochastic networks on the system performance, in particular the significant deviation from the classic complete graph setup, via obtaining various scaling limits, including laws of large numbers, central limit theorems, long-time stability, large deviation principles and moderate deviation principles, together with analyzing the associated accelerated Monte-Carlo schemes of numerical estimation of rare event probabilities. The study of typical asymptotic behaviors will require a combination of tools from the theory of weakly interacting particle systems and random graph/graphon theory. The main challenges of obtaining large and moderate deviation principles arise from system features of infinite dimensional dynamics, vanishing transition rates, and discontinuous statistics. Besides using classic large deviation approaches and weak convergence approaches, the study of atypical asymptotic behaviors will also require the development of new techniques, involving a combination of tools from stochastic analysis and differential equations.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.