Does Size Generalization Imply Disruption Robustness? A Pre-Registered Study of GNN–PPO Scheduling Policies for the Dynamic Flexible Job-Shop Problem

技術要約：サイズ汎化能は、撹乱に対する堅牢性を意味するのか？

問題提起
本研究は、動的かつ確率的な柔軟ジョブショップスケジューリング問題（FJSP）に取り組んでいる。これは、操作を適切な機械に、時間経過とともに割り当てる必要がある組合せ最適化の課題である。静的な決定論的バージョンとは異なり、この問題には3つの不確実性が組み込まれている（ポアソン過程による動的なジョブ到着、対数正規乗数による確率的な処理時間、および対数正規の修理時間を伴う指数関数的な故障時間）。深層強化学習（DRL）とグラフニューラルネットワーク（GNN）の組み合わせは、より大きなインスタンスサイズへの汎化や単一種類の撹乱への対応において有望視されているが、単一のポリシーが「サイズ汎化（学習時よりも大きなインスタンスで良好に機能すること）」と「マルチ・ディスラプション（複数の撹乱が同時に発生する状況）への堅牢性（機械故障、確率的な処理時間、動的な到着の同時発生への対応）」を同時に達成できるかどうかは、未だ検証されていない。

手法
研究者らは、関係的グラフ同型ネットワーク（GIN）エンコーダと近接方策最適化（PPO）エージェントを評価するために、事前登録された統計的に厳格なプロトコルを採用した。

• アーキテクチャ: ポリシーは、3つのエッジタイプ（ジョブ内の先行関係、機械間の競合、および操作と機械の適合性）を、集約前の個別の線形変換を介して区別する関係的GINエンコーダを利用している。この設計は、完全な均質グラフと完全な異種グラフ表現の中間に位置する。アクターヘッドは、インスタンスのサイズに関わらず候補となる操作に対してロジットを出力するため、操作数に依存しないパラメータ数を持つ。
• 学習と報酬: エージェントはMaskablePPOを用いて学習された。堅牢性をテストするため、研究では2つの報酬構造を評価した。一つはメイクスパンを最小化するベースとなるポテンシャルベースの報酬であり、もう一つは、撹乱後の計画開始時刻からの逸脱をペナルティ化する「不安定性ペナルティ（$\kappa \cdot \Delta_{inst}$）」を組み込んだ拡張版である。
• 実験設計: 研究では、HARKing（結果を知った後に仮説を立てること）を避けるため、凍結された意思決定ルールを用いて5つの事前登録された仮説（H1–H5）を検証した。
  • ベースライン: ポリシーは、9種類の優先順位ディスパッチングルール（PDR）、チューニングされた遺伝的アルゴリズム（GA）、および厳密な制約プログラミングソルバー（CP-SAT）と比較された。
  • ベンチマーク: 評価は、Fisher–ThompsonおよびLawrenceファミリー（JSSP）の43インスタンスと、7つのBrandimarteインスタンス（FJSP）、および合成的な拡張インスタンスにわたって行われた。
  • 統計プロトコル: 比較には、ペアワイズ分析のためのウィルコクソン符号付順位検定、および多手法ランキングのためのフリードマン・ネメンニー検定とクリティカル・ディファレンス・ダイアグラムを用いた。効果量も随時報告されている。

主要な結果
5つの事前登録された仮説のうち、4つが棄却され、1つが採択された。結果は以下の通りである。

