コラム・特集

4.6 ジェネラル・モーターズ社における離散形モデルの応用

IEハンドブック
第14部 インダストリアル・エンジニアリングの最適化

第4章 離散形最適化

4.6 ジェネラル・モーターズ社における離散形モデルの応用

機械負荷計画モデル
機械負荷計画モデル(MLP)は製造工場での能力計画に使用される。このモデルの目的は,ある工場で1計画期間中に製造される各部品の機械割当てと,製造サイクルとを決定することである。このモデルは工場倉庫と機械能力とに関する制約を満たした上で,総段取費,総保管費,総残業費を最小にするような製造計画を作成する。このモデルの仮定は次の通りである。

1.部品を工具に割り当てるのはモデル使用者の責任である。このモデルでは部品・工具間,工具・機械間の割り当てではなく,工具・機械間の割り当てだけを考えている。

2.全計画期間中,工具は使われていないか,ただ1つの機械に(おそらく何回か変わるであろうが)取りつけられていなければならない。モデル使用者が指定する機械はそれぞれ固有の能力を持っている。

3 各部品は製造後,定められた貯蔵能力を持つ場所に保管される。

4.全計画期間は,いくつかの等区間に分割できる。たとえば計画期画は16週にわたるというように。

5.各工具と,工具が取りつけられる各機械に対して, サイクルは1, 2, 4, 8時 間区間の部分集合に限られる。実際的立場でこれをいいかえると,通常ある工具は製造のために1,2,4,8週間ごとに1 回機械に取り付けられるということである。

6.モデルは段取費と在庫保管費により計画を評価している。段取費には2種類――主段取費と補助段取費がある。主段取費とは,それまでの工具を機械から取り除き,新しい工具を取りつけるための費用である。補助段取費とは,このような主段取なしで新しい部品を製造するために,工具のさし込みを変更したり,材料の種類を変えたりすることに対する費用である。モデルはすべての補助段取は関連した主段取が行われた後で,あらかじめ決められた順序で行われることを仮定している。

7.全計画期間にわたって需要は一定である。

8.1レベルの部品構成表である。1工程で部品が製造されたら ,そのまま梱包され出荷される。

9.機械上での工具の順序付けは考慮しない。順序はこのモデルの出力にもとづいて使用者が指定する。

モデルの定式化と解法
工具に対しt,機械に対しm,可能なサイクルに対した ,のインデックスを与える。決定変数は,

Xtmk=1 工具tが,第kサイクルで機械物に取りつけられたとき
=0 その他のとき

工具に対する要求,機械上の工具の生産速度,段取時間と費用,在庫保持費,部品の大きさと保管に使うコンテナの大きさなどに基づいて,次の定数が定まる。

Rtmk=全計画期間中の工具rに対する要求を満たすために必要な,第kサイクルでの機械物の所要時間数。

Ftmk=第kサイクルで機械mに取りつけられ作動した, 工具tからの製造品を保管するのに必要な全床面積。

Ctmk=第kサイクルで機械m上の工具tが作動したときの全計画期間にわたる総段取費と総在庫保持費。

 

計画期間中の機械物の利用可能時間をBmとし,製品を保管するのに使える床面積をSとする。

ここでこの問題は次のような整数計画問題としてまとめられる。

(1),(2)の制約式は,ある工具がただ1つのサイクルを用いて,ただ1つの機械でのみ作動し,利用可能機械時間の制約が保たれることを保証するものである。(3)の制約 式は利用可能床面積を超えられないことを意味している。

MLPの典型的な適用例をあげると,およそ1,500個の工具,300台のプレス,4種のサイクルを含んだもので,整数変数は10,000個にも達する。この問題は上の定式化の形では,大き過ぎて計算時間を考えると解くのは無理である。このモデルを簡単にする第1の手段は被優越整数変数を省略することである。工具と機械は同じで,サイクルだけが異なるような整数変数の中で,自分自身よりも費用や時間に関する要求が小さい変数が存在すれば,その整数変数は被優越であるという被優越整数変数は最適解には絶対現われないので,問題から省いてもかまわない。この優越原理によって,約25%の整数変数が省かれ,残りの約8,000個の整数変数が,このMLP問題において取り扱われることになった。

次の手段は,問題を独立した部分問題に分割することによって,モデルを簡単にすることである。これを行うには,完全に独立な工具―機械グループを見つけねばなら ない。この工具―機械グループの基本的な性質といえば, グループ内の工具はそのグループ内の機械でのみ作動し ,このグループの機械は,このグループ内の工具だ けを扱っているということである。このMLP問題では, ほぼ6つの独立な工具―機械グループに分割でき,最も大きなグループで約2,000個の整数変数を含んでいた

