《研究点一实验结果与方法说明》

真实产线规模修正版：以公开水泥厂设备规模为依据，重新完成 Gate 2 规模实验闭环。

一、方法改动位置

原方法 / FSB-B&B

当前 B&B 节点→ 求解当前节点 LP 松弛→ 判断不可行 / 整数化→ 提取候选变量集合 C→ 按通用分支规则或 FSB 评分选择→ 选择分支变量 j*→ 正式分支并返回搜索

EASB 嵌入后

当前 B&B 节点→ 求解当前节点 LP 松弛→ 判断不可行 / 整数化→ 提取候选变量集合 C→ 将候选变量 j 映射到任务 i 和开始时间 t→ 计算能耗敏感评分 e_j：功率、电压影响、爬坡影响、任务深度→ 按 e_j 排序并优先选择高风险变量→ 选择分支变量 j*→ 正式分支并返回搜索

位置	原方法	本文新增
分支候选变量选择阶段	主要依据求解器通用规则或 FSB 评分	加入能耗敏感评分
使用信息	LP 松弛、变量分数性、SB 改善量等通用信息	功率、电压影响、爬坡影响、关键路径/任务深度
作用	选择一个变量进行分支	让高能耗、高约束风险、高关键性的变量优先分支
对搜索的影响	按通用规则展开搜索树	改变搜索树展开顺序，间接影响节点数、Gap 和运行时间

原 STN 代码负责建模并调用求解器。本文不把电压约束、爬坡约束本身作为方法创新，而是在求解过程的分支变量选择阶段插入能耗敏感评分模块。EASB 根据功率、电压影响、爬坡影响和任务深度给候选变量打分，通过改变分支顺序影响搜索节点、Gap 和运行时间。

二、真实产线规模依据与实例映射

规模设定改为从公开真实水泥厂设备规模出发，而不是任意增加一个 24 规模点。American Cement Association 对水泥生产过程的描述包含原料粉磨、窑煅烧形成熟料、熟料粉磨等环节；ZKG 报道的 Citeureup 水泥厂包含 9 条窑线、2 台原料磨和 3 台熟料磨；AECOM 的 Holcim 项目说明真实水泥厂可以以单条大型窑线和配套磨机组成完整生产系统。

依据	公开来源信息	本文实验抽象
生产过程	原料粉磨 → 窑煅烧 / 熟料形成 → 熟料粉磨	一条任务链包含 3 个任务：生料粉磨、煅烧、熟料粉磨
设备规模	Citeureup：9 条窑线、2 台原料磨、3 台熟料磨	设置 9 条窑线、2 个 raw mill 资源、3 个 clinker mill 资源
规模梯度	同一真实产线在不同排程窗口内会包含多批次任务	9×1、9×2、9×3 批次窗口，对应 9 / 18 / 27 条任务链
任务数量	每条任务链含 3 个工序任务	基础任务数为 27 / 54 / 81

说明：这里的“任务链”是调度抽象单元，表示一条窑线在一个批次窗口内的工序链，不等同于把 18 或 27 说成真实生产线数量。

来源： American Cement Association； ZKG Citeureup cement plant； AECOM Holcim Grassroots Cement Plant。

三、EASB 伪代码

输入：候选变量集合 C、任务功率、电压参数、爬坡参数、任务深度。

输出：分支变量 j*。

1. 求解当前 B&B 节点 LP 松弛。

2. 若 LP 不可行，则剪枝。

3. 若 LP 解已整数化，则更新可行解。

4. 否则提取候选分支变量集合 C。

5. 对每个候选变量 j，映射到任务 i 与开始时间 t。

6. 计算功率因子、电压影响因子、爬坡影响因子和关键路径/任务深度因子。

7. 加权得到能耗敏感评分 e_j。

8. 选择评分最高或高风险候选变量 j*。

9. 返回 j* 给求解器执行正式分支。

10. 继续 B&B 搜索。

四、复杂度推导

复杂度分析用于解释为什么 Full Strong Branching 计算成本高，以及 EASB 为什么能降低分支变量选择阶段的额外开销。这里的推导只对应求解层分支策略，不把电压约束、爬坡约束本身当作方法复杂度贡献。

符号	含义
T	B&B 搜索过程中访问的节点数。
n	某个节点上的候选分支变量数量。
L	一次 LP 探测或 LP 重新求解的平均成本。
k	增强版 EASB 中 Top-K 预筛选保留的候选变量数量，通常 k << n。

