一种异构环境下结合LLM进化先验与下界奖励的DAG工作流强化学习调度方法

本项目针对异构环境下 DAG 工作流中任务依赖与设备能力耦合的问题，提出由大语言模型 进化先验引导的强化学习调度方法。LLM4AD 搜索得到的调度表达式提供任务与设备选择偏好； PPO 残差在训练中根据任务与资源状态调整决策，并利用下界增量奖励优化 makespan。 项目提供 openEuler Docker 交互演示，可一键启动、自选工作流，查看与 HEFT 的指标对比、 设备活跃利用率、逐任务分配和甘特图。

方法命名

论文、图表和 README 统一使用以下展示名；命令行保留稳定的英文标识。

展示名	命令行标识	Reward	Heuristic prior	用途
HEFT	heft	—	—	归一化基线
PEFT	peft	—	—	外部启发式基线
CP-SAT	cp_sat	—	—	限时精确参考
BC-MLP	bc_mlp	HEFT imitation	否	行为克隆基线，不执行 PPO
Vanilla MLP-PPO (heuristic-prior)	vanilla_mlp_ppo	makespan increment	是	PPO 基准
LB-reward MLP-PPO (heuristic-prior)	lb_mlp_ppo	lower-bound increment	是	同种子手工先验对照
No-prior MLP-PPO	no_prior_mlp_ppo	lower-bound increment	否	prior 消融
LLM-evolved prior + LB-reward MLP-PPO	llm_prior_ppo	lower-bound increment	固定 LLM4AD 先验	主算法

Vanilla、手工先验 LB-reward 与 No-prior 构成原有的 reward/prior 消融。 LLM 主算法与对应训练 seed 的手工先验 LB-reward 使用相同划分、LB reward、 50 次更新及合法动作约束；同种子配对结果比较两种完整策略的调度表现。

MDP 定义

要素	本项目中的定义
状态 (s_t)	任务、节点、任务—节点对和全局特征，以及依赖关系、资源可用时间和合法动作 mask
动作 (a_t)	从 ready task × feasible node 中选择一个任务—节点对
状态转移	完成一次分配后更新任务起止时间、节点可用时间、已调度集合和后继任务就绪状态
奖励	Vanilla 使用归一化 makespan 增量；LB-reward 和 No-prior 使用 lower-bound 增量
终止条件	DAG 中全部任务完成分配
优化目标	最小化 makespan；统一报告 method_makespan / HEFT_makespan

训练和评测共用合法动作约束。统一 evaluator 同步报告 invalid_actions_filtered，用于核对策略输出的合法性。

策略结构

LLM 主算法

固定先验的任务分数为 1.5 × upward_rank + 0.8 × EFT_sufferage，节点分数为 −2.5 × estimated_finish + 0.3 × processing_time。任务分数在 ready tasks 内、 节点分数在每个任务的 feasible nodes 内分别中心化并按标准差归一化，温度为 1， logit 限幅为 3。PPO 学习零初始化的残差，确定性推理按任务、节点两级选动作； 非法动作仍由 mask 排除。实现和完整特征契约见 src/drl_scheduler/algorithms/llm_normalized_aggregate_mlp_ppo/README.md。

上图按先验发现与调度策略两段展示方法：LLM4AD 搜索并选定表达式，训练时固定该表达式； 状态特征同时进入先验打分和 PPO 残差分支，两者融合后经合法动作 mask 选择任务—节点对。 环境以 lower-bound increment reward 更新 PPO。 图的源文件为 SVG 格式。

手工先验消融网络

原有 PPO 对每个候选任务—节点对拼接 12 维任务特征、12 维节点特征、 11 维配对特征和 6 维全局特征，形成 41 维输入。共享 MLP 41 → 128 → 128 → 1 为候选对生成 logit，隐藏层使用 Tanh。

启用 heuristic prior 时，logit 叠加任务 upward rank、预计完成时间和处理时间 构成的先验项。No-prior 关闭该先验项及对应手工提示特征。 legal_action_mask 将非法动作置为负无穷。

原有 PPO 的 Critic 对任务特征和节点特征分别做均值池化，再与 6 维全局特征 拼接为 30 维状态表示。MLP 30 → 128 → 128 → 1 输出状态价值，供 GAE 和 PPO value loss 使用。原三种 PPO 共用 Actor 和 Critic 结构。

实现要点

