# RCPSP v2 五算法实验报告

## 数据和方法

2026-10-23 在同一台 Windows x64 主机上运行 [可复现脚本](../benchmark/rcpsp/README.md)。使用三个完整但人工构造的 CI、恢复、项目场景，以及官方 PSPLIB J30/J60 的五个固定实例。后者由原始 `.sm` 的单模式时长、四种可再生资源容量/需求、全部前置边无损转换；原始数据与官方界的 SHA-256 固定在 `selection.json`。MoonBit 三种排序和预算 30 次的局部搜索，与单线程、固定种子、5 秒上限的 OR-Tools 9.15.6755 比较。各输入每算法 3 次，共 120 行。所有可行候选均由独立 MoonBit 验证器检查；120 行中验证失败数为 0，可行率均为 100%。

下表每项工期在三次重复中一致。不同案例的时间单位不同，只能在同一行内比较。

| 案例 | Stable | Critical | Recovery | Budgeted | CP-SAT | 已证明最优/官方界 |
| --- | ---: | ---: | ---: | ---: | ---: | --- |
| CI（分钟） | 11 | 11 | 11 | 11 | 11 OPTIMAL | 11，由本次 CP-SAT 证明 |
| 恢复（分钟） | 8 | 8 | 8 | 8 | 8 OPTIMAL | 8，由本次 CP-SAT 证明 |
| 项目（天） | 11 | 12 | 12 | 11 | 11 OPTIMAL | 11，由本次 CP-SAT 证明 |
| `j301_1.sm` | 49 | 46 | 46 | 46 | 43 OPTIMAL | 官方已证明 43 |
| `j309_1.sm` | 100 | 96 | 96 | 91 | 83 OPTIMAL | 官方已证明 83 |
| `j3013_1.sm` | 75 | 64 | 64 | 63 | 58 FEASIBLE | 官方已证明 58；CP-SAT 本次未证明 |
| `j601_1.sm` | 80 | 77 | 77 | 77 | 77 OPTIMAL | 官方已证明 77 |
| `j609_1.sm` | 106 | 100 | 100 | 99 | 92 FEASIBLE | 官方下界 82、已知可行上界 87，未证明最优 |

## 机制与反例

单资源容量 1 的拓扑排序不足以表达这些结果。任务会同时占用多个可再生资源；资源容量在 `[start, finish)` 内逐时刻约束并行数；依赖、释放时间和硬截止又限制候选起点。CI 示例中 `compile-a` 需要 2 单位内存、`compile-b` 需要 3 单位，而容量只有 4，因此两项编译不能重叠，即使有两个 Runner。把内存容量升到 5 会改变可行并行区间；独立验证器会拒绝原容量下重叠的导入计划。这是资源容量机制产生的限制，不是拓扑排序能判断的结果。

预算局部搜索相对其零预算基线，在 `j309_1.sm` 减少 5 单位、`j3013_1.sm` 减少 1、`j609_1.sm` 减少 1；其余五例没有严格改进。它只探索可保持前置关系的相邻交换，不能保证找到更远的任务次序或全局最优。`j301_1.sm` 的 46 比已证明最优 43 高 6.98%；`j309_1.sm` 的 91 比 83 高 9.64%；`j3013_1.sm` 的 63 比 58 高 8.62%。这些是算法质量不足的公开反例，不应只展示与最优相等的案例。

`j609_1.sm` 是状态区分的关键。CP-SAT 5 秒只得到可行解 92，内部下界 59；官方更强的有效下界为 82，已有可行上界为 87。由于 87 小于本次 CP-SAT 的 92，不能把 92 称为最佳已知解，更不能把 87 称为最优。MoonBit 预算结果 99，相对官方已知上界高 13.79%，相对有效下界的界限差距为 20.73%；它的精确最优性差距仍未知。CP-SAT 在 `j3013_1.sm` 也仅给出 `FEASIBLE 58`，最优性证明来自 PSPLIB 官方记录，而非这次 5 秒运行。

`raw.csv`/`raw.json` 保留每次耗时、资源利用率、验证状态、求解状态、界、差距与完整排程。现场毫秒值会随机器负载变化；两张 SVG 是这次快照。实验未测生产故障处理效果，也未声称五个公开实例代表所有 RCPSP 分布。