Near-optimal scheduling with general service times and IHR abandonment times

想象一家繁忙的咖啡店，顾客们正排队等着买饮料，但这里有一个转折：每个顾客都有一个秘密计时器。如果等待时间过长，他们就会感到沮丧并离开，不买任何东西。咖啡师（服务员）必须决定接下来为谁服务。是应该服务等待时间最长的人？还是服务只需要一杯快速浓缩咖啡的人？或者是那个即将放弃离开的人？这就是所谓的“调度”（scheduling）问题，它是数学和计算机科学的一个分支，旨在研究当资源有限且时间紧迫时，如何找到组织任务的最佳方式。

在调度的世界里，有两个主要的成本需要关注。首先是“持有成本”（holding cost），这就像是顾客在排队时损失的精力与耐心。其次是“放弃惩罚”（abandonment penalty），即当顾客愤怒地离开时所造成的销售损失和声誉损失。几十年来，数学家们一直试图解决这个谜题，但他们通常做了一个巨大的简化：他们假设服务时间（制作一杯饮料需要多久）和耐心时间（顾客愿意等待多久）遵循一种简单的、可预测的模式，称为“指数分布”（exponential distribution）。这就像是假设每一次抛硬币都是完全随机且独立的。虽然这让数学计算变得简单，但它并不反映现实生活，因为现实中有些任务会耗费很长时间，而有些人的耐心极高，或者极其缺乏耐心。

Samuli Aalto 撰写的这篇论文解决了这个混乱的、现实世界的版本的问题。作者没有假设简单的、可预测的模式，而是允许任何形式的服务时间（比如制作一杯复杂的拿铁可能要花很久）以及一种特定类型的急躁情绪——即“IHR”（递增风险率）。IHR 是一个高级概念，指的是随着等待时间的增加，你感到厌烦并离开的可能性越来越大——就像一个真实的人，随着队伍移动缓慢，会变得越来越愤怒。该论文使用了一个巧妙的数学工具，叫做“Whittle 指数”（Whittle index），来确定最佳的服务顺序。其主要发现是，这种能够处理这些复杂现实场景的新方法，在计算机模拟中始终优于旧的常规经验法则（称为 $c\mu/\theta$ 规则）。作者证明了他们的公式在问题的简化版本中在数学上是严谨的，并通过模拟实验展示了该方法比以往最好的方法能节省更多资金并让更多顾客保持满意。

不耐烦队伍的故事

想象一个混乱的机场安检队伍。你有一组安检人员（服务员）和一群旅行者（顾客）。每位旅行者都有两个隐形的时钟在倒计时。一个时钟计算着他们的服务时间——即扫描行李和检查身份证件需要多久。另一个时钟计算着他们的耐心时间——即他们在决定放弃飞行回家之前愿意在那里站多久。

在过去，模拟这条线路的数学家假设这两个时钟都以一种非常特定的、“无记忆”的方式倒计时。这就像是在说，无论你已经站了多久，你在下一分钟离开的可能性与你刚到达时是完全一样的。这就是“指数”假设。这是一种精妙的数学技巧，但并不符合人类的真实行为。在现实中，如果你已经等了 20 分钟，那么在下一分钟内发火离去的可能性要比你刚到达时大得多。这就是论文中所说的 IHR（递增风险率）：等待时间越长，你离开的风险就越高。

作者还意识到，现实中的服务时间并不总是那么简单。有时扫描一个包是瞬间完成的；有时则会耗时很久，因为行李箱上有个奇怪的锁。论文允许通用服务时间，这意味着数学可以处理任何形状的等待时间，从快速简便到漫长复杂。

魔法公式：Whittle 指数

那么，如何决定为谁服务呢？论文引入了“Whittle 指数”作为每一位顾客的评分卡。这个分数不仅仅是关于他们等待了多久。它是一个复杂的计算，综合考虑了：

1. 他们已经等待了多久 (x)。
2. 他们已经接受了多少服务 (y)。
3. 让他们等待的成本是多少（持有成本）。
4. 如果他们离开，成本是多少（放弃惩罚）。

作者证明了对于这个问题的简化版本（一个没有新成员加入的“封闭”系统），这个评分卡在数学上是完美的。它是“可索引的”（indexable），这是一个高级说法，意味着你可以根据这个指标将所有人进行排名，从“现在就为我服务！”到“我可以再等等”。

然后，作者将这个评分卡应用到了现实的、连续的世界中，在那里人们不断地到达。最终得到的公式 $W_k(x, y)$ 看起来有点吓人，但它本质上是在问：“如果我为这个人提供一小段时间的服务，与他们离开的风险相比，我能节省多少钱？”

对决：新 vs. 旧

为了验证这种新的“Whittle 指数策略”（WHI）是否真的有效，作者运行了数千次计算机模拟。他们建立了一个虚拟机场，其中有两种类型的旅行者：

• 第一类： 短任务（快速扫描）但耐心程度各异。
• 第二类： 长任务（复杂的扫描）且具有不同的耐心水平。

他们测试了四种不同的场景，通过混合不同类型的服务时间（有些是均匀分布的，有些是“帕累托分布”，这意味着少数人会耗费极长时间）以及放弃成本（有时失去一名顾客代价很低，有时则是巨大的损失）。

结果显而易见。新的 Whittle 指数策略系统性地优于旧的标准，即 $c\mu/\theta$ 规则。

• 在“均匀-均匀”场景下（每个人都相对可预测），新策略比旧规则多节省了约 12% 到 19% 的成本。
• 在“均匀-帕累托”场景下（有些人有非常漫长且不可预测的服务时间），差距进一步扩大。新策略比旧规则多节省了 33% 到 42% 的成本。
• 即使在最棘手的场景中，新策略也始终表现更好，有时甚至高出 52%。

论文还将新方法与其他常见策略进行了比较，例如“先到先得”（First-Come-First-Served，先为等待最久的人服务）和“处理器共享”（Processor-sharing，在所有人之间平分服务时间）。Whittle 指数击败了所有对手。

这为什么重要

核心结论是，通过放弃“完美随机”的假设并拥抱人类产生不耐烦情绪的复杂现实，我们可以构建出更优秀的系统。无论是咖啡店、呼叫中心，还是处理数据的数据网络，使用这个新公式意味着更少的顾客因愤怒而离开、更少的时间浪费以及更多的资金节省。作者不仅仅是猜测，他们证明了该公式在简化版本中在数学上是成立的，并通过严格的模拟实验展示了它在复杂的现实版本中发挥了奇效。这提醒我们，有时解决问题的最佳方法是停止假装世界比实际情况更简单。