ReLA: Representation Learning and Aggregation for Job Scheduling with Reinforcement Learning

📄 arXiv: 2601.03646v1 📥 PDF

作者: Zhengyi Kwan, Zhang Wei, Aik Beng Ng, Zhengkui Wang, Simon See

分类: cs.LG, cs.AI

发布日期: 2026-01-07

备注: 15 pages

💡 一句话要点

提出ReLA，通过强化学习和结构化表示学习解决作业调度问题。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 作业调度 强化学习 表示学习 注意力机制 制造业 深度学习 多尺度架构

📋 核心要点

  1. 现有作业调度解决方案在问题规模增大时，存在运行时间过长或调度质量不足的局限性。
  2. ReLA通过结构化表示学习和聚合，从作业和机器等实体中学习多样化表示，为强化学习决策提供支持。
  3. 实验表明，ReLA在各种规模的作业实例上均优于现有方法，尤其在大型实例上显著降低了优化差距。

📝 摘要（中文）

本文提出了一种基于强化学习（RL）的调度器ReLA，它建立在结构化表示学习和聚合之上，用于解决作业调度问题。ReLA首先使用两个实体内部学习模块（自注意力机制和卷积）和一个实体间学习模块（交叉注意力机制）从作业操作和机器等调度实体中学习多样化的表示。这些模块应用于多尺度架构中，它们的输出被聚合以支持RL决策。在小型、中型和大型作业实例的实验中，ReLA在大多数测试设置中实现了最佳的完工时间。在非大型实例上，ReLA将SOTA基线的优化差距降低了13.0%，而在大型实例上，则降低了78.6%，平均优化差距分别降低至7.3%和2.1%。这些结果证实，ReLA学习到的表示和聚合为RL调度提供了强大的决策支持，并为实际应用实现了快速的作业完成和决策。

🔬 方法详解

问题定义：论文旨在解决制造业系统中常见的作业调度问题，即在各种约束条件下，将有序的作业操作分配给机器。现有方法在处理大规模问题时，面临运行时间过长和调度质量下降的挑战，难以满足实际应用的需求。

核心思路：论文的核心思路是利用强化学习（RL）自动学习高效的调度策略，并通过结构化的表示学习方法，使RL智能体能够更好地理解和利用调度环境中的信息。通过学习作业和机器的有效表示，ReLA能够做出更明智的调度决策，从而优化完工时间。

技术框架：ReLA的整体架构包含三个主要模块：实体内部学习模块、实体间学习模块和RL决策模块。实体内部学习模块使用自注意力机制和卷积神经网络，分别从作业操作和机器的角度学习其内部特征表示。实体间学习模块使用交叉注意力机制，学习作业操作和机器之间的关系表示。最后，将这些学习到的表示聚合起来，作为RL智能体的输入，用于做出调度决策。整个框架采用多尺度架构，以捕捉不同粒度的信息。

关键创新：ReLA的关键创新在于其结构化的表示学习方法，它能够从作业和机器等调度实体中学习到多样化的、有意义的表示。与传统的基于规则或启发式的调度方法相比，ReLA能够自动学习最优的调度策略，并且能够更好地适应不同的调度环境。此外，多尺度架构和注意力机制的使用，使得ReLA能够有效地处理大规模的调度问题。

关键设计：ReLA使用深度Q网络（DQN）作为RL智能体，并采用ε-贪婪策略进行探索。损失函数采用Huber损失，以提高训练的稳定性。在网络结构方面，自注意力机制和交叉注意力机制均采用多头注意力，以捕捉更丰富的关系信息。具体的参数设置（如学习率、批量大小、注意力头数等）通过实验进行调整，以获得最佳的性能。

📊 实验亮点

实验结果表明，ReLA在小型、中型和大型作业实例上均取得了优异的性能。在非大型实例上，ReLA将SOTA基线的优化差距降低了13.0%，而在大型实例上，则降低了78.6%，平均优化差距分别降低至7.3%和2.1%。这些结果表明，ReLA能够有效地解决大规模的作业调度问题，并且具有很强的竞争力。

🎯 应用场景

ReLA具有广泛的应用前景，可应用于各种制造业场景，例如半导体制造、汽车制造和航空航天等。通过优化作业调度，ReLA可以显著提高生产效率，缩短生产周期，降低生产成本。此外，ReLA还可以应用于云计算资源调度、物流调度等领域，具有重要的实际价值和未来影响。

📄 摘要（原文）

Job scheduling is widely used in real-world manufacturing systems to assign ordered job operations to machines under various constraints. Existing solutions remain limited by long running time or insufficient schedule quality, especially when problem scale increases. In this paper, we propose ReLA, a reinforcement-learning (RL) scheduler built on structured representation learning and aggregation. ReLA first learns diverse representations from scheduling entities, including job operations and machines, using two intra-entity learning modules with self-attention and convolution and one inter-entity learning module with cross-attention. These modules are applied in a multi-scale architecture, and their outputs are aggregated to support RL decision-making. Across experiments on small, medium, and large job instances, ReLA achieves the best makespan in most tested settings over the latest solutions. On non-large instances, ReLA reduces the optimality gap of the SOTA baseline by 13.0%, while on large-scale instances it reduces the gap by 78.6%, with the average optimality gaps lowered to 7.3% and 2.1%, respectively. These results confirm that ReLA's learned representations and aggregation provide strong decision support for RL scheduling, and enable fast job completion and decision-making for real-world applications.