相同并行机调度问题中契约验证的单提示大语言模型启发式合成的行为塌缩至最长处理时间调度

《Engineering Applications of Artificial Intelligence》：Behavioral collapse to longest-processing-time scheduling in contract-validated single-prompt large language model heuristic synthesis for identical parallel machine scheduling

　　

摘要

本文评估了大语言模型通过单提示词进行代码生成所产生的调度启发式方法，是具备行为多样性的、适用于工程专家系统部署的策略，还是退化为已知的经典规则。应用领域为相同的并行机器完工时间最小化问题（$P\|C_{\max}$），实验方案使用六个模型和三种提示词变体的540次生成结果，在锚定最长处理时间（LPT）调度启发式方法的单提示词、无修复设置下进行。一个五合同筛选漏斗用于判定可执行部署性，而通过筛选的调度器则在2160个实例的基准上，通过完工时间最大值指纹进行分类。在540次生成结果中，463次（85.7%）通过了所有合同；其中，463中有461次（99.6%）在基准上具有与最长处理时间调度等价的指纹，但这并不意味着分配方案相同或在测试实例之外具有等价性。唯一与基准不同的合规类别——即最长处理时间调度后接首次改进成对交换局部搜索——将对抗性实例上的平均精确遗憾值从5.02%降至0.53%。推理模式推理将可见标记成本增加了至少22.31倍，但并未增加行为多样性。事后锚点变异实验的结果更倾向于支持训练先验的解释而非纯粹的上下文内模仿，但并非因果证据。人工智能方面的贡献是：面向大语言模型代码合成的合同验证行为指纹筛选方法。工程方面的贡献是：一种依赖情境的专家系统调度验证协议，展示了单步合成在何种情况下足够、以及何时需要显式的算法结构或局部搜索。

引言

调度启发式方法是制造业、物流和计算基础设施等专家系统的核心，其设计质量直接影响运营成本和服务可靠性（Pinedo, 2016, Burke et al., 2013）。大语言模型（LLMs）使得通过单次应用程序编程接口调用即可请求可执行的调度代码成为可能（Liu et al., 2024, Romera-Paredes et al., 2024, Ye et al., 2024, van Stein and B?ck, 2025），但相关的部署问题在于行为层面而非语法层面：独立生成的调度器是否实现了不同的策略，还是以不同的代码形式重新表述了同一种熟悉的启发式方法？

这一问题对专家系统具有直接后果。如果单提示词合成要作为一种可行的知识获取机制，生成的启发式方法必须编码不同的调度策略，而非单一已知规则的语法变体。任何基于大语言模型的启发式方法管道，其有效性都依赖于一个在调度领域尚未直接检验过的假设：表观的代码多样性必须对应行为多样性。如果行为退化为单一主导策略，那么单步合成并未创建启发式方法组合，而是重新生成了一条已知规则，任何感知到的多样性都是虚幻的。

本文以相同的并行机器完工时间最小化问题（$P\|C_{\max}$，其中 $C_{\max}$ 表示最大完工时间）为研究对象，因为该问题兼具实际相关性和精确的行为参照标准。当 $m \geq 2$ 时，该问题是非确定性多项式时间难解的（NP-hard）（Garey and Johnson, 1979），但最长处理时间（LPT）调度是一个具有已知保证和已知弱项的经典基线（Graham, 1969, Coffman et al., 1978）。这一设置使得基准级别的完工时间最大值指纹可以进行精确比较：在所有基准实例上与LPT匹配意味着在这些实例上的完工时间相同，而非分配方案相同或普遍策略等价。更丰富的调度模式会引入额外的建模选择和较弱的参照策略，因此在此被视为边界条件而非主要的验证设置。

在六个大语言模型和三种提示词变体的540次生成结果中，均在严格的单提示词、零样本、无修复、全保留协议下，463个输出通过了五合同部署性漏斗。在这些合同合规的输出中，463中有461个（99.6%）在2160个实例的基准上具有与LPT调度等价的基准级别 $C_{\max}$ 指纹。这种退化具有可衡量的代价：在对抗性精确实例上，主导类别的遗憾值平均为5.02%，而唯一与基准不同的合规类别——LPT后接首次改进成对交换——将平均遗憾值降至0.53%。

为组织论证，本文回答四个研究问题：

1. RQ1：部署性。在 $P\|C_{\max}$ 的单提示词启发式方法合成中，合同合规的部署性如何随大语言模型和提示词变体而变化？

2. RQ2：行为退化。在合同合规的生成结果中，是否产生了行为多样性，还是输出退化为LPT等价调度行为？

