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

Problem

This work addresses the computational expense associated with training reinforcement learning models on large job shop scheduling instances. It also tackles the challenges of generalization across different instance sizes, which is critical for effective scheduling in practical applications. The paper is a preprint and has not undergone peer review.

Method

The authors propose a Graph Neural Network (GNN) based reinforcement learning architecture. The training methodology employs curriculum learning, where the model is first trained on smaller job shop scheduling instances before progressing to larger ones. Specifically, the target sizes for training are 20 x 20, 25 x 25, and 30 x 30 instances. The model is evaluated on unseen instances ranging from 8 x 8 to 30 x 30. The primary metric used for evaluation is the optimality gap, which measures the difference between the solution provided by the model and the optimal solution.

Results

The proposed method demonstrates significant improvements over traditional single-size training approaches. The mean optimality gap is reduced by 8.1 percentage points compared to single-size training. When specifically considering the target sizes, the mean optimality gap reduction is 8.6 percentage points. Additionally, the training time is reduced by approximately 50 hours when compared to single-size training, indicating a substantial efficiency gain in the training process.

Limitations

The authors do not report any limitations in their study. However, it is important to note that the generalizability of the results to even larger or more complex job shop scheduling instances remains untested, which could be a potential area for future research.

Why it matters

This research has significant implications for the field of job shop scheduling, particularly in enhancing the efficiency of reinforcement learning models. By leveraging curriculum learning and GNNs, the approach not only reduces training time but also improves generalization across varying instance sizes. This could lead to more scalable and effective scheduling solutions in industrial applications, paving the way for further advancements in automated scheduling systems.