经典调度问题 $P_m||\sum_j w_j U_j$ 要在 $m$ 台相同并行机器上安排每个作业的处理时间、权重和截止日期，使迟到作业的总权重最小。若作业在截止日期后完成则视为迟到。Lawler 与 Moore 于 1969 年提出的动态规划在 $O(n d_{\max}^m)$ 时间内求解，其中 $n$ 为作业数，$d_{\max}$ 为最大截止日期。本文证明只需计算动态规划的部分状态即可在 $\tilde{O}(n + d_{\max}^{m+1})$ 时间内得到最优解，$\tilde{O}$ 隐含多项式对数因子。该结果在单机情形 $m=1$ 给出 $\tilde{O}(n + d_{\max}^2)$，正面回答了 Hermelin、Molter 与 Shabtay 在 2024 年提出的开放问题。
点评: 通过削减状态空间，作者将指数依赖从 $d_{\max}^m$ 降至 $d_{\max}^{m+1}$，在实际 $d_{\max}$ 较大时显著加速，尤其在单机情况下实现了理论上最优的准线性时间。