生産を支援する最適化技法のご紹介

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

Download Report