Exploiting Edge Semantics in Job Shop Scheduling Problem With Heterogeneous Graph Transformers

Abstract

The Job Shop Scheduling Problem (JSSP) is commonly represented as a disjunctive graph in which nodes denote operations, while edges encode technological precedence constraints and machine‐sharing conflicts. Most existing deep reinforcement learning (DRL) approaches model this graph as homogeneous by merging precedence and contention edges into a single relation type, thereby overlooking their distinct semantics. To address this limitation, we propose the Heterogeneous Graph Transformer (HGT)‐Scheduler, a reinforcement learning framework that explicitly models the JSSP as a heterogeneous graph. Unlike existing learning methods, the proposed framework employs edge‐type‐specific attention mechanisms to distinguish precedence and machine‐contention relations, enabling richer scheduling representations. The scheduling policy is optimized using Proximal Policy Optimization (PPO). The proposed framework is evaluated on the Fisher–Thompson benchmark instances. On FT06, the HGT‐Scheduler achieves an optimality gap of 8.4%, significantly outperforming both an identical architecture without edge‐type awareness () and a Graph Isomorphism Network (GIN) baseline. On the larger FT10 instance, the proposed approach demonstrates favorable scalability, although heterogeneous and homogeneous representations exhibit comparable performance under a 50,000‐step training budget. Ablation studies identify a three‐layer attention architecture as the most effective configuration. Overall, the results demonstrate that explicitly modeling edge semantics improves reinforcement learning for intelligent job shop scheduling.