RUI: Controlling Complex Networks: Approximate Linear Programming Techniques

这项拨款为开发更快的算法提供资金，用于解决广泛的网络控制问题。 神经动力学编程（NDP）的方法，使用函数逼近和学习。 该方法将控制问题转化为一个非常大的线性规划，然后通过利用其结构消除大部分约束来提高效率。 对这些网络的详细了解，包括流体，布朗和大偏差分析，最优性方程的分析和最优策略的特征，将用于设计近似架构。 将寻求近似，给出一个鲁棒的准确的最优成本的界限，有效的政策将被构造从线性规划与已知的算法相结合的政策。 自适应形式的算法将被调查，包括模拟和学习迭代完善的近似架构。 将进行数值测试，使用半导体制造和电话呼叫中心的例子。 算法的一般行为将在误差界和收敛方面进行研究。嵌入式网络控制为制造过程、供应链、服务操作和计算机网络中的调度问题提供了一个分析框架。 如果成功，该项目将提供一个公共领域的软件工具，扩展可以解决的网络控制问题的规模。 基于对小型网络的测试，对于具有多达大约8个缓冲区的网络，最优成本的严格界限应该是可达到的，而对于较大的网络，最优成本的严格界限应该是较宽松的。 这一工具将有助于在这些领域制定节省费用的业务政策，主要是通过改进启发式政策的设计和基准。 来自数学和计算机科学的本科生将参与这项研究工作。

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.