图增强深度强化学习求解多目标无关并行机调度问题 Graph-Enhanced Deep Reinforcement Learning for Multi-Objective Unrelated Parallel Machine Scheduling
PPO+GNN框架解决多目标调度，同时最小化加权延误和总准备时间
前置知识
无关并行机调度问题（UPMSP）
UPMSP是一类经典调度问题，其中一组作业需要在多台并行机器上处理，关键特点是处理时间不仅取决于作业本身，还取决于具体分配到哪台机器，即$p_{jk}$对于不同的机器$k$可以任意变化。这反映了现实制造环境中机器因年龄、能力或专业化程度不同而存在异质性的场景。本文进一步考虑了释放日期$r_j$（作业最早可开始时间）、机器资格约束$M_j \subseteq M$（限制哪些机器可以处理特定作业）以及序列依赖和机器依赖的准备时间$s_{ijk}$。
理解UPMSP的定义和约束是理解本文研究问题的基础，所有方法设计都围绕如何有效处理这些约束展开。
近端策略优化（PPO）
PPO是OpenAI提出的一种策略梯度强化学习算法，核心创新在于通过裁剪机制约束策略更新幅度，防止训练不稳定。具体来说，PPO在目标函数中引入裁剪参数$\epsilon$，限制新旧策略的概率比$r_t(\theta) = \frac{\pi_\theta(a_t|s_t)}{\pi_{\theta_{old}}(a_t|s_t)}$在$[1-\epsilon, 1+\epsilon]$范围内，从而避免过大的策略更新导致性能崩溃。相比REINFORCE等简单策略梯度方法，PPO在样本效率和稳定性之间取得了良好平衡。
PPO是本文的核心学习算法，其稳定性和在复杂控制任务中的有效性使其成为处理大规模调度问题的理想选择。
图神经网络（GNN）
GNN是一类专门处理图结构数据的深度学习架构，通过消息传递机制迭代聚合节点邻域信息，学习能够同时编码节点特征和图拓扑的强大嵌入表示。GNN的核心优势在于能够处理可变大小的输入，这对于组合优化问题尤其重要。本文使用的是GATv2（图注意力网络v2）变体，共4层，隐藏维度128，使用ReLU激活函数。
GNN是本文状态表示的关键组件，能够有效捕获作业、机器和准备状态之间的复杂关系，使智能体能够做出更全局化的决策。
多目标优化
本文需要同时优化两个相互冲突的目标：最小化总加权延误$TWT = \sum_{j=1}^{n} w_j \max(0, C_j - d_j)$和最小化总准备时间$TST = \sum_{k=1}^{m} \left( s_{0k(1)k} + \sum_{l=1}^{n_k-1} s_{k(l)k(l+1)k} \right)$。这两个目标存在内在冲突——优先处理一个目标往往会对另一个目标产生负面影响，因此需要设计特殊的奖励函数来引导智能体学习平衡两者。
多目标优化是本文的核心挑战，理解目标间的冲突关系对于理解方法设计和实验结果至关重要。
异构图表示
异构图是包含多种类型节点和多种类型边的图结构。本文设计的异构图包含三类节点：作业节点（特征包括权重$w_j$、处理时间、截止日期等）、机器节点（特征包括当前状态、最后处理的作业等）和准备节点（表示不同的准备配置）。边类型包括：作业-机器边（连接可处理该作业的机器，特征为处理时间$p_{jk}$和准备时间）、机器-准备边、作业-准备边和准备-机器边（表示准备转换的代价）。
异构图设计是本文的关键创新之一，它使得GNN能够显式建模调度环境中不同类型实体之间的复杂关系。
研究动机
传统调度方法在处理多目标UPMSP时面临严重局限。启发式规则如ATCSR_Rm虽然计算效率高，但做出的是贪婪、近视的决策，仅基于局部信息，在面对序列依赖准备和多目标的复杂交互时性能显著下降。元启发式方法如遗传算法（GA）虽然可以探索更广的解空间，但需要大量的问题特定参数调优，计算成本高，且无法保证最优性。精确方法如混合整数规划（MIP）或约束编程（CP）由于组合复杂性面临维度灾难，仅适用于极小的问题规模。本文实验表明，ATCSR_Rm在最大实例（100个作业、15台机器）上的平均TWT高达610.0，TST为290.0，远高于所提方法的420.0和225.0。
本文的目标是本文的目标是开发一个基于深度强化学习的框架，能够直接学习调度策略，有效平衡最小化总加权延误（TWT）和总准备时间（TST）这两个相互冲突的目标。该框架需要能够处理UPMSP的完整复杂性，包括释放日期、序列依赖和机器依赖的准备时间以及机器资格约束，同时在问题规模扩大时保持良好的泛化能力和计算效率。
与已有工作不同的是，现有DRL方法在UPMSP上的应用存在几个关键空白：（1）大多数工作聚焦于单一目标如TWT，未显式处理多目标冲突；（2）一些方法从预定义启发式规则中选择而非学习直接策略，或仅调整现有规则的参数；（3）虽然GNN已被使用，但针对多目标UPMSP设计的图表示需要进一步研究，特别是如何捕获TWT和TST之间的权衡信息。本文的独特切入角度是将鲁棒的PPO算法、针对多目标UPMSP设计的异构GNN状态表示以及显式的多目标奖励函数三者结合，形成一个统一的框架来学习直接调度策略。
核心方法
本文方法的核心思路是将调度问题建模为智能体与离散事件仿真环境之间的交互过程。在每个决策点（如机器变为空闲时），环境提供当前状态$s_t$给智能体，智能体使用学习到的策略$\pi$选择动作$a_t$（将作业分配给机器或等待），环境执行该动作并返回下一状态$s_{t+1}$和即时奖励$r_t$。智能体收集这些经验并使用PPO算法更新策略和价值函数参数，目标是最大化累积折扣奖励$\sum_{t} \gamma^t r_t$。状态表示采用复合结构：全局特征向量提供系统状态摘要，异构图则详细表示作业、机器和准备配置之间的关系。GNN作为特征提取器处理图表示，将丰富的结构信息传递给PPO智能体的策略网络和价值网络。
本文的核心创新在于三个方面：（1）采用PPO算法学习UPMSP的直接调度策略，相比REINFORCE等简单策略梯度方法具有更好的训练稳定性；（2）设计了专门针对多目标UPMSP的异构GNN状态表示，显式建模作业、机器、准备状态及其复杂关系，包括作业-机器边（编码处理时间和准备时间）、机器-准备边（表示当前准备状态）、作业-准备边（表示作业优先级）和准备-机器边（表示准备转换代价）；（3）开发了显式的多目标奖励函数，通过精心设计的权重因子$\alpha$和$\beta$平衡TWT和TST目标，引导智能体学习同时最小化两个冲突目标的策略。这与现有方法的本质区别是：启发式规则做贪婪决策，元启发式做迭代搜索，而本文方法直接学习一个端到端的调度策略。
方法步骤详情
方法包含以下步骤：首先，构建MDP模型，定义状态空间、动作空间和奖励函数。状态空间包括全局特征向量（当前WIP数量、近期内到达的作业数、当前延误作业数、平均流动时间、已产生的TST、空闲机器数、正在设置的机器数等）和异构图$G_t$。动作空间是所有可行的作业-机器对$(J_j, M_k)$，通过动作掩码机制确保只有可行动作有非零概率。其次，设计GNN架构：4层GATv2消息传递，隐藏维度128，ReLU激活。GNN编码器输出的嵌入被传递到两个独立的MLP（各2层，256神经元），分别输出策略（动作概率）和价值估计。第三，使用PPO算法训练：学习率$\eta = 1 \times 10^{-4}$线性衰减，折扣因子$\gamma = 0.99$，GAE参数$\lambda_{GAE} = 0.95$，裁剪参数$\epsilon = 0.2$，每个数据收集阶段10个优化epoch，mini-batch大小64，总训练步数$10^6$。第四，定义多目标奖励函数$r_t = -\alpha \cdot \Delta TWT_j - \beta \cdot s_{i'jk}$，其中$\alpha$和$\beta$控制两个目标的相对重要性。
技术新颖性
本文的技术新颖性体现在以下几个方面：（1）GNN架构创新——设计了包含三种节点类型（作业、机器、准备配置）和四种边类型的异构图，这比现有工作中使用机器-作业对节点的表示更加灵活和富有表达力。准备节点的引入使得即使当前没有机器处于某种准备状态，也能汇总需要该准备的作业信息。（2）奖励函数设计——通过探索多种结构（密集奖励、事件奖励、混合奖励、约束惩罚），找到能够有效引导智能体平衡TWT和TST的奖励信号，这比简单的加权和方法更加精细。（3）动作掩码机制——确保智能体只考虑可行的作业-机器对（满足释放日期、机器资格、机器可用性约束），这既保证了调度的可行性，也加速了学习过程。（4）端到端学习——与选择预定义规则或调整规则参数的方法不同，本文直接学习从状态到动作的映射，能够发现超越人类设计规则的调度策略。
实验结果
实验结果表明PPO-GNN方法在所有测试问题规模上都显著优于基线方法。在小规模实例（20个作业、5台机器）上，PPO-GNN的平均TWT为110.0，比GA的120.0低8.3%，比ATCSR_Rm的150.0低26.7%；平均TST为65.0，比GA的70.0低7.1%，比ATCSR_Rm的75.0低13.3%。在中等规模（50个作业、10台机器）上，PPO-GNN的TWT为260.0，比GA的300.0低13.3%，比ATCSR_Rm的355.0低26.8%；TST为140.0，比GA的165.0低15.2%，比ATCSR_Rm的190.0低26.3%。在最大规模实例（100个作业、15台机器）上，PPO-GNN的TWT为420.0，比GA的475.0低11.6%，比ATCSR_Rm的610.0低31.1%；TST为225.0，比GA的255.0低11.8%，比ATCSR_Rm的290.0低22.4%。所有差异经配对t检验均具有统计显著性（$p < 0.01$）。计算时间方面，PPO-GNN的推理时间在最大实例上仅为1.57秒，远低于GA的约60秒，虽然比ATCSR_Rm慢，但在实际应用中完全可接受。更重要的是，PPO-GNN在两个目标上同时优于所有基线，实现了帕累托前沿上的主导位置，表明它能够学习到内在减少准备时间和延误的复杂调度策略。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| 小规模UPMSP调度（20作业/5机器） | 平均总加权延误（Avg TWT） | 110.0 | GA: 120.0, ATCSR_Rm: 150.0 | 比GA低8.3%，比ATCSR_Rm低26.7% |
| 小规模UPMSP调度（20作业/5机器） | 平均总准备时间（Avg TST） | 65.0 | GA: 70.0, ATCSR_Rm: 75.0 | 比GA低7.1%，比ATCSR_Rm低13.3% |
| 中等规模UPMSP调度（50作业/10机器） | 平均总加权延误（Avg TWT） | 260.0 | GA: 300.0, ATCSR_Rm: 355.0 | 比GA低13.3%，比ATCSR_Rm低26.8% |
| 中等规模UPMSP调度（50作业/10机器） | 平均总准备时间（Avg TST） | 140.0 | GA: 165.0, ATCSR_Rm: 190.0 | 比GA低15.2%，比ATCSR_Rm低26.3% |
| 大规模UPMSP调度（100作业/15机器） | 平均总加权延误（Avg TWT） | 420.0 | GA: 475.0, ATCSR_Rm: 610.0 | 比GA低11.6%，比ATCSR_Rm低31.1% |
| 大规模UPMSP调度（100作业/15机器） | 平均总准备时间（Avg TST） | 225.0 | GA: 255.0, ATCSR_Rm: 290.0 | 比GA低11.8%，比ATCSR_Rm低22.4% |
| 大规模UPMSP调度（100作业/15机器） | 推理时间（秒） | 1.57 | GA: ~60.0, ATCSR_Rm: ~61.29 | 比GA快38倍，适合实时调度 |
局限与改进
本文存在若干局限性：首先，实验仅在生成的基准实例上进行测试，虽然参数设置参考了文献方法，但未在真实工业数据集上验证，实际制造环境可能存在论文未考虑的约束和动态特性。其次，GA基线的性能高度依赖参数设置和允许的计算时间，论文承认进一步精细调优或更长运行时间可能改善GA结果，这使得比较的公平性存在一定争议。第三，论文未详细讨论PPO-GNN的训练成本，$10^6$步的训练在$10^6$环境步数加上多个并行actor的设置下，实际训练时间可能相当长，这限制了方法的快速部署能力。第四，奖励函数中的权重参数$\alpha$和$\beta$需要经验调优，论文探索了多种结构但未提供系统的调优方法论，不同权重设置会导致不同的权衡行为。第五，论文测试的最大规模为100个作业和15台机器，对于更大规模的工业应用（如数百台机器、数千个作业），方法的可扩展性尚未验证。最后，论文假设作业是独立的，未考虑作业之间的优先约束或资源约束，这限制了方法在更复杂生产环境中的适用性。
独立分析的弱点
本文存在几个值得改进的弱点：（1）动作空间设计——当前将所有可行作业-机器对作为动作，在大规模问题上动作空间可能过大，可以考虑层次化动作设计，先选择机器再选择作业，或使用注意力机制动态生成候选动作。（2）状态表示效率——异构图中包含所有作业和机器节点，在作业数量很大时图的规模会迅速增长，可能导致GNN推理变慢，可以考虑引入作业聚类或采样机制来控制图的规模。（3）奖励函数设计——当前使用手工设计的线性组合$r_t = -\alpha \cdot \Delta TWT_j - \beta \cdot s_{i'jk}$，对权重敏感且可能无法捕获复杂的权衡关系，可以考虑使用帕累托优化方法或基于学习的自适应权重调整。（4）泛化能力——论文仅在训练分布内的问题规模上测试，对于超出训练范围的更大规模问题，需要重新训练或使用迁移学习技术。（5）实时适应性——当前方法假设环境是静态的，未考虑作业取消、机器故障、紧急订单插入等动态事件，实际部署时需要额外的机制处理这些情况。
未来方向
作者提出和基于成果可延伸的未来研究方向包括：（1）探索更先进的图神经网络架构，如异构图变换器（HGT）或更深层的消息传递网络，以捕获更复杂的调度模式；（2）将方法扩展到动态调度场景，处理作业到达时间不确定、机器故障、紧急订单等实时变化；（3）研究多智能体强化学习方法，让每台机器或每组机器有自己的智能体，通过协调机制实现分布式调度决策；（4）引入课程学习策略，从简单实例逐步增加难度，加速训练收敛并提升对复杂实例的泛化能力；（5）探索元学习方法，使智能体能够快速适应新的调度场景而无需从头训练；（6）将方法与其他优化技术结合，如使用DRL生成初始解，再用局部搜索进行精细优化；（7）在更多现实约束下验证方法，如考虑作业优先关系、资源约束、维护计划等；（8）研究帕累托前沿的显式建模，使用多目标强化学习方法直接优化帕累托最优解集。
复现评估
本文的复现性较好，作者承诺源代码和数据将在GitHub仓库github.com/bulentsoykan/GNN-DRL4UPMSP公开。实验使用PyTorch和Stable Baselines3库实现，这些都是广泛使用的开源工具。训练硬件配置为Intel Core i9 CPU和NVIDIA RTX 3090 GPU，这在当前深度学习研究中属于标准配置。实例生成方法参考了文献[34]，参数设置有详细描述，包括作业规模$n \in \{20, 50, 100\}$、机器规模$m \in \{5, 10, 15\}$、处理时间$p_{jk} \sim DU(1, 100)$等。PPO超参数也有详细记录：学习率$\eta = 1 \times 10^{-4}$、折扣因子$\gamma = 0.99$、裁剪参数$\epsilon = 0.2$等。然而，论文未提供完整的训练日志、随机种子设置或多次运行的标准差，这可能影响结果的完全复现。此外，GA基线的参数调优过程描述不够详细，可能需要大量实验才能复现论文中报告的GA性能。
论文图表