多服务器排队系统中二分匹配的优化设计：帕累托效率与服务奖励

本文是一篇深入探讨二分匹配排队系统优化设计的研究论文，主要关注于多类多服务器排队系统中，如何在有限的服务规则——即FCFS-ALIS（First-Come-First-Served with Alternative Largest Increasing Service）服务策略下，设计出一个在客户类别和服务器之间实现帕累托效率的最优匹配拓扑。研究的核心目标是平衡两个关键性能指标： 1. 最小化客户等待时间：研究者在高流量情况下发现，任何二分匹配系统可以被分解为一组完整的资源池（CRP）子系统，这些子系统通过直接互连的无环图（DAG）进行连接。DAG的结构与CRP组件的总服务能力密切相关，它直接影响了稳态等待时间的分布。特别是，论文指出平均等待时间与CRP组件的数量成比例，且当系统规模增大时，这种比例关系尤为显著。 2. 最大化匹配奖励：由于计算匹配奖励的复杂性，随着客户类别和服务器数量的增长，匹配奖励的精确计算变得难以处理。为此，作者提出了一种二次规划（QP）公式来近似计算匹配奖励，这在实际问题中表现出很高的准确性和效率。实验证明，对于大部分问题实例，QP公式提供的近似奖励与精确值之间的相对误差在98%的情况下小于2%，表明其在求解中的有效性。 3. 混合整数线性程序（MILP）的应用：为了进一步寻找帕累托边界，即在平均等待时间和匹配奖励之间的最优权衡，论文结合了对CRP组件数量和QP近似结果的理解，构建了一个混合整数线性程序模型。这个模型能够帮助决策者找到一系列匹配拓扑，它们共同定义了系统的帕累托效率前沿，使得在服务效率和客户满意度之间找到最佳平衡。 该研究不仅揭示了二分匹配排队系统的基本结构特性，还开发了有效的数学工具来解决实际优化问题，对于理解和优化复杂的多类多服务器排队系统具有重要的理论价值和实践意义。