💻 computer science

Modelling Reinforcement Learning Scheduling Agents: Action spaces, reward designs, and expert demonstrations

This paper investigates how modeling choices in Deep Reinforcement Learning affect scheduling policies for the Flexible Job-shop Scheduling Problem, demonstrating that integrating Constraint Programming-derived optimality bounds and expert demonstrations into a multi-agent framework significantly improves reward design and accelerates convergence to achieve superior, real-time scheduling performance.

Original authors: Alexandre Jesus, Arthur Corrêa, Miguel Vieira, Catarina Marques, Cristóvão Silva, Samuel Moniz

Published 2026-09-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexandre Jesus, Arthur Corrêa, Miguel Vieira, Catarina Marques, Cristóvão Silva, Samuel Moniz

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the heart of modern manufacturing, a silent and complex puzzle plays out every second. Factories must decide the order in which thousands of tasks are performed on a limited number of machines. Some tasks can only be done on one specific machine, while others can be handled by several different ones, each taking a slightly different amount of time. The goal is simple to state but incredibly hard to solve: finish all the work as quickly as possible. This challenge, known as the flexible job-shop scheduling problem, is a classic test of efficiency. For decades, experts have relied on rigid mathematical rules or trial-and-error methods to find good solutions. However, these traditional methods often struggle when the factory floor changes or when the number of possibilities becomes too vast to calculate quickly. In recent years, a new approach has emerged: teaching computers to learn by doing. This method, called reinforcement learning, allows an artificial intelligence to explore millions of scenarios and discover its own strategies for organizing work, promising to make decisions faster and more adaptively than ever before.

A team of researchers from universities in Portugal has now taken a closer look at how these learning machines are built, asking a fundamental question: does the way we teach them matter more than the intelligence of the machine itself? They focused on two specific choices that designers make when creating these scheduling agents. The first choice is the level of detail the agent sees. Does it look at the entire job and decide which one to start next, or does it zoom in to see every single step of every job and decide exactly which step to perform? The second choice is the reward system, the feedback loop that tells the agent whether it is doing a good job. Is the agent praised for simply finishing a task quickly, or is it rewarded for how that task fits into the overall picture of the factory? To find the answers, the researchers did not just let their agents guess. Instead, they used a powerful, traditional mathematical solver to generate perfect or near-perfect schedules for a wide variety of factory scenarios. They then used these expert solutions as a reference point, a gold standard, to measure how well their learning agents were actually performing.

The researchers discovered that the best approach depends entirely on the nature of the factory floor. When the jobs are all very similar to one another, a simpler view works best. In these cases, having the agent look at the whole job and pick the next one to run is efficient and effective. However, when the factory is full of variety—where some jobs are long and complex while others are short, and where machines have very different speeds—the simple view fails. In these chaotic environments, the agent needs to see the fine details. It must look at every single operation and decide exactly which machine should handle it. The study showed that ignoring these details in a complex factory leads to significantly worse results, proving that there is no single "one-size-fits-all" way to design these learning agents.

The team also found that the way they rewarded the agents was even more critical than the level of detail they saw. Many previous studies had relied on a global reward, where the agent only received feedback when the total time to finish all jobs changed. This is like a coach who only speaks up when the final score changes, leaving the player guessing about what they did right or wrong in the middle of the game. The researchers found this approach often left the agents confused, especially in complex settings. Instead, they designed a new reward system that gave immediate, local feedback. The agent was rewarded based on how efficiently it used the specific machine it was working on compared to the other machines available for that specific task. This constant, immediate feedback acted like a steady hand on the shoulder, guiding the agent step-by-step. When they combined this local guidance with the global picture, the agents learned much faster and produced schedules that were much closer to the perfect solutions found by the traditional mathematical solver.

To push the performance even further, the researchers introduced a hybrid method. They realized that letting an agent start from scratch is inefficient. So, before the agent began its own learning journey, they showed it a thousand examples of perfect schedules created by the expert mathematical solver. This process, known as learning from demonstrations, gave the agent a head start, allowing it to skip the early, clumsy phase of random guessing. The result was a system that not only learned faster but also became more stable and reliable. In their tests, this hybrid approach reduced the gap between the agent's schedule and the perfect schedule by about five percent compared to standard learning methods. Perhaps most importantly, this high level of performance came without the need for complex, heavy computer architectures. The system remained lightweight and fast, capable of making decisions in less than a second.

The study concludes that the secret to building effective scheduling agents lies not just in the algorithm itself, but in carefully matching the design to the specific problem at hand. By using expert solutions to guide the learning process and by tailoring the reward signals to the specific mix of machines and jobs, it is possible to create intelligent systems that are both powerful and practical. These findings suggest that the future of factory management does not require impossibly complex AI, but rather a thoughtful combination of traditional mathematical precision and modern learning techniques. The result is a tool that can help factories adapt to change in real-time, ensuring that the flow of production remains smooth even when the world around it is anything but.

Technical Summary: Modelling Reinforcement Learning Scheduling Agents

Problem Definition

This research addresses the Flexible Job-shop Scheduling Problem (FJSP), a combinatorial optimization problem central to modern manufacturing. The FJSP extends the classical Job-shop Scheduling Problem (JSP) by allowing operations to be processed on multiple candidate machines, introducing two decision layers: operation allocation (selecting the machine) and machine sequencing (determining the order). The objective is to minimize the makespan ( $C_{max}$ ), defined as the completion time of the last operation.

