RUI: Controlling Complex Networks: Approximate Linear Programming Techniques

RUI：控制复杂网络：近似线性规划技术

• 批准号: 0620787
• 负责人: Michael Veatch
• 金额: --
• 依托单位: Gordon College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-09-15 至 2010-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0620787&HistoricalAwards=false
• 关键词: RUI; Controlling; Complex; Networks; Approximate

This grant provides funding for the development of dramatically faster algorithms for a broad class of queueing network control problems. A neurodynamic programming (NDP) approach is taken that uses function approximation and learning. The approach converts the control problem to a very large linear program, which is then made efficient by exploiting its structure to eliminate most of the constraints. A detailed understanding of these networks, including results from fluid, Brownian, and large deviation analysis, analysis of the optimality equations, and characteristics of optimal policies, will be used to design the approximation architecture. Approximations will be sought that give a robustly accurate bound on optimal cost; effective policies will be constructed by combining the policy obtained from the linear program with known heuristics. Adaptive forms of the algorithm will be investigated that incorporate simulation and learning to iteratively refine the approximation architecture. Numerical tests will be performed, using examples from semiconductor manufacturing and telephone call centers. The general behavior of the algorithms will be investigated in terms of error bounds and convergence.Queueing network control provides an analytic framework for scheduling issues in manufacturing processes, supply chains, service operations, and computer networks. If successful, this project will provide a public domain software tool that extends the size of network control problems that can be solved. Based on tests with small networks, tight bounds on optimal cost should be attainable for networks with up to roughly eight buffers and looser bounds for larger networks. The tool will facilitate the development of cost-saving operating policies in these fields, primarily by allowing better design and benchmarking of heuristic policies. Undergraduate students from mathematics and computer science will be involved in this research effort.

这笔拨款为开发更快的算法来解决广泛的排队网络控制问题提供了资金。采用神经动态编程(NDP)的方法，使用函数逼近和学习。这种方法将控制问题转化为一个非常大的线性规划，然后通过利用其结构来消除大多数约束来使其高效。对这些网络的详细了解，包括流体分析、布朗分析和大偏差分析的结果，最优性方程的分析，以及最优策略的特征，将用于设计近似体系结构。将寻求给出关于最优成本的稳健准确的界的近似；将从线性规划获得的策略与已知的启发式方法相结合，将构建有效的策略。算法的自适应形式将被研究，它结合了模拟和学习来迭代地改进近似体系结构。将使用半导体制造和电话呼叫中心的例子进行数值测试。排队网络控制为制造过程、供应链、服务运营和计算机网络中的调度问题提供了一个分析框架。如果成功，该项目将提供一个公共领域软件工具，扩大可以解决的网络控制问题的规模。根据对小型网络的测试，对于最多有大约8个缓冲区的网络，应该可以达到最佳成本的严格界限，而对于较大的网络，应该可以达到较宽松的界限。该工具将促进在这些领域制定节约成本的业务政策，主要是通过允许更好地设计和确定启发式政策的基准。来自数学和计算机科学的本科生将参与这项研究工作。