Graph-RHO: Critical-path-aware Heterogeneous Graph Network for Long-Horizon Flexible Job-Shop Scheduling

Yujie Li; Jiuniu Wang; Mugen Peng; Guangzuo Li; Wenjia Xu

cs.LGApr 11, 2026

Graph-RHO: Critical-path-aware Heterogeneous Graph Network for Long-Horizon Flexible Job-Shop Scheduling

Authors: Yujie Li, Jiuniu Wang, Mugen Peng, Guangzuo Li, Wenjia Xu

Organizations: Beijing University of Posts and Telecommunications Beijing, China · City University of Hong Kong Hong Kong, China · Chinese Academy of Sciences Beijing, China

Abstract

Long-horizon Flexible Job-Shop Scheduling~(FJSP) presents a formidable combinatorial challenge due to complex, interdependent decisions spanning extended time horizons. While learning-based Rolling Horizon Optimization~(RHO) has emerged as a promising paradigm to accelerate solving by identifying and fixing invariant operations, its effectiveness is hindered by the structural complexity of FJSP. Existing methods often fail to capture intricate graph-structured dependencies and ignore the asymmetric costs of prediction errors, in which misclassifying critical-path operations is significantly more detrimental than misclassifying non-critical ones. Furthermore, dynamic shifts in predictive confidence during the rolling process make static pruning thresholds inadequate. To address these limitations, we propose Graph-RHO, a novel critical-path-aware graph-based RHO framework. First, we introduce a topology-aware heterogeneous graph network that encodes subproblems as operation-machine graphs with multi-relational edges, leveraging edge-feature-aware message passing to predict operation stability. Second, we incorporate a critical-path-aware mechanism that injects inductive biases during training to distinguish highly sensitive bottleneck operations from robust ones. Third, we devise an adaptive thresholding strategy that dynamically calibrates decision boundaries based on online uncertainty estimation to align model predictions with the solver's search space. Extensive experiments on standard benchmarks demonstrate that \mbox{Graph-RHO} establishes a new state of the art in solution quality and computational efficiency. Remarkably, it exhibits exceptional zero-shot generalization, reducing solve time by over 30% on large-scale instances (2000 operations) while achieving superior solution quality. Our code is available here.

Figures & tables

Fig. 1: Illustration of Graph-RHO. Within the RHO loop, each subproblem is mapped to a heterogeneous graph that explicitly encodes topological constraints via multi-relational edges. Leveraging this structural representation, the neural network identifies stable operations (solid dark green lines) and fixes their machine assignments.

Fig. 2: Overview of Graph-RHO: i) Graph-RHO Inference : The model predicts stability probabilities for overlapping operations, employing an adaptive threshold $\tau_{t}$ to fix high-confidence variables and prune the search space for subproblem $\mathcal{P}_{t}$ . ii) Network Architecture : The $\mathbb{M}_{gnn}$ processes heterogeneous graph states via stacked GNN layers and global aggregation ( $f_{aggr}$ ) to simultaneously optimize operation stability ( $\hat{y}^{\text{fix}}$ ) and path criticality ( $\hat{y}^{\text{crit}}$ ) predictions. iii) Heterogeneous GNN Layer : The layer executes 4-path message passing to capture multi-relational dependencies, coupled with a reverse flow for machine updates. The GAT Inset illustrates the edge-feature-aware attention mechanism, where edge constraints $\mathbf{e}_{uv}^{r_{i}}$ are injected as structural bias.

Fig. 3: Temporal Distribution Shift and Thresholding Strategies. (Left) The Ridgeline plot illustrates the evolving density of predicted fix probabilities across RHO iterations. A static threshold (red line) fails to adapt, whereas our adaptive threshold (orange line) dynamically tracks the distribution’s tail. (Right) The resulting adaptive threshold values fluctuate to maintain a consistent fixing ratio.

	600 (10, 20, 30)		800 (10, 20, 40)		1200 (10, 20, 60)		2000 (10, 20, 100), Transfer
	Time (s) $\downarrow$	Makespan $\downarrow$	Time (s) $\downarrow$	Makespan $\downarrow$	Time (s) $\downarrow$	Makespan $\downarrow$	Time (s) $\downarrow$	Makespan $\downarrow$
CP-SAT (10 hours) [ 2 ]	36000	1583 $\pm$ 65	36000	2128 $\pm$ 75	36000	3206 $\pm$ 87	36000	18821 $\pm$ 1986
CP-SAT (30 minutes) [ 2 ]	1800	2274 $\pm$ 147	1800	4017 $\pm$ 413	1800	10925 $\pm$ 1013	1800	39585 $\pm$ 2707
GA [ 3 ]	1800	3659 $\pm$ 87	1800	5150 $\pm$ 92	1800	8086 $\pm$ 111	1800	10406 $\pm$ 640
ARD-LNS (Time-based) [ 19 ]	300	2100 $\pm$ 269	400	3298 $\pm$ 365	600	5115 $\pm$ 558	1000	14258 $\pm$ 1522
ARD-LNS (Machine-based) [ 19 ]	300	3974 $\pm$ 633	400	6594 $\pm$ 1227	600	12764 $\pm$ 4206	1000	52225 $\pm$ 1793

