Scaling limits of queueing systems on graphs

图上排队系统的缩放限制

• 批准号: 2308120
• 负责人: Ruoyu Wu
• 金额: $ 18.5万
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-09-01 至 2026-08-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2308120&HistoricalAwards=false
• 关键词: Scaling; limits; queueing; systems; graphs

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.

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