計算時間から考えてみて,2,000個の整数変数をもつMLP問題となっても,なお商用整数計画コードで解くにはあまりにも大きすぎる。そこで次の手段は,床面積制約をゆるめることによって,問題をさらに簡単にすることである。「準勾配法」とよ ばれる手法を用いて床面積制約を取り除き, 目的関数の中で,その影響を考慮することにした。準勾配法では,制約条件式(2を目的関数の中に取り入れて,床面積の帰属コストを見積もることにより原問題の緩和をはかる。この床面積の帰属コスト を用いて原問題の目的関数の保管費の成分が調整される。修正されたMLPモデルは次のようになる。

ここで C′tmkはCtmkに床面積を占有するための費用を加えたものである。

この修正モデルと同じ 構造を持つ大規模問題が解ける専用の整数計画コードが使われる。このコードは,ラグランジュ緩和法を用いて目的関数に(5),(7)式の制約条件を取り入れ,この修正モデルをナップザック問題に変換するものである。得られたナップザック問題はRossとSoland の研究に基づく分枝限定法を使用して解かれる。

以上要約すると,大規模で複雑な整数モデルをいくつかのより小さい簡単な整数モデルに変換し,これを専用の整数計画コードにより非常に効率よく解くことができた。典型的なMLP問題の最適化フェーズに必要なコンピュータ時間は, IBM 370/168でlCPU分である。

モデルの実施

前節で述べたモデルは,MLPシステムと呼ばれる能力計画システムでの解法フェーズに組み込まれたものである。この節では同じシステムのデータベース作製フェ ーズと,出カフェーズについて簡単に触れ,さらにこのシステムが,どのようにジェネラル・モーターズ(GM) 社のプラスチックや金属のプレス部門の生産計画を改善 するのに使われているかを説明する。

データベース作製フェーズでは工場の現在の生産管理, IE,会計のファイルからMLP用データを取り入れ,それを編集する。MLPの意思決定を行うのに必要なデータは部品・工具・機械に分類できる。部品データは,たとえば打抜きのような,特定の作業での部品の製造と,その後の貯蔵に関連する情報を含んでいる。必要な部品 データとしては,単位在庫保管費を計算するための部品材料費と,付加労務費,部品在庫の必要容量を決めるための標準部品容器,標準梱包量,貯蔵場所,全計画期間中での種々の製造サイクルにおける総保管費と,必要機械時間能力を決定するための平均部品需要データなどがある。

工具データは,特定の作業での工具の段取と製造の特性に関連する情報である 必要な工具データとしては, ある機械へのある工具の段取費用を計算するための主段 取工数,段取のためにどのくらい機械が停止し製造に使え ないかを決めるための段取時間,モデルが各工具に対して選択する可能性のあるサイクルを与える利用可能生産サイクル,すべての運転時間と停止時間の許容範囲を考慮に入れた各工具の生産速度,特定の工具で部品を生産するに必要な人数として与えられる必要生産労働量などがある。

機械データとしては設置場所,構成,能力などの情報 が必要である。機械は単一の設備としても,機械ラインの部分としても,また機械ライン全体でも指定できる。機械の能力は全計画期間中の時間単位で与えられる。全計画期間中に利用可能な正確な能力を決めるには,休日,週末,定時間勤務,残業勤務などを考慮に入れた勤務時間が必要である。

システムには, またどの工具がどの部品を作るかを正確に指定するため,部品・工具割当データが必要となる。特定の部品を作ることのできる工具中の凹みの個数も,部品の生産速度 (個数/時間)を計算するのに必要な情報である。システムは工具さし込みの変更と,加工される材料の種類の変更の費用と時間を決きるためにある工具の種々の部品に対する補助段取データを考慮する能力を備えている。

このモデルを動かしているデータは工具・機械組合せデータである。これはすべての可能な工具・機械の割当てを各割当ての優先度の順番に示したものである。各工具に対してモデル使用者は ,その工具が作動できるすべての可能な機械と,それぞれの可能な割当てに対する相対的望ましさを指定しなければならない。モデル使用者は,また工具・機械組合せデータを作るに際し ,接合の形状 , トグルプレスの位置,材料剥離,オートメーション ,生産速度効率のような問題も考慮しなければならない。

MLPシステムは多様な報告書を作り出す。機械負荷報告書は,システムが各機械に割当てた工具を表示する。機械に割当てられた各工具に対して,報告書は工具の推奨サイクルと全計画期間中の必要段取時間と必要製造時間を示す。機械負荷要約報告書は機械,トン数, 部門,工場ごとの機械稼動率を与える。倉庫報告書は, 計画倉庫負荷(平方フィート)とMLP生産計画による利用可能倉庫空間の利用率を示す。容器報告書は容器型式ごとの所要量を示し,コスト報告書は与えられた生産計画に対する貯蔵費・段取費・残業費を表示する。

MLPシステムは短期,長期両方の計画に利用できる。 短期計画においては, システムは日程計画を支援するために用いられる。あるGM工場の日程計画担当者は,このシステムが勧告する,各工具に対する機械の割当てとサイクルにもとづいて日程を作製している。現在の在庫 の状況,最近の部品仕掛リスト ,資源調整の制約については人手で考え,指定された機械上での工具の順序づけも,人手で実施している。このような利用の場合,MLPシステムはスケジュールを単純化し過ぎている。日程 計画担当者がMLPによる負荷計画の通りに実施できないのは,1台の機械にあまりに多くの作業が負荷されてしまうことによるものである。

MLPシステムはまた,現在の週より先の計画を立てるのにも利用される。長期計画においては , このシステムを利用して,需要の変動がどのように機械,容器,倉庫の必要保持能力に影響を与えるかについての, “仮定の”質問に対して管理者に答えることができる。いくつかの工場では,予測需要を満足するに必要な機械の追加の量と型を決めるのに,このシステムを用いている。かさばった部品を生産している別の工場では,このシステムを用いて,貯蔵倉庫設備の設計を行っている。MLPシステムは,計算にそれほど多くのコンピュータ時間を要しない。1,500個の工具と300台のプレスを持つ実例において,このシステムはIBM370/168の約2CPU分を必要とした。このような短い計算時間のゆえに,システムの利用者は,管理者の“仮定”型の質問に答える場合,パラメータを変えた何回もの計算の繰り返しを気軽に実行できる。

このMLPシステムは最近,多層の部品構成環境の下での能力計画に拡張された。現在このシステムは 週別能力計画システムに拡げられ,これによりある工具に対する 機械割当てと生産サイクルの決定に付け加えて,生産開始の週も決定されている。

材料と技術の評価システム
自動車製造業者の全車両燃料消費量は,各車種別の販売量にもとづいて計算されている。これらの車種はEPA (環境保護局)検定の手続きによって決められる 各車種内では,あらかじめ定められた刻み幅を持つ重量クラスにグループ分けされている。各重量クラス毎に決められた燃料消費量基準を用いて,販売量で重み付けした全車両燃料消費量が計算できる。

与えられた販売車種と数量に対して,計画担当者は2つの方法によって全車両燃料消費量を改善できる。(1)重量変更により,他の重量クラスに車を移すことがてきる。 (2)技術的変更により,第1の方法は車に特別材料(PM) 要素を加えることによって実現される。PM要素とは, 車のある部品を特別な材料で作ったもっと軽い部品に置き換えることである。これによりコスト高にはなるけれども,たとえば,鋼製のフードをアルミ製のものに置き代えることができる。第2の方法は技術(TECH)要素を加えることである。TECH要素とは改良された技術 (たとえば新型のタイヤ)を用いて,燃料消費量を改善することである。この場合,標準の要素に比べて,重量は軽くなることも重くなることもあるが,コストは増加する。

大きな製造業者にとって,車にこれらの要素を適用する方法は非常に多様で,人間が実際的に評価するのは難しい。材料と技術の評価システム(MATES)は,望ましい全車両燃料消費量の目標値を確保するために:割増しコストでの重量軽減と燃料節約技術の両要素の利用を最適化することをねらって開発されたものである。

この問題を一般的にまとめると,最小コスト妨法で, 各車種に適用すべきPMとTECHの両要素を選択することである。この場合,車と要素間の適用可能性の制約の下で,全車両燃料消費量の到達目標が達せられることが必要である。さらに,加工方法の決定や要素の容量も考慮されねばならない。

一般モデルが定式化され,200種の車,15個の要素, 6重量クラスをもつ代表的な問題に対して, 4,200個以上の0-1変数と6,000本の制約条件式が必要とされた単純化した一般問題を解くのにさえ,商用の最適化コードによる数時間のコンピュータ時間と,特殊目的のコードの開発を必要とするであろうシステムの実行を容易にするため,加工方法と要素の容量の制約は省略した。このことは戦術的な意思決定におけるシステムの有用性を損なわないし,戦略的な意思決定の評価は,このシステムの繰返し実施によって可能となるはずである。

問題をいくつかの論理的な要素使用制約に分割してみても, 0-1変数の個数は大きい。システムに実用可能 な応答時間を与えるために発見的方法が開発された。こ れは次の3つの手法の上に成り立っている。(1)一連のナップザック問題を解くこと。(2)可能な車・要素の組み合 わせの部分集合を考えること。(3)ラベリング手法を用いて車への要素の利用状況を指示すること。

1つ の重量クラスの中では,どんな重量であろうと燃料消費量基準は同じであるから,不足しているPM要素は,できるだけ少ししか利用しないで,望みの重量クラスの中に留まっているのが最適である。いかなる重量の車に対しても,現在の重量クラスの上限までの重量増加幅と,次に低い重量クラスの上限までの重量減少幅とが分かっている。問題はこの目標を超え(切ら)ないで,できるだけ密接にこの重量増加(減少)目標を満足させるよう,取り除く(加える)べきPMあるいはTECH要素を選ぶことにある。要素は離散値の重量を持っているから,その都度必要に応じて,加えたり取り除いたりすべき要素の,最良の組合せを見つけるためナップザック問題が解かれている。

ナップザック手法20は ,各車の重量減少目標を最も有効に達成するような要素の組合せ(要素パケット)を作り出すために用いられている。ある車に適用できるすべての可能な要素の組合せを考えることを避けて,考えるべき要素パケットの数を制限するための,コスト・有効性 決定規則が用いられている。発見的規則でのこのような制限の1例をあげると,要素パケット中のTECH要素の数を1以下におさえることがある。

発見的方法として順位づけ法がある。この方法では各 繰返しごとに,コスト・有効性と燃料経済の立場から最良の政策が適用される。この方法はまず一度に1台の車 を考えて,その車を望ましい重量区間に留めるのに必要な要素を加えたり取り除いたりする。要素パケットがナップザック法によって作り出され,コスト・有効性の順位で適用されていく。各段階で,車の重量を変えないでおく場合,重量増加(要素の除去)の場合,要素パケットを適用して次の下の重量クラスヘ落とす場合,それぞれのコストと燃料経済への効果が評価され,処理されていく。

柔軟性を増すために, ラベリング法が各車への要素の使用と一貫性を指示するのに用いられている。 この手法により大規模問題への良好な解を短時間で見つけ出すことができる。この発見的手法は,CRT(ディスプレイ端末)向きの経営情報システムと結合して用いられている。これを用いて, いろいろな仮定の下での各種の燃料経済上の対応処置を,手軽に評価することができる。この材料と技術の評価システムは,現在と将来の年 次モデル計画に広く用いられており,全車両へのPM要素とTECH要素の使用方針を決定し, これらの要素に要求される容量レベルを決めている。

自動車生産ライン割当てモデル
自動車生産ライン割当てモデル(CALM)は,自動車生産ライン(1品種の製品と対応する )を組立工場に割り当てる過程において,企業経営者を援助するために作られた数学的道具である。この意思決定過程に用いられる数学的手法は混合整数計画法である。

このモデルの目的は,各組立工場にどの自動車生産ラインを建設すべきか,そして割り当てられた自 動車生産ラインは,それぞれ何本ずつ作るべきかを決めることにある。その場合,需要と生産に関する制約条件を満足し, 関係する組立費と輸送費と最小化することを目的とする。 現在このモデルは,次の各要素を考慮に入れる性能をもっている。

1.自動車生産ラインと販売地域ごとの需要予測

2.工場の生産規則と制約(たとえばある工場には一定数の自動車生産ラインし か割り当できない。また自動車生産ラインのある組み合わせは設置できない)

3 現在の工場の位置と能力

4.社外への輸送費(完成車を販売業者へ)

5.社内での輸送費(製造工場から組立工場へ)

6.ローカル・コンテントの制約(カナダ/アメリカ通商協定による)

7.生産コスト

a)工具準備と 整理
b)資本支出
c)残業
d)組立て

