💻 computer science

Machine Learning-Based Waiting Time Prediction for Priority Queues with Preemptive and Non-Preemptive Service Rules

本文表明，机器学习模型，特别是循环神经网络，仅利用队列长度和客户优先级，即可准确预测复杂且随时间变化的优先级队列系统中的等待时间，并在非抢占式及多种抢占式服务规则下表现优于基于树的方法。

原作者： Sahil Singh Bhandari, T.G. Deepak

发布于 2026-06-29

📖 1 分钟阅读☕ 轻松阅读

原作者： Sahil Singh Bhandari, T.G. Deepak

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正站在主题公园里一个拥挤的队伍中。通常情况下，规则是“先到先得”。但在本文中，作者研究了一个更复杂的队伍，其中有些人是 VIP（优先级 1），而另一些人是普通游客（优先级 2）。VIP 可以插队，这改变了其他人的等待时间。

核心问题是：我们能否使用计算机程序（机器学习）来准确预测一个人的等待时间，即使队伍处于混乱状态且 VIP 不断插队？

以下是他们所做工作的简单拆解，并使用了日常类比。

排队的三个规则

作者在三种不同的“交通规则”（即排队方式）下测试了他们的计算机程序：

“不中断”规则 (Non-Preemptive)： 想象理发师正在为顾客理发。即使有 VIP 走进来，理发师也会在切换任务前完成当前的理发。坐在椅子上的人原地不动。
“重新开始”规则 (Preemptive-Repeat)： 想象厨师正在烹饪一份牛排。如果 VIP 到达，厨师会停止为普通顾客烹饪，把那份牛排扔掉，然后为 VIP 从头开始做一份全新的。当 VIP 离开后，普通顾客必须从零开始制作他们的牛排。
“恢复”规则 (Preemptive-Resume)： 想象视频游戏中的角色正在与 Boss 战斗。如果 VIP 到达，战斗暂停。普通顾客的“血条”保持原样。当 VIP 离开后，战斗从刚才停止的地方继续。

数据：200 天的模拟

由于他们无法在现实中的队伍里等待 200 天来进行测试，因此他们构建了一个数字模拟系统。他们创造了一个虚拟世界，其中：

人们在随机时间到达（有时队伍是空的，有时则是人山人海）。
有两种类型的人：VIP 和普通人。
他们运行了这个模拟 200 个“天”，以生成关于谁等待了多久的海量数据。

竞赛：五个“计算机大脑”

他们让五种不同类型的“计算机大脑”（机器学习模型）进行对决，看谁能最好地预测等待时间。

“树”型大脑 (GBM & Random Forest)： 把这些想象成由一系列“是/否”问题组成的侦探团队。“队伍长吗？这个人是 VIP 吗？” 他们通过构建决策树来猜测等待时间。他们还测试了一个版本，即强制这些侦探分成两个独立的团队（一个针对 VIP，一个针对普通人），以观察这是否会有所帮助。
“时空旅行者”大脑 (RNN)： 这是一种循环神经网络。把它想象成一个能记住队伍“故事”的大脑。它不仅仅看当前时刻，它还会记住之前到达的人员序列。它理解“在长长的普通人队伍之后紧接着出现一名 VIP”会产生怎样的特定连锁反应。

重大发现

1. “时空旅行者”大脑赢得了比赛
RNN（那个能记住事件序列的模型）是明显的赢家。它在预测等待时间方面最为准确，尤其是在发生中断的“重新开始”和“恢复”规则下。

原因： 因为在优先级的队伍中等待不仅仅取决于现在发生了什么，更取决于刚刚之前发生了什么，以及接下来可能会发生什么。RNN 擅长阅读这种“故事”。

2. “树”型大脑表现不错，但并不完美
决策树模型（GBM 和 Random Forest）做得还算可以，但不如 RNN 那么敏锐。当受到频繁干扰时，它们的表现会稍显吃力。

3. 分组并不奏效
作者尝试强制决策树模型拥有针对 VIP 和普通人的独立团队（“强制优先级拆分”）。他们认为这可能会帮助模型更好地聚焦。

结果： 这几乎没有产生什么影响。标准的模型本身就已经足够聪明，能够自动识别 VIP 和普通人的区别。这就像雇佣两个专门的厨师，其实一个优秀的厨师就能处理两种菜单。

4. “神奇的双重输入”
这是最令人惊讶的部分。通常，为了完美预测等待时间，你需要了解一切：准确的到达率、服务速度、时间点等。

发现： 作者发现，模型仅使用两项信息就能非常准确地预测等待时间：
1. 现在队伍里有多少人？（队列长度）
2. 此人是 VIP 还是普通人？（优先级）
即使不知道具体的时间或人们通常到达的速度，仅仅知道当前的拥挤程度和个人的身份状态，计算机就足以做出极佳的猜测。

总结

本文表明，你不需要一个拥有百万级数据点的超级复杂系统来预测优先队伍的等待时间。

如果你想要最高的准确度，请使用能够记住事件序列的模型（如 RNN）。
如果你想要简洁性，只需统计队伍人数并检查其优先级标识，就能获得令人惊喜的良好结果。

这对现实世界的系统（如医院或呼叫中心）来说是个好消息，因为这些系统往往没有完美的到达率数据，但他们确实知道有多少人在等待以及谁是重要的客户。他们可以利用这些简单的输入，为人们提供准确的等待时间预估。

技术摘要：基于机器学习的优先级队列等待时间预测

问题陈述