调度器每一步从 ready task × feasible node 合法动作集合中选择任务—节点对， 目标是最小化 makespan。主算法 llm_prior_ppo 将固定、归一化的 LLM4AD 先验 与可训练 PPO 残差结合，使用 lower-bound increment reward。实验规模为 RNC50、RNC100、RNC300。

• 主算法用任务和条件节点两级 MLP 残差打分。DAG 约束、就绪状态和调度代价 由环境与观测特征提供。
• 训练与推理共用动作 mask；训练使用批量张量环境，统一 evaluator 逐实例复核 调度合法性。
• checkpoint 按 validation30 选择，test30 用于最终报告。
• HEFT、PEFT、CP-SAT、BC-MLP 和 PPO 均实现同一策略接口，进入同一评测链路。

项目结构

项目根目录/
├─ README.md                   项目、运行与测试说明
├─ pyproject.toml              Python 安装与测试配置
├─ LICENSE                     开源许可证
├─ src/
│  ├─ drl_scheduler/           调度器、算法和 cli/ 统一入口
│  ├─ llm4ad_next_adapter/     LLM 先验适配器
│  ├─ custom_evaluator.py      赛题评测接口兼容模块
│  └─ configs/                 算法、数据、运行和依赖配置
├─ tests/
│  ├─ data/hetero_json/        三个规模的固定工作流
│  ├─ benchmark_results/       冻结评测结果和图片
│  └─ reproduction/            冻结实验复现脚本
├─ docs/                       决赛提交 PDF 材料
├─ demo/                       openEuler Docker 演示与 checkpoints/ 部署模型
└─ presentation/               决赛 PPT 和演示视频

核心类职责

