PaperlayerView exact revision on arXiv

Source-linked AI summary

Curriculum Learning with GNN-based Reinforcement Learning for Job Shop Scheduling

Jayakrishnan K. Vasudevan, Jonathan Hoss, Noah Klarmann

arXiv:2609.28085v1cs.LGcs.AI

TL;DR

Large JSSP instances make GNN-based reinforcement-learning training costly, and evidence about curriculum learning’s effects across instance sizes remains limited. This paper compares progressive size-based curricula with single-size training; the strongest reported benefits occur at 30 × 30, in both optimality gap and training time.

  • Problem

    Training GNN-based RL on large JSSP instances is computationally expensive, while curriculum learning’s effects on cross-size generalization, target-size specialization, and training cost remain insufficiently explored.

    Source: §I · p. 1

  • Method

    The study compares single-size training with a curriculum that progressively trains the policy on smaller instances before adapting it to larger target sizes.

    Source: §I · p. 1, B. CL Training Strategies · p. 3

  • Results

    At 30 × 30, curriculum learning saves approximately 50 hours and reduces mean OG by approximately 8.1 percentage points across evaluation sizes and 8.6 percentage points on the target size.

    Source: C. Results for 30 × 30 Target Size · p. 5, §VII · p. 6

  • Takeaways & Limitations

    Curriculum learning appears particularly useful when direct target-size training is costly, as smaller instances provide shorter episodes and more learning opportunities before adaptation to larger instances.

    Source: §VII · p. 6

    The study fixes curriculum switches at 10M steps and covers only JSSP instances with J/M = 1.

    Source: §VII · p. 6

Abstract

from arXiv · show

The job shop scheduling problem is a challenging combinatorial optimization problem, and recent reinforcement learning approaches using graph neural networks have shown promise for learning scheduling policies directly from problem instances. However, training on large instances remains computationally expensive, and generalization across instance sizes remains challenging. This paper studies curriculum learning for graph neural network-based reinforcement learning in the job shop scheduling problem by comparing it with single-size training across three target sizes: 20 x 20, 25 x 25, and 30 x 30. In the curriculum setting, the policy is first trained on smaller instances and then progressively adapted to larger target sizes, allowing scheduling behavior learned in earlier stages to support learning on larger instances. Models are evaluated on unseen instances from 8 x 8 to 30 x 30 using the optimality gap, considering both generalization across all evaluation sizes and specialization on the target size. Results show that curriculum learning consistently reduces wall-clock training time, with larger benefits as the target size increases. The strongest advantage is observed at 30 x 30, where curriculum learning reduces the mean optimality gap across all evaluation sizes by approximately 8.1 percentage points, reduces the target-size mean optimality gap by approximately 8.6 percentage points, and saves approximately 50 hours of training time.

I. INTRODUCTION

Large JSSP instances make GNN-based reinforcement learning computationally expensive, while generalization across sizes and training efficiency remain open concerns. This study compares size-based curriculum learning with single-size training across generalization, target-size specialization, and wall-clock time.

I. INTRODUCTION

  • Larger JSSP instances make direct GNN-based RL training costly because they require longer episodes, larger graphs, and more complex decision dependencies.JSSP is a combinatorial optimization problem with applications in scheduling and resource allocation.Source: §I · p. 1
  • Curriculum learning progresses from simpler to harder tasks, using smaller JSSP instances as early stages before adapting the policy to larger targets.Smaller instances have shorter episodes, smaller graphs, and lower per-step computational cost.Source: §I · p. 1
  • Existing JSSP curriculum studies leave open how size-based curricula affect cross-size generalization, target-size specialization, convergence behavior, and wall-clock training cost.Prior work either ordered instances within one problem size or primarily evaluated final solution quality.Source: §I · p. 1
  • The study compares size-based curriculum learning with single-size training across unseen-size generalization, target-size specialization, and wall-clock training time.The comparison uses identical model, evaluation, and hardware settings.Source: §I · pp. 1–2
  • The study examines whether shifting learning to cheaper early stages can reduce computational cost without compromising solution quality as target size increases.Its contributions include separating generalization from specialization and jointly analyzing training-time savings and optimality-gap performance.Source: §I · pp. 1–2

II. RELATED WORK

Prior work applies graph-based reinforcement learning to scheduling and explores curricula based on task progression, instance size, or difficulty. The paper also formulates JSSP as sequential decision-making and evaluates learned schedules relative to a heuristic.