この問題は,ある自動車生産ラインを,ある工場に建設するかどうかについての肯定/否定の決定を,整数変数によって示す混合整数計画モデルとして定式化される。図表14.4.6はこのモデルの構造を示す。

マトリックスの輸送型の部分は,古典的なネットワーク型の配送問題として定式化される。このネットワークは工場,工場への自動車生産ラインの割当て,輸送, 自動車の品種別,販売地区別の需要を表わすアークにより成り立っている。整数変数は工場―自動車生産ラインでの生産を表わしており,ある整数変数が1に置かれたとき,それに対応する特定の工場―自動車生産ラインの, アークの生産の上限と下限が実現されることを保証している。

組合せ型の制約の部分は,ある組立工場に設置できる自動車生産ラインの組合せを与える方程式である。すべ ての可能な組合せでの組立てを考えたのでは,その工場にとって複雑すぎるので,ある特定の組合せだけを許すことにする。図表14.4.7に示す例は,ある工場がシボレー (CHV),ポンチャック(PON),オズモビル(OLD), ビュイック(BUK)部門に対する, 4種のA型車と4種のX型車のいずれかを作る能力を持っていることを示している。そのときの制約は,A型車とX型車は同時に 作ることはできないことと, 3つ以上の異なった自動車生産ラインを,その工場に割り当てることはできないということである。始めの4本の組合せ型制約式は,A型車のいずれかが割り当てられると(対応するA変数は 1 に置かれる),X型車を表わすすべての変数には0が置かれ,割り当てすることができない。

