首次实现无重叠约束的界一致过滤，显著减少搜索节点数。
Towards Bound Consistency for the No-Overlap Constraint Using MDDs
- 基于MDD构建无重叠约束的界一致算法
- 在时间窗调度问题中减少搜索树节点数
- 与传统方法互补，适合复杂调度场景
实现无重叠约束的界一致已知为NP完全问题。为此，研究者提出了多项多项式时间紧化技术，如边查找、非首非尾推理和能量推理。本文首次提出针对无重叠约束的界一致算法。基于Ciré与van Hoeve定义的无重叠MDD，提取作业时间窗边界，可在MDD节点数的多项式时间内紧化起始与结束时间。为控制大小与时间复杂度，将MDD宽度限制在阈值内，形成松弛的MDD，可用于放松界一致过滤。在带时间窗和准时目标（1 ∣ r_j, d_j, d̄_j ∣ ∑E_j + ∑T_j）的排序问题上实验表明，即使设置宽度阈值，所提过滤仍比此前的优先级检测算法显著减少搜索树访问节点数。该过滤方法与经典传播方法具有互补性，在多个实例上大幅降低节点数和求解时间。
原文摘要 · Abstract (English)
Achieving bound consistency for the no-overlap constraint is known to be NP-complete. Therefore, several polynomial-time tightening techniques, such as edge finding, not-first-not-last reasoning, and energetic reasoning, have been introduced for this constraint. In this work, we derive the first bound-consistent algorithm for the no-overlap constraint. By building on the no-overlap MDD defined by Ciré and van Hoeve, we extract bounds of the time window of the jobs, allowing us to tighten start and end times in time polynomial in the number of nodes of the MDD. Similarly, to bound the size and time-complexity, we limit the width of the MDD to a threshold, creating a relaxed MDD that can also be used to relax the bound-consistent filtering. Through experiments on a sequencing problem with time windows and a just-in-time objective ($1 \mid r_j, d_j, \bar{d}_j \mid \sum E_j + \sum T_j$), we observe that the proposed filtering, even with a threshold on the width, achieves a stronger reduction in the number of nodes visited in the search tree compared to the previously proposed precedence-detection algorithm of Ciré and van Hoeve. The new filtering also appears to be complementary to classical propagation methods for the no-overlap constraint, allowing a substantial reduction in both the number of nodes and the solving time on several instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。