A. GNN-based RL for Scheduling

  • Graph-based RL represents JSSP structure, but larger graphs and more node embeddings increase computational demands.Prior work used disjunctive-graph and graph-based state encodings to capture operation dependencies and support generalization,.Source: A. GNN-based RL for Scheduling · p. 2

B. CL for COP

  • Curriculum approaches order training by instance difficulty or progressively increase problem size, with some adapting difficulty according to model performance [10], [11], [15].These strategies embody different assumptions about useful learning progressions.Source: B. CL for COP · p. 2

A. JSSP and RL Formulation

  • JSSP schedules must respect job precedence and machine capacity, and the goal is to minimize makespan.The RL formulation selects one eligible operation per decision step; feasible actions are determined using action masking.Source: A. JSSP and RL Formulation · p. 2
  • Optimality gap measures the learned policy’s relative makespan difference from the FDD/MWR heuristic, with lower values indicating better solution quality.Source: A. JSSP and RL Formulation · p. 2

A. GNN-Based RL Framework and Graph Representation

The policy constructs schedules by selecting feasible operations from a graph-encoded shop-floor state. Curriculum training progresses through larger instance sizes while retaining learned policy and value-function parameters between stages.

A. GNN-Based RL Framework and Graph Representation

  • At each decision step, an operation–machine graph is processed by a GNN and actor head to select the next feasible operation, while a critic estimates state value.The actor–critic policy uses PPO, and the graph includes precedence and operation-to-machine assignment edges.Source: A. GNN-Based RL Framework and Graph… · pp. 2–3

B. CL Training Strategies

  • The three-stage curriculum uses progressively larger instances, allocates 10M environment steps per stage, and matches the single-size baseline’s 30M-step total budget.The symmetric stage schedule keeps the curriculum directly comparable to the baseline; the environment and size-dependent settings change at transitions while policy and value parameters are retained.Source: B. CL Training Strategies · p. 3
  • At each stage, PPO updates follow trajectory collection until the stage budget is exhausted, with policy evaluation on a fixed held-out dataset at regular intervals.Source: B. CL Training Strategies · p. 3

A. Instance Sizes and Problem Setting

The study controls for the job-to-machine ratio while comparing curriculum learning (CL) with single-size training at three target sizes. CL uses smaller instances as intermediate stages before training on the target size.

A. Instance Sizes and Problem Setting

  • The study uses equal numbers of jobs and machines (J/M = 1) to control for changes in problem structure as instance size increases.The setting is motivated as highly saturated, with pronounced machine contention.Source: A. Instance Sizes and Problem Setting · p. 3
  • The three target sizes are 20×20, 25×25, and 30×30, with the larger sizes chosen to examine CL as problem complexity grows.The 20×20 size is the base target, identified in prior work as supporting strong zero-shot generalization.Source: A. Instance Sizes and Problem Setting · p. 4

B. Training Procedure

  • Both strategies use the same architecture, hyperparameters, hardware, and evaluation intervals; each setting is repeated with three random seeds.Reported curves and final values are means across runs, with shaded regions showing one standard deviation.Source: B. Training Procedure · p. 4
  • Each CL run uses smaller instance sizes as stages before reaching the same target size used by its corresponding single-size baseline.The 20×20 curriculum uses 10×10 and 15×15; the 25×25 curriculum uses 10×10 and 15×15; and the 30×30 curriculum uses 10×10 and 20×20.Source: B. Training Procedure · p. 4

C. Evaluation Dataset

The policy is evaluated periodically on a fixed held-out set spanning seven instance sizes, with instances disjoint from training.

C. Evaluation Dataset

  • Evaluation occurs every Δeval steps on a fixed dataset of 140 instances, with 20 instances at each of seven sizes from 8×8 to 30×30.The sizes are 8×8, 10×10, 12×12, 15×15, 20×20, 25×25, and 30×30.Source: C. Evaluation Dataset · p. 4
  • Held-out instances follow the training generation procedure but use a different random seed, keeping evaluation instances disjoint from training.Source: C. Evaluation Dataset · p. 4
  • Regular evaluations allow comparison of convergence behavior between curriculum learning and single-size training.Source: C. Evaluation Dataset · p. 4

D. Evaluation Metrics

The study measures generalization across evaluation sizes, specialization on the target size, and training efficiency. Its results section compares optimality-gap curves by training steps and wall-clock time.

