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.