PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning

Junyoung Park, Jaehyeong Chun, Sang Hun Kim, Youngkook Kim, Jinkyoo Park

arXiv:2106.01086v1cs.AIcs.MA

TL;DR

JSSP scheduling requires sequential machine assignments under precedence and machine-sharing constraints, while existing exact and search-based approaches face practical limitations in scale or changing conditions. The paper represents JSSP states as graphs, jointly learns GNN representations and scheduling policies with PPO, and reports strong generalization to unseen and larger instances without further training.

  • Problem

    JSSP requires sequential assignments under precedence and machine-sharing constraints, while exact methods face dimensionality limits and search methods must be rerun when conditions change.

  • Method

    The framework formulates scheduling as an MDP, represents states as disjunctive graphs, and jointly trains a GNN representation module and scheduling policy with PPO.

  • Results

    The GNN scheduler outperformed PDRs and showed robust performance across benchmark instances, while producing high-quality schedules for larger JSSPs without additional training.

  • Takeaways & Limitations

    The learned policy captures general JSSP properties rather than a specific instance, enabling direct transfer to new JSSPs without further training.

  • Takeaways & Limitations

    Benchmark error varies significantly across instances, possibly because JSSP characteristics and difficulty levels differ substantially.

Abstract

from arXiv · show

We propose a framework to learn to schedule a job-shop problem (JSSP) using a graph neural network (GNN) and reinforcement learning (RL). We formulate the scheduling process of JSSP as a sequential decision-making problem with graph representation of the state to consider the structure of JSSP. In solving the formulated problem, the proposed framework employs a GNN to learn that node features that embed the spatial structure of the JSSP represented as a graph (representation learning) and derive the optimum scheduling policy that maps the embedded node features to the best scheduling action (policy learning). We employ Proximal Policy Optimization (PPO) based RL strategy to train these two modules in an end-to-end fashion. We empirically demonstrate that the GNN scheduler, due to its superb generalization capability, outperforms practically favored dispatching rules and RL-based schedulers on various benchmark JSSP. We also confirmed that the proposed framework learns a transferable scheduling policy that can be employed to schedule a completely new JSSP (in terms of size and parameters) without further training.

1 Introduction

The paper frames JSSP scheduling as sequential decision-making over graph-structured states and proposes a GNN-RL scheduler that learns representations and scheduling policies jointly. The resulting policy is reported to outperform dispatching rules and generalize to unseen JSSP instances.

  • JSSP determines sequential machine assignments for operations while preserving processing-precedence and machine-sharing constraints.
  • Exact methods guarantee optimality but face dimensionality limits, while search-based methods must be rerun when dynamic scheduling conditions change.
  • PDRs remain widely used because they are simple, interpretable, and computationally inexpensive, but they ignore scheduling’s sequential nature.
  • The framework represents JSSP states as graphs, uses a GNN to learn node embeddings, and maps those embeddings to scheduling actions.
  • PPO jointly trains the GNN state-representation module and parameterized decision-making policy in an end-to-end fashion.
  • The GNN scheduler outperforms dispatching rules on benchmark JSSPs and can schedule completely new instances without further training.

2 Backgrounds

The background introduces MDPs and graph representation learning as foundations for sequential optimization with structured data. It situates GNN-RL methods as approaches that learn graph-aware representations and policies without requiring precomputed optimal solutions.

  • 2.1 Markov decision process and reinforcement learning: An MDP comprises states, actions, transition probabilities, rewards, and a discount factor for modeling sequential decision-making.
  • 2.1 Markov decision process and reinforcement learning: RL learns a policy that selects actions to maximize expected cumulative future rewards through iterative MDP optimization.
  • 2.2 Representation learning on graph structured data: Graph representation learning uses nodes, edges, and node features to extract embeddings that support decision-making on complex structured data.
  • 2.2 Representation learning on graph structured data: GNNs update node features by learning pairwise interactions, aggregating neighborhood messages, and incorporating the aggregated features.
  • 2.2 Representation learning on graph structured data: Because GNNs model graph structure and node features, trained models can be applied to graphs with different sizes and edge connectivities without additional training.
  • Supervised combinatorial-optimization methods learn from precomputed solutions, whereas RL formulates iterative solution search as an MDP and learns stage-wise policies.