D. Evaluation Metrics

  • Generalization performance is measured by average optimality gap across all evaluation sizes, reflecting performance on unseen instance sizes.Source: D. Evaluation Metrics · p. 4
  • Specialization performance is measured by average optimality gap on the target size, using only evaluation instances of that size.For a 20×20 target, this metric uses only 20×20 evaluation instances.Source: D. Evaluation Metrics · p. 4
  • Training efficiency is measured by elapsed wall-clock time, including environment interaction, optimization, logging, and periodic evaluation.Time saved is calculated relative to the corresponding single-size training baseline.Source: D. Evaluation Metrics · p. 4

VI. RESULTS AND DISCUSSION

  • For each target size, the results compare mean optimality gap across all evaluation sizes and on the target size, each plotted against steps and wall-clock time.For the 20×20 target, the figure plots all-size mean optimality gap against training steps in the top panel and wall-clock time in the bottom panel.Source: §VI · pp. 4–5, Figure 1 · p. 5

A. Results for 20 × 20 Target Size

At 25×25, curriculum learning improves cross-size generalization and reduces training time, while direct training retains a slight target-size specialization advantage. At 20×20, it saves time with similar generalization but a small specialization loss.

A. Results for 20 × 20 Target Size

A. Results for 20 × 20 Target Size; B. Results for 25 × 25 Target Size

B. Results for 25 × 25 Target Size

  • At 25×25, curriculum learning reduces mean optimality gap across evaluation sizes by approximately 1.6 percentage points and wall-clock training time by approximately 40 hours, or 42%.It increases target-size mean optimality gap by approximately 1.3 percentage points compared with single-size training.Source: B. Results for 25 × 25 Target Size · p. 5

C. Results for 30 × 30 Target Size

For the 30 × 30 target, curriculum learning delivers the strongest reported result: lower optimality gaps on both evaluation scopes and the largest absolute training-time saving. The curriculum also uses a 20 × 20 intermediate stage, and its relative time reduction is only slightly above the 25 × 25 setting.

C. Results for 30 × 30 Target Size

  • At 30 × 30, CL reduces mean OG by approximately 8.1 percentage points across evaluation sizes and 8.6 points on the target, saving approximately 50 hours (43%) versus single-size training.The absolute time saving is the largest among tested target sizes.Source: C. Results for 30 × 30 Target Size · p. 5
  • Unlike smaller target settings, 30 × 30 improves target-size performance as well as generalization and training efficiency.The reported target-size mean OG falls rather than showing the small specialization loss seen at smaller targets.Source: C. Results for 30 × 30 Target Size · p. 6
  • The absolute time saving is largest at 30 × 30, although its relative reduction is only slightly above the 25 × 25 setting.The authors suggest the 20 × 20 intermediate stage in the 30 × 30 curriculum may contribute to the larger absolute saving.Source: C. Results for 30 × 30 Target Size · p. 6
  • The 30 × 30 curriculum uses 20 × 20 as its intermediate stage, compared with 15 × 15 for the 20 × 20 and 25 × 25 curricula.Source: C. Results for 30 × 30 Target Size · p. 6

VII. CONCLUSION

The conclusion reports that curriculum learning reduces training time across target sizes, with the strongest solution-quality gains at 30 × 30. Its benefit varies by target size, and the study is bounded by its fixed switch interval and J/M = 1 setting.

VII. CONCLUSION

  • At 25 × 25, CL lowers mean OG across evaluation sizes by approximately 1.6 points but raises target-size mean OG by 1.3 points; at 20 × 20, target-size mean OG rises by 1.2 points.For 20 × 20, generalization remains similar to single-size training.Source: §VII · p. 6
  • CL reduces training time at every tested target size, and absolute time savings increase as the target size grows.Source: §VII · p. 6
  • For 30 × 30, CL reduces mean OG by approximately 8.1 percentage points across evaluation sizes and 8.6 points on the target size.Source: §VII · p. 6
  • Smaller instances offer shorter episodes and more frequent learning opportunities, while spending less of the training budget on the target can trade off specialization at smaller and medium sizes.The conclusion says generalization, specialization, and efficiency benefits become more pronounced as target size increases.Source: §VII · p. 6
  • The study fixes curriculum switches at 10 M steps and covers only J/M = 1; broader comparisons and tests on larger instances and other ratios remain future work.Source: §VII · pp. 6–7
Loading 2609.28085v1…