TABLE I: FJSP under Makespan Objective. Each column corresponds to a different FJSP size given by the format: total number of operations, followed by a tuple of (

N_{m},N_{j},N_{ops/job}

), i.e., number of machines

|\mathcal{M}|

, jobs

|\mathcal{J}|

, and operations per job. “Transfer” means transfer from the 1200 case without fine-tuning.

	Scale Generalization				Load Robustness
	$(15,30,30)$		$(20,40,30)$		$(10,30,30)$		$(10,40,30)$
Method	Time (s) $\downarrow$	Makespan $\downarrow$	Time (s) $\downarrow$	Makespan $\downarrow$	Time (s) $\downarrow$	Makespan $\downarrow$	Time (s) $\downarrow$	Makespan $\downarrow$
Default RHO	$179\pm 19$	$1455\pm 78$	$166\pm 9$	$1539\pm 84$	$354\pm 25$	$2176\pm 86$	$471\pm 30$	$2864\pm 85$
L-RHO	$72\pm 6$	$1451\pm 69$	$76\pm 7$	$1529\pm 78$	$196\pm 27$	$2162\pm 88$	$213\pm 36$	$2860\pm 105$
Graph-RHO (Ours)	42 $\pm$ 4	1435 $\pm$ 67	46 $\pm$ 3	1453 $\pm$ 75	142 $\pm$ 19	2144 $\pm$ 89	160 $\pm$ 20	2831 $\pm$ 101

TABLE II: Comparison of generalization capabilities across unseen problem scales and load densities. The model is trained solely on the small-scale (

10,20,30

) setting and directly evaluated on larger or denser instances without fine-tuning.

Method	$\mathbb{M}_{gnn}$	$\mathbb{M}_{cpa}$	$\mathbb{M}_{thr}$	Time (s) $\downarrow$	Makespan $\downarrow$	Time (s) $\downarrow$	Makespan $\downarrow$	Time (s) $\downarrow$	Makespan $\downarrow$	Time (s) $\downarrow$	Makespan $\downarrow$
	Core Contributions			600		800		1200		2000 (Transfer)
Default RHO (Baseline)	-	-	-	$244\pm 21$	$1558\pm 73$	$348\pm 26$	$2103\pm 78$	$545\pm 36$	$3136\pm 91$	$862\pm 42$	$5207\pm 114$
+ $\mathbb{M}_{gnn}$	$\checkmark$	-	-	$114\pm 19$	$1501\pm 72$	$143\pm 19$	$1995\pm 83$	$250\pm 36$	$2987\pm 99$	$415\pm 48$	$4962\pm 129$
+ $\mathbb{M}_{gnn}$ + $\mathbb{M}_{cpa}$	$\checkmark$	$\checkmark$	-	$114\pm 22$	$1498\pm 75$	$148\pm 21$	$1991\pm 76$	$232\pm 29$	$2982\pm 103$	$388\pm 36$	$4951\pm 124$
Graph-RHO (Full)	$\checkmark$	$\checkmark$	$\checkmark$	$\mathbf{99\pm 21}$	$\mathbf{1493\pm 73}$	$\mathbf{139\pm 29}$	$\mathbf{1985\pm 80}$	$\mathbf{189\pm 29}$	$\mathbf{2972\pm 97}$	$\mathbf{321\pm 30}$	$\mathbf{4938\pm 119}$

TABLE III: Ablation Studies. We incrementally integrate the three core contributions: Heterogeneous GNN Encoder, Critical-Path-Aware Mechanism, and Adaptive Thresholding, to evaluate their individual impact.

\mathbb{M}_{gnn}

introduces the GNN Encoder;

\mathbb{M}_{cpa}

introduces the critical-path-aware objective;

\mathbb{M}_{thr}

applies the confidence-aware inference strategy.

Flexible Job Shop Scheduling

See all 14 papers

Oct 19, 2026

CoRS: Fast Neural Flexible Job-Shop Scheduling via Composite Interval State Reuse