3 Problem formulation

The paper represents JSSP states as feature-augmented disjunctive graphs and formulates scheduling as an MDP. It reduces computation by retaining only non-trivial transitions while preserving the original process through a semi-MDP interpretation.

  • 3.1 Graph state representation: In the disjunctive graph, operation nodes encode jobs, conjunctive edges encode precedence constraints, and disjunctive edges encode machine-sharing constraints.
  • 3.1 Graph state representation: Dynamic node features augment the static graph with operation status, processing time, and degree of completion during scheduling.
  • 3.1 Graph state representation: The graph state excludes dummy source and sink nodes because they represent imaginary operations without features.
  • 3.2 MDP formulation of JSSP: The scheduling process is formulated as an MDP whose state contains static and dynamically changing JSSP information and whose actions load operations onto available machines.
  • 3.3 Efficient MDP formulation of JSSP: The efficient formulation ignores computationally unattractive unit-time transitions driven by null actions and defines states around non-trivial scheduling opportunities.
  • 3.3 Efficient MDP formulation of JSSP: Non-trivial states require at least one available machine and at least two operations ready for processing on a machine.
  • 3.3 Efficient MDP formulation of JSSP: The index τ counts non-trivial transitions, while t(τ) identifies the corresponding primitive transition in the original process.
  • 3.3 Efficient MDP formulation of JSSP: When multiple machines are available, one is randomly sampled so each transition loads an operation and advances the primitive transition index.

4 Methodology

The methodology uses a relation-aware GNN to embed graph states and a dispatching policy to select feasible operations. PPO trains the representation and decision modules jointly, with stochastic action selection supporting trajectory exploration.

  • The framework combines a representation module that generates node embeddings with a dispatching module that computes feasible-action probabilities.
  • Node embeddings represent nodes in continuous vector space while preserving relational information for downstream scheduling decisions.
  • 4.1 Node embedding procedure: The proposed embedding layer explicitly models distinct JSSP relations through precedent, succedent, disjunctive, and target node updater functions.
  • 4.1 Node embedding procedure: The embedding update uses ReLU and concatenation, with neighborhood sets distinguishing precedent, succedent, and disjunctive relationships.
  • 4.1 Node embedding procedure: Each updated node embedding uses six inputs, including neighborhood embeddings, graph-level context, previous embeddings, and initial node features.
  • 4.1 Node embedding procedure: Stacking K embedding layers gives node embeddings information from K-hop neighborhoods and produces a graph-level representation of the JSSP.
  • 4.2 Decision making with node embedding: The actor maps node embeddings to logits and applies softmax over processible nodes, selecting one feasible scheduling action stochastically.
  • 4.2 Decision making with node embedding: The stochastic policy explores multiple suboptimal scheduling trajectories, while PPO supplies a critic-based policy-gradient training procedure.

5 Training procedure

The training procedure simulates JSSP transitions and jointly optimizes the GNN representation and decision-making policy with PPO. It uses waiting-job rewards, graph-based actor–critic modules, and periodically regenerated instances to train and validate the scheduler.

  • Training procedure: The simulator transforms JSSP states into disjunctive graphs, applies scheduling actions, advances trivial actions automatically, and emits transition samples for reinforcement learning.It also computes the cumulative reward associated with each transition.
  • Reward design: The policy minimizes makespan using a waiting-job reward equal to the negative number of waiting jobs at each transition.The cumulative waiting-job objective is strongly associated with minimizing makespan and provides more frequent training signals than a terminal makespan reward.
  • PPO training: PPO jointly updates the GNN and policy parameters with a clipped surrogate objective, limiting policy-ratio changes to [1−ϵ, 1+ϵ].The objective also uses generalized advantage estimation, a value-function error, and an entropy bonus for exploration.
  • Decision modules: The actor produces a softmax probability distribution over feasible operations, while actor and critic MLPs compute node logits and graph values from learned embeddings.The implementation uses 8-dimensional node embeddings and three GNN embedding iterations.
  • Hyperparameters: K = 3 embedding iterations were sufficient for the largest testing JSSP with 20 machines and 100 jobs, while larger K increased computation without significant performance gains.Deeper and wider ReLU networks likewise did not improve scheduling performance.
  • Training schedule: Training collects transitions from 20 episodes over 20 instances, regenerates random instances every five updates, and stops when validation makespan converges.Initial training instances vary machines, jobs, processing times, machine order, and operation assignments.