1. 静的な競争力 (H1 - 棄却): GNN-PPOポリシーは、静的なインスタンスにおいて最良のディスパッチングルールを上回ることができなかった。ポリシーの平均相対百分率偏差（RPD）は24.82%であり、最良のPDR（FIFO）の18.96%と比較して劣っていた。FJSPの全インスタンスで敗北し、JSSPにおいては18.6%のインスタンスでのみ勝利した。
2. サイズ汎化 (H2 - 採択): ポリシーは、学習セットよりも1.5倍から3.0倍大きいインスタンスサイズに対して、正常に汎化することができた。絶対的なRPDは最良のPDRと比較して競争力がないままだったが、10の手法におけるその「ランク」は、どのサイズ層においても最良のPDRのランクより有意に悪化していなかった。これは、絶対的な解の質ではなく、相対的な競争力の転移を示している。
3. マルチ・ディスラプションへの堅牢性 (H3 - 棄却): ポリシーは、9つの異なる撹乱レジーム（故障、確率的な処理時間、および到着の組み合わせ）の下で堅牢性に失敗した。すべてのレジームにおいて、ポリシーの堅牢性指標（RI）は最良のPDRよりも有意に悪かった。「動的な到着」の軸は、学習中に見られなかった分布シフト（エピソード中盤でのジョブ挿入）を代表していたため、特に致命的であった。
4. 撹乱を考慮した報酬 (H4 - 棄却): 報酬に不安定性ペナルティ（$\kappa > 0$）を加算しても、堅牢性は向上しなかった。むしろ、名目上の（撹乱のない）パフォーマンスを崩壊させ、RPDを46.6から106.0ポイント増加させた。研究では、この失敗の原因を、ドメインランダム化された撹乱エピソードのみで学習を行い、撹乱のない（名目上の）エピソードに一度も曝露させていなかったことによるものと診断している。
5. 意思決定レイテンシ (H5 - 厳格な閾値下で棄却): ポリシーの意思決定レイテンシ（4–11 ms）は、大規模で困難なインスタンスにおいてCP-SATよりも数桁速かったが、事前登録された厳格な閾値（CP-SATの時間の1%未満であること）には、43インスタンス中42のケースで失敗した。この失敗は主に、CP-SATが問題をほぼ瞬時に解決してしまう小規模なインスタンスによって引き起こされた、数学的なアーティファクトによるものである。

意義と主張
本論文の中心的な貢献は、解の質に関する肯定的な結果ではなく、GNN-PPOスケジューリング・ポリシーの限界を診断し、統計的に厳格に特徴付けたことにある。著者らは、サイズ汎化とマルチ・ディスラプションへの堅牢性は、同一のアーキテクチャから自動的に現れる「パッケージ・セット」ではなく、分離可能な特性であると主張している。

• アーキテクチャの転移 vs 競争力: 本研究は、サイズ不変のアーキテクチャが、絶対的な競争力が低い場合であっても、相対的なランクとしての競争力を転移できる（サイズが増加しても、他の手法に対して「同等程度」であり続けられる）という経験的証拠を提供している。
• 共同目的のコスト: H3およびH4の棄却は、複数の撹乱タイプに対して堅牢性を最適化しつつ、名目上のパフォーマンスを維持することは、特定のアーキテクチャまたは学習レジームの調整なしには不可能であることを示唆している。「不安定性ペナルティ」が失敗したのは、学習レジーム（名目上のエピソードへの曝露を欠いたドメインランダム化）が報酬設計と不適合であったためである。
• 方法論的厳密さ: 仮説と意思決定ルールを事前登録することで、研究は、DRLスケジューリング文献における説明のつかない失敗の傾向に対抗する、防御可能な「負の結果」を提供している。著者らは、単なる「分布シフト」といった曖昧な言葉に帰すのではなく、具体的な失敗のメカニズム（例：学習から名目的なエピソードを除外したことによる具体的な影響）を特定している。

著者らは、実務者はサイズ汎化の主張のみから撹乱への堅牢性を推論すべきではないと結論付けている。代わりに、これらの能力は、別々の評価とエンジニアリングを必要とする独立した設計軸として扱うべきである。また、本研究は、高速で反応的なGNNポリシーが撹乱時の即時的なフォールバックとして機能し、同時に、より低速だが高品質なソルバー（GAまたはCP-SAT）が並行して動作し、最適化されたスケジュールを生成するという、ハイブリッドなデプロイメント戦略の可能性を示唆している。