Source-linked AI summary
Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, Chi Xu
TL;DR
JSSP commonly depends on manually designed PDRs whose construction is costly and whose performance can vary across instances. The paper learns PDRs end to end with a DRL agent that embeds disjunctive-graph states using a GNN and a size-agnostic policy. Experiments report strong performance against manually designed PDRs and useful generalization to much larger unseen instances.
Problem
Designing effective PDRs for JSSP is costly, knowledge-intensive, and trial-and-error driven, while their performance can vary drastically across instances.
Method
The method formulates PDR-based scheduling as an MDP, embeds disjunctive-graph states with a GNN, and trains a size-agnostic policy by policy gradients without supervision.
Results
The learned PDRs significantly outperform existing manually designed PDRs and generalize reasonably well to much larger unseen instances.
Takeaways & Limitations
The approach learns high-quality PDRs from elementary raw features and transfers knowledge from small instances to large-scale JSSP instances.
Takeaways & Limitations
The method sacrifices interpretability because deep neural networks are unexplainable, which may make it untrustworthy for some applications.
Abstract
from arXiv · showhide
Priority dispatching rule (PDR) is widely used for solving real-world Job-shop scheduling problem (JSSP). However, the design of effective PDRs is a tedious task, requiring a myriad of specialized knowledge and often delivering limited performance. In this paper, we propose to automatically learn PDRs via an end-to-end deep reinforcement learning agent. We exploit the disjunctive graph representation of JSSP, and propose a Graph Neural Network based scheme to embed the states encountered during solving. The resulting policy network is size-agnostic, effectively enabling generalization on large-scale instances. Experiments show that the agent can learn high-quality PDRs from scratch with elementary raw features, and demonstrates strong performance against the best existing PDRs. The learned policies also perform well on much larger instances that are unseen in training.
1 Introduction
JSSP scheduling commonly relies on manually designed priority dispatching rules, but creating effective rules is costly and instance-sensitive. The paper proposes an end-to-end DRL method that learns PDRs from disjunctive-graph states and generalizes across instance sizes.
- JSSP assigns constrained jobs to heterogeneous machines while optimizing objectives such as makespan, flowtime, or tardiness.Its NP-hardness often makes exact solutions impractical, motivating heuristic or approximate methods.
- PDRs are fast, intuitive, easy to implement, and naturally capable of handling practical uncertainties.Despite these advantages, designing effective PDRs requires substantial domain knowledge and trial-and-error.
- PDR performance can vary drastically across instances, motivating automated design for classes of JSSP instances with shared characteristics.
- Existing DRL methods for other combinatorial problems do not directly apply to structurally different JSSP, leaving representation and learning mechanisms challenging.
- The proposed method formulates PDR-based scheduling as an MDP, encodes disjunctive-graph states with a GNN, and uses a size-agnostic policy network trained by policy gradients.It learns high-quality PDRs without supervision and is designed to generalize from small training instances to larger ones.
2 Related Work
Deep learning has been explored for several combinatorial optimization problems, but JSSP scheduling remains relatively underexplored. Existing JSSP learning methods have limitations in problem scope, supervision, state representation, or reliance on predefined dispatching rules.
- Deep reinforcement learning research has focused mainly on routing, graph optimization, and satisfiability problems, while scheduling—especially JSSP—remains relatively unexplored.
- Prior job-scheduling studies address simpler tasks without the internal operation dependencies essential to JSSP.
- A cloud task-scheduling method uses GNN embeddings and arbitrary-task scaling, but its DAG representation and resource features do not model JSSP machine-order structure without hard-bounding resources.
- An imitation-learning approach requires optimal solutions labeled by a MIP solver and considers only instances up to 10 jobs × 10 machines.The reliance on enough optimal large-instance solutions limits its applicability.
- Earlier JSSP learning methods use manual state features or select from candidate PDRs, whereas the proposed method extracts knowledge from raw disjunctive-graph features and makes decisions end to end.
3 Preliminaries
JSSP schedules ordered operations across heterogeneous machines while satisfying precedence and non-preemption constraints. The disjunctive-graph representation captures both within-job precedence and alternative ordering between operations sharing a machine.
- A JSSP instance contains jobs whose operations must visit eligible machines in a specified order, with each operation having an integer processing time.
- A feasible schedule assigns starting times to operations while respecting precedence, single-operation machine capacity, and no preemption.
- The objective is to minimize makespan, defined as the maximum completion time across operations.Instance size is denoted as |J| × |M|.
- The disjunctive graph represents operations as vertices, conjunctive arcs as same-job precedence constraints, and disjunctive arcs as pairs of operations requiring the same machine.
4 Method
The method formulates PDR-based JSSP scheduling as an MDP whose states are disjunctive graphs, then learns dispatching policies with a size-agnostic GNN trained by PPO.
- Markov Decision Process Formulation: PDR-based scheduling makes consecutive dispatching decisions over eligible operations, allocating each selected operation at its earliest feasible machine time.The action space contains eligible operations, with at most one ready operation per job.
- Markov Decision Process Formulation: Each state records directed and remaining disjunctive arcs plus scheduled indicators and completion-time lower bounds for every operation.The initial state represents the original instance, while the terminal state has all disjunctive arcs directed.
- Markov Decision Process Formulation: The reward is the decrease in the lower-bound makespan between successive states, so maximizing cumulative reward with γ = 1 minimizes the final makespan.The quality measure is H(st) = max_i,j{CLB(Oij, st)}.
- Parameterizing the Policy: The policy parameterizes action probabilities with a GNN that extracts node and graph embeddings from disjunctive-graph states.GIN performs iterative node updates and average pooling produces a global graph representation used for action selection.
- Parameterizing the Policy: Replacing undirected disjunctive arcs with opposite directed arcs is computationally dense, so the method instead adds only directed arcs fixed by scheduling decisions.The adding-arc approximation produces progressively denser but much sparser-than-fully-directed state graphs.
- Parameterizing the Policy: Shared parameters make the policy independent of instance size, supporting generalization across different-sized instances without retraining.The authors also identify potential extensions to dynamic uncertainty and other shop-scheduling problems, leaving those extensions for future work.
- Parameterizing the Policy: PPO trains the actor policy and a critic that shares the GIN encoder and estimates cumulative rewards from the graph embedding.Training uses N independent trajectories and cumulative gradients to update network parameters.
5 Experiment
Experiments on generated and public JSSP benchmarks evaluate performance, computational efficiency, and generalization across instance sizes. The learned PDR consistently outperforms traditional baselines and remains effective on larger unseen instances.
- Experimental Setup: Evaluations cover generated instances, Taillard’s and DMU benchmarks, and generalization from smaller policies to larger instances.Generated sizes range from 6 × 6 to 100 × 20; public evaluations include 80 Taillard’s and 80 DMU instances.
- Generated Instances: The learned PDR consistently outperforms SPT, MWKR, MOPNR, and FDD/MWKR across generated instance sizes.Baseline performance deteriorates as instance size increases, whereas the learned PDR remains relatively stable.
- Computational Efficiency: The method’s inference time exceeds traditional PDRs but remains acceptable given its performance improvement and is far below OR-Tools’ 3600s runtime on most larger instances.The comparison concerns generated instances of 20 × 20 and 30 × 20, where OR-Tools takes 3600s on the vast majority.
- Generalization: Policies trained on 20 × 20 and 30 × 20 instances deliver much better solutions than traditional PDRs on 50 × 20 and 100 × 20 instances.The largest instances receive high-quality solutions within 30s.
- Generalization: The 20 × 20 policy performs only slightly worse than the 30 × 20 policy, indicating relatively robust generalization.
- Public Benchmarks: On Taillard’s and DMU benchmarks, learned PDRs outperform baselines on same-size and generalized larger instances with reasonable time.Taillard’s results cover 80 instances across eight size groups; DMU results report 30 × 20 policies generalized to 50 × 15 and 50 × 20.
6 Conclusions and Future Work
The paper concludes that end-to-end deep reinforcement learning can automatically learn high-quality PDRs for JSSP using disjunctive graphs and a size-agnostic GNN policy. Experiments support superiority over manually designed PDRs, while future work targets stronger performance, other shop types, and uncertain environments.
- The method automatically learns high-quality PDRs for JSSP through an end-to-end deep reinforcement learning approach.
- A disjunctive-graph MDP formulation and size-agnostic GNN policy extract and reuse structural patterns across instance sizes.
- Experiments on generated and public benchmark instances confirm superiority over traditional manually designed PDRs.
- Future work will enhance performance and extend the method to other shop scheduling problems and uncertain environments.
Broader Impact
The automated end-to-end system aims to reduce the human effort required to design dispatching rules for job-shop scheduling. Its limitations include reduced interpretability and the possibility that automation conceals critical details affecting trust and understanding.
- The system seeks to free human labor from the tedious design of effective dispatching rules for particular job-shop scheduling problems.
- Deep neural networks reduce interpretability compared with traditional intuitive dispatching-rule systems.
- Highly automated end-to-end processing may conceal critical details and bias human understanding of the underlying system.
A Details of the Training Algorithm
The training procedure uses PPO with multiple actors solving sampled JSSP instances, while the scheduling state and baseline-rule notation are specified for dispatch decisions.
- Training procedure: PPO trains the agent using N actors, each solving one JSSP instance drawn from distribution D.Unlike original PPO, updates use all data collected by the actors rather than a sampled batch.
- Training procedure: The algorithm records rewards and next states while iterating through training steps and handles terminal states during rollout.The supplied pseudocode also includes actor-instance sampling and reward reception.
- Baseline notation: Baseline PDRs compute operation priority indices from the defined scheduling quantities before selecting dispatch operations.The section introduces these notations and then gives each baseline’s decision principle.
- Baseline notation: The baseline notation defines Zij as an operation’s priority index, ni as its job’s operation count, and pij as its processing time.All jobs are assumed available at time zero, so Rei = 0 for every job.
C Result on Taillard’s Benchmark
On Taillard’s benchmark, the learned PDRs outperform baselines across most evaluated instances and generalize strongly from smaller training groups to unseen instances.
- Training and testing: 92% of Taillard instances up to 30 × 20 outperform the baselines, covering 46 of 50 instances.The reported gaps are calculated using the best solutions in the literature.
- Generalization: The policies trained on 20 × 20 and 30 × 20 instances achieve the best performance on all 30 generalization instances without further training.The 30 × 20 policy performs slightly better than the 20 × 20 policy.
- Evaluation reference: The Taillard result tables use UB for the best solution from the literature and an asterisk for optimal solutions.These references contextualize the learned policies’ reported gaps and solutions.
D Result on DMU Benchmark
On the DMU benchmark, learned policies outperform traditional baselines in both training-sized evaluations and generalization tests, including unseen instance groups.
- Training and testing: 87.5% of DMU training and testing instances up to 30 × 20 outperform the baselines, covering 35 of 40 instances.Results are reported for four groups used for training and testing.
- Generalization: 77.5% of DMU generalization instances outperform the baselines, covering 31 of 40 instances.The policies were trained on 20 × 20 and 30 × 20 instances and evaluated on held-out groups.
- Experimental settings: Figure 4 varies processing-time scales across problems, including {1, 99} and {1, 199} for the 20 × 20 and 30 × 20 sizes.The scale denotes an integer uniformly distributed over the indicated range.
E Training Curve
Training curves report averaged makespan as learning progresses across multiple JSSP sizes, with training durations varying substantially by problem.
- Training curves: After every 200 totally new instances, the curves plot average makespan over those 200 instances.This evaluation is repeated for each problem size.
- Training cost: Training times reported for the problems range from 0.95h to 20.3h.The passage lists separate durations for the displayed curves.