Abstract
長い時間幅を持つ柔軟ジョブショップスケジューリング（Long-horizon Flexible Job-Shop Scheduling~(FJSP)）は、長い時間幅にわたって発生する複雑で相互に依存し合う意思決定により、非常に手強い組合せ最適化の課題となっています。学習ベースのRolling Horizon Optimization~(RHO)は、不変な操作（インバリアント）を特定して固定することで解決を高速化する有望なパラダイムとして注目されてきましたが、その有効性はFJSPの構造的な複雑さによって阻害されています。既存の手法はしばしば、グラフ構造として表現される精緻な依存関係を十分に捉えられず、予測誤りの非対称なコスト（重要度の高い操作を誤って分類することは、重要でない操作を誤って分類することよりも大幅に損害が大きい）を無視しています。さらに、ローリング過程における予測に対する確信の動的な変化により、静的な枝刈り（プルーニング）の閾値では不十分になります。これらの制約に対処するため、我々は新しいクリティカルパスを意識したグラフベースのRHOフレームワークであるGraph-RHOを提案します。まず、サブ問題を、複数の関係を持つエッジを備えた操作・機械グラフとしてエンコードする、トポロジーに配慮した異種グラフネットワークを導入し、エッジ特徴に応じたメッセージパッシングを用いて操作の安定性を予測します。次に、高い感度を持つボトルネック操作と頑健な操作を区別するために、学習中に帰納的バイアスを注入するクリティカルパスを意識したメカニズムを組み込みます。第三に、オンラインでの不確実性推定に基づいて意思決定境界を動的にキャリブレーションする適応的な閾値設定戦略を設計し、モデルの予測をソルバの探索空間と整合させます。標準ベンチマークにおける大規模な実験により、
mbox{Graph-RHO}が解の質と計算効率の両面で新たな最先端の成果を達成することを示します。特筆すべきことに、優れたゼロショット汎化を示し、大規模インスタンス（2000操作）において、解決時間を30s%以上短縮しながら、より高い解の質を達成します。コードは
\href{https://github.com/IntelliSensing/Graph-RHO}{こちら} で利用できます。
