结合Benders分解和列生成方法进行多队列服务器分配与调度

《Omega ω》：Combining benders decomposition and column generation for server allocation and scheduling in multiple queues

本文研究多队列场景下移动服务器的动态分配与调度问题，提出非线性混合整数模型及基于Benders分解与列生成算法的优化方法，在景点和机场实测数据中验证，显著降低服务器工作时间并控制排队长度，比传统方法效率提升14.13%。

　　

王成凯|刘然|潘尔顺|金丁|范晓宇

上海交通大学工业工程与管理系，中国上海东川路800号，200240

摘要

本文研究了具有多个位于不同位置的队列的服务系统中的服务器分配和调度问题。每个队列都会经历随机且随时间变化的客户到达情况。除了固定的服务器外，移动服务器也可以根据需求的变化进行重新部署。我们的研究动机来源于大型景点和机场的应用场景。例如，在一个大型景点中，员工会被动态分配到不同的入口处以缩短游客的排队时间；同样，在大型机场中，安保团队也会被动态分配到不同的航站楼以减少乘客的安检排队时间。引入移动服务器可以提高服务水平并缩短排队长度，但由于旅行时间的不确定性，这也增加了路由和调度的复杂性。我们构建了一个非线性混合整数模型来描述这个问题。通过利用原始模型的结构特性，我们开发了一个混合整数凸规划模型，并基于Benders分解和列生成算法开发了高效的精确求解方法，得到了高质量的解决方案。使用来自一个大型景点的真实世界数据集进行评估后发现，与现有调度方案相比，所提出的框架平均减少了14.13%的员工工作时间。结果还揭示了移动服务器的两个关键作用：高峰时段的支持和低峰时段的连续性。机场数据集进一步证实了我们的方法在满足所有排队长度约束的同时，能够减轻服务器的工作负担，其性能优于现有的最先进方法。

引言

许多服务系统都有分散在空间中的队列，需要动态地在多个队列之间分配服务器。在本文中，我们研究了如何高效地调度服务器以控制队列长度。这一研究的动机来源于两个实际问题：一个是上海植物园（SBG）的服务运营管理问题，另一个是大型国际机场的问题。上海植物园是中国上海一个著名的大型景点，占地面积约为818,000平方米，在春节和花展期间吸引大量游客。由于植物园面积较大，它设有四个入口，每个入口都有一到多个售票通道供游客购票。与其他排队系统（如呼叫中心）不同，员工（称为服务器）被分配到不同的入口处。他们的分配可以在规划期内进行调整，以维持服务水平，例如控制排队长度和等待时间。如果某个入口的队列过长，服务器可能会从其他入口暂时调来以增加该入口的通道数量。然而，对于上海植物园的管理者来说，确定何时以及如何在不同入口之间分配服务器存在三个主要挑战。

首先，所有入口的游客到达情况都是随机的，且到达率会随时间变化。在这样一个随时间变化的排队系统中管理排队长度或等待时间是一个重大挑战。其次，由于各入口的位置不同，游客的到达模式也有所不同。例如，靠近地铁站的入口与靠近大型停车场的入口的到达高峰时间可能不同。第三，不同入口之间的旅行时间也会增加复杂性，因为不同时间的游客数量会有波动。当游客密度较高时，游客在走道上停留会导致交通延误，从而影响服务器的工作效率。相反，在游客密度较低时，旅行时间较短。因此，如果管理者预计未来某个入口的队列可能会变长，最好提前进行服务器的重新分配。本文探讨了上海植物园面临的特定服务器调度问题，制定了所有员工的工作时间表，明确了他们在工作日内应何时驻扎在某个入口（无论是工作还是休息），以及何时需要转移到另一个入口。这个问题被称为多队列中的服务器分配与调度（SASMQ）。

除了上海植物园，上海虹桥国际机场（SHA）也面临SASMQ问题。该机场有两个航站楼，每个航站楼都设有安检通道。乘客在登机前必须在安检通道排队接受检查。安检过程包括行李检查和身体扫描等任务，由安检人员执行，他们被视为服务器。乘客的到达情况基于航班起飞时间而随机变化，并且全天在不同航站楼之间也有差异。有时一个航站楼的安检队列较长，而另一个航站楼的队列较短。在这种情况下，如果工作人员发现某个航站楼的队列正在增长或预计会快速增长，他们可能会选择关闭一个较不繁忙的安检通道，并将一个或多个安检人员重新分配到较繁忙的航站楼。因此，管理这个大型机场的安检服务器调度也可以被视为一个SASMQ问题。

