# 核心算法、数学模型与工程边界

## 统一模型

`scheduling/` 与企业领域包解耦。输入为任务集合 `V`、有向前置边 `E`、独占资源集合 `R` 和可选目标窗口 `T`。任务 `i` 有整数时长 `dᵢ > 0`、资源 `rᵢ ∈ R` 和整数优先级；边 `j → i` 意为 `j` 完成后才能开始 `i`。时间从 0 开始，所有输入使用调用方约定的同一单位。任务不可抢占，每项只使用一个容量为 1 的资源；不同资源可以并行。

求开始时间 `sᵢ ≥ 0`，结束时间 `fᵢ = sᵢ + dᵢ`，满足每条边 `sᵢ ≥ fⱼ`，且任意 `rᵢ = rⱼ` 的两项任务区间 `[sᵢ,fᵢ)` 与 `[sⱼ,fⱼ)` 不重叠。目标为最小化 `Cmax = maxᵢ fᵢ`，空任务集定义 `Cmax = 0`。若给出目标 `T`，`Cmax ≤ T` 表示这份排程达标。最长依赖路径长度 `Lpath` 与最大单资源总负载 `Lresource = maxᵣ Σᵢ:rᵢ=r dᵢ` 构成下界 `LB = max(Lpath,Lresource)`；`LB > T` 可证明目标不可达，`LB ≤ T` **不能**证明可达。

## 从输入到可验证结果

1. `validate_problem` 拒绝重复/缺失 ID、非正时长、未知资源、重复边、自依赖及环。Web 导入首先通过版本化 JSON 校验，再调用 MoonBit 引擎。单独的拓扑排序仅解决依赖次序，无法给出资源占用和完成窗口。
2. `StableTopological`、`RecoveryHeuristic`、`CriticalPath` 以不同就绪任务优先规则构造活动列表；同一串行解码器把每项安排在前置完成后、其独占资源的最早可行空档。因此即使列表中较晚出现，也可能填入更早的空档。详细平局规则见[通用接口](scheduling-interface.md)。
3. `optimize_schedule` 比较三种基线，取工期最短者作为保底。另构造一个按剩余依赖路径、资源总负载及优先级排序的自适应种子；在预算内尝试相邻任务交换，仅评估保持前置可行的列表，且只接受严格缩短 `Cmax` 的候选。`budget = 0` 禁用局部搜索，仍可保留自适应种子。输出候选评估次数、接受次数、初始工期和下界。
4. `validate_schedule` 独立于生成算法，重验任务完整性、前置关系、资源区间、时长和可选目标。适配器在评估目标时使用无目标约束的候选排程，再单独报告是否达到目标，避免把“本次启发式未达标”误称为不可行证明。
5. `exact_reference` 对最多 8 项的实例在节点预算内枚举可行活动列表；**仅完整搜索结束**才标记 `proven_optimal` 并可计算最优性差距。其活动列表与串行生成的适用依据见[精确参照说明](exact-reference.md)。更大实例的最优性未知。

三种基线与预算搜索都受独立约束校验。数组扫描和资源空档查找尚未优化为专用索引；搜索预算限制候选数，不保证找到全局最优，也不提供多资源、抢占、动态到达或概率模型。

## 超出拓扑排序的职责与可核查案例

`examples/recovery_window` 有总计 70 分钟的任务，依赖与独占资源约束下实际窗口为 45 分钟；不同资源并行，最长依赖路径下界为 30 分钟，最大资源负载下界为 35 分钟。程序输出逐任务起止时间，并区分下界与实际计划。仅输出拓扑序无法求这 45 分钟窗口。`examples/ci_pipeline` 把七个阶段映射到三个 Runner，调用同一通用核心比较三种基线与预算搜索，而不在适配器复制调度算法。

`local-order-trap` 是独占资源顺序的反例：共享资源上的 `a(10)` 后接独立资源上的 `c(1)`，`b(1)` 后接独立资源上的 `d(8)`。先完成 `b` 可让 `d` 与 `a` 并行，工期为 12；原始基线最佳为 19。预算搜索在 10 次候选内找到 12，小实例精确枚举证明其最优。该案例说明**同一 DAG 的合法拓扑次序可能带来不同工期**，也说明本项目核心必须负责资源空档解码、候选选择、目标评估和合法性证明。它不证明预算搜索在所有图上有效。

## 消融与适用条件

`optimize_schedule_with_features(problem, budget, critical_path_priority, resource_load_awareness, local_search)` 是实验开关，每次关掉一个自适应机制；三种基线保持不变。完整 6 组 × 3 种子实验中，关闭三项机制各自都没有改变最终工期；定向 `local-order-trap` 中关闭局部搜索会从 12 增至 19。**当前没有证据证明关键路径和资源负载排序在这组样本上有独立边际收益。** 基线回退会掩盖较弱候选的影响，资源热点可能使排序无关紧要。保留两项低成本种子规则是待进一步数据验证的工程选择；后续真实任务图若仍无收益，应删除或替换。完整原始数据和复现命令见[实验报告](benchmark-report.md)。

## 架构、API 与迁移

`core.mbt` 至 `auth.mbt` 保存原有服务、BIA、故障、演练等领域能力；`adapters/recovery` 和 `adapters/pipeline` 单向依赖 `scheduling/`。原 `plan_recovery` 接口和行为保留，新 `analyze_recovery` 是增量路径；没有把 RTO/RPO 强塞进通用任务。`web/engine` 是 MoonBit 到 ESM 的 JSON 边界，静态 Web 从 `web/engine.mjs` 调用相同领域和调度操作。命令行示例、Web 页面和基准分别是三种调用入口；它们共享核心语义。

调度 Web 导入格式的机器可读约束见 [`schema.v1.json`](../web/scenarios/schema.v1.json)，字段及操作见[调度工作区](scheduling-workspace.md)。版本 1 输入仅有任务 ID、时长、资源、优先级、前置 ID、可选目标窗口与时间单位；旧服务库存与 BIA 浏览器数据不是该格式，需要调用方显式映射。原有浏览器本地存储与 `plan_recovery` 不作自动迁移。对于新 API，调用方须检查错误与 `target_met`，并保留自己的单位和目标来源。此边界可防止把演示估算误当成实际 RTO 承诺。