.png){kind=icon}
.png){kind=icon}
Return
Exploiting Edge Semantics in Job Shop Scheduling Problem With Heterogeneous Graph Transformers
.png){kind=icon}
OA
AI
DOI：10.1002/aisy.70522.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 (<span class="fallback__mathEquation" data-altimg="/cms/asset/88db7e77-d576-4966-a3a9-da1705aba87d/aisy70522-math-0001.png"></span>
<math altimg="urn:x-wiley:26404567:media:aisy70522:aisy70522-math-0001" alttext="p equals 0.011" display="inline" location="graphic/aisy70522-math-0001.png">
<semantics>
<mrow>
<mi>p</mi>
<mo>=</mo>
<mn>0.011</mn>
</mrow>
<annotation encoding="application/xtex">
$p &#x00026;amp;amp;amp;amp;amp;amp;amp;amp;amp;equals; 0.011$
</annotation>
</semantics>
</math>) 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.
Keywords:
deep reinforcement learning
disjunctive graph
heterogeneous graph transformer
job shop scheduling problem
proximal policy optimization
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
6.1
Papers:
2.0K
Citations:
8.4K