On the Study of Curriculum Learning for Inferring Dispatching Policies on the Job Shop Scheduling

Zangir Iklassov, Dmitrii Medvedev, Ruben Solozabal Ochoa de Retana, Martin TakácIJCAI 2023 · DOI

Abstract

Solving the Job-shop Scheduling Problem (JSP) efficiently is critical for industrial productivity. While Reinforcement Learning (RL) has emerged as a potential solution for real-time scheduling, scaling these models to large, complex instances remains challenging. This paper introduces RASCL (Reinforced Adaptive Staircase Curriculum Learning), a strategy that intelligently manages problem difficulty during training. By adaptively sampling instances and preventing catastrophic forgetting, RASCL significantly reduces the optimality gap on standard benchmarks, demonstrating superior generalization to large-scale scheduling tasks.

Introduction

The Job-shop Scheduling Problem (JSP) is a classic NP-hard combinatorial optimization problem where multiple jobs must be processed on a set of machines, each following a specific sequence of operations. The objective is typically to minimize the makespan—the total time required to complete all jobs. Traditional methods like Integer Programming provide high-quality solutions but are computationally prohibitive for real-time applications. Conversely, simple Priority Dispatch Rules (PDRs) are fast but often yield suboptimal results. Neural Combinatorial Optimization (NCO) seeks to learn efficient dispatching policies that combine the speed of PDRs with the solution quality of advanced solvers.

Methodology

The authors propose a size-agnostic neural architecture capable of handling varying numbers of jobs and machines. The model uses an Actor-Critic framework where the policy is learned autoregressively.

Model Architecture

  • Operation Sequencing: A backward-running LSTM encodes the temporal dependencies within each job's sequence of operations.
  • Equivariance and Scalability: A set2set module aggregates information across all jobs. This ensures the model is invariant to the order in which jobs are presented and allows it to process problem instances of any size.
The proposed neural architecture for JSP, featuring operation embedding, sequencing, and a set2set job aggregator within an Actor-Critic framework.

RASCL: Reinforced Adaptive Staircase Curriculum Learning

The core innovation is the RASCL training strategy. Standard curriculum learning often fails in RL due to "catastrophic forgetting," where an agent loses its ability to solve simpler tasks as it encounters more complex ones. RASCL mitigates this by:

  1. Performance Monitoring: Tracking the optimality gap across different difficulty levels (problem sizes).
  2. Adaptive Sampling: Dynamically focusing training on levels where the model's performance is currently weakest.
  3. Staircase Progression: Introducing larger problem sizes only after the model achieves a predefined performance threshold on current levels.

Experimental Results

The model was evaluated on the Taillard and Demirkol (DMU) benchmarks. Training was performed on instances ranging from 15x15 to 30x20, while testing included zero-shot generalization to 100x20 instances.

Comparison of (a) curriculum strategies and (b) inference strategies across various problem sizes. RASCL consistently achieves the lowest optimality gaps.

The results show a dramatic improvement over previous NCO methods. On Taillard instances, the average optimality gap was nearly halved, dropping from 19.35% to 10.46%. On the more challenging Demirkol instances, the gap was reduced from 38.43% to 18.85%.

Key findings include:

  • The Necessity of Curriculum: Training directly on large instances (the "Base" model) results in poor performance, confirming that a structured learning path is essential for RL in this domain.
  • Mitigating Forgetting: RASCL’s revisit mechanism ensures the model maintains high performance on smaller instances while learning to solve larger ones.
  • Inference Strategy Impact: While greedy decoding is efficient, using "Sampling" (evaluating 128 trajectories) significantly improves solution quality, outperforming traditional heuristics.

Conclusion

This research demonstrates that the training curriculum is as vital as the neural architecture for solving complex scheduling problems with RL. RASCL provides a robust framework for training agents that generalize well to large-scale industrial instances. Future work will explore extending this approach to dynamic environments with stochastic elements like machine failures and real-time job arrivals.

Summary updated

BibTeX
@inproceedings{iklassov2023study,
  author = {Zangir Iklassov and Dmitrii Medvedev and Ruben Solozabal Ochoa de Retana and Martin Takác},
  title = {{On the Study of Curriculum Learning for Inferring Dispatching Policies on the Job Shop Scheduling}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/594},
}
Figure