A Genetic Algorithm with Critical‑Path‑Driven Dual‑Neighborhood Search for Flexible Job Shop Scheduling

技術要約：柔軟なジョブショップ・スケジューリングのための、クリティカルパス駆動型デュアル近傍探索を備えた遺伝的アルゴリズム

問題定義
本論文は、現代の製造業において広く普及している強NP困難な最適化課題である、柔軟なジョブショップ・スケジューリング問題（FJSP）に取り組んでいる。各操作の機械割り当てが固定されている古典的なジョブショップ・スケジューリング問題（JSP）とは異なり、FJSPでは、各操作が代替候補となる一連の機械のいずれかで処理されることが可能であり、多くの場合、処理時間は機械ごとに異なる。主な目的は、すべてのジョブの最大完了時間として定義されるメイクスパン（$C_{max}$）を最小化することである。この問題には、先行関係の制約および機械の可用性を満たしながら、各操作の機械選択と各機械における処理順序の両方を決定することが含まれる。

手法：HGVNSA
著者らは、グローバルな探索のための遺伝的アルゴリズム（GA）と、クリティカルパス駆動型の変数近傍探索（VNS）によるローカルな搾取を統合した、ハイブリッド遺伝的変数近傍探索アルゴリズム（HGVNSA）を提案している。

1. エンコーディングとデコーディング： 解は、操作シーケンス（OS）ベクトルと機械選択（MS）ベクトルの二層エンコーディングを用いて表現される。実行可能なスケジュールを生成するために、アクティブ・デコーディング戦略が採用されている。
2. 個体群の初期化： 品質と多様性のバランスをとるため、初期個体群はハイブリッド戦略を用いて生成される：グローバル選択（60%、グローバル負荷増分を最小化）、ローカル選択（30%、ジョブ内の負荷を均衡化）、およびランダム選択（10%）。
3. 遺伝的操作：
   • 交叉（Crossover）： パス・リリンキング（PR）に基づく交叉オペレータが導入されている。ランダムな遺伝子の入れ替えではなく、ある親の解を別の親へと系統的に変換し、その過程で中間解を記録・評価することで、親の間の探索空間を活用する。
   • 突然変異（Mutation）： 適応型突然変異メカニズムにより、個体の適応度と世代数に基づいて確率を調整する。2種類の突然変異が使用される：OS突然変異（操作順序のシャッフル）およびMS突然変異（機械割り当ての変更）。
4. クリティカルパス駆動型デュアル近傍VNS： GAフレームワーク内に組み込まれたこのローカルサーチは、クリティカルパス（離散グラフにおける最長経路）上に位置する操作に焦点を当てる。これは、2つの補完的な近傍構造を利用する：
   • N8近傍： 同一機械上の操作の順序を最適化する。これは、クリティカルブロック外のクリティカルな操作を、ブロックの端点やブロックの前方・後方位置へ移動させることを可能にすることで、従来のN5-N7移動を拡張したものである。
   • k-挿入近傍： クリティカルな操作を異なる機械へと再割り当てする。これには、代替機械を横断して操作を探索し、循環依存性をチェックしながら、実行可能な位置に操作を挿入するプロセスが含まれる。
   • 探索戦略： VNSプロセスはN8近傍（計算コストが低い）を優先し、改善が見られない場合にのみk-挿入（コストが高く、より広範な探索）へと切り替えることで、効率性と探索の深さのバランスを確保している。

主な貢献
本論文は、5つの主要な貢献を概説している：

1. ハイブリッドフレームワーク： 「グローバル探索を先行させ、その後にローカルな搾取を行う」という相乗的なフレームワークを確立し、解の精度と計算効率を効果的に両立させている。
2. デュアル近傍の統合： N8近傍とk-挿入近傍を、FJSPのための統一されたVNSフレームワーク内に統合した最初の事例である。この組み合わせは、機械内のシーケンシングと機械間の再割り当ての両方に対処し、ローカルサーチ能力を大幅に向上させている。
3. 強化された遺伝的操作： パス・リリンキング交叉と適応型突然変異確率の導入により、解の探索空間の探索能力と収束の安定性が強化された。
4. ベンチマーク性能： Brandimarte MKベンチマークセットにおいて、HGVNSAは10インスタンス中6つ（MK01-MK04, MK08-MK09）で既知の最適解に到達し、比較対象となったアルゴリズム（HGWO, HLO-PSO, HA, SLGA, ISLGA）の中で最も低い平均相対パーセント偏差（RPD）0.06%を達成した。
5. 実世界への応用： アルゴリズムは、会社Aにおけるギアシャフト加工シナリオに適用された。従来の遺伝的アルゴリズムと比較して、HGVNSAは生産効率を8.81%向上させ、その工学的実用性を実証した。

結果と検証

• ベンチマークテスト： MK01-MK10のインスタンスを用いた広範な実験により、HGVNSAは解の質と安定性の両面で比較アルゴリズムを上回ることが示された。アブレーション研究により、VNSコンポーネント、デュアル近傍構造、または適応メカニズムを除去すると、大幅な性能低下を招くことが確認された（例：VNSを除去すると、MK02における平均メイクスパンが26から30.4に増加した）。
• ケーススタディ： 10個のジョブと15台の機械にわたる59個の操作を含む会社Aのケーススタディにおいて、アルゴリズムはメイクスパンスを従来のGAの522から476へと減少させた。
• 収束性： 収束分析は、他のアルゴリズムが初期の急速な収束後に停滞する一方で、HGVNSAはローカルサーチメカニズムを通じて解を精緻化し続け、後半のイテレーションにおいても局所最適解を打破できることを示した。

意義
本論文は、HGVNSAがFJSPに対して効率的かつ堅牢なソリューションフレームワークを提供し、グローバル探索とローカル探索のバランス、および効果的な近傍構造の設計という課題に効果的に対処していると主張している。本研究は、クリティカルパス駆動型のローカルサーチと遺伝的進化を組み合わせることが、理論的ベンチマークと実用的な産業設定の両方において優れた結果をもたらすことを検証している。著者らは、本研究が分散型スケジューリングや、インテリジェントな近傍選択のための深層強化学習の研究への基礎を築くものであると示唆しているが、これらの拡張機能が現在の研究において実装されているとは主張していない。