6 Experiments

The experiments evaluate the GNN scheduler against dispatching rules and learning-based schedulers, emphasizing zero-shot performance on unseen JSSP instances. Across testing distributions, benchmark types, sizes, and altered processing-time or order distributions, the scheduler generally maintains strong performance and transferability.

  • Experimental setup: The experiments use a zero-shot GNN scheduler, pretrained without additional training, to evaluate testing-distribution, benchmark, and generalization performance.Testing includes instances sampled from the training distribution, literature benchmarks, and transferability tests involving different instance properties.
  • Performance evaluation on testing distribution: The GNN scheduler achieved 14.7% average relative error on testing-distribution instances, outperforming all evaluated PDRs.Only MOR achieved comparable performance; the other PDRs exceeded 20% relative error.
  • Performance evaluation on benchmark problems: Across benchmark types, average relative errors ranged from 12.6% to 20.9%, with the GNN scheduler lowest except on ABZ and TA.On ABZ and TA, its difference from the best PDR was within 0.1%.
  • Performance evaluation on benchmark problems: The scheduler ranked best across nearly all instance sizes, ranking second for 20×30 and 20×50 with 4.4% and 2.7% gaps from the best PDR.The 6×6 benchmark size was excluded because only FT06 represents that size.
  • Performance evaluation on benchmark problems: The GNN scheduler was relatively robust to variations in problem distribution and size, whereas MOR and FIFO deteriorated substantially on SVW benchmarks.The authors attribute this robustness to graph embeddings that extract state features across sizes and processing times.
  • Performance evaluation on benchmark problems: Relative error varied significantly across benchmark instances, reflecting differences in problem characteristics and difficulty.Because optimal schedules are unique assignment sequences, a single order change can substantially degrade performance.
  • Comparison of generalization performance for learning-based schedulers: GNN1, GNN2, and GNN3 achieved the lowest errors when training and testing sizes matched but processing times and order distributions differed.GNN0 also scheduled all test JSSPs with only slightly increased error, suggesting transfer from small training instances to larger ones.

7 Analysis on computational complexity

The computational-complexity analysis varies the numbers of jobs and machines to measure how GNN embedding time scales with JSSP size. Runtime grows approximately quadratically with jobs and proportionally with machines, and exceeds PDR runtime in the reported implementation.

  • Experimental design: The analysis varies the number of jobs while fixing machines, and varies machines while fixing jobs, to assess computational complexity.The experiments quantify how embedding computations change with each graph-size factor.
  • Scaling with instance size: Computational time is likely proportional to the square of the number of jobs, with fitted curve y = 0.0125n^2 −0.1857n + 0.7543 and R^2 = 0.9984.The fitted second-order polynomial describes the job-count relationship.
  • Scaling with instance size: Computational time seems proportional to the number of machines, consistent with JSSP graph edge counts proportional to n^2 + nm.The graph structure provides the stated basis for both scaling relationships.
  • Comparison with PDRs: The GNN scheduler requires more computational time than PDRs because it computes node embeddings before selecting actions.The reported implementation uses no parallelization, although the authors expect parallel embedding computation to reduce the gap.

8 Conclusion

