コラム・特集

5.5 IEでの問題解決におけるネットワーク・モデルの応用

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

第5章 ネットワーク最適化

5.5 IEでの問題解決におけるネットワーク・モデルの応用

生産計画… 一輸送問題の例
生産計画問題は輸送問題としてモデル化できる。向こう3カ月間における生産計画問題を考えてみよう各製品の生産費は12ドルである。日ごとの需要は400,700, 600単位であり,この需要は必ず満たされねばならない。工場の生産能力は500単位/月である。各月とも残業が可能である残業は月間生産量を200単位まで増やせるが,割り増し費用が3ドル/単位かかる。在庫費用は2ドル/単位/月である。問題は,「総費用を最小にするために,いかに生産計画をたてるべきか」ということである。

これを輸送問題に変換するため,供給点として生産期 間を考え,需要点として各期の市場を考える残業による生産が可能であるから, 6つの供給点がある。決定変数は,

x1j=1月の定時生産をj月に使用する量
x2j=1月の残業生産をj月に使用する量
x3j=2月の定時生産をj月に使用する量
x4j=2月の残業生産をj月に使用する量
x5j=3月の定時生産をj月に使用する量
x6j=3月の残業生産をj月に使用する量

である。

定時生産量と残業生産量の和が総需要量を超過するので,余剰の供給量を吸収するためのダミー市場を作らねばならない。図表14.5.10がこの問題に対する輸送モデルを示している。

この図の中のいくつかの要素はM(無限に大きい値)としてあり,輸送が不可能であることを示している。すなわち2月や3月の生産で, 1月の需要に応ずることはできないということである。将来の需要に応ずるために製品を在庫する場合には,生産費に2ドル/単位 /月の在庫費用を加えておくこうすればこの生産計画問題は輸送型アルゴリズムを使って解くことができる。

生産ラインの日程計画一一割り当て問題の例
異なった製品グループの生産が可能な,多製品生産ラインを考えてみよう各製品の部品は物理的な形,大きさ,重さ,成分の異なる個別の品目である。最終製品は1部品だけからなる場合もあり, 2個,あるいはそれ以上の部品から の組立品である場合もある。各製品に対する加工手順は類似しているが,異なる点もいくつかある。加工工程そのものは製品ごとにかなり違っている。各製品ごとの工程手順と,各工程の内容はYoungが示したように,工程設計部門であらかじめ設定されているものとする。

各種の製品に対する 需要計画は,生産管理部門によって,日ごと,週ごと,月ごとに設定され,生産ラインには一定数の生産工程が配置され,各工程には一定数の機械や作業ステーションが配置されている。これらの工程の一般的な配置もまた,工場レイアウト機能の一部としてすでに決められているものとする。

ある需要期間に対する生産ラインの日程計画が,選ばれた製品グループに対して作られる。このグループは,そのラインで計画されうる製品群の一部分だけのことある製品はその期間の総需要によって制限される経済的ロット によってラインに計画されねばならぬ。すなわち,各製品の1つあるいそれ以上のバッチ生産が,その需要期間中に実施されるが,その場合どのバッチもその期間の需要を超えることはできない。

まず第1に, 1つの製品から他の製品に生産ラインを段取替えするときの費用を考慮して,生産ラインで各製品の日程計画をたてるときの,最適な順序を決めることが必要となる。これらの切替え費用は,過去のデータから計算され,あるいは見積もられているものと仮定する。ある製品から他の製品への切替え費用を計算するにあたっては,工具交換や機械の段取替えのための時間を考慮して,機械や作業者の遅延時間の費用も含めて考えることが必要である。第2に,与えられた需要期間の中で,製品の全日程に対する総段取費を最小にするような,各製品の生産バッチの最適な順序を見つけることが必要である。この順序づけの最適化に,割り当て問題を利用することを検討するため,図表14.5.11に示すような切替え(段取)費用を持つ5製品の日程計画を考える。

表中の数字は製品(供給点)から製品 (需要点)へのライン切替え費用を表わしている(対角線上の1,000ドルは技巧的なもので,製品が自分自身に後続しないようにするためのものである ) 解の行列は図表14.5.12となり,最小費用の解は任意に製品1から始めたとして, 1→ 3→ 4→ 2→ 5となり費用は300ドルである。

場合によってはこの方法は,最小費用の製品順序が切替えの多重サイクルを 含むために,満足のいく解を与えないことがある(たとえば, 3-5-3, 1-4-21)。この状態が起こった場合には, もっと複雑な巡回セールスマン・アルゴリズムを使わなければならない。

投資収益率の最大化―― 最長パス解析の実例
投資家が代替投資案をもつ場合を考える。たとえば, 1年では年10%,3年では年12%,5年では年19%の債券を買うことができるとする投資家が期間を一定と考えると,問題は収益率を最大化することである。

