RUI: Analysis and Control of Infinite Dimensional Queueing Models

RUI：无限维排队模型的分析与控制

• 批准号: 1510198
• 负责人: Amber Puha
• 金额: $ 18万
• 依托单位: California State University San Marcos Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-15 至 2019-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1510198&HistoricalAwards=false
• 关键词: RUI; Analysis; Control; Infinite; Dimensional

This project entails investigating some mathematical questions that emerge in the behavioral analysis of certain queueing models. Queueing models are probabilistic models that capture the inherent randomness in a variety of modern networks, such as those that arise in customer service systems, computing and telecommunications, as well as transportation and hi-tech manufacturing. The network structure is typically deterministic and the scheduling policy is usually specified. Randomness results from exogenous arrival times, service times, and internal routing. Feedback and non-head-of-the-line (HL) scheduling policies are common in such networks. These local dynamics interact to produce aggregate behavior that is complex and often evades closed form analysis. Hence, tractable approximations are needed. The project involves specifying and validating various model approximations, analyzing their performance and/or optimal control and interpreting those results for the original system.More specifically, this project concerns the study of three queueing models with distinct features presenting unique mathematical challenges as follows:(1) to develop a diffusion approximation for networks of processor sharing queues, under general distributional assumptions in the presence of feedback;(2) to employ nonstandard, distribution dependent scaling to obtain a diffusion approximation for shortest remaining processing time queues;(3) to obtain asymptotically optimal scheduling policies for multiclass queues with abandonment under general distributional assumptions through the study of fluid control problems.Each model has been analyzed in various forms that include some Markovian distributional assumptions (i.e., exponentially distributed interarrival, service, and/or abandonment times). Such assumptions aren't particularly realistic for modeling the behavior of modern applications. Furthermore, the performance can be dramatically different for such systems in the presence of non-Markovian distributional assumptions. Therefore, system performance needs to be understood more fully. From a mathematical point of view, general distributional assumptions result in the need to track significantly more information in order to track the system state. For example, residual service times or residual abandonment times for each job in the system must be tracked in some form. This naturally leads to an infinite dimensional system where measure-valued state descriptors provide an effective tool for tracking the system state. In spite of employing this common modeling tool, the nature of the mathematical challenges are distinct for each model due to the distinct system dynamics. For processor sharing networks, a new strategy for analyzing the long time behavior of fluid model solutions will be developed. We anticipate that this methodology will translate to other systems where time-sharing is present. For shortest remaining processing time queues, nonstandard distribution dependent scaling is required to account for the order of magnitude difference between the queue length and workload processes in heavy traffic. Such behavior has not been observed for other scheduling policies. For the control of multiclass queues, new frameworks need to be developed to provide an analysis of the fluid control problem for generally distributed abandonment times. Such advances should further help in the analysis of a diffusion control problem.

这个项目需要调查一些数学问题，出现在行为分析的某些行为模型。 随机模型是一种概率模型，它捕捉了各种现代网络中固有的随机性，例如在客户服务系统、计算和电信以及运输和高科技制造中出现的网络。 网络结构通常是确定性的，调度策略通常是指定的。 随机性是由外部的到达时间、服务时间和内部路由决定的。 反馈和非头的线（HL）调度策略是常见的，在这样的网络。 这些局部动态相互作用，产生复杂的聚合行为，往往逃避封闭形式的分析。 因此，需要易于处理的近似。 该项目涉及指定和验证各种模型近似，分析它们的性能和/或最优控制，并解释原始系统的这些结果。更具体地说，该项目涉及研究具有不同特征的三个排队模型，这些模型提出了独特的数学挑战，如下：（1）在存在反馈的一般分布假设下，开发处理器共享队列网络的扩散近似;（2）采用非标准的、分布相关的缩放来获得最短剩余处理时间队列的扩散近似;（三）通过对流体控制问题的研究，得到了在一般分布假设下具有放弃的多类排队系统的渐近最优调度策略。一些马尔可夫分布假设（即，指数分布的到达间隔、服务和/或放弃时间）。这样的假设对于现代应用程序的行为建模并不特别现实。 此外，在非马尔可夫分布假设的存在下，这种系统的性能可能会显着不同。因此，需要更全面地了解系统性能。从数学的角度来看，一般的分布假设导致需要跟踪更多的信息，以跟踪系统状态。例如，必须以某种形式跟踪系统中每个作业的剩余服务时间或剩余废弃时间。这自然会导致一个无限维的系统，测量值的状态描述符提供了一个有效的工具，用于跟踪系统的状态。尽管采用这种常见的建模工具，由于不同的系统动态特性，每个模型的数学挑战的性质是不同的。对于处理器共享网络，将开发一种分析流体模型解的长时间行为的新策略。我们预计，这种方法将转化为其他系统的分时。对于剩余处理时间最短的队列，非标准分布相关的缩放需要考虑到在繁忙的交通量的队列长度和工作量之间的数量级差异。其他调度策略尚未观察到此类行为。对于多类队列的控制，需要开发新的框架，以提供一般分布的放弃时间的流体控制问题的分析。这些进展应进一步有助于扩散控制问题的分析。