This paper introduces UP-AAC, a novel Deep Reinforcement Learning (DRL) framework designed to optimize Job-Shop Scheduling Problems (JSSP) under structural uncertainty. The core idea is an Asymmetric Actor-Critic (AAC) architecture that trains the Critic on deterministic hindsight states to provide stable learning signals, decoupled from environmental stochasticity. Complementing this, an Uncertainty Perception Model (UPM) quantifies and incorporates global risk insights. UP-AAC empirically demonstrates state-of-the-art performance, outperforming existing approaches in reducing makespan on benchmark instances.
Problem
The paper addresses the following bottlenecks in Job-Shop Scheduling under structural uncertainty:
Structural Uncertainty: Unlike parameter uncertainty (e.g., variable processing times), structural uncertainty arises when a job's processing route is not fixed but may branch into multiple paths, determined dynamically by situational factors not known in advance. This transforms scheduling from a static sequencing task into a dynamic planning challenge.
Incorrect Credit Assignment: In standard Actor-Critic (AC) frameworks, the Critic evaluates actions based on stochastic states, leading to high variance in the learning signal. A high-quality action might be unfairly penalized if it leads to a time-consuming path due to random path realizations, or a poor action rewarded if it happens to follow a time-efficient path.
Unstable Learning and Ineffective Policy Optimization: The high variance in reward signals, driven by environmental stochasticity rather than the policy's actual performance, undermines the reliability of the Critic's baseline. This results in unstable gradients and hinders effective policy optimization for the Actor.
Key Contributions
UP-AAC Framework: Proposal of UP-AAC, a novel DRL framework to solve JSSP with structural uncertainty, featuring a core Asymmetric Actor-Critic architecture that enables stable learning in highly stochastic environments.
Uncertainty Perception Model (UPM): Introduction of UPM, a knowledge-guided module that explicitly quantifies and incorporates uncertainty, enhancing policy robustness.
State-of-the-Art Performance: Extensive experiments demonstrating that the method achieves state-of-the-art performance, outperforming a wide range of baselines.
Method
The UP-AAC framework integrates offline uncertainty analysis from the UPM with online policy learning of the Asymmetric Actor-Critic (AAC) architecture. The process alternates between collecting experience in the stochastic environment and performing asymmetric updates using hindsight-reconstructed data.
Markov Decision Process Formulation: The scheduling process is formulated as an MDP to minimize makespan.
State (S): Represented by a dynamic disjunctive graph, referred to as the stochastic state (Ssto), where nodes correspond to uncompleted operations with attributes like status, processing time, and job-level metrics. Edges represent precedence and resource constraints.
Action (A): The agent selects an eligible operation for dispatch at discrete event points.
State Transition (P): Inherently stochastic, driven by structural uncertainty, where a branching operation leads to a single feasible path realization, altering the graph topology.
Reward (R): A dense reward shaping mechanism is used, where the immediate reward rt is the negative growth of the estimated makespan lower bound.
r(st, at) = CLB(St) – CLB(St+1)
where CLB(S) is the makespan lower bound.
Asymmetric Actor-Critic (AAC): This architecture decouples the Actor's exploration in a stochastic environment from the Critic's evaluation in a deterministic one, achieved via Hindsight Reconstruction.
Actor: Operates exclusively on the stochastic state Ssto, learning a policy πθ(at|Ssto,t) to make robust decisions in uncertain environments.
Critic: Trained exclusively on a deterministic state Sdet, which is reconstructed in hindsight using the specific path actually realized during an episode. This allows the Critic to learn a stable, low-variance state-value function Vφ(Sdet,t) by conditioning on a deterministic future.
Advantage Function: The Actor's policy gradient is calculated using a low-variance advantage estimate, where the value baseline is provided by the Critic based on the corresponding deterministic state.
A(Ssto,t, at) = rt + γVφ(Sdet,t+1) - Vφ(Sdet,t)
Uncertainty Perception Model (UPM): This module performs a one-time, offline analysis to generate a global risk feature vector, Zupm, to guide the Actor.
Heuristic Risk Prior: For each sampled deterministic JSSP scenario SCk, a prior pk is calculated based on maximum job length (Lmax) and maximum machine workload (Wmax).
pk = max(Lmax(SCk), Wmax(SCk))
Risk-Aware Attention: Each scenario SCk is encoded into a feature vector hk by a shared GNN encoder. An attention mechanism, modulated by the risk prior, aggregates information from ns = 100 scenarios into the final risk vector Zupm.
ejk = (Wqij)T(Wkhk) / √dk + w · Pk
Actor Conditioning: The static Zupm is concatenated with features from the dynamic state ssto,t, conditioning the Actor's policy πθ(at|Ssto,t, Zupm).
Technical Details
Architecture:
GNN Encoder: The core GNN encoder consists of 3 graph convolution layers.
Hidden Dimension: 72 for the GNN encoder.
Actor and Critic Networks: Both are 3-layer MLPs.
Activation Functions: Layer Normalization and LeakyReLU activation functions are incorporated in Actor and Critic networks.
Uncertainty Perception Model (UPM):
Scenario Sampling: ns = 100 deterministic scenarios are sampled for each instance during training to construct the stochastic path model.
Optimization:
Training Procedure: Alternates between collecting experience in the stochastic environment and performing asymmetric updates using hindsight-reconstructed data.
Critic Update: Minimizes the mean squared temporal-difference error using deterministic trajectory data.
Actor Update: Uses a low-variance advantage estimate from the Critic.
Implementation:
Framework: Implemented in PyTorch.
Hardware: Trained on a single NVIDIA V100 GPU.
Model Configuration: A separate, specialized UP-AAC model is trained for each of the 12 instance configurations.
Results
Datasets: 12 sets of benchmark instances, procedurally generated by adapting Taillard benchmark suite rules.
Problem Sizes (jobs × machines, branching operations per job):
Standard AC agent: Uses the same GNN architecture as UP-AAC but trained with a conventional setup where the Critic receives the same stochastic state as the Actor.
Reference Solutions:
Small/Medium instances (nj < 10): Optimal makespan (Copt) from a Constraint Programming (CP) solver.
Large instances (nj ∈ {15, 20}): Best makespan found among all tested methods.
Numeric Results (UP-AAC vs. Baselines):
Small/Medium Instances (Table 1 examples):
(5×10, 1): UP-AAC Avg 689.26, CVaR 721.99, Gap 1.86%. Best among baselines.
(10×20, 3): UP-AAC Avg 1334.83, CVaR 1457.83, Gap 2.37%. Best among baselines.
Large Instances (Table 2 examples):
(15×10, 1): UP-AAC Avg 1161.13, CVaR 1215.98. Best among baselines.
(20×20, 3): UP-AAC Avg 1884.30, CVaR 1967.20. Best among baselines.
Ablation Study (Table 3 examples for Small/Medium instances):
w/o UPM: (10×20, 3) Avg 1369.99, CVaR 1508.02 (Avg increases by 2.6%, CVaR by 3.4% compared to full UP-AAC).
w/o AAC: (10×10, 1) Avg 934.49, CVaR 1000.31 (Avg is higher than Standard AC Avg 930.98).
Overall Performance: UP-AAC consistently achieves the best performance across all instance sizes and uncertainty levels in terms of average makespan and Conditional Value-at-Risk. It averages a 1.94% gap on small/medium instances and 0.18% on large instances.
Runtime/Training Cost: Not stated in the paper.
Weaknesses / Limitations
Performance Gap on Large Instances: On large-scale instances, while UP-AAC maintains top-ranking performance, its relative improvement over the strongest baselines appears to be smaller. This is attributed to two factors: increased problem size and congestion making powerful heuristics more effective, and the Gap (%) for large instances being calculated against the "Best Found" solution from the experiment itself (an internal baseline), which is less stringent than the CP solver's optimal solution used for smaller instances, potentially leading to a perceived reduction in the performance gap.
Evidence
Method evidence: "To address this challenge, we propose UP-AAC, an integrated DRL framework with two key innovations. At its core is a novel Asymmetric Actor-Critic (AAC) architecture. Unlike in standard AC where the Critic observes the same uncertain states as the Actor (Smit et al. 2025; Zhang et al. 2020), our AAC redefines the Critic's learning process by training it on a deterministic hindsight state, reconstructed using the specific path actually realized during an episode." (section: Abstract)
Result evidence: "Across all instance sizes and uncertainty levels, UP-AAC achieves the best performance among all competing methods. In terms of average makespan (Avg), it consistently yields the most efficient solutions. Notably, its advantage is even more pronounced in the Conditional Value-at-Risk (CVaR) metric." (section: 5.2 Main Results Analysis)
Limitation evidence: "On large-scale instances (Table 2), while UP-AAC maintains its top-ranking performance, its relative improvement over the strongest baselines like MWKR appears to be smaller. This phenomenon can be attributed to two factors. First, as problem size and congestion increase, the scheduling environment becomes more constrained, making powerful heuristics that manage key bottlenecks more effective. UP-AAC's ability to consistently find superior solutions in these environments demonstrates its strength in fine-grained optimization. Second, the Gap (%) for large instances is calculated against the Best Found solution from the experiment itself, rather than a certified optimum. This internal baseline is inherently less stringent than the CP solver's optimal solution used for smaller instances, which can lead to a perceived reduction in the performance gap." (section: 5.2 Main Results Analysis)
Additional Figures
Figure 1: An example of the credit assignment problem. The same dispatched operation can lead to drastically different makespans due to random path realizations. This unfairly re- wards or penalizes the actor’s choice, obscuring the action’s true quality and hindering the learning process.