尽管我们的研究动机来源于这两个具体的服务系统，但SASMQ问题并不局限于此场景，在世界各地都有应用。例如，在波士顿洛根国际机场，也存在类似的动态分配和调度安检人员的挑战，这凸显了SASMQ框架的广泛应用性[1]。在云计算系统中，调整任务队列中的服务器分配也会遇到类似的问题[2]。

尽管SASMQ问题非常重要，但在文献中却鲜有研究。本文以上海植物园为例，为其开发了一个混合整数非线性模型。我们的目标是在有效管理不同入口队列长度的同时，最小化服务器的工作时间。为了解决动态环境中队列长度计算的复杂性，我们提出了一种新的线性化方法，将问题转化为混合整数规划（MIP）模型。由于SASMQ问题被证明是NP难的（见附录B），我们开发了一种结合基于逻辑的Benders分解和列生成（CG）算法的解决方案策略来处理大规模实例。通过对上海植物园和两个国际机场的真实世界数据进行数值实验，证明了我们方法的有效性，其性能优于传统方法和现有算法。

本文的结构如下：第2节回顾相关文献；第3节定义问题并介绍模型及其线性化形式；第4节介绍基于逻辑的Benders分解，第5节详细介绍列生成；第6节展示数据集、实验结果和计算结果；第7节总结讨论未来研究方向。

文献综述

与多队列场景相比，大多数研究都集中在单队列中的服务器调度问题上。对于单个随时间变化的队列，已经开发了多种人员配置和调度方法来优化性能指标，如队列长度、等待时间和延迟概率[3]、[4]、[5]。关于随时间变化的队列及其在劳动力管理中的应用，可参考Green等人[6]和Defraeye与Van Nieuwenhuyse[7]的综述。

问题描述与数学模型

我们定义了上海植物园面临的SASMQ问题，并介绍了相关的符号和参数。设$G=\{1,2,\; ,\; \dots ,Q$表示所有入口的集合，其中$Q表示上海植物园的入口总数。每个入口$$i$都配备有多个服务窗口（通道），由员工操作，负责向到达的游客售票。上海植物园的营业时间为$t_{}$至$t_{}$，通常从$t_{}$开始，到$t_{}$结束。游客以非平稳且随机的方式到达每个入口。

解决方法

我们首先证明了即使在客户到达率和服务率确定的情况下，SASMQ问题也是NP难的（强形式）。

定理3

即使客户到达率和员工服务率都是确定的，SASMQ问题也是NP难的（强形式）。

证明

详见附录B。

尽管问题模型可以被线性化（见第3节），但其强NP难性质以及替代调度方案的组合爆炸性使得计算变得非常具有挑战性。

Benders分解子问题的列生成算法

在基于逻辑的Benders框架中，子问题决定了在给定人员配置计划下每个服务器的详细调度安排。然而，由于调度模式的大小随工作周期的数量呈指数级增长，子问题包含大量的调度变量。这些调度变量被分为中的固定员工调度集和中的移动员工调度集。直接解决这样一个具有庞大调度空间的子问题是

实验数据

我们在两个真实世界数据集上进行了数值实验。一个数据集来自上海植物园，另一个数据集来自两个大型机场。

结论

我们建模并解决了SASMQ问题，该问题在大型景点和机场等领域有应用。SASMQ问题与传统的调度问题有几个不同之处，包括存在可以在队列之间移动的移动服务器，以及需要控制队列长度。为了解决这个问题，我们首先使用PSFFA方法来估计多个入口的预期队列长度，然后提出了一种线性化算法来构建MIP模型。

CRediT作者贡献声明

王成凯：撰写 – 审稿与编辑、撰写 – 原稿撰写、可视化、软件开发、项目管理、方法论研究、概念构思。刘然：撰写 – 审稿与编辑、监督、资源协调、项目管理、方法论研究、资金获取、形式分析、概念构思。潘尔顺：撰写 – 审稿与编辑。金丁：软件开发。范晓宇：软件开发、方法论研究。

利益冲突声明

作者声明他们没有已知的财务利益或个人关系可能影响本文的研究结果。

致谢

本工作得到了国家自然科学基金（项目编号：72371161）的支持。我们感谢审稿团队的辛勤付出和宝贵意见，这些意见极大地帮助我们改进了论文的内容和表述。