基于公平指标的排队系统优化理论及应用

Fairness is an important performance metric of queueing systems and it can be quantified by metrics such as variance. However, the variance or other fairness metrics usually include the high-moment statistics. Since the traditional queueing theory always studies the average metrics which are first-moment statistics, it is difficult to handle the optimization problem with fairness metrics. MDP (Markov decision process) is a fundamental theory for the performance optimization of queueing systems. A standard MDP model requires that the performance function should be linear and additive. However, the fairness metrics, such as variance, are always nonlinear. It makes the Bellman optimality equation does not hold for the variance optimization problem of MDP. The classical optimization method of MDP, such as policy iteration or value iteration, cannot be directly applied to this problem. This proposal aims to use the sensitivity-based optimization theory to study the MDP problem with variance criterion. By combining the structure property of queueing systems, we further study the fairness-based optimization theory of queueing systems. Moreover, we apply the fairness-based optimization theory to study several typical control problems in queueing systems, including the task assignment problem, the service rate control problem, and the admission control problem. We will further develop the online learning algorithms to find the optimal policy for these problems. Fairness-based optimization is a new problem emerging in queueing systems. The research in this proposal is beneficial to build a more complete framework of optimization theory of queueing systems. It has important theoretical significance and application background.

公平性是排队系统的重要性能指标，可用方差等指标来衡量，但由于方差等公平指标涉及高阶统计量，而传统排队论大多研究平均指标等一阶统计量，难以处理基于公平指标的性能分析和优化问题。马氏决策过程（MDP）是排队系统性能优化的理论基础，标准MDP模型要求性能函数线性可加，而方差等公平指标具有非线性因素，Bellman最优性方程在该问题中不成立，无法使用经典MDP优化理论。本项目将利用基于灵敏度信息的优化理论来分析和解决考虑方差准则的MDP优化问题，进一步结合排队系统的结构特点，建立排队系统公平指标的优化理论，并将优化理论应用于解决排队系统中考虑公平因素的任务分配、服务率控制、准入控制等控制优化问题，给出具体的最优策略和优化算法的在线学习与实现。公平优化是排队系统性能优化的新问题，本研究项目能够促进排队系统优化理论体系的完善和发展，具有重要的理论意义和应用价值。

本课题围绕排队系统的服务资源的动态控制与优化问题展开，以公平性作为一个新颖的优化目标，发展考虑公平性指标的排队系统动态优化理论。目前文献中排队理论的相关研究大都集中于各类排队模型的建立与性能分析，将排队系统与动态控制相结合的研究较少，进一步考虑公平性指标的排队系统的动态控制与优化更是研究空白和具有创新性。.本课题的主要研究内容如下。考虑顾客等待时间的方差作为衡量方差的指标，研究基于方差的马氏决策过程(MDP)优化理论，由于方差所具有的非线性和不可加性，导致该动态优化问题不属于标准的马氏决策过程模型，经典动态规划理论无法适用，我们从基于性能灵敏度优化理论出发，发展了MDP方差优化方法，得到了在不考虑均值的情况下，最小化方差的MDP优化方法，并提出了策略迭代类的优化算法，该算法相对于经典梯度优化方法来说，具有更快的收敛速度和收敛性质。进一步研究基于参数化策略的MDP方差最小化优化方法，提出了相关优化理论。继续研究在给定均值约束条件下的方差优化方法，提出了带约束条件的方差最小化的MDP优化方法。将上述理论方法应用于排队系统的资源配置问题，分别研究了MAP/M/1排队系统的服务率优化控制问题、带能量约束条件的串行排队系统服务率优化控制问题、排队网络的定价和服务率控制问题等典型排队系统的动态控制问题。.基于上述研究内容，在控制领域的顶级刊物IEEE Transactions on Automatic Control发表长文3篇，在Automatica发表论文2篇，在DEDS期刊发表论文2篇。并在排队系统的动态优化控制领域取得了较好的国内外影响力，得到了国际著名排队论专家的认可和合作，如美国斯坦福大学P. Glynn教授（美国工程院院士）、美国斯坦福大学N. Bambos教授、加拿大滑铁卢大学的Q. He教授、美国CMU大学M. Harchol-Balter教授等。.上述研究启发了本人在该领域的进一步后续研究，目前已经在排队论的动态控制与经济博弈学相结合、基于数据驱动的学习控制优化理论等领域展开了深入研究，有望继续取得研究成果，并促进了本人与腾讯、华为等公司的应用合作研究项目。