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.

排队系统的网络在应用概率和操作研究中具有广泛的应用，例如在呼叫中心，工厂，商店，办公室，医院，公共交通服务和云计算系统的设计中。该项目的目的是了解网络对大型交互排队系统性能的影响，无论是在典型的情况下以及罕见和意外情况下带来的重大后果。这项研究将帮助系统经理设计排队网络和排队政策，这将提高系统效率和稳定性。该项目还将开发针对互动队列网络问题的新数学技术，结果将有助于研究排队系统（例如社会科学和流行病学）的领域。 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.将考虑三类图：经典完整图，具有均匀限制的随机图和异质随机图。 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.对典型渐近行为的研究将需要从弱相互作用的粒子系统和随机图/图形理论理论中结合使用工具。获得大型和中等偏差原理的主要挑战是由无限尺寸动态，消失的过渡速率和不连续统计的系统特征引起的。除了采用经典的大偏差方法和弱收敛方法外，对非典型渐近行为的研究还将需要开发新技术，涉及从随机分析和差分方程的工具组合。该奖项反映了NSF的法定任务，并认为通过基金会的知识优点和广泛的criteria crietia crietia crietia crietia crietia crietia criteria criperia criperia crietia crietia criteria criteria criperia均值得通过评估。