1．はじめに
最適化（数理計画法）の教科書に現れる「生産計 画の例題」には 3 種の原材料を異なった割合で所要 する 2 つの製品 X,Y について，各原材料の在庫の範 囲内で利益を最大化する「最適な」X,Y の生産量を 求めよ，といったものが多い．決まって答えはいず れかの原材料を使い切る，いかにも順当なものにな る．あくまで例題なので問題が小規模で単純なもの になるのはやむを得ないが，残念ながらこれは生産 の実務において解くことを要請されている問題とは かけ離れていると言わざるを得ない．そもそも生産 の現場において生産量は「最適化」できるものでは なく，制約として与えられるもので，所与の生産ノ ルマを，所与のリソースの制約下，いかにしてこな すか，という問題意識が実務における眼目となるの が普通であろう．
より現実に近い設定の例題としてこのようなもの はどうだろうか．ある会社のある日のミーティング 希望がたとえば 100 件あり，それぞれに希望の開催 時刻が紐づいているとして，10 個の会議室に重な らずに割り当てられるよう，ミーティングの開催ス ケジュールを調整することを考えてみる．
図 1 は希望時刻をガントチャートにし，各時刻の 同時利用会議室数をグラフ化したものである．昼の 時間帯において重なっている様子が見て取れる．ミ
ーティングスケジュールを前後一時間までは動かし てよいものとして，同時利用会議室の数が 10 を超 える分を最小化するという設定で，最適化ソルバー が算出した結果を図 2 に示す．この程度の規模であ れば最適化ソルバーは 1 秒以下で解を出力する．
2．より実務的な最適化とは この例題は
●
所定の数の工作機械（⇒会議室）において生産 予定（⇒ミーティング）を実施する
●
所定の数の車両（⇒会議室）で配送（⇒ミーテ ィング）を実施する
などの様々な読み替えが可能な点でより実務的なも のに近い．しかし，同時に利用されている会議室の 数が 10 を超える分を最小化する「最適解」は一つ ではなく，この解を出発点としてミーティングを交 換するなどすれば，会議室に収容可能な解は複数生 成できることがわかる．最適化ソルバーによって提 示されているのは膨大な可能性の一つに過ぎない．「最 適解」がこのように多数存在してしまうことは，最 適化が計算機任せにできない本質的な理由の一つで ある．
解が複数あるのならば問題の設定を変更すること で，解を絞り込んでゆくのは自然な発想である．た とえば予定を動かすミーティングの総数は少ない方 が望ましいのでそのように目的関数を変更すること が考えられる．しかし，少数のミーティングを大幅 に動かす調整と，多数のミーティングを小さく動か す調整はいずれが良いのかは結論が出にくい．より 実務に適合させるために制約の追加も必要となろう．
例えばメンバーの予定によってはミーティングの開 始時刻・終了時刻に制約が生じるし，同一人物の参 加するミーティングのスケジュールは重ねない制約 が必要である．
− 50 − 生 産 と 技 術 第67巻 第１号（2015）
Optimization for production
Key Words：optimization, production planning, scheduling, mathematical programming
1967年8月生
京都大学 理学部（1990年）
中央大学大学院 理工学研究科（2005年）
現在、NTTデータ数理システム 数理計 画部 部長 博士（工学） 自動微分・数 値的最適化
TEL：03-3358-1701 FAX：03-3358-1727 E-mail：[email protected]
生産を支援する最適化技法のご紹介
＊
Takahito TANABE
田 辺 隆 人
＊企業リポート
図 2 最適化ソルバーによる調整結果のガントチャートと 同時利用会議室数
図 1 スケジュール調整前のガントチャートと 同時利用会議室数
このように実務における最適化問題はいわゆる「数 学パズル」のように完全な形で提示されることはな い．骨組みとなる一般的な構造から出発するが，そ の結果を実務に適用しようとするとき個別的な様々 な要件が制約として追加されてゆく．さらに制約を すべて充足する解の存在は保証の限りではないので 必ずしも制約を厳密に満たす解のみが求められるわ けでもない．
3．人間系と最適化技法
ミーティングスケジュール調整問題に対するこの 議論は，会議室を工作機械に，ミーティング希望を 生産予定に置き換えた場合にも同様に成り立つ．会 議室と違って機械は定期的なメンテナンスが必要で あったり，生産を機械に割り当てる順序によっては 段取り替えコストが生じたりするなど，より複雑な 制約や目的関数に入れるべき要件が出現する．さら にどのような調整結果が最適なのかをあらかじめ明 確に定義することは簡単ではない．たとえば納期の 厳しい生産は他の生産予定を調整してでも優先させ るべきだが，どの範囲までのコスト増を許容すべき かは場合に依存して変化する．このように問題の定
義そのものが流動的なのでシステムが現場に追いつ くのは容易ではなく，実務的な計画系業務は主に人 間系に委ねられているのが現状である．計画系業務 の IT 化といってもそれは人間が生成した結果をチ ェックする，共有する，プリントアウトするといっ たいわば周辺部分に留まっている．
ただ，計画系業務の多くは数学的に抽象化すると 大規模で複雑な組み合わせ問題となるので，規模が 増大すると人手のみで適当な解を探し出すことには 大きな困難が伴う．実際に我々は製造の現場向けに 上記のミーティングスケジュール調整問題と同じ構 造を持つ問題に取り組んだが，会議室，ミーティン グ希望の数にして数百〜数千程度に相当する規模で あり，人間がアドホックに行う場合よりも，機械の 稼働率を大幅に向上させることができた．
融通が利かないながらも計算機と数学的技法を用 いて組み合わせ爆発を制御する技術である最適化技 法を援用することによって，人間系による計画系業 務を省力化し，結果を改善することが期待できるの ではないか，というのが我々の立場である．
− 51 −
生 産 と 技 術 第67巻 第１号（2015）
4．厳密解法とメタ・ヒューリスティクス
最適化技法の戦略の基本は，あり得る解に目的関 数（あるいは制約の充足度合の重み付き和）という 評価値を付け，評価値の低いものは考慮から外して ゆくことで効率を上げるというものである．古典的 な厳密解法（分枝限定法）と呼ばれる方法では，線 形計画法などの数学的な道具を用いて解の存在範囲 を絞り込み，解の存在領域すべてを実際に探すこと なく，効率良く最適解を取得する．例えば動力プラ ントのエネルギーコスト最小化というテーマにおい ては，最適化によって得られた削減の積み重ねがコ ストダウンに直結するので，この方法が適当である．
しかし，前述のように問題設定に曖昧性があって，
解が一意に定まらない実務的な計画業務に対しては，
時間をかけて最適解の一つを厳密に追い求めるのは 必ずしも適切ではない．そのようなニーズに対応す るのが，計算機の速度が向上するとともに台頭して きたメタ・ヒューリスティクスと呼ばれる方法であ る．この方法は厳密な最適解を求めるという最適化 の古典的な目的を放棄し，初期解から解を少しずつ 良い方向に変化させることを繰り返して，制限時間 内に可能な限り多数の良解を求めようとする方法で あり，解の更新の出発点となる初期値は乱数で決め る，同一の評価値の解の更新を選ぶときにも乱数を 用いる，一定のタイミングで現状の解を目的関数が 悪化する方向に変更する，など，無駄なく一直線に 解に至ろうとする古典的な解法とは対照的な挙動に よって，より多様な解を探そうとする．計算機の速 度を引き出す実装と適用する問題分野への適合次第 であるが，メタ・ヒューリスティクスは実務的な配 車問題，シフトスケジュール問題に対して十分な性 能と柔軟性を発揮することが知られている．厳密解 法とメタ・ヒューリスティクスという二つの対照的 な技法は，最適化が実務における人間のニーズにそ れぞれ歩み寄ってきたものだと考えることもできよ う．
我々は実務的な問題の最適化において「列生成」
とよばれる枠組み [1] でこの両者の解法を融合させ た手法を用いることがある．設備や時間の制約など，
動かすことができない「固い」制約と，メンバーの 教育的配慮や平等性など，調整が可能な「柔らかい」
制約が共存しているときには厳密解法が求めた「固 い」制約を満たす解のパーツを，「柔らかい」制約
を考慮しながらメタ・ヒューリスティクスで組み合 わせて多様な解を生成して人間系に提示する，とい う方法が適している．
5．おわりに（最適化のメリット）
我々 NTT データ数理システムは数理科学とコン ピュータサイエンスを軸にしたパッケージやサービ スを展開しているが，最適化ソルバー [2] の開発・
販売とそれを用いたシステム開発はここ 15 年あま りで我々のソリューションの主要な一つとして成長 した．その中で最適化技法を用いることのメリット として認識されているものを以下に列挙してみる．
本稿が生産の実務において最適化技法を試してみる きっかけとなることを願っている．
厳密性
制約を厳密に考慮して計画を立てることができるの で，解の質が担保できる．特に化学反応や状態変化，
機器の特性などの物理的な要件が制約として折り込 まれている場合には有効である．
裏付け
最適化技法は人間が与える解に「裏付け」を与える．
特に厳密解法を適用している場合には目的関数を改 善できる限界値を知ることができ，人間系による解 の探索に指針を与えることができる．
標準化
最適化技法に基づくシステムの開発に伴って人間系 が行ってきた計画系業務そのものが明文化されるた め，これまで属人化していた業務を標準化し，技術 を継承しやすくする．
恣意性の排除
人間系が制約を満たす解を生成することができると しても，考慮できる解の多様性には限界がある．メ タ・ヒューリスティクスアルゴリズムは計算機にお いてなるべく多様な解を探そうとするため，人間が 生成する解に混入しがちな恣意性を排除することが できる．
概要の把握
メタ・ヒューリスティクスに制限時間内で多様な良 解を出力させることによって，制約を満たす解が大 量にあるのか，少数しかないのかという見当をつけ て問題の解を大づかみにし，人間系が解を探索する 指針を得ることができる．
生 産 と 技 術 第67巻 第１号（2015）
− 52 −
