arXiv:2510.16663cs.DScs.LG2025-10

在预测逐渐变准但工人减少的情况下,动态调度算法能最小化人力过剩或不足的损失。

Robust Dynamic Staffing with Predictions

  • 设计对抗性预测下的在线算法,平衡早招(人多但预测不准)与晚招(预测准但人少)的矛盾
  • 理论证明算法在最坏情况下仍能实现最优成本,且可高效计算
  • 适用于多任务、可调整决策、预测不一致等实际场景,适合物流调度等应用

我们研究一个自然的动态排班问题:决策者需在有限时间段内逐次雇佣工人以应对未知需求,需求在期末才揭晓。随着过程推进,对需求的预测逐渐更准确,但工人可用性下降。这引发根本权衡:早期雇佣可避免缺工(此时人多但预测不准),晚期雇佣可避免冗员(此时预测准但人少)。该问题源于最后一公里配送,如亚马逊依赖零工经济人员,其可用性随运营日临近而降低。为克服贝叶斯模型的实际局限(尤其对预测方法敏感),我们在对抗性预测框架下建模:序列预测以对抗性选择的不确定性区间形式出现,这些区间(近似)包含真实需求。目标是最小化最坏情况下的排班失衡成本。主要成果是提出一种简单且计算高效的在线算法,达到极小极大最优。我们首先通过多项式规模线性规划刻画受限对抗者的极小极大成本,再将其推广至一般情形。基础模型针对单一需求,扩展至多个需求(公平/功利目标)、雇佣决策不可逆的成本、以及预测区间不一致的情形。还引入一种实用的“重求解”变体,证明其同样极小极大最优。数值实验表明,该算法在成本和速度上优于贝叶斯启发式,在可计算时甚至媲美(近似或精确)贝叶斯最优策略。

原文摘要 · Abstract (English)

We consider a natural dynamic staffing problem in which a decision-maker sequentially hires workers over a finite horizon to meet an unknown demand revealed at the end. Predictions about demand arrive over time and become increasingly accurate, while worker availability decreases. This creates a fundamental trade-off between hiring early to avoid understaffing (when workers are more available but forecasts are less reliable) and hiring late to avoid overstaffing (when forecasts are more accurate but availability is lower). This problem is motivated by last-mile delivery operations, where companies such as Amazon rely on gig-economy workers whose availability declines closer to the operating day. To address practical limitations of Bayesian models (in particular, to remain agnostic to the underlying forecasting method), we study this problem under adversarial predictions. In this model, sequential predictions are adversarially chosen uncertainty intervals that (approximately) contain the true demand. The objective is to minimize worst-case staffing imbalance cost. Our main result is a simple and computationally efficient online algorithm that is minimax optimal. We first characterize the minimax cost against a restricted adversary via a polynomial-size linear program, then show how to emulate this solution in the general case. While our base model focuses on a single demand, we extend the framework to multiple demands (with egalitarian/utilitarian objectives), to settings with costly reversals of hiring decisions, and to inconsistent prediction intervals. We also introduce a practical "re-solving" variant of our algorithm, which we prove is also minimax optimal. Finally we conduct numerical experiments showing that our algorithms outperform Bayesian heuristics in both cost and speed, and are competitive with (approximate or exact) Bayesian-optimal policies when those can be computed.

动态调度对抗性预测资源分配优化算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。