論文の概要: HGT-Scheduler: Deep Reinforcement Learning for the Job Shop Scheduling Problem via Heterogeneous Graph Transformers

• arxiv url: http://arxiv.org/abs/2603.06777v1
• Date: Fri, 06 Mar 2026 17:59:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-10 15:13:13.103604
• Title: HGT-Scheduler: Deep Reinforcement Learning for the Job Shop Scheduling Problem via Heterogeneous Graph Transformers
• Title（参考訳）: HGT-Scheduler:不均一グラフ変換器によるジョブショップスケジューリング問題に対する深層強化学習
• Authors: Bulent Soykan,
• Abstract要約: ジョブショップスケジューリング問題(JSSP)は一般に、ノードが操作を表現し、エッジが技術的優先の制約を符号化し、マシン共有の競合を符号化する解離グラフとして定式化されている。 既存の強化学習アプローチのほとんどは、このグラフを均質で、ジョブプレッデンスとマシンコンテンションエッジを単一の関係タイプとしてモデル化している。 我々は、JSSPを異種グラフとしてモデル化する強化学習フレームワークであるHGT-Schedulerを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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.
• Abstract（参考訳）: ジョブショップスケジューリング問題(JSSP)は一般に、ノードが操作を表現し、エッジが技術的優先の制約とマシン共有の競合を符号化する解法グラフとして定式化されている。 既存の強化学習アプローチのほとんどは、このグラフを均質で、ジョブプレッデンスとマシンコンテンションエッジを単一の関係タイプとしてモデル化している。 このような単純化は、問題構造の固有の不均一性を見落とし、重要な関係情報の喪失につながる可能性がある。 この制限に対処するため,JSSPをヘテロジニアスグラフとしてモデル化する強化学習フレームワークであるHGT-Schedulerを提案する。 提案アーキテクチャは、不均一グラフ変換器を用いて、エッジ型依存型アテンション機構を優先および競合関係に適用することにより、タイプ固有のリレーショナルパターンをキャプチャする。 スケジューリングポリシは、プロキシポリシー最適化を使用してトレーニングされる。 提案手法の有効性をFisher-Thompsonベンチマークインスタンスで評価した。 FT06インスタンスでは、HGT-Schedulerは8.4\%の最適性ギャップを達成し、エッジタイプ(p = 0.011$)を無視した同一アーキテクチャと標準グラフ同型ネットワークベースラインの両方を統計的に上回る。 より大きなFT10インスタンスでは、このアプローチは好ましいスケーラビリティを示している。 しかし、5万ステップのトレーニング制限の下では、不均一グラフモデルと均質グラフモデルのパフォーマンスは同等であり、エッジタイプの認識はより大きな問題インスタンスに対してより長いトレーニング地平線を必要とすることを示唆している。 アブレーション解析は、3層アテンションアーキテクチャが最高のパフォーマンスを提供することを示している。 全体として、異なるエッジセマンティクスを明示的にモデル化することで、効果的なスケジューリングポリシーの学習が向上することを確認した。

関連論文リスト

• Scalable Graph Generative Modeling via Substructure Sequences [50.32639806800683]
  本稿では,グラフ生成用トランスフォーマー事前学習フレームワークである生成グラフパターンマシン(G$2$PM)を紹介する。 G$2$PMはグラフインスタンス(ノード、エッジ、グラフ全体)をサブ構造のシーケンスとして表現する。 それは、一般化可能かつ伝達可能な表現を学ぶために、シーケンスに関する生成的事前学習を採用する。
  論文  参考訳（メタデータ） (2025-05-22T02:16:34Z)
• Adaptive Homophily Clustering: Structure Homophily Graph Learning with Adaptive Filter for Hyperspectral Image [21.709368882043897]
  ハイパースペクトル画像(HSI)クラスタリングは、ゼロトレーニングラベルによる基本的だが難しい課題である。 本稿では,HSIのための適応フィルタクラスタリング法(AHSGC)を用いたホモフィリ構造グラフ学習を提案する。 AHSGCには高いクラスタリング精度、低い計算複雑性、強い堅牢性が含まれています。
  論文  参考訳（メタデータ） (2025-01-03T01:54:16Z)
