arXiv:2605.23957cs.AIcs.LG2026-05被引 1

用低成本标签训练智能调度器,自动选最优规则。

Low-Cost Labels, Reliable Choices: Rollout-Calibrated Hyper-Heuristics for Job Shop Scheduling

  • 用滚动回放标签+邻居不确定性估计优化选择策略
  • 在合成数据上平均误差比随机调度低10倍以上
  • 适合需要稳定可靠调度的工业场景

学习辅助的超启发式方法可在保持构造性作业车间调度可行性和可解释性的前提下,动态选择调度规则。其主要计算开销在于生成监督标签,而非模型拟合,因为每个标签通常需从部分调度出发回放候选规则。本文研究了标签成本与可靠性问题:学习到的选择器不应在无足够可信收益时切换至弱规则。提出的选取器采用归一化后悔值的回放标签、上下文KNN不确定性估计,并引入仅当预测收益超过调整后阈值才激活的门控机制。同时通过调节回放深度与广度,评估成本-质量权衡。在合成作业车间实例上,该门控选择器在所有学习型选择器中实现最低均值相对偏差(RPD),性能接近最佳固定调度规则,且将随机超启发式(Random-HH)的均值RPD降低一个数量级以上。

原文摘要 · Abstract (English)

Learning-assisted hyper-heuristics can select among dispatching rules while preserving the feasibility and interpretability of constructive Job Shop Scheduling Problem (JSSP) heuristics. Their main computational cost lies in label generation rather than model fitting, since each supervised label usually requires rolling out candidate rules from a partial schedule. We study this label-cost problem together with a reliability problem: a learned selector should not switch away from a strong default rule unless the predicted gain is credible. The proposed selector uses regret-normalized rollout labels, a contextual KNN uncertainty estimate, and a gate that acts only when the predicted improvement exceeds an uncertainty-adjusted margin. We also vary rollout depth and breadth to measure the cost-quality trade-off. On synthetic JSSP instances, the gated selector achieves the lowest mean RPD among learned selectors, remains close to the best fixed dispatching rule, and reduces Random-HH mean RPD by more than an order of magnitude.

调度优化超启发式机器学习工业应用

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