基于差分灵敏度信息的排队系统性能优化

The performance analysis and optimization method of queueing models usually has the following difficulties in the practical engineering applications. First, for the queueing networks with complicated structure, traditional queueing theory cannot give a closed-form solution for the system performance. Thus, we cannot analyze and optimize the system performance directly based on formulas. Second, because of the constraints of problem structures and parameters, such type of problems usually cannot be modeled as a standard Markov decision process (MDP). Thus, we cannot directly apply the MDP optimization theory to solve these problems. The goal of this proposal is to study some classical control and optimization problems of queueing systems from a new research perspective, i.e., perturbation analysis based on performance difference sensitivity information. The targeted problems include service rate control problem and admission control problem in queueing systems. We plan to propose an effective and efficient optimization method for these problems. We will further study the online implementation of optimization algorithms and the combination with learning algorithms. Our method has the following advantages. Compared with the traditional gradient-based optimization methods, the performance difference can provide more sensitivity information. The optimization method based on difference sensitivity information can efficiently utilize the structural properties of queueing systems. Our method provides a totally new research direction for such type of optimization problems in queueing systems. The research results of this proposal will thrust the application of optimization theory of queueing systems to the practical engineering systems.

在实际工程应用中，基于排队模型的系统性能分析与优化往往存在如下困难：对于结构复杂的排队网络，传统的排队理论无法给出闭合形式的解析解，难以直接进行分析优化；另一方面，由于问题结构和参数的内在约束，这类问题往往无法建模成为标准的马氏决策过程（MDP），使得MDP优化理论无法直接运用。本项目拟从新的研究角度出发，即基于差分灵敏度信息的摄动分析，研究排队系统中的经典控制与优化问题，包括服务率控制问题和准入控制问题等，给出快速有效的优化方法，并研究优化算法的在线化实现及其与学习类算法的结合。该方法的优点在于，相对于传统的梯度优化方法，差分信息能够提供更多的性能灵敏度信息，基于差分灵敏度信息的优化方法能够充分发掘排队系统的结构特点，为解决此类排队系统优化问题提供了一个全新的研究思路。该项目的研究成果将推进排队系统优化理论在实际工程系统中的实施与应用。

排队系统是一类非常重要的随机服务模型，在制造、通信、交通、物流、医疗等工程领域具有广泛应用背景，传统排队理论主要关注排队模型的建立和性能评估，如何进行性能优化是排队理论研究的重点之一。本项目主要研究排队系统中的基于差分灵敏度信息的优化方法，针对排队系统中的经典控制问题，包括服务率控制问题和准入控制问题等，分析优化问题的最优性质，给出快速有效的优化方法。Jackson网络是最复杂的排队模型之一，针对Jackson网络的服务率控制问题，本项目的研究成果证明了当报酬函数相对于服务率为凸函数时，最优服务率取值在边界点上，也即Bang-Bang控制是该问题的最优控制，并给出了快速迭代算法找出最优服务率策略，该结论是目前针对排队系统服务率控制问题的最广泛结论，将文献中Bang-Bang最优控制所要求的线性报酬函数扩展到凸函数。针对Jackson网络的准入控制问题，证明了最优准入控制策略相对于顾客数具有单调性质，并进一步证明了最优策略具有阈值型特点，给出了最优策略的迭代算法。上述两个成果极大简化了原优化问题的复杂度，从指数爆炸的复杂度简化为线性复杂度，从而避免了这类问题的维数灾难题。针对Jackson网络服务率控制的博弈问题，给出了博弈均衡点的性质以及寻找均衡点的迭代算法。研究基于事件的优化理论，给出了基于策略梯度的事件优化方法，研究马氏决策过程的参数化策略优化问题，给出了最优参数策略的优化算法。本项目的研究成果在充分发掘排队系统结构特点的基础上，能够利用差分灵敏度信息为简化排队系统优化问题复杂度提供了一种有效方法，推进了相关优化问题的国际研究新进展，为解决此类排队系统优化问题提供了一个全新的研究思路。