Dynamic Scheduling and Resource Control in Stochastic Processing Networks: Beyond Priority Rules

随机处理网络中的动态调度和资源控制：超越优先级规则

• 批准号: 0969328
• 负责人: David Yao
• 金额: $ 32.5万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-06-01 至 2014-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0969328&HistoricalAwards=false
• 关键词: Dynamic; Scheduling; Resource; Control; Stochastic

The goal of this project is to study resource control that extends beyond the classical priority rules, and to do so in the general setting of stochastic processing networks, allowing features such as concurrent occupancy and sharing of resources. Dynamic allocation of resources to serve different kinds of customers or job classes is a central issue in the design and analysis of many complex systems. The research plan is to investigate the asymptotic behavior of the system under a general class of resource control, which optimizes in each system state a utility function (e.g., a "fairness" measure as in the case of the Internet protocol, also prevalent in many service systems). This will be carried out by deriving the limiting regimes of the main performance processes, such as workloads and congestion levels, under fluid and diffusion scalings. These limits are useful in evaluating the system performance. They also establish the connection between the utility function, which the control maximizes locally (or "greedily") in each state, and the performance objective that is optimized by the control globally over any given planning horizon, finite or infinite.Results from the project are expected to help the design of dynamic resource control rules in stochastic processing networks in two ways: given a control scheme, its performance can be evaluated; and conversely, given a performance objective, one or several control schemes can be identifed to optimize the objective. More broadly, the project will add to the mathematical foundation of stochastic networks, enhance the understanding of the implications of utility- maximizing resource allocation schemes on network performance, and lead to new decision tools and computational techniques for systems design and optimization.

这个项目的目标是研究资源控制，超越了经典的优先级规则，这样做的随机处理网络的一般设置，允许的功能，如并发占用和共享资源。动态分配资源以服务于不同类型的客户或作业类是许多复杂系统设计和分析中的核心问题。该研究计划是研究系统在一般资源控制下的渐近行为，该资源控制在每个系统状态下优化效用函数（例如，如在因特网协议的情况下的“公平性”度量，也在许多服务系统中流行）。这将通过推导出的主要性能过程，如工作量和拥塞水平，根据流体和扩散缩放的限制制度。这些限制在评估系统性能时是有用的。它们还建立了效用函数之间的联系，控制在局部最大化（或“贪婪地”）在每个状态下，以及通过在任何给定的规划范围（有限或无限）内进行全局控制来优化的性能目标。该项目的结果预计将有助于随机处理网络中动态资源控制规则的设计以两种方式：给定一个控制方案，就可以评估其性能;反之，给定一个性能目标，就可以确定一个或几个控制方案来优化该目标。更广泛地说，该项目将增加随机网络的数学基础，增强对效用最大化资源分配方案对网络性能影响的理解，并为系统设计和优化带来新的决策工具和计算技术。