类	文件	职责
SchedulingEnv	environment.py	维护单个 DAG 的合法动作、状态转移和 makespan
VectorizedSchedulerEnv	tensor_env/environment.py	并行推进批量环境并生成 PPO 所需的 mask 与 reward
TensorWorkflowDataset	tensor_env/dataset.py	加载固定数据划分并构造张量工作流
SchedulerPolicy	evaluator.py	定义逐步选择任务—节点对的策略接口
VectorizedMLPPolicy	torch_mlp_ppo/vectorized_policy.py	实现三种 PPO 共用的 MLP actor-critic
VectorizedMLPCheckpointPolicy	torch_mlp_ppo/evaluator_policy.py	加载 checkpoint 并接入统一 evaluator
HEFTSchedulerPolicy / PEFTSchedulerPolicy / CPSATSchedulerPolicy	algorithms/*/policy.py	封装启发式和限时精确基线

逐步调度策略使用 reset/select_action；CP-SAT 与部署模型通过 solve_instance 返回完整调度。两类策略均进入统一评测器。

端到端流程

graph LR
    A[训练验证测试数据] --> B[数据准备]
    B --> C[训练 LLM 主算法与对照方法]
    C --> D[验证集选择模型]
    D --> E[统一评测器]
    A --> E
    F[外部调度基线] --> E
    E --> G[逐实例与逐种子结果]
    G --> H[统计图表]
    G --> I[openEuler验证]

数据隔离

数据集	Train	Validation	Test
RNC50	120	30	30
RNC100	120	30	30
RNC300	120	30	30

• rand0000–rand0119：训练。
• rand0120–rand0149：验证和 checkpoint 选择。
• rand0150–rand0179：最终测试。

实验结果

每个工作流先计算 method_makespan / HEFT_makespan，mean_ratio 为这些比值的平均值， 越低越好。

正式 test30 主结果

所有学习方法先在 validation30 上选择 checkpoint，再由统一 evaluator 评测固定 test30。下表中的 LLM 行为每个规模按 validation30 选出的部署检查点结果。

方法	RNC50	RNC100	RNC300
HEFT	1.0000	1.0000	1.0000
PEFT	1.1175	1.2681	1.3989
CP-SAT	0.7859 (27/30)	0.7915 (26/30)	0.9308 (1/30)
BC-MLP	1.1940	1.1959	1.0660
Vanilla MLP-PPO (heuristic-prior)	0.8605	0.8662	0.8831
LB-reward MLP-PPO (heuristic-prior)	0.8409	0.8582	0.8592
No-prior MLP-PPO	0.8843	0.9078	0.9192
LLM-evolved prior + LB-reward MLP-PPO	0.8298	0.8421	0.8589

点表示测试实例的均值，误差线表示 95% t 置信区间；LLM 行的浅绿色阴影标出其置信区间。 浅蓝色背景对应优于 HEFT 的比值范围。CP-SAT 括号内为限时求解得到有效解的实例数， 其均值按有效子集计算。基线逐实例记录位于 tests/benchmark_results/formal/， LLM 部署结果位于 llm_prior_test30/。

10-seed 稳定性与消融

四种 PPO 使用 seeds 42–51，在固定 test30 上评测。表中为 10 个训练 seed 的 均值 ± 95% t 置信区间；每个点代表一个 seed 的 test30 均值。

规模	Vanilla MLP-PPO (heuristic-prior)	LB-reward MLP-PPO (heuristic-prior)	No-prior MLP-PPO	LLM-evolved prior + LB-reward MLP-PPO
50	0.8709 ± 0.0098	0.8556 ± 0.0096	0.9003 ± 0.0225	0.8288 ± 0.0026
100	0.8778 ± 0.0105	0.8701 ± 0.0098	0.9293 ± 0.0117	0.8522 ± 0.0035
300	0.9034 ± 0.0119	0.8705 ± 0.0109	0.9465 ± 0.0137	0.8617 ± 0.0051

箱体表示四分位区间，圆点表示独立训练 seed；数值越低越好。图中展示 Vanilla、 No-prior 和 LLM 主算法的分布。下表进一步用相同训练 seed 的手工先验模型 计算配对差值，给出直接对照。

规模	LLM 先验均值 ± 95% CI	对应种子手工先验均值 ± 95% CI	配对差值均值 [95% CI]	seed 胜/平/负
50	0.8288 ± 0.0026	0.8569 ± 0.0070	−0.0281 [−0.0354, −0.0208]	10/0/0
100	0.8522 ± 0.0035	0.8701 ± 0.0070	−0.0180 [−0.0265, −0.0094]	10/0/0
300	0.8617 ± 0.0051	0.8705 ± 0.0078	−0.0088 [−0.0198, +0.0022]	7/0/3

配对差值为 LLM 减手工先验，越低越好。加粗表示该行最低均值。RNC50/100 的 配对 95% 区间低于零；RNC300 的配对均值差为 −0.0088，区间跨零。 逐 seed、逐工作流结果及胜负分布见 llm_prior_multiseed_test30/。

LLM 先验的训练收敛示例

下图展示 RNC300 的四种 PPO 方法收敛示例。曲线表示截至每次更新的验证集最优 makespan / HEFT，数值越低越好。LLM 主算法在第 4 次更新达到 0.95， 手工先验 LB-reward MLP-PPO 在第 15 次达到，Vanilla MLP-PPO 在第 50 次达到； No-prior MLP-PPO 在 50 次更新内未达到。图中纵轴放大显示 0.885–1.085 区间。 逐更新数据。

代表性调度

rand0167_hetero 上，LLM 主算法将 makespan 从 HEFT 的 81.36 s 降至 66.06 s，降低 18.8%，ratio 为 0.8119。

图中每个色块表示一个任务的执行区间，虚线表示最终 makespan。对应调度记录位于 tests/benchmark_results/schedule_case_rnc50.csv。

同一工作流上，按每台设备的任务执行总时长除以该方法的 makespan 计算活跃利用率。 八台设备的平均值为 LLM 主算法 57.1%、HEFT 46.4%。

项目已在 openEuler 24.03 LTS SP3 x86_64 虚拟机完成 CPU 兼容性验证： 46 项通用测试通过、12 项 CUDA 专用测试显式跳过，RNC50 的 7 方法 × 3 实例 smoke 产生 21 条记录。结果位于 tests/benchmark_results/openeuler/。

交互演示

这是 openEuler 容器中的 CPU 模拟调度演示，使用已有模型推理。页面可选择 RNC50、RNC100、RNC300 内置任务流或上传同格式 JSON，选择调度方法后运行。 结果展示 makespan、相对 HEFT 的比值、设备活跃利用率、逐任务分配和甘特图。

从仓库根目录启动：

docker compose -f demo/compose.yaml up --build -d

打开 http://localhost:8501。输入格式、结果下载和命令行用法见 demo/README.md。

复现固定 LLM 先验实验

llm_prior_ppo 使用固定的归一化 LLM4AD 先验、LB increment reward 和 50 次 PPO 更新。 每个训练 seed42–51 依据 validation30 选择最佳更新，再在独立 test30 上与 相同训练 seed 的手工先验 LB-PPO 配对。完整结果见 逐 seed 与逐工作流记录。

每个规模按验证集选择一个检查点的部署评测 与上述 10-seed 配对统计分别展示。实验依据汇总于 LLM 主算法证据说明。

训练与部署模型评测命令见分阶段复现。

环境

要求 Python 3.11。CUDA 环境：

python -m venv .venv
.\.venv\Scripts\Activate.ps1
python -m pip install --upgrade pip
python -m pip install -r src/configs/requirements/cuda.txt
python -m pip install -r src/configs/requirements/analysis.txt
python -m pip install -e . --no-deps

实验命令

一键训练与部署评测

以下命令依次执行数据准备、LLM 主算法的三规模 10-seed 训练、仓库附带的 验证集选定部署模型的 validation/test 统一评测，以及图表生成：

python -m drl_scheduler.cli all

all 的默认值为 RNC50/100/300、seeds 42–51、PPO 50 次更新、 64 个并行环境和 256 的 PPO minibatch。train 单独运行时默认 RNC50、seed42。 设备使用 auto；PPO 正式训练需要 CUDA，openEuler CPU 虚拟机用于兼容性与 smoke 验证。

默认命令包含 30 个 LLM 训练运行，并评测仓库附带的全部基线部署检查点。 新训练的 30 个 seed 模型保存在 outputs/runs/；冻结的 10-seed 配对结果与 验证集选定的部署检查点保存在各自目录。配对结果可运行 python tests/verify_llm_prior_results.py 从逐 seed JSON 重新核对。 中断后可直接重跑，已有 training_summary.json 和 checkpoint 的运行会复用。

运行时文件与仓库附带的冻结结果分别列于下方主要产物。

分阶段复现

准备三规模张量缓存和 train-only HEFT 示范：

python -m drl_scheduler.cli prepare --tasks 50 100 300

正式训练 LLM 主算法，统一 seeds 42–51：

python -m drl_scheduler.cli train `
  --methods llm_prior_ppo `
  --tasks 50 100 300 `
  --seeds 42 43 44 45 46 47 48 49 50 51 `
  --updates 50

如需重新训练原有手工先验消融和 BC 基线，显式指定方法：

python -m drl_scheduler.cli train `
  --methods bc_mlp vanilla_mlp_ppo lb_mlp_ppo no_prior_mlp_ppo `
  --tasks 50 100 300 `
  --seeds 42 43 44 45 46 47 48 49 50 51 `
  --bc-epochs 20

统一评测和绘图：

python -m drl_scheduler.cli evaluate --tasks 50 100 300
python -m drl_scheduler.cli figures
python -m pytest -q

CP-SAT 默认对 RNC50 限时 30 秒，对 RNC100/300 限时 60 秒。

主要产物

类别	位置	内容
原始证据与基线	source/、formal/	冻结实验记录、正式 test30 基线逐实例结果
LLM 多种子对照	llm_prior_multiseed_test30/	三规模、10 个训练 seed 与同种子手工先验的配对结果
部署模型评测	llm_prior_test30/、validation/	LLM 部署检查点的 test30 结果、原有方法的 validation30 结果
图表	figures/	PNG、PDF、SVG 图表及 QA.md
部署检查点	demo/checkpoints/	模型文件、selection.json 验证集选择记录与 manifest.json SHA-256 清单
新运行结果	tests/data/tensor_cache/、tests/data/demonstrations/、outputs/runs/、tests/benchmark_results/latest/	数据缓存、训练示范、训练日志与最新评测结果；运行后生成
交互演示	demo/README.md、demo/compose.yaml	openEuler Docker 启动说明；结果写入 outputs/demo/runs/

赛题内容与仓库位置

内容	位置
DAG 建模与调度方法	本页“MDP 定义”“策略结构”及方法文档
启发式、行为克隆与 DRL 对比	正式实验协议、formal/
三规模数据与独立划分	tests/data/hetero_json/、数据隔离
10-seed 统计与图表	llm_prior_multiseed_test30/、figures/
可复现训练与评测	实验命令、src/drl_scheduler/cli/
可选任务流调度演示	demo/README.md、demo/compose.yaml
openEuler 环境验证	验证记录、openeuler/

数据和系统模型源自 AasishKumarSharma/grapheonrl-benchmark 及其 STG JSON 数据集。