• Learning Cartesian Product Graphs with Laplacian Constraints [10.15283812819547]
  ラプラシアン制約下でのカルト積グラフの学習問題について検討する。 我々は、ペナルティ化された最大推定値に対する統計的整合性を確立する。 また、構造的欠落のある値の存在下で、効率的な共同グラフ学習と計算を行う方法を拡張した。
  論文  参考訳（メタデータ） (2024-02-12T22:48:30Z)
• Addressing Heterophily in Node Classification with Graph Echo State Networks [11.52174067809364]
  ノード分類のためのグラフエコー状態ネットワーク(GESN)を用いた異種グラフの課題に対処する。 GESNはグラフのための貯水池計算モデルであり、ノードの埋め込みは訓練されていないメッセージパッシング関数によって計算される。 実験の結果, 貯水池モデルでは, ほぼ完全に訓練された深層モデルに対して, より優れた精度あるいは同等の精度が得られることがわかった。
  論文  参考訳（メタデータ） (2023-05-14T19:42:31Z)
• Joint Graph Learning and Model Fitting in Laplacian Regularized Stratified Models [5.933030735757292]
  ラプラシア正規化成層モデル(Laplacian regularized Stratified Model、LRSM)は、サブプロブレムの明示的または暗黙的なネットワーク構造を利用するモデルである。 本稿では,LRSMにおけるグラフ重みの重要性と感度を示し,その感度が任意に大きいことを示す。 本稿では,1つの最適化問題を解くことで,モデルパラメータを適合させながらグラフを共同学習する汎用的手法を提案する。
  論文  参考訳（メタデータ） (2023-05-04T06:06:29Z)
• GIF: A General Graph Unlearning Strategy via Influence Function [63.52038638220563]
  Graph Influence Function (GIF)は、削除されたデータにおける$epsilon$-massの摂動に応答してパラメータの変化を効率的に正確に推定できる、モデルに依存しない未学習の手法である。 我々は,4つの代表的GNNモデルと3つのベンチマークデータセットについて広範な実験を行い,未学習の有効性,モデルの有用性,未学習効率の観点からGIFの優位性を正当化する。
  論文  参考訳（メタデータ） (2023-04-06T03:02:54Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Training Robust Graph Neural Networks with Topology Adaptive Edge Dropping [116.26579152942162]
  グラフニューラルネットワーク(GNN)は、グラフ構造情報を利用してネットワークデータから表現をモデル化する処理アーキテクチャである。 彼らの成功にもかかわらず、GNNは限られた訓練データから得られる準最適一般化性能に悩まされている。 本稿では、一般化性能を改善し、堅牢なGNNモデルを学習するためのトポロジ適応エッジドロップ法を提案する。
  論文  参考訳（メタデータ） (2021-06-05T13:20:36Z)
• Tensor Graph Convolutional Networks for Multi-relational and Robust Learning [74.05478502080658]
  本稿では,テンソルで表されるグラフの集合に関連するデータから,スケーラブルな半教師付き学習(SSL)を実現するためのテンソルグラフ畳み込みネットワーク(TGCN)を提案する。 提案アーキテクチャは、標準的なGCNと比較して大幅に性能が向上し、最先端の敵攻撃に対処し、タンパク質間相互作用ネットワーク上でのSSL性能が著しく向上する。
  論文  参考訳（メタデータ） (2020-03-15T02:33:21Z)
• Heterogeneous Graph Transformer [49.675064816860505]
  Webスケールの不均一グラフモデリングのための不均一グラフ変換器(HGT)アーキテクチャ 動的ヘテロジニアスグラフを扱うために、HGTに相対時間符号化手法を導入する。 Web スケールのグラフデータを扱うため,ヘテロジニアスなミニバッチグラフサンプリングアルゴリズム--HGSampling--を設計し,効率的かつスケーラブルなトレーニングを行う。
  論文  参考訳（メタデータ） (2020-03-03T04:49:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。