The paper formulates JSSP scheduling as an MDP with graph states and trains a GNN scheduler using reinforcement learning. The resulting scheduler generalizes across instance distributions and sizes, while computational cost and practical constraints remain limitations.

  • 8 Conclusion: The framework represents JSSP states as graphs and uses a GNN to learn node embeddings that capture spatial structure.The scheduling module uses these embeddings to recommend the next operation, while RL accounts for temporal effects across dispatching decisions.
  • 8 Conclusion: The GNN scheduler outperformed all PDRs on instances generated from the training distribution and showed more robust performance across benchmark sets.PDR solution quality fluctuated with the properties of the given JSSP.
  • 8 Conclusion: The scheduler achieved better scheduling than RL-based schedulers under the stated testing restriction.
  • 8 Conclusion: Training on small JSSPs enabled the scheduler to generate high-quality schedules for larger JSSPs without additional training.The authors describe this as a generalizable scheduling policy.
  • 8 Conclusion: Node-embedding computation rapidly increases with JSSP size because the graph requires n^2 + nm edges.The authors plan to reduce this cost by introducing machine nodes and reducing the edge count toward mn.
  • 8 Conclusion: The current formulation excludes practical constraints including batch processes, waiting-time regulations, and flexible-shop settings.The authors propose expanding the MDP and modifying rewards to address these constraints.

A Generating distributions of benchmark JSSP instances

The appendix summarizes how benchmark JSSP instances were generated. It notes that the original manuscripts for the FT, LA, and SWV instances were inaccessible to the authors.

  • A Generating distributions of benchmark JSSP instances: The benchmark-instance appendix provides a generating-procedure summary for each benchmark JSSP instance.
  • A Generating distributions of benchmark JSSP instances: The original manuscripts proposing the FT, LA, and SWV instances were not accessible to the authors.
  • A Generating distributions of benchmark JSSP instances: The stated lack of access concerns the source manuscripts for these benchmark-instance generation procedures.

A.1 ORB instances

ORB instances comprise ten 10 × 10 problems assembled from five existing instances and five original instances. The original ORB1–5 generation procedure is described only broadly.

  • A.1 ORB instances: All ORB instances have size 10 × 10.
  • A.1 ORB instances: The ORB set combines five collected instances—MT10, ABZ5, ABZ6, LA19, and LA20—with five original instances named ORB1 through ORB5.
  • A.1 ORB instances: The original ORB1–5 generation procedure is not specified precisely.The authors report that the instances were generated in Bonn in 1986 with prescribed processing orders designed to make the problems difficult.
  • A.1 ORB instances: For each original problem, two random processing-time sets were generated and the set with the greatest gap between the optimum and a standard lower bound was retained.

A.2 ABZ instances

ABZ5–9 instances require every job to visit every machine, with randomly generated machine sequences and instance-specific uniform processing-time distributions.

  • A.2 ABZ instances: In all ABZ5–9 instances, every job is processed on all machines.
  • A.2 ABZ instances: Each job’s machine sequence is randomly generated from a uniform distribution.
  • A.2 ABZ instances: ABZ5 processing times follow the integer uniform distribution U[50, 100].
  • A.2 ABZ instances: ABZ6, AB7, AB8, and AB9 processing times follow U[25, 100], U[11, 40], U[11, 40], and U[11, 40], respectively.

A.3 YN instances

The YN1-4 instances are fixed at size 20 × 20 with processing times sampled from U[10, 50], while TA01-80 varies in size and uses U[1, 99] processing times. TA01-80 machine orders are generated through randomized swaps of succeeding operations.

  • YN1-4 instances all have 20 × 20 jobs and machines, with processing times sampled from U[10, 50].
  • YN1-4 does not specify the generation scheme for machine sequences of jobs.
  • TA01-80 draws machines from U[15, 20], jobs from U[15, 100], and processing times from U[1, 99].
  • TA01-80 machine orders begin without perturbation, then repeatedly swap each assigned machine with a randomly chosen succeeding operation.
Loading 2106.01086v1…