Multi-objective optimization of production scheduling with evolutionary computation: A review
多目的最適化および進化計算（EC）のレビュー論文
背景
製造業における計画やスケジューリングでは，以下のような要求がある：
- 在庫数の最適化
- 納期の遵守
- 注文対応までの時間短縮
- 顧客の好みへの広い対応
これらの要求に対して「どうやって最適な作業順を素早く決めるか？」は大きな課題である．
近年のスマート工業（AI と生産業の融合，IoT も含む）の発展により，従来の方法では限界が見えてきた． この課題に対しては進化的計算による解決が不可欠である．
また，単一目的の最適化では対応できないため，多目的最適化の重要性が増している． 特に NP 困難な問題に対しては，正確な解を求めるよりも，良質な解をいかに早く導出するかが重要となっている．
生産スケジューリング
生産スケジューリングとは，限られたリソースを用いて，各作業をいつ，どこで，どの順序で実行するかを決定することである．
ジョブスケジューリングのイメージ．縦がノードで横が処理時間
制約にもよるが，ジョブスケジューリングには並べ替えや配置で何万パターンも存在する．
記号の定義
- i：ジョブ（作業）番号（1〜n）
- j：機械番号（1〜m）
- k：作業内の工程番号
- p_ij：ジョブ i を機械 j で処理するのにかかる時間
- r_i：ジョブ i の着手可能時刻（リリースタイム）
- d_i：ジョブ i の納期
- w_i：ジョブ i の重要度（重み）
スケジューリングの種類
- 単一機械
- フローショップ
- 機械の故障や急な注文などがある動的なスケジューリング
- リアルタイム性が重要
- ジョブショップ
- 決められた順序で複数の機械を通る必要があるジョブが与えられる
- 総完了時間（makespan）などを最小化する
- 柔軟ジョブショップ
- 各工程を実行可能な複数の機械から選択可能
- 機械の故障や急な注文などの動的な要素に対応
- リアルタイム性が重要
最適化指標
主な指標：
- 納期遅れ（Tardiness）
- 完了時間の合計（Total Completion Time）
-
最大遅れ時間（Lmax）など
記号 説明 Cj Completion time（完了時刻） Li / Lmax Lateness / Maximum lateness（遅れ/最大遅れ） Ti / Tmax Tardiness / Maximum tardiness（遅延/最大遅延） Ui Unit penalty（単位ペナルティ） Cmax Makespan（最大完了時刻） ΣCj Total completion time（完了時刻の合計） Σ(di - Ci) Total earliness（早期完了の合計） ΣTi Total tardiness（遅延の合計） ΣUi Number of late jobs（遅延ジョブの数） ΣwiCj Total weighted completion time（重み付き完了時刻の合計） ΣwiUj Weighted number of tardy jobs（遅延ジョブ数の重み付き合計） ΣwiTi Total weighted tardiness（重み付き遅延合計） Σwi(di - Ci) Total weighted earliness（重み付き早期完了合計）
多目的最適化
多目的最適化は，互いに矛盾する可能性のある複数の目的を同時に最適化する手法である． MO（Multi-Objective）最適化の特徴として，単一の最適解ではなく，パレート最適な解の集合が得られる．
パレート最適解（Pareto optimal solution）とは？
多目的最適化問題において，複数の目的関数（$f_1, f_2, …, f_k$）が存在する場合， 「一つの解が他のすべての解に対して，すべての目的で優れているとは限らない」という状況が発生する．
パレート優越（Pareto dominance）の定義
解(x_1)が解(x_2)を支配（dominate）する条件：
- すべての目的関数$f_i$において$f_i(x_1) \leq f_i(x_2)$
- 少なくとも 1 つの目的関数$f_j$において$f_j(x_1) < f_j(x_2)$
パレート最適解の定義
- パレート最適解：他のいかなる解にも支配されない解
- パレートフロント：パレート最適解全体の集合
図的な理解例
- X と Y：互いに支配しない → パレート最適解
- Z：X と Y の両方に支配される → 非パレート解
多目的最適化の方法の分類
| 分類 | 手法の概要 | 代表的アルゴリズム例 |
|---|---|---|
| A priori 型 | 目的関数の重みや優先順位を事前に決定 | - ユーティリティ関数法 - 目標計画法（Goal Programming） - レキシコグラフィ法 |
| A posteriori 型 | 解集合を生成し後で選択 | - NSGA-II（Non-dominated Sorting GA） - SPEA（Strength Pareto EA） - MOPSO（Multi-objective PSO） - MOEA/D（MO Evolutionary Algorithm based on Decomposition） |
| Interactive 型 | 人間との対話を通じて最適解を選定 | - NIMBUS（対話型多目的最適化） - PI-EMO（Preference-based Interactive EMO） |
代表的な進化的多目的最適化アルゴリズム（EC ベース）
| アルゴリズム | 概要と特徴 |
|---|---|
| NSGA-II | 高速な非劣解ソート，クラスタリングなし，広く使われる（Deb et al. 2000） |
| SPEA | 各解に「強さ」を割り振って選択するアプローチ |
| MOGA | 遺伝的アルゴリズムに基づいた多目的最適化 |
| MOPSO | 粒子群最適化（PSO）を MO に拡張したもの |
| MOEA/D | 問題を複数のスカラー化問題に分解して解く分散型アプローチ |
| PESA-II | パレートエンベロープを用いたアーカイブベースの選択方式 |
| PI-EMO-VF | 人間の好みに基づいた値関数による対話型進化最適化 |
ハイブリット多目的最適化
Exact アルゴリズム 最適解が得られるが，計算時間が爆発する．ジョブスケジューリングには向かない．
近似アルゴリズム 最適解に近い解を求める．誤差もわかる 実問題に合わせにくい時がある
ヒューリスティックアルゴリズム． 短時間でいい解を出す 最適性は保証されない．誤差もわからない
メタヒューリスティックアルゴリズム ヒューリスティックの中で汎用性と拡張性を持たせたもの 特定問題に依存しない NP 困難に有効 例：GA, PSO（粒子群最適化），ACO（アリコロニー），Kalman Filter
ハイブリッド戦略とは GA ＋ルールベース PSO+ローカルサーチ ，，，など
レビュー
2005~2019 年でいっぱい論文集めました
生産スケジュールにおける進化的計算（EC）
EC とは，生物の進化の仕組みを模倣したアルゴリズム群
- 初期集合をランダムに生成
- 各個体の評価
- 考査と突然変異で新しい世代を生成
- 優秀な個体を選択して繰り返す
応用事例
シミュレーションモデルを用いた応用が多い． ジョブショップあからフレキシブルだったり色々とステージを上げて現実に近づけていくイメージ
議論
多目的最適化の動向
- 多目的最適化の実用化においては、単にパレート最適解集合を出すだけでは現場では不十分
- 現実では、意思決定者（decision maker, DM）がパレート解の中から一つを選ぶ必要がある
- そのため、以下のような要素が求められる：
- 視覚的表示（visualization）：パレート解の分布を理解しやすく表示
- 選好モデル（preference models）：ユーザの好みを反映したフィルタリング
- インタラクティブ選択：ヒューマン・イン・ザ・ループによる意思決定支援
EC アルゴリズムのよくないところ
GA や PSO は交叉率や変異率に敏感である
今後の研究展望
- よりリアルな制約・動的変化を扱うモデルの開発
- オンライン学習・強化学習的手法との統合
QA
リアルタイム最適化とユーザの選好は両立できるのか？
Q1. パレート解集合を出すだけではリアルタイムには不十分？
はい。パレート解集合は複数の最良解を同時に提示するが， リアルタイム環境ではユーザがそれを吟味して選んでいる時間はない． → 必要なのは「即時に一つの解を自動で選ぶ仕組み」．
Q2. パレート解を出すなら、アルゴリズムの速さは重要ではない？
はい（ある程度）。パレート解集合をオフラインで使う前提なら， 多少時間がかかっても良い（可視化・分析に使うため）． だが、リアルタイムで使うなら高速な一解抽出の仕組みが必要．
Q3. リアルタイム最適化ではどう工夫すればよい？
方法 1：オンライン MOEA（Online Multi-objective Evolutionary Algorithm）
- 解を逐次生成し、最新の最適解を 1 つだけ提示
- パレート集合を都度更新し続けるような形
方法 2：ユーザ選好の組み込み（Preference-integrated）
- 「コスト優先」などのユーザの好みを事前に反映
- 解候補にスカラー化を適用し、解の選択を自動化
方法 3：ルールベースな即時判断（Rule-based selection）
- 「納期よりコスト」「処理時間 < 10 秒」などのルールを設定
- ルールに合致するものを即時選出（if-then 型）
Q4. どんな技術がその両立に役立つ？
| 技術 / 方法 | 説明 |
|---|---|
| オンライン最適化 | 問題が動的に変化してもリアルタイムで解を更新 |
| 選好モデル（preference model） | 人間の判断傾向を数値モデルに落とし込んで選択を自動化 |
| 強化学習（RL） | 過去の選択履歴からポリシーを学習し，動的に適応 |
| Human-in-the-loop | 「Yes/No」「どちらが好ましいか」など最小限の人間介入 |
| 可視化と要約 | 解の意味やトレードオフを簡単に伝える支援 UI |
結論
リアルタイムでの多目的最適化には，「速さ」「一意性」「選好の反映」 が同時に求められる． そのためには、従来のパレート集合提示型 MOEA ではなく， 選好統合・即時判断・ユーザ支援の仕組みを組み込む必要がある．