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.