While exact methods like Mixed-Integer Linear Programming (MILP) and Constraint Programming (CP) can find optimal solutions, they often struggle with computational costs in large-scale or dynamic environments. Conversely, Deep Reinforcement Learning (DRL) offers low inference times and adaptability but suffers from a lack of systematic understanding regarding how modelling choices (action spaces, reward functions) interact with specific problem structures (e.g., job heterogeneity, machine flexibility). Existing DRL studies often rely on trial-and-error design or heuristic baselines, lacking a rigorous connection to optimality bounds.

Methodology

The authors propose a multi-agent Deep Q-Learning (DQL) framework operating under a Centralized Learning with Decentralized Execution (CLDE) paradigm. Each agent represents a machine on the shop floor, making local decisions based on partial observations.

1. Constraint Programming (CP) Integration

A state-of-the-art interval-based CP model (using IBM CP Optimizer) serves two distinct roles:

Analytical Baseline: CP is used to compute optimality bounds (lower bounds) and high-quality solutions for benchmark instances. These serve as the ground truth to evaluate the optimality gap of DRL policies.
Expert Demonstrations: CP solutions are decomposed into state-action transitions to pre-train the DRL agent, acting as "expert demonstrations."

2. Multi-Agent DQL Architecture

The framework utilizes a value-based approach where agents share a single Deep Q-Network (DQN) policy.

State Representation: Agents observe partial system states including waiting operations, processing times, action history, remaining operations, machine utilization, and queue density.
Action Spaces: Two granularities are evaluated:
- Operation-level ( $L_O$ ): Agents select specific operations from the queue.
- Job-level ( $L_J$ ): Agents select a job, and the environment schedules the next operation.
Reward Design: The study systematically evaluates various reward functions, including:
- Global signals: Penalizing makespan increments ( $r_{MI}$ ).
- Local signals: Penalizing total time between actions ( $r_{TBA}$ ) or idle time ( $r_{IT}$ ).
- Proposed Hybrid Signals: New rewards ( $r_Q$ , $r_{OE}$ ) that penalize inefficient machine selection by comparing the chosen processing time against the fastest available candidate for that operation.

3. Hybrid Learning Strategy (DQL-D)

The authors introduce DQL-D, a hybrid method incorporating Deep Q-Learning from Demonstrations (DQLfD).

Pre-training: The DQN is initialized using transitions derived from CP solutions (top 5 solutions per instance).
Prioritized Experience Replay: The replay buffer contains both expert demonstrations and self-generated RL transitions. Transitions are sampled based on loss, prioritizing states where the agent has not yet mastered the expert behavior.
Training: The agent continues to learn via standard DQL, allowing it to explore beyond the expert's policy while benefiting from the stability of the initial guidance.

Key Contributions

Systematic Analysis of Modelling Choices: The paper provides a rigorous evaluation of how action granularity and reward scope interact with structural instance properties (job heterogeneity, machine flexibility, and processing time variability).
Novel Reward Functions: The authors design reward functions ( $r_Q$ and $r_{OE}$ ) that explicitly account for machine heterogeneity. These signals outperform existing global or purely local rewards, reducing the optimality gap by roughly 10% in high-heterogeneity scenarios.
Hybrid DQL-D Framework: The integration of CP-derived demonstrations into a multi-agent DQL architecture accelerates convergence and improves stability without requiring complex graph encoders or attention mechanisms.

Experimental Results

The methodology was tested on three standard FJSP benchmark datasets (FMJdata, BRdata, DPdata) with varying scales and flexibility levels.

Action Granularity: In instances with homogeneous job structures, job-level actions ( $L_J$ ) performed comparably to operation-level actions ( $L_O$ ). However, in heterogeneous job structures (common in BRdata and DPdata), operation-level actions ( $L_O$ ) yielded significantly lower optimality gaps (approx. 5% improvement in median error).
Reward Design:
- Standard global rewards ( $r_{MI}$ ) and total time rewards ( $r_{TBA}$ ) often led to higher optimality gaps.
- The proposed local efficiency reward ( $r_Q$ ) consistently outperformed others, achieving an average gap to CP of 13.62% over all instances and reducing the optimality gap by roughly 10% in high-heterogeneity scenarios compared to standard baselines. This reward effectively normalizes action quality across agents with different workloads.
Performance of DQL-D:
- Convergence: DQL-D achieved faster convergence and lower variance than standard DQL. It reduced the optimality gap by approximately 5% relative to the standard DQL baseline.
- Comparison: DQL-D achieved competitive performance against state-of-the-art graph-based DRL methods (HGNN and MPGN), often outperforming them in instances where those methods were less suited.
- Efficiency: The lightweight DQL-D framework achieved inference times 3 to 9 times faster (sub-second) than complex graph-based architectures, making it highly suitable for real-time scheduling.

Significance and Claims

The paper claims that optimality-guided DRL modelling, combined with expert demonstrations, enables the creation of lightweight, fast, and reliable scheduling agents.

Modelling Insights: The study demonstrates that a "one-size-fits-all" DRL approach is insufficient; action spaces and reward functions must be tailored to the specific structural properties of the scheduling instance (e.g., using operation-level actions for heterogeneous jobs and local efficiency rewards for heterogeneous machines).
Practical Viability: By leveraging CP for pre-training and using a simple value-based architecture, the authors show that complex representation learning (like Graph Neural Networks) is not strictly necessary to achieve state-of-the-art performance. This offers a practical solution for manufacturing systems requiring decentralized decision support with strict real-time constraints.
Future Direction: The work suggests that hybrid frameworks combining exact methods (CP) with DRL can bridge the gap between theoretical optimality and practical deployment, paving the way for dynamic and online scheduling variants.