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.

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