本文研究了在时变条件下，多类优先级队列系统中瞬态等待时间预测的挑战。虽然经典排队论为简单的平稳系统提供了精确的解析结果，但现实世界的应用（如医疗保健、呼叫中心、物流）通常涉及非平稳到达率、复杂的服务时间分布以及抢占规则。在这些环境中，客户的等待时间不仅取决于当前的队列状态，还取决于未来的高优先级到达，这使得解析预测变得十分困难。

本研究专门探讨了机器学习（ML）模型是否能够利用有限的、在操作层面可观测的数据——具体而言是到达时的队列长度和客户的优先级类别——来准确预测等待时间，而无需获取底层到达率函数或服务时间分布的详细知识。

研究方法

数据生成

作者通过模拟 200 个独立的、处于时变环境下的两类优先级队列（ $G(t)/G/1$ ）天数，生成了一个合成数据集。

到达过程： 使用分段齐次区间结合相位类型（Phase-Type, PH）分布来模拟非平稳到达，以捕捉超出简单指数分布假设的变异性。
服务规则： 模拟了三种不同的服务规则：
1. 非抢占式（Non-Preemptive）： 一旦开始服务，服务将持续进行，不会被中断。
2. 抢占-重复（Preemptive-Repeat）： 高优先级到达会中断低优先级任务，且该任务在恢复时必须从头开始。
3. 抢占-恢复（Preemptive-Resume）： 高优先级到达会中断低优先级任务，但该任务在恢复时从中断点继续执行。
特征： 测试了两种特征配置：
1. 四特征集： 到达时间、到达间隔时间、优先级类别和到达时的队列长度。
2. 两特征集： 仅包含优先级类别和到达时的队列长度。

评估模型

对比了五种机器学习模型：

梯度提升机（GBM）： 标准的决策树集成模型。
强制优先级拆分 GBM（FS-GBM）： 一种变体，在训练独立的 GBM 模型之前，先按优先级类别对数据集进行硬拆分。
随机森林（RF）： 标准的去相关决策树集成模型。
强制优先级拆分 RF（FS-RF）： 一种变体，为每个优先级类别训练独立的 RF 模型。
循环神经网络（RNN）： 一种基于 LSTM 的架构，旨在捕捉一天内客户到达序列中的时间依赖性。

性能评估指标包括平均绝对误差（MAE）、均方误差（MSE）、均方根误差（RMSE）以及决定系数（ $R^2$ ）。

核心贡献

统一框架： 本研究提供了一个统一的模拟框架，用于生成涵盖非抢占、抢占-重复和抢占-恢复规则以及时变到达的瞬态数据。
评估优先级感知结构： 论文明确测试了通过按优先级类别进行硬拆分数据（FS-GBM, FS-RF）是否能比将优先级作为特征的普通模型提高预测效果。
最小信息可行性： 研究表明，仅使用两个输入（队列长度和优先级）即可实现准确的等待时间预测，这挑战了“数据驱动方法需要详细系统参数”的假设。
对比分析： 针对优先级队列背景，对树集成模型和基于序列的深度学习模型进行了全面的比较。

研究结果

模型性能

RNN 的优越性： 循环神经网络（LSTM）在所有三种服务规则和两种特征设置下均一致地实现了最高的准确度。它展示了建模复杂时间动态的能力，特别是在抢占式设置中，由于服务中断的存在，会产生复杂的时间依赖关系。
- 在非抢占设置（4 特征）中，RNN 实现了 0.987 的 $R^2$ ，而基于树的模型约为 0.94。
- 在抢占-恢复设置（最复杂的场景）中，RNN 仍保持 0.987 的 $R^2$ ，而基于树的模型降至约 0.927。
树模型的稳定性： GBM 和随机森林模型提供了稳定且具有竞争力的表现，尤其是在非抢占设置中。然而，与 RNN 相比，它们在抢占式场景中的准确度有所下降。
强制拆分的无效性： “强制优先级拆分”变体（FS-GBM 和 FS-RF）与其标准对应版本相比，仅提供了微小且不一致的改进。作者得出结论，当优先级作为输入特征时，标准的树模型已经能够隐式地学习特定优先级的非线性特征，因此显式的硬拆分并无必要。

特征缩减

将输入特征从四个减少到两个（移除到达时间和到达间隔时间）导致性能仅出现了适度的下降。

RNN 即使在输入极简的情况下仍保持了强大的预测能力，在非抢占情况下实现 $R^2$ 为 0.974，在抢占-恢复情况下为 0.972。
树模型也保持了稳定性，这表明队列长度和优先级编码了所需的大部分预测信息。

重要性与主张

论文声称，机器学习（尤其是像 RNN 这样的基于序列的模型）为基于优先级的服务系统中的实时等待时间预测提供了一种实用且强大的替代方案。

实际可部署性： 研究强调，仅使用队列长度和优先级即可实现准确预测，这是一个重大的实际优势。在许多现实世界系统中（如医院、呼叫中心），详细的到达率函数或服务分布是未知的或难以估计的，但队列长度和优先级是易于观测的。
处理抢占： 研究表明，ML 模型可以有效地捕捉抢占（无论是重复还是恢复）的复杂影响，而无需对中断逻辑进行显式建模，而这在解析法中是极具挑战性的。
模型选择： 虽然 RNN 被确定为捕获抢占系统中时间动态的最有效工具，但树模型也被视为可靠、稳定且计算高效的替代方案，尤其是在偏好可解释性或更简单架构时。
结构化修改的局限性： 论文谦虚地总结道，显式强制进行优先级拆分并不会显著提升性能，这表明现代集成方法通过标准的特征包含，已足够鲁棒地处理优先级异质性。

作者强调，他们的工作架起了经典排队论与现代数据驱动预测之间的桥梁，为适用于数据可用性有限且运行条件动态变化的系统提供了一个框架。