「重ね合わせ」タイプのモデル 応用その一:生産計画問題

「時間」という概念を入れると「セット販売」のパターンが自然に量産できて 「セット販売」のうまい重ね合わせ、という話がぐっと実務性を帯びてきます。 具体的に申しましょう。今度の例は物を買う話ではなくて作る話になります。 ある製品をある日までに出荷しようとすると、 それに先立って、生産やその準備、箱詰め、といった作業量が「セット」として付随してきます。

次は 4/10 に製品1個を出荷しようとするときに、当日と先立つ 4 日間に 発生する作業量を棒グラフにしたものだとします。

4/10 にできるだけ製品を沢山出荷したいが、各日の作業上限が決まっているとします。 例えば一日50単位の作業しかできないのならば、 このままだと 4/7 の作業量上限がボトルネックになって、下の絵のように 4/10 には 10 個しか出荷できない ?

いえ。沢山作りたいときには、一部作業を前倒ししてピークをカットしますよね。 数理最適化でこの「前倒しによるピークカット」を表現してみましょう。 4/9 以前の作業を「前倒し」するパターンを幾つか作っておきます。 まず一日前倒しするパターン(4/5 から準備を始める)、 さらに二日前倒しして 4/4 から準備を始めるパターンも作っておきましょう。 あとは重ね合わせて作業が所与の値を超えない、ということを表現すれば 数理最適化モデルのできあがりです。

このモデルの数理最適化の最適解は 17個 (標準パターンで 3 個、一日前倒しパターン、二日前倒しパターンでそれぞれ7個ずつ)、でした。 合計作業量のグラフは

という感じで、一日にいろいろな作業を重ねてぎりぎり 50に納めている様子 がわかります。 今度は「作業量」というありがたくないものが「セット販売」になってきていますが、 「重ね合わせて条件を判定」という気持ちは「まんじゅう」のケースと同じ。 モデルに「時間」という要素が入っているので 袋A,袋Bなどの「セット販売」のパターンに相当するものが、 時間をずらすだけで自然に沢山作れてしまいますね。

生産と梱包の作業は違う人が担当するので単純に合計の上限が 50 ではなく、 それぞれ作業上限枠がある、とかパターンの作り方が単細胞すぎるので 質的に違ったパターンを選択肢に入れたい、 といった話もちゃんと取り込むことができて、 ここまで来れば実務的に役立つ生産計画モデルまであと一息、 今時の数理最適化ソルバーなら数千のパターンがあっても解けますので十分実用的です。 重ね合わせタイプのモデルは数理最適化モデルの代表選手で、 違った背景で同じ構造を持つ問題はまだまだあります。 次回は「経路」という概念を入れてネットワーク問題を解く例を紹介しましょう。