Joint Planning of Assembly Sequence Planning and Assembly Line Balancing Based on Improved Artificial Fish Swarm Algorithm

技術要約：改良型人工魚群アルゴリズムに基づく組立シーケンス計画と組立ライン・バランシングの共同計画

問題提起
本論文は、組立シーケンス計画（ASP）と組立ライン・バランシング（ALB）を同時に最適化するという複雑な課題に取り組んでいる。これら2つの問題は本質的に結合している。ASPはコストを最小化するためにコンポーネントの組み立て順序を決定し、ALBはこれらのタスクをワークステーションに割り当ててアイドル時間を最小化し、ラインを均衡させる。両者は共に、多項式時間で解ける非決定性多項式困難（NP困難）な問題に分類される。著者らは、これらの問題を個別に最適化すると、多くの場合、システム全体のパフォーマンスが最適ではなくなることを指摘している。さらに、既存のASP手法は、グラフ探索を用いる場合に「組合せ爆発」に陥ることが多い。また、従来の行列生成手法は、複雑な製品に対しては時間がかかり非効率である。加えて、多くのALB研究は、ASPに固有の組立工具や方向の動的な変化を考慮しておらず、その結果、実際の組立プロセスにおいて非現実的なバランシング結果を招いている。

手法
提案手法は、改良型人工魚群アルゴナズム（HAFSA）を用いて、ASPとALBを統一された多目的最適化フレームワークへと統合するものである。この手法は、主に以下の3つのフェーズで構成される。

1. BOMおよび制約行列によるASPモデリング:

   • 組合せ爆発を引き起こすAND/ORグラフのみに依存するのではなく、部品表（BOM）の階層図に基づいたモジュール式組立制約行列を構築する。
   • 組立制約行列（$E(G)$）は、要素が部品を表し、値が優先順位および接続関係（例：直接前の接続は$1$、後の接続は$-1$、直接ではない前の接続は$9$など）を示す有向グラフを用いて定義される。
   • サブアセンブリの分割: アルゴリズムがBOM階層を分析し、サブアセンブリの独立性を判断する。制約行列の列の値を反復的にチェックし、ある部品グループが外部の部品に対して一貫して非正または非負の関係を示している場合、それらを独立したサブアセンブリとして特定する。そうでない場合は、アルゴリズムが特定の行を剥離することで、実行可能な独立モジュールを作成する。
   • 内部計画: 特定された各サブアセンブリ内では、制約行列の値に基づいて実行可能な内部組立シーケンスを生成するために、特定の入れ替えおよび固定化アルゴリズムが使用される。

2. 多目的最適化モデル:
   統合モデルは、以下の3つの目的関数を同時に最小化することを目指す。

   • ワークステーション時間のバランス: 生産リズム（$T_c$）と個々のワークステーションの時間（$T_m$）の間の分散を最小化する。
   • 切り替えコスト: 連続するタスク間における組立工具の変更回数および組立方向の変更回数の合計を最小化する。
   • 最大ワークステーション時間: サイクルタイム（全ワークステーションの中の最大時間）を最小化する。

3. ハイブリッド人工魚群アルゴリズム（HAFSA）:
   この多目的問題を解決するために、著者らは人工魚群アルゴリズム（AFSA）に粒子群最適化（PSO）とパレート最適性の概念を組み合わせたHAFSAを提案する。

   • エンコーディング／デコーディング: 組立タスクは、サブアセンブリ内の優先度重みに基づいてエンコードされる。デコーディングでは、サイクルタイムの制約を超えた場合にのみ新しいワークステーションを開設しながら、タスクをワークステーションに順次割り当てる。
   • パレート解集合: 外部リポジトリに非劣解を保存する。多様性を維持しリポジトリのサイズを管理するために、混雑距離メカニズムが使用される。
   • アルゴリズムの改良:
     • 行動ロジック: アルゴリズムは、尾を追う（tail-chasing）、採餌（foraging）、集団形成（clustering）、ランダム行動という一連の探索順序に従う。
     • PSOの統合: アルゴリズムが局所最適解に陥るのを防ぐため（標準的なAFSAの既知の弱点）、PSOの操作を導入する。これには、一定の確率で悪化する解を受け入れるためのメトロポリス基準（焼きなまし法に近い概念）が含まれており、これにより探索が局所的な罠から脱出することを可能にする。
     • 動的慣性: 人工魚の「視界」（探索範囲）は、PSOに触発された慣性重み（$\omega$）を用いて動的に調整される。最初は広範なグローバル探索のために大きなフィールドから始まり、局所的な収束のために狭まっていく。

主な貢献

• 統合フレームワーク: 本論文は、ASPとALBを逐次的に扱うのではなく、それらの相互依存性を認識した上で、共同して計画する手法を提案している。
• 行列ベースのサブアセンブリ特定: BOM階層と組立制約行列を用いて、独立したサブアセンブリを自動的に特定する新しいアプローチにより、探索空間を縮小し、組合せ爆発を回避する。
• HAFSAアルゴリズム: PSO操作と焼きなまし法の原理を取り入れることで、標準的なAFSAよりもグローバル探索能力を向上させ、局所最適解を回避するように改良された、パレートベースのハイブリッド人工魚群アルゴリズムの開発。
• 多目的処理: 従来の時間のバランスに加え、工具の変更と方向の変更を最適化目的として明示的に含めている。

結果
提案手法は、21の組立タスクを持つ特定の製品のケーススタディを用いて検証された。HAFSA（AFSA&PSOと表記）は、標準的な粒子群最適化（PSO）アルゴリズムおよび標準的な人工魚群アルゴリズム（AFSA）と比較された。

• ワークステーションのバランス: 3つのアルゴリズムすべてが、31分という同一の最大ワークステーション稼働時間を達成した。しかし、HAFSAのステーション間バランス値は0.69であり、これはPSOの結果（0.75）よりも優れており、標準的なAFSA（0.69）と同等であった。
• 切り替え効率: HAFSAは計22回の変更（工具＋方向）を達成した。これはPSOの結果（22）と同等であったが、24回の変更となった標準的なAFSAよりも大幅に優れていた。
• データからの結論: HAFSAは、ステーション時間を効果的にバランスさせつつ、総操作切り替え回数を最小化するパレート最適解を見出す能力を示した。これは、切り替えの削減において標準的なAFSAを上回り、バランス指標においてPSOに匹敵または凌駕する結果となった。

意義および主張
本論文の主な意義は、ASPとALBの共同計画の効率性と実現可能性を向上させることにあると主張している。BOM階層を利用してサブアセンブリを事前処理することにより、手法は探索空間をより標的化し、それによって解決効率を向上させ、大量の実行不可能な解の生成を回避している。

著者らは、提案されたHAFSAが、この特定の多目的問題に対して従来のAFSAおよびPSOアルゴリズムよりも効果的であると断言している。魚群の行動にPSOの操作を統合することで、アルゴリズムは局所最適解をより良く脱出することができ、その結果、より高品質なパレート解が得られる。本研究は、この統合されたアプローチが、特に工具や方向の変更が重要なコスト要因となる場合において、より合理的かつ効率的な組立ラインの計画手法を提供すると結論付けている。