R-ConstraintBench: Evaluating LLMs on NP-Complete Scheduling

📄 arXiv: 2508.15204v1 📥 PDF

作者: Raj Jain, Marc Wetter

分类: cs.AI

发布日期: 2025-08-21

💡 一句话要点

提出R-ConstraintBench以评估LLMs在NP完全调度问题上的表现

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 调度问题 大型语言模型 资源约束 可行性评估 约束交互 数据中心迁移 有向无环图

📋 核心要点

  1. 现有方法在高约束条件下评估LLMs的可靠性不足，尤其是在复杂调度问题中。
  2. R-ConstraintBench框架通过逐步增加约束，系统性地评估LLMs在资源约束项目调度问题上的表现。
  3. 实验结果表明，模型在简单优先级约束下表现良好，但在复杂约束交互中性能显著下降，揭示了约束交互的影响。

📝 摘要（中文）

有效的调度在资本项目、制造、物流和IT舰队过渡等多个领域中至关重要。然而，现有的大型语言模型（LLMs）在高约束条件下的推理能力尚未得到充分评估。为此，本文提出了R-ConstraintBench，这是一个可扩展的框架，用于评估模型在资源约束项目调度问题（RCPSP）上的表现。该框架通过线性增加约束的方式逐步增加非冗余的优先级约束，并引入停机时间、时间窗口和选择性约束。通过在数据中心迁移场景中的实例化，我们评估了多种LLMs的可行性和错误分析，识别出与失败最相关的约束类型和降级阈值。实证结果表明，强模型在仅有优先级的有向无环图（DAGs）上表现接近上限，但在停机时间、时间窗口和选择性约束交互时可行性表现显著下降，表明约束交互是主要瓶颈。

🔬 方法详解

问题定义：本文旨在解决大型语言模型在高约束调度问题中的可靠性评估不足，尤其是在资源约束项目调度问题（RCPSP）中，现有方法未能充分揭示模型的推理能力和局限性。

核心思路：R-ConstraintBench框架通过逐步增加非冗余优先级约束，结合停机时间、时间窗口和选择性约束，系统性地评估LLMs的表现，旨在揭示约束交互对模型性能的影响。

技术框架：该框架包括多个阶段：首先构建有向无环图（DAGs），然后逐步引入约束，最后进行可行性和错误分析，以评估模型在不同约束条件下的表现。

关键创新：R-ConstraintBench的创新在于其可扩展性和系统性评估方法，通过线性增加约束的方式，揭示了约束交互对模型性能的影响，这在现有文献中尚属首次。

关键设计：框架设计中，关键参数包括约束的类型和数量，损失函数用于评估可行性，模型结构则基于现有的LLMs进行调整，以适应调度问题的特定需求。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果显示，强模型在仅有优先级约束的DAGs上表现接近上限，但在引入停机时间、时间窗口和选择性约束后，模型的可行性性能显著下降，揭示了约束交互的影响。此发现强调了在高约束条件下评估LLMs的重要性。

🎯 应用场景

R-ConstraintBench的研究成果在多个领域具有潜在应用价值，尤其是在需要高效调度的资本项目、制造业和IT迁移等场景。通过评估LLMs在复杂调度问题上的表现，可以为实际应用提供更可靠的决策支持，推动智能调度系统的发展。

📄 摘要（原文）

Effective scheduling under tight resource, timing, and operational constraints underpins large-scale planning across sectors such as capital projects, manufacturing, logistics, and IT fleet transitions. However, the reliability of large language models (LLMs) when reasoning under high-constraint regimes is insufficiently characterized. To address this gap, we present R-ConstraintBench, a scalable framework that evaluates models on Resource-Constrained Project Scheduling Problems (RCPSP), an NP-Complete feasibility class, while difficulty increases via linear growth in constraints. R-ConstraintBench incrementally increases non-redundant precedence constraints in Directed Acyclic Graphs (DAGs) and then introduces downtime, temporal windows, and disjunctive constraints. As an illustrative example, we instantiate the benchmark in a data center migration setting and evaluate multiple LLMs using feasibility and error analysis, identifying degradation thresholds and constraint types most associated with failure. Empirically, strong models are near-ceiling on precedence-only DAGs, but feasibility performance collapses when downtime, temporal windows, and disjunctive constraints interact, implicating constraint interaction, not graph depth, as the principal bottleneck. Performance on clean synthetic ramps also does not guarantee transfer to domain-grounded scenarios, underscoring limited generalization.