排队网络基于性能势的优化理论和并行算法

Many practical stochastic artificial systems，such as high-speed communication networks, flexible manufacturing systems, traffic control systems and quality management systems, can be modeled as queuing networks or Markov processes. Motivated by the needs of optimization and design of these systems, we focus on the study of the optimization theory and optimization algorithms for a class of controlled queuing networks and Markov control processes based on Markov performance potentials. In this project, we give the definition of Markov performance potentials by a generalized Poisson equation. Through the balance equation and generalized Poisson equation, we obtain a performance potentials-based optimality principle, and a performance potentials-based average-cost optimality equation, for continuous time Markov control processes (including queuing networks). Under some weak assumptions, an existence theorem of solutions to the optimality equation for Markov control processes with compact action set is driven. In order to calculate optimal average-cost policies, we propose several algorithms including a gradient-based algorithm, a policy iteration algorithm and a value iteration algorithm. Furthermore, the convergence of the iteration algorithms is established, which shows that the algorithms will stop in a finite number of steps with epsilon-policies. All the results be applied to discrete time Markov control processes and controlled queuing networks, and will provide a uniform and fundamental theory framework for further studying the optimization problems of general Markov control processes, as well as for devising algorithms to compute an optimal policy. An important character of performance potentials is that they are easy to be estimated unbiasedly through a single sample path, which can be obtained by simulating a real system or observing the operation of an actual system. We have discussed some optimization algorithms for Markov control processes and controlled queuing networks based on a single sample path. These simulation-based methods will be applicable for solving the optimization problems of large-scale actual systems whether the information of models are known or partially unknown. Notice that most of the work in optimization processes is the computation related to many matrices and vectors, which can be easily dealt with by parallel methods. Therefore, we have also discussed parallel simulation-based optimization algorithms, so as to save the storage space of a single computer and improve the computing speed.

本项目研究由排队网络模型所描述的一类网络系统的性能优化问题，将排队网络性能势理论和连续时间马尔可夫决策过程相结合，建立基于性能势的优化理论框架，提出一种新的高效并行优化仿真算法。它的优点在于减弱了理论约束条件，加速了寻优收敛过程，具有很强的实用性，能够应用于更广泛的一类实际网络系统的性能测试度优化问题。