はじめに

　サクラスケジューラでは、核となるスケジューリングロジックにメタ戦略に基づくラグランジュ緩和（分解・調整）法と遺伝的アルゴリズムを採用しています。メタ戦略には、タブー検索法や焼き鈍し法などもあり、最新の組合せ最適化手法の一つです。では、そもそも生産スケジューリングにおけるメタ戦略とはなんなのでしょうか。このページでは、生産スケジューリングの分野におけるメタ戦略の意味を分かり易く解説します。

従来の最適化手法

　「最適化生産スケジューリングとは」のページで解説したように、最適化生産スケジューリングとは、納期順守率や生産リードタイムなどの評価値を可能な限り良くしつつ、課せられた制約を満足するように各ジョブの各作業の開始時刻と処理する機械を調節することでした。そして、この最適化生産スケジューリングは NP 困難な非常に解くのが難しい問題でした。

　この難問に対して、従来は最適性の保証はないものの、経験的にある程度良いスケジュールが得られることが知られている近似的解法や発見的手法が使われてきました。例えば、最適性の評価値（納期順守率や生産リードタイムなど）への貢献度を表す局所的な評価値に基づいてスケジュールを組む貪欲法や、与えられたスケジュールを簡単な操作で変えてみて評価値が改善するかどうかを調べる局所探索法です。

　しかし、これらの従来の最適化手法には、最適性の保証がないことに起因する致命的な欠点がありました。それは、局所的に最適なスケジュールを作ってしまうという問題です。x - y 軸を持つ２次元のグラフを想像してください。y 軸が最適性の評価値、そして x 軸がスケジュールを表すと考えてください。例えば、発見的手法では、x 方向にスケジュールをちょっとだけ変えてみて y の値（すなわち最適性の評価値）が良くなるかどうかを探ります。しかし、生産スケジューリング問題のグラフは山あり谷ありです。そして深い谷もあれば、浅い谷もあります。従来の最適化手法では、全体最適な深い谷ではなく、局所最適な浅い谷を最適だと判定してしまっていたのです。

メタ戦略とは

　メタ戦略による最適化生産スケジューリングを要約すると次のようになります。

メタ戦略とは、従来の最適化手法よりも多少の時間が掛っても、数学的に近似的な最適性の保証のあるスケジュールを求める解法の一般的な枠組みのことです。

　サクラスケジューラで採用しているメタ戦略であるラグランジュ緩和（分解・調整）法は、双対定理と相補性定理という数学的な背景を持ち、遺伝的アルゴリズムは一様マルコフ連鎖という数学的な背景を持っています。（ここでは、簡単のために各定理や理論がなんなのかは省略します）。また、ラグランジュ緩和（分解・調整）法や遺伝的アルゴリズム以外にも、メタ戦略にはタブー探索法や焼き鈍し法などがあり、遺伝的アルゴリズムと同様に一様マルコフ連鎖という数学的な背景を持っています。

　ここで、厳密にはラグランジュ緩和（分解・調整）法はメタ戦略ではないことに気を付けてください。一般的には、メタ戦略とは「解を生成してはその最適性の評価値や実行可能性を評価するという操作を繰りかえす」手法を意味しますが、このホームページでは簡単のためにラグランジュ緩和（分解・調整）法もメタ戦略と呼んでいます。

メタ戦略の威力

　実は、これらのメタ戦略に基づく生産スケジューリングの研究は最近始まったことではなく、1980年代から精力的に研究されていました。しかしながら、当時のコンピュータの性能では「多少の時間が掛っても」というメタ戦略の考えは実現不可能で、実用化されていませんでした。でも、今は状況が違っています。コンピュータの性能は飛躍的に向上しており、生産スケジューリングの分野でもより高度な手法によって納期順守率を向上し、生産リードタイムや段取り時間を短縮することが求められています。

　では、本当のところ、これらの最先端の理論を使ってスケジューリングした結果はどれだけ良くなるのでしょうか？努力する甲斐はあるのでしょうか？下の表をご覧ください。

貪欲法（従来の最適化手法）1,194,283
ラグランジュ緩和（分解・調整）法899,684

　２つの数字は納期順守率や生産リードタイムなどの評価値だと思ってください（厳密には違います）。数字が小さくなればなる程よいスケジュールであることを表しています。メタ戦略であるラグランジュ緩和（分解・調整）法を使うことによって、従来の最適化手法である貪欲法と比較して、スケジュールの評価値が 25% も改善されています。もしあなたの工場の納期順守率が 25% 改善したとしたら、もしあなたの工場の生産リードタイムが 25% 短縮されたとしたらどうでしょうか。これがメタ戦略の威力です。