Source-linked AI summary
Flexible Job Shop Scheduling via Dual Attention Network Based Reinforcement Learning
Runqing Wang, Gang Wang, Jian Sun, Fang Deng, Jie Chen
TL;DR
FJSP requires coordinated operation sequencing and machine assignment, while existing DRL methods can still lag exact solvers and struggle with representation and scalability. The paper proposes DANIEL, combining a compact state representation, dual attention over operations and machines, and size-agnostic DRL. DANIEL outperforms traditional PDRs and state-of-the-art DRL, matches exact methods in some cases, and generalizes to large-scale and unseen tasks.
Problem
FJSP has complex operation–machine relationships, and existing DRL solutions still have room to improve relative to exact methods while requiring better state representations and scalable decision-making.
Method
DANIEL combines a tight state representation, dual attention over operation precedence and machine competition, and size-agnostic DRL for joint operation sequencing and machine assignment.
Results
DANIEL outperforms traditional PDRs and the state-of-the-art DRL method, achieves results comparable to exact methods in some cases, and generalizes to large-scale and unseen FJSP tasks.
Takeaways & Limitations
The framework provides computationally efficient, high-quality scheduling across synthetic and public benchmark instances, including cases where it beats OR-Tools.
Abstract
from arXiv · showhide
Flexible manufacturing has given rise to complex scheduling problems such as the flexible job shop scheduling problem (FJSP). In FJSP, operations can be processed on multiple machines, leading to intricate relationships between operations and machines. Recent works have employed deep reinforcement learning (DRL) to learn priority dispatching rules (PDRs) for solving FJSP. However, the quality of solutions still has room for improvement relative to that by the exact methods such as OR-Tools. To address this issue, this paper presents a novel end-to-end learning framework that weds the merits of self-attention models for deep feature extraction and DRL for scalable decision-making. The complex relationships between operations and machines are represented precisely and concisely, for which a dual-attention network (DAN) comprising several interconnected operation message attention blocks and machine message attention blocks is proposed. The DAN exploits the complicated relationships to construct production-adaptive operation and machine features to support high-quality decisionmaking. Experimental results using synthetic data as well as public benchmarks corroborate that the proposed approach outperforms both traditional PDRs and the state-of-the-art DRL method. Moreover, it achieves results comparable to exact methods in certain cases and demonstrates favorable generalization ability to large-scale and real-world unseen FJSP tasks.
I. INTRODUCTION
FJSP captures flexible manufacturing but remains difficult because operation sequencing and machine assignment create a large, constrained solution space. DANIEL addresses limitations in existing DRL approaches with a compact state representation, dual attention, and size-agnostic decision-making, achieving strong benchmark performance and generalization.
- I. INTRODUCTION: FJSP extends job-shop scheduling by allowing each operation to use multiple machines, adding machine assignment to operation sequencing and enlarging the solution space.The objective can include minimizing completion time, while FJSP is described as strongly NP-hard.
- I. INTRODUCTION: Existing DRL methods improve on traditional priority dispatching rules but still require more precise state representations and better exploitation of operation–machine relationships.Completed operations may be irrelevant at a given step, while representing all operations can reduce performance and efficiency.
- I. INTRODUCTION: DANIEL introduces a tight state representation containing decision-relevant operations and machines, with a state space that decreases as scheduling proceeds.The representation is designed to be minimal and sufficient for downstream decision-making.
- I. INTRODUCTION: Its dual-attention network extracts operation features from precedence constraints and machine features from competitive relationships between machines.The architecture contains interconnected operation and machine message attention blocks.
- I. INTRODUCTION: The framework uses size-agnostic DRL to address operation sequencing and machine assignment jointly rather than as isolated decisions.This supports a single learned approach across different problem sizes.
- I. INTRODUCTION: DANIEL outperforms traditional PDRs and the state-of-the-art DRL method on two synthetic data distributions by a considerable margin.The supplied introduction reports that performance is comparable to exact methods with time limits on some tasks.
- I. INTRODUCTION: Models trained on small-scale instances generalize to large-scale and out-of-distribution instances while producing high-quality solutions.The paper frames this generalization as favorable performance on unseen task distributions.
II. PRELIMINARIES AND PROBLEM FORMULATION
The preliminaries formulate FJSP as a constrained scheduling problem and represent its structure with a disjunctive graph. They also introduce GATs, which use learned attention to aggregate neighboring features into node embeddings.
- A. Flexible job-shop scheduling problem and disjunctive graph: Each job contains an ordered sequence of operations, and each operation may be processed by multiple compatible machines with machine-dependent processing times.All jobs are assumed to arrive simultaneously at production time Ts = 0.
- A. Flexible job-shop scheduling problem and disjunctive graph: FJSP assigns each operation to one compatible machine and a start time while respecting job precedence and machine-capacity constraints.Its objective is to minimize the maximum completion time, or makespan.
- A. Flexible job-shop scheduling problem and disjunctive graph: The disjunctive graph represents operations and start/end dummy nodes as vertices, with directed conjunctions encoding within-job processing order.The graph is written as G = (V, C, D).
- A. Flexible job-shop scheduling problem and disjunctive graph: Figure 1 depicts the disjunctive-graph representation used for FJSP.The figure is identified as the disjunctive graph for FJSP.
- A. Flexible job-shop scheduling problem and disjunctive graph: Undirected disjunctions connect operations that can be processed by the same machine, and updating these edges yields a feasible scheduling solution.An operation can participate in disjunction groups for different compatible machines.
- B. Graph attention network: A graph attention layer takes nodal feature vectors as input and produces a new feature vector for each node.Each node aggregates information from its first-hop neighbors, including itself.
- B. Graph attention network: GAT attention coefficients are computed from transformed pairs of node features and normalized with a softmax function.The transformation is shared across nodes, while the attention mechanism uses a learned weight vector and LeakyReLU activation.
- B. Graph attention network: The normalized coefficients weight neighboring features, whose sum is passed through a nonlinear activation to form the updated node representation.Multiple graph attention layers can be stacked, with final node embeddings used for downstream tasks.
III. THE PROPOSED METHOD
DANIEL formulates FJSP scheduling as an MDP in which the agent repeatedly assigns compatible operation-machine pairs, using a compact state and makespan-related rewards. Its end-to-end workflow combines dual-attention feature extraction with DRL decision-making.
- III. THE PROPOSED METHOD: The proposed workflow combines a dual attention network for operation-machine feature extraction with an actor-critic DRL network that prioritizes available operation-machine pairs.The policy produces a probability distribution over feasible actions from the current state.
- A. MDP formulation of FJSP: DANIEL models scheduling as an MDP where each action assigns a compatible operation to an idle machine at the current production time.The environment updates production status and returns a reward related to makespan after each assignment.
- A. MDP formulation of FJSP: The state retains features for relevant operations, machines, and compatible pairs while excluding entities that cannot affect subsequent scheduling.This state becomes smaller as scheduling proceeds, supporting real-time and large-scale applications.
- A. MDP formulation of FJSP: The action space consists of all compatible operation-machine pairs and shrinks as more operations are scheduled.The environment updates the relevant entity sets, action set, and features after each action.
- A. MDP formulation of FJSP: Rewards are based on differences between estimated makespan values at consecutive decision steps, linking cumulative reward to makespan minimization.With γ = 1, maximizing cumulative reward is equivalent to minimizing makespan.
B. Dual attention network
The dual attention network separates operation precedence relationships from dynamic machine competition. Its attention blocks, multi-head processing, pooling, and reduced graph structure produce compact features for downstream scheduling decisions.
- B. Dual attention network: DAN decomposes operation and machine relationships into separate attention blocks, explicitly modeling precedence among operations and competition among machines.The machine block uses dynamic eligibility and competition information, while the operation block connects operations through job precedence.
- B. Dual attention network: The operation message block attends to an operation’s predecessor, itself, and successor, using dynamic masking as operations disappear from the state.Stacked blocks propagate messages across all operations in a job.
- B. Dual attention network: The machine message block represents competition between two machines through the operations they can both process, with competition changing as production proceeds.The summed features of competed candidates provide a competition measure used to compute machine attention coefficients.
- B. Dual attention network: Multiple attention heads learn varied relationships, and separate average pooling of operation and machine features is concatenated into global instance features.These learned global features are used by downstream decision-making tasks.
- B. Dual attention network: DAN reduces computational overhead by handling two smaller graphs with O(3|O|+|M|^2) total connections instead of a larger disjunctive-graph representation.The machine graph captures disjunctive competition, while the operation graph retains precedence structure.
C. Decision-making module
The decision-making module uses actor-critic reinforcement learning to score feasible operation-machine actions and convert their scores into a size-agnostic stochastic policy, while a critic estimates state value.
- C. Decision-making module: The actor concatenates operation, machine, global, and compatible-pair features, then uses an MLP to produce a scalar score for each feasible action.The actor applies a softmax over these scores to generate the action distribution.
- C. Decision-making module: The policy probability for each feasible action is obtained by applying softmax normalization to its actor score.This preserves a distribution over the current action set A(t).
- C. Decision-making module: The critic receives the global feature representation and outputs a scalar estimate of the current state value.The actor and critic use separate MLPs with parameters θ and ϕ, respectively.
D. Training procedure
DANIEL is trained with PPO using parallel same-scale FJSP environments, collected transitions, generalized advantage estimates, repeated parameter updates, resampling, and validation.
- D. Training procedure: PPO trains DANIEL by collecting transitions from parallel same-scale FJSP environments and updating the model parameters from those data.Each transition contains the current state, sampled action, reward, and next state.
- D. Training procedure: During each episode, the behavior policy samples actions, receives rewards and successor states, and records transitions across environment steps.The procedure iterates over training instances and time steps before computing update statistics.
- D. Training procedure: Generalized advantage estimates are computed from collected transitions before the total loss is used to update all parameters.The algorithm repeats parameter updates for K iterations within the training loop.
- D. Training procedure: Training data are periodically resampled, and the current policy is periodically validated on a fixed validation set.These operations occur every Nr and Nval episodes, respectively.
IV. EXPERIMENTS
The experiments compare DANIEL with dispatching rules, exact optimization, genetic algorithms, and a state-of-the-art DRL method on synthetic and public FJSP benchmarks.
- DANIEL is evaluated against PDRs, Google OR-Tools, a genetic algorithm, and the DRL method from.
A. Datasets
The study uses two synthetic FJSP distributions across six instance scales, training on smaller instances and testing on larger and public benchmark tasks.
- Two synthetic distributions, SD1 and SD2, are used to examine learning and generalization.SD1 permits varying numbers of operations, while SD2 uses a wider processing-time range.
- Experiments cover six scales from 10×5 to 40×10, with training on four smaller sizes and testing on two larger sizes.Validation and unseen testing sets each contain 100 instances.
- The model uses two dual-attention layers with four attention heads per layer, alongside specified MLP and PPO hyperparameters.
C. Baselines and performance metrics
The evaluation compares DANIEL with heuristic, exact, genetic, and DRL baselines using makespan and optimality-gap performance on synthetic instances.
- DANIEL outperforms all PDRs and improves over the DRL solution across both synthetic data distributions and problem sizes.The comparison reports average makespan and gap on testing instances matching each model’s training scale and distribution.
- DANIEL beats OR-Tools by 1.03% on 20 × 10 SD1 instances, although OR-Tools solved none of those instances optimally within the time limit.
- DANIEL’s optimality gap is below 5% on three tasks when using the sampling strategy.
- DANIEL remains computationally efficient, with runtime comparable to PDRs and close to.
- DANIEL converges more smoothly to better solutions than DRL on the tested 10 × 5 and 20 × 10 instances.The curves average makespan over 100 validation instances using matched training and validation settings.
E. Results on benchmarks
On public benchmarks, DANIEL combines attention-based representation learning with reinforcement learning and generally surpasses or matches the prior DRL method while retaining practical runtime.
- DANIEL outperforms the state-of-the-art DRL method on most public benchmark cases and has comparable performance in the remaining cases.Both DRL methods outperform the best PDR with acceptable runtime, while OR-Tools and 2SGA generally achieve better performance at much higher computational cost.
- DANIEL jointly addresses operation sequencing and machine assignment through a dual attention network and actor-critic reinforcement learning.The method uses GAT-style attention to extract features from decision-relevant operations and machines and is trained with PPO.
- The framework is size-agnostic, training on small problems and deploying on larger-scale and real-world instances.
VI. APPENDIX
The state representation records feature vectors for operations, machines, and their scheduling status. These features capture processing-time characteristics, workload, readiness, and machine availability.
- Operation features include processing-time statistics, compatibility proportion, scheduling status, completion-time lower bound, and remaining job workload.Dynamic properties also include waiting time and remaining processing time.
- Job-level features include remaining operation count and the summed average processing time of unscheduled operations.
- Operation-state features track waiting time and remaining processing time to distinguish ready, scheduled, and unfinished operations.Waiting time is zero for operations that are not ready, while remaining processing time is zero for unscheduled operations.
- Machine features describe processing-time statistics, the number of schedulable and unscheduled operations, candidate count, and machine availability.Availability is represented through free time, waiting time, working status, and remaining processing time.
- Machine-state features encode whether a machine is free or working and quantify its associated waiting and remaining processing times.Working and remaining-processing indicators are zero when the machine is free.
3) Features of compatible operation-machine pairs:
Compatible operation-machine pairs are represented with eight features centered on processing time and normalized comparisons. The representation also incorporates operation workload and combined operation-machine waiting time.
- Each compatible operation-machine pair records processing time plus ratios against several operation, machine, and candidate processing-time maxima.The ratios compare the pair with the operation, machine candidates, unscheduled operations, and compatible pairs.
- Pair features normalize processing time against the remaining workload of the operation’s job.
- The representation also sums the operation’s and machine’s waiting times.