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

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

TL;DR

ReLA (Representation Learning and Aggregation) is a new reinforcement learning framework designed to solve complex job scheduling problems in manufacturing. By using a multi-scale architecture that combines self-attention, convolution, and cross-attention, it achieves state-of-the-art results—reducing the optimality gap of previous methods by up to 78.6% on large-scale industrial problems.

What Problem Does This Paper Address?

In modern manufacturing, Flexible Job Shop Scheduling (FJSP) is a constant headache. You have a set of jobs, each consisting of a sequence of operations, and a set of machines. The goal is to assign these operations to machines to minimize the makespan (the total time to finish everything) while respecting constraints like operation order and machine compatibility.

This is an NP-hard combinatorial optimization problem. Traditional "exact" solvers like OR-Tools provide high-quality schedules but are painfully slow as the number of jobs grows, making them useless for real-time decision-making. On the other hand, existing Reinforcement Learning (RL) schedulers are fast but often use oversimplified "state representations," leading to poor schedule quality on large-scale, realistic factory floors. ReLA aims to bridge this gap: providing the speed of RL with the schedule quality of a heavy-duty solver.

Methods

The authors propose a "representation-first" philosophy. Instead of squashing the entire state of the factory into a single vector, ReLA uses a modular architecture to capture different structural properties of the scheduling environment:

  1. Intra-Entity Learning: To understand the relationships within a group (e.g., how operations in a single job depend on each other), ReLA uses Self-Attention to capture long-range dependencies and 1D Convolutions to capture local structural patterns.
  2. Inter-Entity Learning: To evaluate the "fit" between an operation and a machine, the model employs Cross-Attention. This allows the model to weigh the requirements of an operation against the current workload and availability of a machine.
  3. Multi-Scale Architecture: These modules operate at two different scales (different embedding dimensions) simultaneously.
  4. Deep Supervision: To ensure the model learns effectively across these scales, the training signal is applied to both, preventing information loss during the aggregation process.
  5. RL Policy: The aggregated representations are fed into an Actor-Critic framework (specifically PPO-Clip). The "Actor" scores feasible operation-machine pairs, while the "Critic" evaluates the overall quality of the current factory state.

Datasets

The researchers evaluated ReLA across several benchmarks:

  • SD1 & SD2: Synthetic datasets generated to simulate various manufacturing conditions. SD2 is specifically designed to be more challenging, featuring a wider variance in operation processing times.
  • Public Benchmarks: The classic mk (Brandimarte) and la (Lawrence) instances, which are standard in the scheduling literature.
  • Scales: Testing ranged from small instances (10 jobs × 5 machines) to massive industrial-scale problems (200 jobs × 5 machines).

Key Insights and Ideas

  • Diversity Over Depth: The "aha moment" here is that for scheduling, having multiple types of representations (convolutional for local sequences, attention for global context) is more effective than simply building a deeper, single-modality neural network.
  • Zero-Shot Generalization: Remarkably, a ReLA model trained on small 10x5 instances can be directly applied to 200x5 instances without retraining, maintaining high performance. This suggests the model is learning fundamental scheduling "physics" rather than just memorizing patterns.
  • The Power of Local Patterns: While most recent SOTA models rely solely on attention, ReLA shows that convolutions are vital for capturing the "local" nature of job sequences, which attention mechanisms sometimes overlook.

Key Results

  • Large-Scale Dominance: On the largest synthetic instances (100+ jobs), ReLA reduced the optimality gap of the previous state-of-the-art (DANIEL) by a staggering 78.6%.
  • Closing the Gap with Exact Solvers: On medium-sized problems, ReLA achieved an average optimality gap of only 7.3% compared to OR-Tools, but it produced these results in seconds rather than the 30 minutes required by the solver.
  • Negative Gaps: In several complex scenarios (SD2 datasets), ReLA actually achieved "negative gaps," meaning it found better solutions than OR-Tools within the solver's 1,800-second time limit.

Limitations and Future Work

While ReLA is highly effective, the authors note a few areas for growth:

  • Computational Overhead: Because ReLA uses multiple parallel representation modules, it has a slightly higher computational cost per decision step compared to simpler RL models (though it remains orders of magnitude faster than traditional solvers).
  • Static vs. Dynamic: The current work focuses on static FJSP where all jobs are known upfront. Future work could extend this to "dynamic" scheduling, where new jobs arrive unexpectedly—a common occurrence in real-world "Smart Manufacturing."
  • Broader Constraints: The paper primarily focuses on makespan. Future iterations could incorporate multi-objective optimization, such as balancing completion time with energy consumption or machine wear-and-tear.

Summary updated

Abstract

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.
BibTeX
@misc{kwan2026rela,
  author = {Zhengyi Kwan and Wei Zhang and Aik Beng Ng and Zhengkui Wang and Simon See},
  title = {{ReLA: Representation Learning and Aggregation for Job Scheduling with Reinforcement Learning}},
  year = {2026},
  eprint = {2601.03646},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.03646},
}
Figure