Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling¶
会议: NeurIPS 2026
arXiv: 2606.13133
OpenReview: https://openreview.net/forum?id=OVhc0m9SE8
领域: 优化/理论
关键词: 学习增强算法, 无关并行机调度, 极差最小化, 近似算法, 预测误差平滑退化
一句话总结¶
本文针对无关并行机极差调度（\(R\|C_{\max}\)）设计了首个带预测误差平滑退化保证的学习增强近似算法，利用对大作业机器分配的预测进行局部化搜索与残差线性规划舍入，在准确预测下以多项式时间达成 \((1+\varepsilon)\mathrm{OPT}\) 近似，并在任意低质预测下平滑退化至经典 \(2\mathrm{OPT}\) 基线。
研究背景与动机¶
无关并行机上的极差（Makespan）最小化问题（符号记为 \(R\|C_{\max}\)）是组合优化与调度理论中的奠基性难题。在这一经典模型中，存在 \(m\) 台异构机器与 \(n\) 个作业，每个作业 \(j\) 在机器 \(i\) 上的加工时间为机器相关的正实数 \(p_{ij}\)。目标是寻找作业到机器的分配映射，以最小化所有机器的最大负载。该问题具备极强的计算复杂性壁垒：Lenstra、Shmoys 与 Tardos（LST）在 1990 年给出了著名的多项式时间 2 近似算法，并证明当近似比低于 1.5 时该问题即便在多项式时间内也是 NP-难的。对于追求 \((1+\varepsilon)\mathrm{OPT}\) 的多项式时间近似方案（PTAS），经典方法必须依赖对所有大作业（即加工时间超过 \(\varepsilon T\) 的分配）进行全局暴力枚举搜索，这导致算法运行时间包含诸如 \((n+1)^{m/\varepsilon}\) 或 \(2^{mn}\) 的指数项，除非机器数量 \(m\) 固定为很小的常数，否则在实际大规模异构集群中完全不具备计算可行性。
近年来，随着机器学习在各类组合决策场景下的预测能力显著提高，利用未经验证的机器学习预测指导算法设计的学习增强算法（Learning-Augmented Algorithms）成为前沿热点。这类算法的核心诉求在于兼顾一致性（预测准确时突破经典复杂度或近似比下界）、健壮性（预测极端错误时仍保持经典最坏情况理论底线）以及平滑性（算法表现随预测误差连续单调退化）。在离线 NP-难近似算法领域，Antoniadis 等人（ICLR 2025）率先建立了一套适用于顶点覆盖、斯坦纳树、背包与团等具备线性目标函数的集合选择问题黑盒框架，证明了预测误差可平滑转化为近似比损失。然而，调度问题其目标函数为最大机器负载而非简单的集合权值线性和，加之离散分配约束的拓扑复杂性，使得其无法被纳入集合选择框架。Antoniadis 等人遂将“如何为调度等非选择类核心组合优化问题设计平滑学习增强近似算法”明确列为开放问题。
本文的切入视角直击经典大/小作业分解（Heavy/Short Decomposition）的结构瓶颈：既然经典的计算瓶颈在于对可能的大作业分配进行指数级全局穷举，那么如果机器学习模型能预先给出一份部分大作业分配预测，算法便无需在全域盲目搜索，而仅需在预测分配的局部邻域内修正少量遗漏的重载任务，剩余的小任务则交由多项式时间 LP 松弛与 Shmoys-Tardos 舍入完成。核心 idea：将机器学习预测引入无关机调度的重作业分解框架，利用预测锚定重任务骨干并以搜索预算 \(K\) 进行定向补全，构建支持可变截断阈值 \(\tau\) 的残差 LP 与无损舍入，从而在预测准确时以多项式时间斩获 \((1+\varepsilon)\mathrm{OPT}\)，并随假阴性/假阳性误差平滑退化至最坏情况 \(2\mathrm{OPT}\)。
方法详解¶
整体框架¶
本文算法采用内外双层解耦架构。外层过程负责在多项式数量的离散关键阈值集合中同步搜索目标极差，内层过程则在给定目标极差 \(T\)、容许误差 \(\varepsilon\)、局部搜索预算 \(K\) 以及预测分配 \(\widehat{\phi}\) 的前提下，执行预测引导的重任务补全、残差 LP 求解与紧舍入。
在内层执行流中，算法首先根据当前测试极差 \(T\) 执行投影操作，仅保留加工时间超过 \(\varepsilon T\) 的强相关重作业预测，过滤掉可能导致过载的小作业噪声。随后，基于常数搜索预算 \(K\)，算法仅穷举补全至多 \(K\) 个未被预测覆盖的大作业分配；随后固定所有大作业并计算各机器已有固定负载，在由加工时间离散化构成的候选阈值集 \(\Lambda(T)\) 上求解残差线性规划；最后调用 Shmoys-Tardos 广义分配舍入算法获得整数调度解，返回在当前 \(T\) 下极差最小的候选解。外层算法则首先以经典 LST 2 近似解的极差 \(B = C_{\max}(S_0)\) 标定最优极差所属区间 \([B/2, B]\)，生成有限个临界极差分割点 \(\mathcal{T}\)，并遍历调用内层过程，最终与基线解 \(S_0\) 取最优输出。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
In["输入：机器作业矩阵 p_ij + 预测分配 phi_hat"] --> OutB["基线计算与临界区间定界<br/>LST 2-近似得到极差 B"]
OutB --> OuterLoop["外层临界极差离散搜索<br/>枚举 T ∈ T_crit ⊆ [B/2, B]"]
OuterLoop --> Proj["大作业投影与噪声过滤<br/>筛选 p_ij > εT 的预测分配"]
Proj --> SearchAug["预算受限的假阴性局部补全<br/>枚举至多 K 个缺失重作业"]
SearchAug --> SolveLP["自适应残差线性规划求解<br/>枚举 τ ∈ Λ(T) 限制残差边权"]
SolveLP --> Round["多项式时间无损极差舍入<br/>Shmoys-Tardos 极值点舍入"]
Round --> BestCand["双向误差平滑融合与保底决策<br/>取所有候选解与 S_0 的最优值"]
BestCand --> OutFinal["输出：满足平滑退化界的可行调度 S"]关键设计¶
1. 大作业投影与噪声过滤：阻断小作业低质预测污染
经典近似模式在处理小作业时并不需要组合搜索，因为加工时间不超过 \(\varepsilon T\) 的短作业即便全由连续 LP 舍入分配，对任意单台机器造成的附加负载累积至多也不超过 \(\varepsilon T\)。因此，若盲目采纳预测模型给出的全部作业分配，极易因小作业预测错误导致机器容量被无端挤占。针对这一问题，算法设计了参数化极差尺度投影算子：
该设计使得预测模型支持安全弃权（Abstention），预测模型仅需专注识别高耗时瓶颈任务，而无需对全量作业做全景预测。所有被过滤掉的作业将无缝回退至后续残差线性规划中统一调度，从根本上隔离了短作业低置信度预测对系统造成的不可逆过载。
2. 预算受限的假阴性局部补全：以多项式时间置换重作业漏检
若预测模型发生假阴性（False Negative），即最优调度中某些耗时大于 \(\varepsilon T\) 的重作业未能被 \(\widehat{\phi}_T\) 覆盖，传统做法将因无法识别关键约束而彻底破坏理论近似保证。为此，算法引入非负整数常数预算 \(K\)，仅在未被 \(\widehat{\phi}_T\) 固定的剩余作业中枚举至多 \(K\) 个新增重作业分配 \(A: [n] \to [m] \cup \{\bot\}\)，使得满足：
这种局部增广搜索的枚举状态数严格受限于 \(\sum_{s=0}^{K} \binom{n}{s} m^s \le (K+1)(mn)^K\)。当选定 \(K\) 为常数时（如 \(K=0, 1, 2\)），搜索复杂度保持为标准多项式阶数，与机器总数 \(m\) 无关。通过该设计，算法成功将经典全局搜索 \((n+1)^{m/\varepsilon}\) 的组合爆炸约束转化为用户可自由调节的平滑参数 \(K\)：即使 \(K\) 不足以补全所有漏检的重作业，剩余最大的漏检重任务加工时间也将作为平滑误差项严格受控。
3. 自适应残差线性规划求解：动态边界兼容未修复大作业
在固定局部增广后的重作业分配 \(\psi_A = \widehat{\phi}_T \cup A\) 之后，每台机器已承担固定初始负载 \(\ell_i^{\mathrm{fix}}(\psi_A) = \sum_{j: \psi_A(j)=i} p_{ij}\)。由于搜索预算 \(K\) 可能小于实际漏检数，残差作业集中仍可能潜藏 processing time 大于 \(\varepsilon T\) 的重作业，若直接采用经典 LP 的边权截断界 \(\varepsilon T\)，会导致 LP 判定无解。本文创造性地将边权截断阈值扩展为可变参数 \(\tau \ge \varepsilon T\)，并在离散临界点集 \(\Lambda(T) = \{\varepsilon T\} \cup \{p_{ij} \mid p_{ij} \ge \varepsilon T\}\) 内枚举求解：
当 \(\tau = \tau^\star = \max\{\varepsilon T, R_{T,K}^{-}(\widehat{\phi}, \sigma)\}\) 时，最优调度 \(\sigma\) 中未被补全的重任务其处理时间天然被 \(R_{T,K}^{-}\) 压制，因而在松弛 LP 中是可行的，且目标值 \(L \le C_{\max}(\sigma) + R_{T}^{+}(\widehat{\phi}, \sigma)\)。该机制完美桥接了离散误差与连续规划。
4. 多项式时间无损极差舍入与双向误差平滑融合：严格把控理论底线
得到残差 LP 的极值点可行解后，算法调用 Shmoys-Tardos 拟二分匹配舍入定理。根据其结构性质，每个机器至多接收一个分数边引起的附加作业，由于所有入选边的加工时间均严格满足 \(p_{ij} \le \tau\)，舍入过程对机器负载造成的最大附加偏移绝不超过 \(\tau\)。从而最终调度极差保证满足 \(C_{\max}(S) \le L_{\psi_A} + \tau\)。外层进一步结合经典 LST 2 近似解 \(S_0\) 取下确界，最终形成显式的双向误差解析上界：
其中假阳性过载定义为机器上错误固定重作业的最大堆叠量 \(R_T^{+}(\widehat{\phi}, \sigma) = \max_{i} \sum_{j: \widehat{\phi}_T(j)=i \neq \sigma(j)} p_{ij}\)，而假阴性残差 \(R_{T,K}^{-}(\widehat{\phi}, \sigma)\) 恰为漏检重作业中第 \(K+1\) 大的处理时间。
一个完整示例¶
考虑一个拥有 \(m=3\) 台机器与若干作业的调度实例，设最优调度极差 \(\mathrm{OPT}=100\)，令参数 \(\varepsilon=0.1\)，则大作业判定阈值为 \(\varepsilon \mathrm{OPT} = 10\)。假定最优调度中有三个大作业 \(j_1, j_2, j_3\)，在对应机器上的耗时分别为 \(p_{\sigma^\star(j_1), j_1} = 30\), \(p_{\sigma^\star(j_2), j_2} = 25\), \(p_{\sigma^\star(j_3), j_3} = 15\)。
预测模型 \(\widehat{\phi}\) 给出了部分预测：正确预测了 \(j_1\) 分配，但完全漏检了 \(j_2\) 与 \(j_3\)（假阴性集合 \(\mathrm{Miss} = \{j_2, j_3\}\)）；同时将某个耗时 12 的短任务 \(j_4\) 错误指派给机器 1（假阳性，在机器 1 上产生附加固定负载 12）。 1. 若设置局部搜索预算 \(K=0\)：算法不执行补全，未修复重任务中最大处理时间为 \(j_2\) 的 25，故残差 LP 阈值扩展到 \(\tau=25\)。LP 求解出各机负载加上舍入偏差 25 与假阳性过载 12，最终极差界为 \(\mathrm{OPT} + 25 + 12 = 137\)。 2. 若设置局部搜索预算 \(K=1\)：算法在组合补全步骤中尝试各种单任务分配，当枚举到将 \(j_2\) 分配给其正确机器时，剩余未覆盖的大任务仅剩 \(j_3\)（耗时 15）。此时有效假阴性阈值下降为 \(R_{\mathrm{OPT}, 1}^{-} = 15\)，使得残差 LP 阈值收缩至 \(\tau=15\)，算法输出极差界紧缩为 \(\mathrm{OPT} + 15 + 12 = 127\)。 3. 若提升预算至 \(K=2 \ge |\mathrm{Miss}|\)：算法成功恢复全部漏检重作业，\(R_{\mathrm{OPT}, 2}^{-} = 0\)，阈值直接归位为标准值 \(\tau = \varepsilon \mathrm{OPT} = 10\)。消除全部假阴性损耗，输出极差仅为 \((1+0.1)\mathrm{OPT} + 12 = 122\)。整个计算过程始终在秒级内多项式时间收敛。
实验关键数据¶
主实验¶
实验基于经典的合成基准分布评测算法表现（作业加工时间独立均匀采样自 \(U[1, 100]\)，设置 \(\varepsilon = 0.01\)，每组配置采用 5 个随机种子统计均值与标准误差）。对比基线包括：经典 LST 多项式时间 2 近似基线、经典大作业枚举 \((1+\varepsilon)\mathrm{OPT}\) 近似算法（由于指数级耗时，机器数较大时超时不可行），以及本文方法在不同局部搜索预算 \(K \in \{0, 1, 2\}\) 下的实测比值 \(C_{\max}(S) / \mathrm{OPT}\)。
下表给出了在规模 \(m=10, n=100\) 下，固定单一误差类型时各算法的极差近似比表现：
| 实验配置 (\(m=10, n=100\)) | 指标 \(C_{\max}/\mathrm{OPT}\) | 本文 (\(K=0\)) | 本文 (\(K=1\)) | 本文 (\(K=2\)) | 经典 LST (2-近似) | 经典 \((1+\varepsilon)\)-PTAS |
|---|---|---|---|---|---|---|
| 完美预测 (\(\rho^-=0, \rho^+=0\)) | 极差近似比 | 1.000 | 1.000 | 1.000 | 1.258 ± 0.012 | 超时 (>600s) |
| 低假阴性 (\(\rho^- \approx 0.1, \rho^+=0\)) | 极差近似比 | 1.041 ± 0.005 | 1.000 | 1.000 | 1.258 ± 0.012 | 超时 (>600s) |
| 中假阴性 (\(\rho^- \approx 0.14, \rho^+=0\)) | 极差近似比 | 1.082 ± 0.008 | 1.035 ± 0.006 | 1.000 | 1.258 ± 0.012 | 超时 (>600s) |
| 全假阴性 (\(\rho^- = 1.0, \rho^+=0\)) | 极差近似比 | 1.185 ± 0.011 | 1.171 ± 0.010 | 1.158 ± 0.009 | 1.258 ± 0.012 | 超时 (>600s) |
| 低假阳性 (\(\rho^-=0, \rho^+ \approx 0.1\)) | 极差近似比 | 1.032 ± 0.004 | 1.032 ± 0.004 | 1.032 ± 0.004 | 1.258 ± 0.012 | 超时 (>600s) |
| 高假阳性 (\(\rho^-=0, \rho^+ \approx 0.5\)) | 极差近似比 | 1.142 ± 0.009 | 1.142 ± 0.009 | 1.142 ± 0.009 | 1.258 ± 0.012 | 超时 (>600s) |
消融实验：运行时间随机器数规模的可扩展性¶
在固定作业数 \(n=10\)、同时引入假阴性与假阳性误差率各 0.1 的条件下，检验不同算法随机器数量 \(m\) 增加的端到端求解耗时（秒）：
| 机器数 \(m\) | 本文 (\(K=0\)) 耗时 | 本文 (\(K=1\)) 耗时 | 本文 (\(K=2\)) 耗时 | LST 2-近似基线 | 经典 LST PTAS | Mordechai PTAS |
|---|---|---|---|---|---|---|
| \(m = 2\) | 0.012s | 0.025s | 0.058s | 0.008s | 0.42s | 0.35s |
| \(m = 4\) | 0.018s | 0.048s | 0.162s | 0.011s | 12.8s | 8.5s |
| \(m = 6\) | 0.026s | 0.082s | 0.380s | 0.015s | 145.2s | 98.4s |
| \(m = 8\) | 0.035s | 0.135s | 0.790s | 0.019s | >400s (截断) | 385.0s |
| \(m = 10\) | 0.048s | 0.210s | 1.450s | 0.024s | >600s (超时) | >600s (超时) |
关键发现¶
- 假阴性与假阳性误差的非对称性得到实证印证：在假阴性消融中，增大搜索预算 \(K\) 能产生立竿见影的极差改进（\(K=1\) 在误差率 \(\le 0.1\) 时即可完全抹平漏检影响重获最优解）；而在假阳性消融中，\(K=0, 1, 2\) 的表现曲线完全重合，这是因为单纯的重任务补全无法消除已经错误固定的假阳性过载，完全契合理论定理中的独立过载项 \(R_{\mathrm{OPT}}^{+}\)。
- 即使预测全部失效亦优于理论最坏界：当所有大作业预测被完全抹去（\(\rho^- = 1.0\)）时，本文算法实测极差为 \(1.185 \mathrm{OPT}\)，依然显著优于 LST 算法实测的 \(1.258 \mathrm{OPT}\) 与理论保证的 \(2 \mathrm{OPT}\)，展现出极强的鲁棒平滑性。
- 突破经典 PTAS 的规模诅咒：经典算法耗时随 \(m\) 呈超指数级增长，当 \(m=8\) 时便已接近或超出实用上限；而本文方法即便是 \(K=2\) 阶局部搜索，在 \(m=10\) 时耗时仅为 1.45 秒，展现了工业级部署可行性。
亮点与洞察¶
- 将学习增强范式成功拓宽至非线性极差调度领域：直接回应了 Antoniadis 等人在 ICLR 2025 留下的开放性课题，打破了此前学习增强近似算法局限于集合权值线性选择问题的范式束缚。
- 精妙的非对称误差补偿机制：巧妙揭示了组合优化中预测误差的内生机理——假阴性是“可通多项式算力搜索修复的”，其代价值表现为计算时间；假阳性是“占用容量的过载”，其代价值表现为极差界上升。这种用常数算力换取理论保证的设计极具通用启发意义。
- 可编辑预测模型（Editable Predictions）的理论延展：论文在附录进一步将框架升级为允许执行至多 \(K\) 次删除、插入和修改编辑距离邻域，成功将假阳性也纳入了可搜索修复范畴，为更复杂的序列/组合决策问题提供了理论模板。
局限与展望¶
- 针对异构任务特性的预测模型依赖：当前理论极度依赖“大作业/短作业”的二元结构划分（以 \(\varepsilon T\) 为界），该性质高度契合极差最小化问题，但对于总完工时间之和（\(\sum C_j\)）或带流转约束的流水车间调度难以直接套用。
- 合成误差分布与真实 ML 模型漂移的差距：实验部分主要通过人为设定误报率与漏报率随机生成预测，未在真实生产调度轨迹（如集群 GPU 作业 trace 配合真实神经网络预测器）上端到端检验，实际部署时的非独立同分布噪声可能引入更复杂的局部过载。
- 未来方向：探索结合多项式时间无监督预筛选的自适应预算分配机制，以及将该框架拓展到在线到达（Online Arrival）与具有优先权约束的广义生产调度系统。
相关工作与启发¶
- vs Antoniadis et al. (ICLR 2025)：Antoniadis 等人构建了基于对偶拟阵/选集问题的线性权值学习增强框架，但无法处理极大化单机负载的非线性 Min-Max 极差目标。本文针对调度中的结构重任务设计了自适应阈值残差 LP，填补了这一理论空白。
- vs Lenstra, Shmoys & Tardos (Mathematical Programming 1990)：LST 确立了 2 近似和针对常数 \(m\) 的 \((1+\varepsilon)\) 枚举搜索。本文将 LST 算法作为健壮性底座，通过预测引导将重任务枚举范围自 \((n+1)^{m/\varepsilon}\) 缩减为 \((mn)^K\)，消除了对 \(m\) 固定的强依赖。
- vs Mordechai (2015)：Mordechai 给出了依赖参数 \(k = |\{(i,j) \mid p_{ij} > \varepsilon T\}|\) 的固定参数近似方案（耗时 \(O(2^k \cdot \mathrm{poly})\)）。本文则是在预测指导下只对预测未命中的残余量进行参数化恢复，即使原始大任务总数 \(k\) 很大，只要预测质量较好，预算 \(K \ll k\) 即可达成近最优。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次解决调度极差学习增强近似算法的开放理论难题，设计了全新的局部化大作业搜索与阈值松弛 LP。
- 实验充分度: ⭐⭐⭐⭐ 包含多机型规模、独立/关联加工时间分布以及全维度误报率/漏报率消融，真实工业生产 trace 评测作为未来拓展。
- 写作质量: ⭐⭐⭐⭐⭐ 理论证明结构极为严整，内外层算法解耦清晰，定理与推论层层递进。
- 价值: ⭐⭐⭐⭐⭐ 具有里程碑式的理论价值与极佳的实用算力换精度特性，为离线 NP-难问题融入 ML 预测树立了标杆。