Full Strong Branching

FSB 在每个 B&B 节点对全部 n 个候选变量进行上、下两个方向的 LP 试探，因此单节点探测成本为：

C_FSB,node ≈ n · (2L) = 2nL = O(nL)

若搜索过程访问 T 个节点，则总复杂度为：

C_FSB,total = O(TnL)

稳定版 EASB

稳定版 EASB 不做 strong-branch 探测，而是对每个候选变量计算一次能耗敏感评分；功率、电压影响、爬坡影响和任务深度均可由变量 metadata 与实例参数常数时间取得。

S(j) = O(1)

C_EASB,node ≈ nS + n = O(n)

C_EASB,total = O(Tn)

增强版 EASB

增强版 EASB 先用能耗评分筛选 Top-K 候选变量，再只对 k 个候选变量执行 strong-branch 探测，因此把 LP 探测项从 nL 降为 kL。

C_sort = O(n log k)

C_probe ≈ k · (2L) = O(kL)

C_{enhanced,total} = O(T(n log k + kL))

方法	单节点主要操作	单节点复杂度	总复杂度	与实验指标的对应
Full Strong Branching	对全部候选变量做上下分支 LP 探测	O(nL)	O(TnL)	LP iterations 和运行时间可能较高
稳定版 EASB	对全部候选变量做能耗敏感评分并线性选择	O(n)	O(Tn)	降低分支选择开销，并通过搜索顺序影响 Gap、节点数和时间
增强版 EASB	Top-K 预筛选后只对 k 个变量做 strong-branch 探测	O(n log k + kL)	O(T(n log k + kL))	当 k << n 时减少 LP 探测量，但当前仅作为增强变体

结论口径：理论复杂度说明 EASB 能减少分支变量选择阶段的计算开销；实际是否带来更低运行时间、更低 Gap 或更少 LP iterations，仍以实验结果为准。当前论文主线采用稳定版 EASB，增强版仅作为变体/消融说明。

五、运行时间与 Gap 对比

图 1：不同任务链规模下各分支策略运行时间对比，单位为秒。9 任务链下四种方法均证明最优，EASB 用时 25s，低于 default 的 60s、most-infeasible 的 33s 和 full-strong 的 210s。18 和 27 任务链下 300s 均达到时间上限，因此这两个规模用于观察固定预算压力状态。

图 2：不同任务链规模下各分支策略 Gap 对比。9 任务链下 Gap 均为 0；18 任务链下 300s 四种方法 Gap 均约 0.707；27 任务链下四种方法均未证明最优，不能据此夸大 EASB 优势。

六、固定预算与延长预算验证

300s 用作统一固定计算预算，目的是比较同一资源限制下的求解状态、Gap 和可行解质量；它不代表大规模实例“必须在 300s 内解完”。因此在 18 任务链真实 profile 上补充 600s 验证，观察时间延长后各方法是否改善。

18 任务链下，300s 时四种方法 incumbent makespan 均为 128；600s 时 EASB 改善到 84，most-infeasible 为 121，default 和 full-strong 仍为 128。

18 任务链下，600s 时 EASB Gap 降至约 0.105，default 和 full-strong 约 0.684，most-infeasible 约 0.592。该结果说明延长时间后，EASB 在真实 profile 的固定时间解质量上更有优势。

图 3：固定 300s 下的求解状态。9 任务链可证明最优；18 和 27 任务链均能找到可行解但未证明最优，说明它们是真实 profile 下的压力规模，而不是随意设置的规模点。

七、排产结果示例图

该图为 18 任务链真实 profile 下 EASB 输出的实际调度方案，展示原料磨、窑线和熟料磨资源上的任务安排。

功率 / 电压 profile 用于展示该调度方案满足电力约束；本组最小电压为 0.9325，未低于模型阈值 0.93。

八、简短总结

方法位置EASB 嵌入分支变量选择阶段，不改变 B&B 主干。

真实规模按 9 条窑线、2 台原料磨、3 台熟料磨构造 9/18/27 任务链。

核心结果9 任务链下 EASB 最快；18 任务链 600s 下 EASB Gap 最低。

排产展示已给出 18 任务链 EASB 调度方案和功率 / 电压曲线。