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

• URL: http://arxiv.org/abs/2604.10073v1
• Date: Sat, 11 Apr 2026 07:35:09 GMT
• Title: Graph-RHO: Critical-path-aware Heterogeneous Graph Network for Long-Horizon Flexible Job-Shop Scheduling
• Abstract summary: Graph-RHO is a novel critical-path-aware graph-based RHO framework.<n>We introduce a topology-aware heterogeneous graph network that encodes subproblems as operation-machine graphs with multi-relational edges.<n>We incorporate a critical-path-aware mechanism that injects inductive biases during training to distinguish highly sensitive bottleneck operations from robust ones.
• Score: 26.97705087364345
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 \href{https://github.com/IntelliSensing/Graph-RHO}{here}.

Related papers

• Defending against Model Extraction for GNNs with Model Reprogramming [57.82196268649236]
  Graph Neural Networks (GNNs) serve as the backbone for high-stakes applications in Machine-Learning-as-a-Service (ML)<n>Still, their black-box deployment exposes them to Model Extraction (ME) attacks.<n>Existing defenses suffer from a critical ''Euclidean bias''<n>We propose GraphRP, a proactive defense framework that repurposes Model Reprogramming for security.
  arXiv  Detail & Related papers  (2026-08-11T23:20:15Z)
• Understanding Rollout Error in Graph World Models [2.571318992830046]
  This paper studies long-horizon rollout error in Graph World Models (GWMs)<n>We formulate a unified fixed-edge and dynamic-edge GWM framework with action nodes for node-, edge-, and graph-level decisions.<n>We propose Error-Aware GWM, which combines spectral regularization, rollout consistency, and critical-node weighting.
  arXiv  Detail & Related papers  (2026-06-26T07:11:29Z)
• RAPNet: Accelerating Algebraic Multigrid with Learned Sparse Corrections [11.742065170002164]
  We propose RAPNet, a graph neural network (GNN) framework that resolves the trade-off between sparsity and convergence quality of coarse-grid operators.<n>Key to our approach is a level-wise training strategy that enables learning from small subgraphs and generalization to million-node domains.<n>We show that our method outperforms classical non-Galerkin baselines on diverse PDE discretizations and graph Laplacians.
  arXiv  Detail & Related papers  (2026-05-26T11:14:59Z)
• HGT-Scheduler: Deep Reinforcement Learning for the Job Shop Scheduling Problem via Heterogeneous Graph Transformers [0.0]
  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.<n>Most existing reinforcement learning approaches model this graph as homogeneous, merging job-precedence and machine-contention edges into a single relation type.<n>We propose the Heterogeneous Graph Transformer (HGT)-Scheduler, a reinforcement learning framework that models the JSSP as a heterogeneous graph.
  arXiv  Detail & Related papers  (2026-03-06T17:59:12Z)
• HELP: HyperNode Expansion and Logical Path-Guided Evidence Localization for Accurate and Efficient GraphRAG [53.30561659838455]
  Large Language Models (LLMs) often struggle with inherent knowledge boundaries and hallucinations.<n>Retrieval-Augmented Generation (RAG) frequently overlooks structural interdependencies essential for multi-hop reasoning.<n>Help achieves competitive performance across multiple simple and multi-hop QA benchmarks and up to a 28.8$times$ speedup over leading Graph-based RAG baselines.
  arXiv  Detail & Related papers  (2026-02-24T14:05:29Z)
• Evolutionary Router Feature Generation for Zero-Shot Graph Anomaly Detection with Mixture-of-Experts [60.60414602796664]
  We propose a novel MoE framework with evolutionary router feature generation (EvoFG) for zero-shot GAD.<n>EvoFG consistently outperforms state-of-the-art baselines, achieving strong and stable zero-shot GAD performance.
  arXiv  Detail & Related papers  (2026-02-12T06:16:51Z)
• Resource-Aware Neural Network Pruning Using Graph-based Reinforcement Learning [0.8890833546984916]
  This paper presents a novel approach to neural network pruning by integrating a graph-based observation space into an AutoML framework.<n>Our framework transforms the pruning process by introducing a graph representation of the target neural network.<n>For the action space we transition from continuous pruning ratios to fine-grained binary action spaces.
  arXiv  Detail & Related papers  (2025-09-04T15:05:05Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  Decentralized server (DFL) eliminates reliance on client-client architecture.<n>Non-smooth regularization is often incorporated into machine learning tasks.<n>We propose a novel novel DNCFL algorithm to solve these problems.
  arXiv  Detail & Related papers  (2025-04-17T08:32:25Z)
• Adaptive Homophily Clustering: Structure Homophily Graph Learning with Adaptive Filter for Hyperspectral Image [21.709368882043897]
  Hyperspectral image (HSI) clustering has been a fundamental but challenging task with zero training labels.<n>In this paper, a homophily structure graph learning with an adaptive filter clustering method (AHSGC) for HSI is proposed.<n>Our AHSGC contains high clustering accuracy, low computational complexity, and strong robustness.
  arXiv  Detail & Related papers  (2025-01-03T01:54:16Z)
• Scalable and Effective Negative Sample Generation for Hyperedge Prediction [55.9298019975967]
  Hyperedge prediction is crucial for understanding complex multi-entity interactions in web-based applications. Traditional methods often face difficulties in generating high-quality negative samples due to imbalance between positive and negative instances. We present the scalable and effective negative sample generation for Hyperedge Prediction (SEHP) framework, which utilizes diffusion models to tackle these challenges.
  arXiv  Detail & Related papers  (2024-11-19T09:16:25Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  We introduce the first-ever completely equivariant model and training to solve problems. It is essential to capture the multiscale structure of the input graph. We propose a Multiresolution scheme in combination with Equi Graph Attention network (mEGAT) architecture.
  arXiv  Detail & Related papers  (2023-10-24T06:22:20Z)
• GIF: A General Graph Unlearning Strategy via Influence Function [63.52038638220563]
  Graph Influence Function (GIF) is a model-agnostic unlearning method that can efficiently and accurately estimate parameter changes in response to a $epsilon$-mass perturbation in deleted data. We conduct extensive experiments on four representative GNN models and three benchmark datasets to justify GIF's superiority in terms of unlearning efficacy, model utility, and unlearning efficiency.
  arXiv  Detail & Related papers  (2023-04-06T03:02:54Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.