Adaptive Mutation Driven Harris Hawk Optimization Algorithm in Hybrid Flow Workshop Scheduling with Robotic Arm

技術要約：ロボットアームを伴うハイブリッドフロー・ワークショップ・スケジューリングにおける適応型変異駆動型ハリスホーク最適化アルゴリズム

問題提起
本論文は、インテリジェント製造において普及している複雑な組合せ最適化課題である、ローディング/アンローディング・マシンを伴うハイブリッドフローショップ・スケジューリング問題（HFSP-LUM）に取り組んでいる。この特定のバリアントは、$n$個のワークピースを$m$個のプロセスにスケジューリングするものであり、各プロセスには並列の同一設備が含まれ、さらに、隣接するステージ間のマテリアルハンドリングを担当するロボットアームが組み込まれていることが重要である。この問題は、高次元性、強い制約（例：非プリエンプティブな処理、単一タスクのロボットアーム、プロセスシーケンス）、および最大完了時間（$C_{max}$）の最小化の必要性を特徴としている。著者らは、従来の受動的な手動スケジューリングや既存のヒューリスティックアルゴリズムが、このような高次元で制約の多い環境において、動的な生産需要、早期収束、および不十分なグローバル探索能力に直面し、苦戦することが多いと指摘している。

手法
これらの課題に対処するため、著者らは**適応型変異駆動型ハリスホーク最適化アルゴリズム（AMDHHO）**を提案している。その手法は、HFSP-LUMの数学的モデルと、強化されたメタヒューリスティックソルバーを統合したものである。

1. 数学的モデリング:

   • $C_{max}$を最小化することを目的とした混合整数計画モデルを構築する。
   • このモデルには、プロセスシーケンス、マシン割り当て（一度に一つのワークピースのみをマシンに割り当て）、ロボットアームの排他性（一度に一つの輸送のみ）、および時間的依存関係（開始時間は輸送および処理の完了時刻を尊重しなければならない）に関する制約が含まれる。
   • 決定変数には、ワークピースの処理シーケンス、マシン割り当て、およびロボットアームのタスク割り当てが含まれる。

2. アルゴリズム設計 (AMDHHO):

   • 基本フレームワーク: アルゴリズムは、標準的なハリスホーク最適化（HHO）のフレームワークに基づいて構築されており、これはハリスホークの「待ち伏せ包囲」狩りの戦術をシミュレートしており、探索（ランダムなパトロール）と搾取（獲物の追跡と攻撃）を交互に行う。
   • ハイブリッドエンコーディング: 解を表すために、3次元のハイブリッドエンコーディング構造を使用する：
     • 処理シーケンスベクトル (PSV): ワークピースの優先順位を決定する。
     • マシン割り当てベクトル (MAV): 並列マシンをワークピースに割り当てる。
     • ロボットアーム割り当てベクトル (RAV): ステージ間の輸送のためにロボットアームを割り当てる。
   • 主要な改良点:
     • レヴィ・フライト（Levy Flight）による攪乱: グローバル探索を強化し、早期収束を防ぐために、探索メカニズムに統合されている。
     • 適応型変異確率: 反復回数と集団のエネルギー状態に基づいて変異確率を調整する動的な戦略であり、初期段階のグローバル探索と後半段階のローカル開発のバランスをとる。
     • マルチメソッド・クロスオーバー: シーケンス最適化のために部分対応マップ交叉（PMX）を用い、マシン/ロボットの割り当てのために一様交叉を用い、適応的な確率制御を行う。
     • デコーディング戦略: 3次元ベクトルを実行可能なスケジュールに変換するステップバイステップのデコーディングメカニズムであり、リソースおよび時間的制約を厳格に遵守しながら、開始/完了時刻を計算する。

主な貢献

• アルゴリズムの革新: 適応型変異とレヴィ・フライト・メカニズムをHHOフレームワークに統合することで、HFSP-LUMを特に対象としたAMDHHOの開発。
• 包括的なモデリング: ロボットアームの制約と輸送時間を明示的に考慮した厳密な数学モデルの構築。これらは標準的なフローショップモデルでは簡略化または無視されることが多い。
• ハイブリッドエンコーディングとデコーディング: ロボット支援型ハイブリッドフローショップの多次元の決定変数に特化した、特定のエンコーディング/デコーディング・スキームの提案。
• 実証的検証: 標準的なベンチマーク・インスタンス（Taillardベース）および、20個のワークピース、11台のマシン、3本のロボットアームを含む実際の産業ケーススタディの両方を用いた広範なテスト。

実験結果
著者らは、5つのスケールの問題インスタンス（10から50個のワークピースの範囲）にわたり、標準的なHHO、メイフライ・アルゴリズム（MA）、遺伝的アルゴリズム（GA）、およびビートル最適化アルゴリズム（DO）との比較実験を行った。

• 標準ベンチマーク:

  • 最大規模のテスト（50個のワークピース、5ステージ、5台のマシン）において、AMDHHOは$C_{max}$ 492.6分を達成した。
  • これは、遺伝的アルゴリズム（557.8分）に対して約11.7%、標準的なHHOに対して**5.0%**の改善を示している。
  • AMDHHOは優れた安定性を示し、標準偏差は3.27であり、GAの7.92よりも大幅に低かった。
  • 収束速度も著しく速く、同じ問題スケールに対して、GAが127回の反復を必要としたのに対し、AMDHHOは57回の反復で収束した。

• アブレーション研究:

  • 適応型変異とレヴィ・フライトの組み合わせが主要な性能向上要因であることを実験で確認した。これは、標準的なHHOと比較して、最適解を約13%、平均解を約15%向上させた。
  • 適応型変異メカニズムは、解の揮発性（標準偏差）を大幅に減少させた（標準偏差の減少率は42.6～45.2%）。

• 実世界への適用（蘇州精密部品製造）:

  • 20個のワークピースと3本のロボットアームを持つ生産ラインに適用。
  • AMDHHOは、最大完了時間を元の手動計画の768分から683分へと短縮し、**85分（11.1%）**の削減を実現した。
  • 平均待ち時間は**39.8%減少し、リソース利用率は82.7%**に増加した。
  • 設備の故障をシミュレートした動的なシナリオにおいて、アルゴリズムは約9.6秒で調整されたスケジュールを生成し、リアルタイムの適応性を実証した。

意義と主張
本論文は、AMDHHOアルゴリズムが、インテリジェント製造の文脈における複雑なワークショップ・スケジューリングに対して、効率的かつ堅牢なソリューションを提供すると主張している。著者らは、アルゴリズムがグローバル探索とローカル開発のバランスをうまくとり、高次元で制約の強い環境における従来の群知能アルゴリズムの限界を克服していると断言している。結果は、AMDHHOが生産サイクルの短縮とリソース利用率の向上において、大きな実用的価値を提供することを示唆している。本研究は、アルゴリズムの動的な適応メカニズムが、設備の故障などの動的な事象への迅速な応答を必要とする環境において特に適していることを強調している。