最初の4本の制約条件式は,またX型の変数に1つでも1がつくと,どのA型変数も1になることはできないことを保証している。この場合, これらの最初の4本の制約条件式は, A型の変数が分数値をとることを許すから,分枝限定型の混合整数計画法コードでは,たとえ0が唯一つの許容値であったとしても,A変数で枝分れすることがあり得る。その次の4本の制約条件式は, X変数のうち1つが1と置かれればもっと強い定式化となる。なぜならば,それはすべてのA変数が直ちに0となることを強制し,不必要な枝分れを取り除くからである。最後の制約式は, 3本以上の自動車生産ラインは,その工場に割り当てできないことを保証している。

典型的なCLAM問題は,150個の整数変数と8,000個の連続変数,それに3,000本の制約条件式を持ったものである。この混合整数計画問題は,商用の整数計画法パッケージには大き過ぎて,時間内に最適解を得ることはできない。IBM社のMPSX―MIPを用いて, IBM370-158で約10CPU時間をかけても,非最適の整数解しか求めることができない。

MPSX―MIPを用いて,この自動車生産ライン割当て問題の整数解を求めるときの最も重要なことは,良い枝分れ戦略を使うことを保証することである。その戦略 は,最も大きい影響を持つ整数変数から先に枝分れさせることである。最初に枝分れすべき変数は,他の整数変数の値を自動的に決めてしまうような性質のものである。これらの変数の値が決まるということは , もうその枝分れをする必要がないことを意味する良い枝分れ戦略のもう1つの重要な性質は,特定の自動車生産ラインに関連する整数変数は,連続して枝分れしないようにするということである。特定の自動車生産ラインに関連する整数変数は,枝分れ過程の中で広く散らさ れるべきであって,同じ自動車生産ラインが,あまりに 多くの工場に割り当てられると,枝分れ過程の終わりごろになって,非許容性を作り出す傾向を持つので,こ れを避けることが必要である。

