はじめに
生産スケジューリングの分野において、近年最適化生産スケジューリングやサプライチェーンの全体最適化などといった「最適化」という言葉をよく目にします。ちなみに、インターネットの百科事典で調べると、「最適化というのは本来、目的に対してもっとも適切な方針・計画をたて、設計を行い、あるいはそうした選択を行うことを意味することばである。」とあります。これだけでは何を言っているのかわかりません。そこで、このページでは、生産スケジューリングの分野における最適化の意味を分かり易く解説します。
なぜ最適化が必要なのか
「生産スケジューリングとは」のページで解説したように、生産スケジューリングとは、課せられた制約を満足するように各ジョブの各作業の開始時刻と処理する機械を調節することでした。しかし、制約を満足さえしていれば、どんなスケジュールでもいいのでしょうか？
例えば、明日お客様に渡さなければならない製品が２個あるとします。１個生産するのに１日かかり、機械は１台しかありません。単に制約を満足させるだけなら、２個の製品の内の１つを明日生産すれば良いことになります。しかし、これでは「明日までに渡す」という納期を守ることができません。すなわち、納期をできるだけ守りつつ、課せられた制約を満足するようなスケジュールを作成する必要があるのです。これが最適化生産スケジューリングです。
最適化生産スケジューリングとは
最適化生産スケジューリングを要約すると次のようになります。
| 最適化生産スケジューリングとは、スケジュールの良し悪しを最適度として数値化し、その数値ができるだけ良くなるように各作業の各機械での開始時刻、およびどの機械で処理するのかを調節することです。 |
スケジュールの良し悪しを表す数値は色々あり、例えば、ジョブの完了時刻が納期とどれだけずれているかや、生産に要する時間（生産リードタイム）がどれだけ短くなっているか、はたまた全てのジョブを処理するのに要する時間などが採用されます。どれを採用するかは、工場がおかれた生産環境によって異なります。ちなみに、このホームページで公開しているソフトウェアでは、スケジュールの良し悪しを測る数値として、ジョブの完了時刻と納期とのずれ、投入時刻と納期逆算の投入予定時刻とのずれを使っています。
最適化生産スケジューリングの難しさ
最適化生産スケジューリングを言葉で表現するのは簡単です。しかし、実はこの最適化生産スケジューリングは、数学的にNP 困難な問題に分類され、非常に難しい問題なのです。
| NP 困難な問題とは、真に最適な解（スケジュール）が多項式時間（x の N 乗の時間）では求められない問題のことです。 |
でも、「何を言っているのだ。すべての場合を列挙してスケジュールの良し悪しを測る数値を計算してみればいいじゃないか。」と思われた方も多いのではないでしょうか？
簡単のために、複数のジョブを処理する順番だけを決める問題を考えてみましょう。ジョブが 3 つの場合は 6 通りあり、4 つの場合は 24 通りあります。では、ジョブが 10 個の場合はどうでしょうか？これは、3,628,800 通りもあります。そしてジョブが 20 個の場合は、なんと約 240 京通りという天文学を超えた数字になるのです。ここで、我々が解こうとしている問題は、処理する順番だけではなく何時、どの機械で処理するのかを決める複雑な問題であることを思い出してください。そこで、例えばラグランジュ緩和（分解・調整）法や遺伝的アルゴリズムなどのメタ戦略を使って、近似的に最適な解（スケジュール）を求めることになります。
最適化生産スケジューリングの威力
最適化生産スケジューリングの手法、ラグランジュ緩和（分解・調整）法と遺伝的アルゴリズムがなんなのかは、難しくなるのでここでは触れません。詳しく知りたい方は左記のリンクをクリックして理論的な解説をご覧ください。このページでは、結果だけを紹介します。
下の表は、通常の生産スケジューリングと比較して、最適化を行うことによって最適度（ここでは、ジョブの完了時刻と納期とのずれ）がどれだけ改善するのかをまとめたものです。
| ラグランジュ緩和法 | 32% |
| 遺伝的アルゴリズム | 17% |
例えばラグランジュ緩和（分解・調整）法の場合、納期順守率が 32% 改善すると言っています。もしあなたの工場の納期順守率が 32% 改善したらどうでしょうか？これが、最適化生産スケジューリングの威力です。