3. RQ3：质量代价。在LPT结构上非最优的实例上，行为退化的可衡量质量代价是多少，以及该代价如何随实例情境而变化？

4. RQ4：诊断解释。观察到的退化现象更符合哪种解释：既有的训练先验效应还是所呈现基线的上下文内锚定效应？

本文的主要贡献包括五个方面：

1. 本文将行为指纹（实例空间分析、质量多样性及超启发式方法研究中已有的概念）改造为面向大语言模型生成调度器的部署导向筛选方法。新颖之处在于整合而非孤立的方法论：将合同验证的部署性漏斗与精确的全基准 $C_{\max}$ 指纹等价性检验相结合，首次应用于单提示词大语言模型合成设置中。

2. 据我们所知，本文首次提供了 $P\|C_{\max}$ 单提示词启发式方法合成中行为退化的合同验证实证刻画。

3. 本文通过在具有分支定界认证最优解（OPT）的子集上进行精确遗憾值分析，以及在完整基准上进行下界归一化的基线差距分析，量化了退化的质量代价，并将其转化为可操作的情境阈值。

4. 本文报告了一项结构化的事后锚点变异探测实验，其结果更符合训练先验的解释而非纯粹的上下文内锚定解释，同时明确不将该模式视为机制的确认性证据。

5. 本文表明行为指纹框架可以迁移到主要验证设置之外的边界探测中，同时也清楚地指出了这种迁移仍属初步的阶段。

本文其余部分组织如下：第2节将本研究置于先前工作的背景中，第3节研究方法论和第4节实验设置定义了协议及其操作化，第5节报告结果，第6节解释这些发现及其局限性，第7节总结全文。

各节摘要

相关工作

本研究处于四条研究脉络的交汇处：自动算法设计、大语言模型驱动的启发式方法生成、经典并行机器调度和行为多样性分析。本节回顾各脉络，权衡其贡献与局限性相对于研究问题的关系，并厘清由此产生的研究空白。

研究方法论

本节定义了所有论断赖以解释的实验协议，规范了问题范围、基准设计、提示词控制的合成体制、合同验证程序以及三层推论计划。图1总结了从生成到合同验证、行为指纹、质量代价分析以及后观察探测的流水线。图中标记的使用方式如下：D1–D3表示部署性分析，B1–B3表示行为退化……

实验设置

本节对第3节定义的协议进行操作化，记录了执行环境、模型访问权限和基础设施限定条件，这些条件对解释所报告的指标是必要的。

结果

本节按照第3.4.3节三层框架所规定的顺序报告实证发现：部署性（第5.1节）、行为退化（第5.2节）、质量代价（第5.3节）以及针对RQ4的后观察机制分析（第5.4节）。随后报告了一项针对从业者干预的稳健性研究（第5.5节），检验常见的轻量级提示词修改是否能打破观察到的LPT退化现象。质量比较仅在合同……之后进行解释

讨论

核心实证发现是：针对 $P\|C_{\max}$ 的合同合规单提示词合成在操作上是可行的，但行为上几乎趋于单一。本节解释该发现的含义而非重复数字，具体如下：首先，该退化意味着什么；其次，从业者应如何应对；最后，哪些局限性制约了论断的强度。这一排序保持了论文从发现到后果到范围的核心论证依赖关系。

结论

本文通过一个部署导向的协议评估了 $P\|C_{\max}$ 的合同验证单提示词大语言模型启发式方法合成，该协议将部署性、行为等价性、精确质量和机制分离开来。在六个模型（从前沿闭源模型到小型开放权重模型）和三种提示词变体的540次生成结果中，463个输出（85.7%）满足所有五项部署性合同，然而其中461个（99.6%）在基准级别上具有与LPT等价的 $C_{\max}$ 指纹，产生……

作者贡献声明（CRediT）

Achraf Ghorbel：撰写—原稿、验证、监督、方法论、调查。Nourchène Elleuch Ben Ayed：撰写—审阅与编辑、验证、方法论。Nassim Tinkicht：软件。Majed Bouchahma：软件。

利益冲突声明

作者声明不存在可能影响本文所述工作的已知竞争性经济利益或个人关系。

致谢

作者衷心感谢机构支持使本研究成为可能。

Achraf Ghorbel | Nourchène Elleuch Ben Ayed | Nassim Tinkicht | Majed Bouchahma

Higher Colleges of Technology, Computer Information Science, Sharjah, United Arab Emirates

（阿联酋沙迦，Higher Colleges of Technology，计算机信息科学系）