MPSX―MIPによる非最適解は,自動車生産ライン割当てプロジェクトに対して,優れたコスト節約の可能性を与えた。しかし,良い整数解を得るのに要した10時間のコンピュータ時間は受け入れることができない。コンサルタントの協力により,専用の整数計画法コードを開発中である。このコード には迅速に最適解を得るために,特殊なネットワーク構造が利用されるはずである。このシステムには,すべての可能性のある自動車生産ラインー組立工場の割り当てに対する社外運搬費用(約10,000レコード )や,販売地域別自動車品種別需要予測値(約5,000レコード)を含む,膨大なデータベースを必要とする。ある特定の解析のために必要なパラメータ は,企業の生産計画部門の利用者がCRT端末を用いて投入する。このシステムは,工場立地研究や長期生産計画での自動車生産ラインの工場への割当てなどの解析に利用されている。今後の開発としては,日程計画に影響を与える他の要因やコストを含めるために,このモデルを拡張することが計画されている。

 本コラムは絶版となっている「IEハンドブック(サルベンティ編・日本能率協会訳・1986)」をアーカイブとして掲載するものです。このハンドブックの各章は多くの事例と理論を通して生産性向上に対するアイデアを提供するべく専門家によって執筆されています。基盤をなしているIEの考え方・原則はインダストリアル・エンジニアリングにかかわるすべてのひとに有用でしょう。

関連記事一覧

2019ものづくり公開セミナーガイド

B2Bデジタルマーケティングセミナー

ものづくり人材育成ソリューション

マーケティング分野オンラインセミナー