この例では,向こう5年間での最大収益を得ることを望んでいるとする投資の流れは,図表14.5.13に示すようなネットワークの形でモデル化ができ る。ノード は問題における投資年度の始まりを表わしており,アークは投資の機会を表わしている。このようにして, 1年目の初めには1年, 3年, 5年の債券が買えるが, 2年目の初めには1年, 3年の債券しか買えない。なぜなら計画期間の5年以内には, 5年債券は満期にならないからである。ノード 5′は5年目の終わりを表わしており,投資計画の終わりである。 問題は資金の収益率を最大にするような ,ノード1から5′までの経路を見つけることである。複利で取り扱っているので,資金は1-2-5-5ら径路に沿えば(1.10)(1.12)3(1.10)の収益となる。ここではアクティビティ上の係数が加算ではなく乗算される。しかし,各収益率の対数を取れば,この径路の値はlog(1.10)+3 log(1.12)+log(1.10)となる。対数は数の大きさに従って増加するから,各アクティビティの係数の対数がと られれば,ネットワーク中での最長径路を見つけることによって,この問題を解くことができる最良の投資戦略は1年債券を続けて2回, 3年債券を1回買うことで, 69.9%の収益率が得られる。

 

容量制限のある配送システムーー最大流問題の例
ネットワーク・フロー・モデルの重要な適用例には, ほとんどLPモデルからの変換を含んでいるが,この点はハンドブックの範囲を超えているので触れない。しかしElmaghrabyは,この章で述べたようなアルゴリズムが,直接に適用できるいくつかの興味深い状況を示している。 複数個の始点S1, S2, ・・・・・ , Sπ から複数個の終点 D1,D2,・・・・・ , Dnへ品物を輸送する問題を考えよう各始点において供給可能な品物がa,単位,各終点において必要としている品物がdj単位ある。そこで輸送はある特定の径路にだけ起こり,その径路の容量は Cijであるする 問題はもし存在するなら 1ぎ,許容輸送パターンを決定することである。この種の問題で, しばしば見られる費用最小化は, ここでは考えていないことを注意しておこう。

 図表14.5.14に,このシステムのモデル化のためのネットワーク手法を表わす始点はノードS1からSmで表わし,終点はノードD1からDnで表わしている。許された径路(i, j)に対して,それぞれ,ノードSiとDjを結ぶ容量Cijを持ったアークが書かれている。

次に,総始点Sと総終点Dがフロー・ネットワークに付け加えられる。容量 aiを持つアーク S-SiはSiからの品物の供給量を与えている。各終点Djでの需要量は同様に,容量 diを持つアーク Dj-Dで与えられている。次に,このモデルに対してネットワーク・フロー法を適用する。Dヘのフローがdiの和に等しければ,この解は問題の条件を満足している。満足していなければ,許された径路を使って始点S,から終点Djへの必要な品物を輸送するのは不可能である。

割り当て問題における効率の最小レベルの最大化 一一 複合ネットワークの概念の例

最適な仕事の割り当てを求める問題で最も一般的な目的は,システムの総効率を最大化することである。しかし、ここでは,最小効率をできる限り大きくするように,仕事を割り当てることを考えてみよう。この問題を最大流 問題として扱う,最初に,任意の割り当てを作る。この割り当ての中で最小の効率を見つけて,その効率およびそれ以下の効率をもつ,すべての可能な割り当ては禁止されたものと考える。有効な割り当てだけのネットワークを作り,ネットワーク・フロー法を使って次の許容解を求める。そこでまた再び最小の効率を見つけ,それと同じか以下の効率の割り当てをそれ以降の考慮から省く。この手順がフロー法で許容な割り当てが見つからなくなるまで続けられる。最後の許容割り当てでの最低効率がこの問題の解となる。

図表14.5.15に示すような割り当て行列が与えられたとしよう。そこで次のような割り当てが任意に作られたとしよう。

J1 → P1 (10)
J2 → P5 ( 5)
J3 → P2 ( 6)
J4 → P3 ( 8)
J5 → P4 ( 4) 

この割り当てでの効率の最小レベルは4(J5→ P4)である。そこで効率4,あるいは,それ以下の割り当てをすべて除いたネットワーク・フロー・モデルを作り(図表14.5.16),その許容性を調べる。

図表14.5.16において,ノード Sは始点でありノードDは終点である。SからDへの流量は割り当てられた仕事の数を表わしている。そこでこの流量が仕事の数に等しいならば,許容な割り当てが見っかったことになる。ノード Jiと Pjはそれぞれ仕事と人とを表わしている。SからJiに至る径路と考からDに至る径路は容量 1 を持ち,おのおのの仕事はただ1回だけ割り当てられ,各作業者はただ1つの仕事をなしうるということを表わしている。すべての許容な割り当ては,適切なJi,と Pjを結ぶアークによって表わされている。たとえば目標を効率が5あるいはそれ以上の場合とすれば ,J5が結合できるのはP2だけである。

最大フロー法を適用することによって,次のよう な最大流5を見つけることができる。

J1 → P4(5)
J2 → P5(5)
J3 → P1(7)
J4 → P3(8)
J5 → P2(5)

こ のようにして許容解を得ることができ,最小効率レベ ルは5であり ,そ れは径路 J1→ P4, J2→ P5, J5→ P2 で現われている。効率が5であるすべての仕事が除かれれば,J5は割り当て不可能となり,最大流は5より小さ くなってしまう。

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

関連記事一覧

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

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

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

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