Neural solvers for the Flexible Job-Shop Scheduling Problem (FJSP) typically refresh graph representations and update feasibility after every operation--machine decision. However, only feasibility must remain exact at every step, whereas graph encoding is substantially more expensive and can potentially be refreshed less frequently. We present CoRS, which decouples them: an interval-level graph representation is reused across multiple sequential decisions, while a stepwise feasibility state is updated after every action. This two-timescale design amortizes graph encoding without parallelizing action generation or relaxing scheduling constraints. CoRS further develops a feasibility-preserving composite-interval decoding scheme with dynamic constraint tracking and boundary state synchronization, which reduces representation refresh frequency while maintaining continuous feasible schedule construction. Furthermore, to alleviate representation staleness caused by interval-level state reuse, CoRS introduces enhanced static features as a compensation mechanism. By providing more comprehensive structural information of the scheduling problem, these features improve the model's perception of overall problem characteristics. Extensive experiments on synthetic and multiple public FJSP benchmarks demonstrate that CoRS significantly reduces inference time while maintaining competitive solution quality, achieving favorable speed-quality trade-offs under tight wall-clock budgets and low-latency scenarios.

Jiang Sutong, Zhao Peng, Wu Xuan +6

College of Computer Science and Technology, Jilin University, China · College of Software, Jilin University, China · College of Computing and Data Science, Nanyang Technological University, Singapore +1

Flexible Job Shop Scheduling Neural Combinatorial Optimization Inference-Time Optimization

Ask PDF

Mar 6, 2026

HGT-Scheduler: Deep Reinforcement Learning for the Job Shop Scheduling Problem via Heterogeneous Graph Transformers

The Job Shop Scheduling Problem (JSSP) is commonly formulated as a disjunctive graph in which nodes represent operations and edges encode technological precedence constraints as well as machine-sharing conflicts. Most existing reinforcement learning approaches model this graph as homogeneous, merging job-precedence and machine-contention edges into a single relation type. Such a simplification overlooks the intrinsic heterogeneity of the problem structure and may lead to the loss of critical relational information. To address this limitation, we propose the Heterogeneous Graph Transformer (HGT)-Scheduler, a reinforcement learning framework that models the JSSP as a heterogeneous graph. The proposed architecture leverages a Heterogeneous Graph Transformer to capture type-specific relational patterns through edge-type-dependent attention mechanisms applied to precedence and contention relations. The scheduling policy is trained using Proximal Policy Optimization. The effectiveness of the proposed method is evaluated on the Fisher--Thompson benchmark instances. On the FT06 instance, the HGT-Scheduler achieves an optimality gap of 8.4%, statistically outperforming both an identical architecture that ignores edge types (

p = 0.011

) and a standard Graph Isomorphism Network baseline. On the larger FT10 instance, the approach demonstrates favorable scalability. However, under a 50,000-step training limit, the performance of heterogeneous and homogeneous graph models is comparable, suggesting that edge-type awareness requires longer training horizons for larger problem instances. Ablation analyses further indicate that a three-layer attention architecture provides the best performance. Overall, the results confirm that explicitly modeling distinct edge semantics improves the learning of effective scheduling policies.

Bulent Soykan

Institute for Simulation and Training, University of Central Florida, Orlando, FL, USA

Job Shop Scheduling RL for Combinatorial Optimization

Ask PDF

Mar 3, 2026

Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling

The rise of smart manufacturing under Industry 4.0 introduces mass customization and dynamic production, demanding more advanced and flexible scheduling techniques. The flexible job-shop scheduling problem (FJSP) has attracted significant attention due to its complex constraints and strong alignment with real-world production scenarios. Current deep reinforcement learning (DRL)-based approaches to FJSP predominantly employ constructive methods. While effective, they often fall short of reaching (near-)optimal solutions. In contrast, improvement-based methods iteratively explore the neighborhood of initial solutions and are more effective in approaching optimality. However, the flexible machine allocation in FJSP poses significant challenges to the application of this framework, including accurate state representation, effective policy learning, and efficient search strategies. To address these challenges, this paper proposes a Memory-enhanced Improvement Search framework with heterogeneous graph representation--MIStar. It employs a novel heterogeneous disjunctive graph that explicitly models the operation sequences on machines to accurately represent scheduling solutions. Moreover, a memoryenhanced heterogeneous graph neural network (MHGNN) is designed for feature extraction, leveraging historical trajectories to enhance the decision-making capability of the policy network. Finally, a parallel greedy search strategy is adopted to explore the solution space, enabling superior solutions with fewer iterations. Extensive experiments on synthetic data and public benchmarks demonstrate that MIStar significantly outperforms both traditional handcrafted improvement heuristics and state-of-the-art DRL-based constructive methods.

Jiaqi Wang, Zhiguang Cao, Peng Zhao +4

Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University · College of Software, Jilin University · Singapore Management University +2

Flexible Job Shop Scheduling Job Shop Scheduling Combinatorial Optimization RL for Combinatorial Optimization Heterogeneous GNNs

Ask PDF

Abstract

Flexible Job Shop Scheduling

Explore similar work

CoRS: Fast Neural Flexible Job-Shop Scheduling via Composite Interval State Reuse

HGT-Scheduler: Deep Reinforcement Learning for the Job Shop Scheduling Problem via Heterogeneous Graph Transformers

Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling