step2
技法の紹介
2-1. 問題定義

GT(グループテクノロジー)の適用は、部品群、マシン群を形成することから始まる。これは、ある部品群があるマシン群で加工される際、それ以外のマシン群との関わりが最小となることを目的とする。セルの形成(セルフォーメーション)は複雑な問題であると認識されており、いくつかの段階に分断して行われる。各段階で制限を設ける必要があり、さもなくば、問題を広げることが問題の複雑化につながり、結果として失敗を招くためである(バービッジ,1993)。バービッジらは少なくとも36の工場にGTを導入し、成功を収めているが、製品設計の変更や加工方法の変更を行っていない。これらは重要な用件ではあるものの、GTの適用と同時に行えば混乱を招くためGT適用後に行うべきであり、GTの適用の際には単純な部品群及びマシン群の形成を行われる。

部品群、マシン群の形成には部品の加工順序が利用される。一般には図2.1.似示すような部品-マシンマトリックスで表される。マトリックスは部品数P(列)×マシン数M(行)の大きさで、1と0によって表現される。ある部品pがあるマシンmで加工されるならば1、そうでなければ0で表される。このマトリックスでは、部品の工程順序は無視され、ある部品が複数回同じマシンを利用しようとしても表現されない。またマシンmはマシンの種類を表しており、各種類ごとのマシンの台数は表現されず、各々十分なキャパシティーを持っているという前提となる。

さてここで、図2.2.のように対角線上にブロック(セル)を2つ任意に形成する。これらは2つの部品群及びマシン群と対応し、部品1,2とマシン1,2が1つのセルに、部品3〜5とマシン3,4が別のセルに分けられる。このような分割が行われると、部品1,3,5は全ての工程を終えるためには2つのセルを渡り歩かなければならない。つまり"1"がブロック外にあり、これらブロックの外の"1"を"Exceptinal Element"と呼び、これらを加工するマシン1,2,3を"ボトルネック"マシンと呼ぶ。また、部品2は同じセルに割当てられたマシン1を利用しておらず、これを"0"であらわす。これら"0"は"Void"と呼ばれる。

この際の評価指標となるのが、

1.ブロック内の"0"の数:Void
2.ブロック外の"1"の数:Exceptional Element
 である。

この図2.2.の行と列を任意に入れ替えたものが図2.3.となる。前者と比較すると、ブロック内の"0"(Void)とブロック外の"1"(Exceptional Element)が少なくなっている。

VoidとExceptional Elementは、対角線上のブロックの数、大きさに依存する。一般的にはブロックの数が減ると、ブロックのサイズが大きくなる。この場合Voidが増え、Exceptional Elementが減る。例えば全ての部品とマシンが1つのセルに割当てられ、ブロックが1つになれば(セルが大きく締まりがなくなり)Voidが最大値をとり、Exceptional Elementがなくなる(アディル,ラジャマニ,ストロング,1993)。例えば図2.1.はVoidが11、Exceptional Elementが0となる。対して、ブロックが増えれば図2.3.のようにVoidが2になり、Exceptional Elementが1になる。つまり、VoidとExceptional Elementの数はトレードオフの関係にある
次に、部品-マシンマトリックスを操作するアルゴリズムをいくつか紹介する。

2-2. BEA: Bond Energy Algorithm

ボンド・エナジー・アルゴリズムは1972年、マコーミック、スキワイザー、ホワイトらが複雑なデータの配列を分割するために開発を行った。ヒューリスティック・アルゴリズム(近似解法)であり最適解の保証はないが、ステップを踏んだ解法であり実際の場で利用される手法である。マコーミック等は有効性指標(ME: Measure of Effectiveness)を提示した。MEは密度の高い集合ほど高い値を示し、配列を評価する。配列AのME(全ての行列の拘束のエネルギー(BE: Bond Energy))は次の式で表現される。

MEの最大化を評価指標とすると、

となり、次の式2.2に変換できる。

行(列)のMEは列(行)によって変化し、MEは行と列の2つの部分に分解できる。これらは、それぞれ独立に最適化することは出来ないため、マコーミックらは次に示す近似最適解の構築方法を提案した。

2-3. BEA 例題

Step1
部品の列を任意に1つ選び i = 1 とする。残りの( P ‐ 1 )コの列を各々( i + 1 )コの候補地(既に配置された i の列の左右)に配置し、MEを算出する。

最もBEの高いものを配置し(BEが同じ場合は任意に一つ選ぶ)i = i + 1 とし、i = P になるまで行う。全ての列が配置されたらStep2に進む。

Step2
マシン(行)についてStep1と同様の操作を行う。


例題1. 図2.4のマトリックスを式(2.1)、(2.2)を使って評価しなさい。

解答例

式2.1を利用したαpmを図2.5に示す。ME(A) = 1 / 2 ( 1 + 1 + 1 + 1 + 2 + 1 + 1 ) = 4 。式2.2の行と列のMEを図2.6に示す。ME (B) = ME(行) + ME(列) = ( 1 ) + ( 1 + 1 + 1 ) = 4



例題2. 図2.7のマトリックスにマコーミックらのアルゴリズムを適用し、配列換えを行え。

解答例

Step1
任意に部品の列、例えばp=1を選ぶ。残りの列を両サイドにおきMEを計算する(表2.1)。なお、既に選ばれた列はアンダーラインで示す。この中で最もMEの高い列を選ぶが、いくつか選択肢があるため、この場合(1,3)を選ぶ。さらに残りの列を配置してMEを計算する(表2.2)。(1,3,2)を選択肢、同様に残りの列を計算する(表2.3)。(1,3,2,4)を選択。その結果図2.8のようになり、Step2に進む。

Step2
Step1と同様の操作を行う。行1を選び、m=1(表2.4)。(1,4)を選択肢計算(表2.5)。(3,1,4)を選択肢(表2.6)。(3,2,1,4)か(2,3,1,4)を選び、図2.9のような結果となる。


BEAの限界
1. 最終的な解は始めに選ぶ行(列)とタイブレーク(評価関数値が同じ場合)の際の選択に強く依存する。
2. Exceptional Elementやボトルネックマシーンについては評価されていない。

2-2. BEA: Bond Energy Algorithm

ボンド・エナジー・アルゴリズムは1972年、マコーミック、スキワイザー、ホワイトらが複雑なデータの配列を分割するために開発を行った。ヒューリスティック・アルゴリズム(近似解法)であり最適解の保証はないが、ステップを踏んだ解法であり実際の場で利用される手法である。マコーミック等は有効性指標(ME: Measure of Effectiveness)を提示した。MEは密度の高い集合ほど高い値を示し、配列を評価する。配列AのME(全ての行列の拘束のエネルギー(BE: Bond Energy))は次の式で表現される。

MEの最大化を評価指標とすると、

となり、次の式2.2に変換できる。

行(列)のMEは列(行)によって変化し、MEは行と列の2つの部分に分解できる。これらは、それぞれ独立に最適化することは出来ないため、マコーミックらは次に示す近似最適解の構築方法を提案した。

2-4. ROC: Rank Order Clustering

ランク・オーダー・アルゴリズム(以下ROC)は、1980年キングによって提案された。ROCは効果的かつ効率的に問題を解く手法であり、容易に電算化が行える。部品-マシンマトリックスの各々の行(列)を二進数で表現し、これを十進数により評価、行(列)の入替えを行う。行(列)、列(行)の順で変化がなくなるまでこれを繰り返す。アルゴリズムを次に示す。

ROCアルゴリズム

Step1
行、m=1,2,………,Mについて、二進数を読み取り、十進数 に変換する。

の値に従い、行を降順に並び替える。タイブレーク(値が同じ)場合は、独自のルールに従い順序を決める。

Step2
列、p=1,2,………,Pについて、二進数を読み取り、十進数 に変換する。

の値に従い、行を降順に並び替える。タイブレーク場合は、独自のルールに従い順序を決める。

Step3
もし、部品-マシンマトリックスに変化がない様であれば終了。そうでなければStep1へ戻る。

2-5. ROC 例題

例題3. 図2.11の部品マシンマトリックスにROCを適用せよ。

解答例

Step1
十進数の評価は図2.12の右手に与えられる。降順の順位が括弧により表現される。これをもとに行を入れ替える(図2.13)。

Step2
列の順位付けが図2.13にされている。これを降順に並び替えたものが図2.14。

Step1 (2回目)
再度図2.14のマトリックスの行に順位付けを行い、降順に並び替える(図2.15)。

Step2 (2回目)
図2.15の列に順位付けを行ったが順位に代わりがない。

Step3
Step1、Step2ともに変化がないため、これで終了となる。

図2.15に対角線上のブロックを当てはめ、セル(部品群、マシン群)を形成する(図2.16、図2.17)


ROCの限界
1. 二進数で読み取る際、コンピュータの限界が生じる。現実的には1~48桁ぐらいまでが限界であり、それ以上は計算が行えなくなるため、それ以上のサイズのマトリックスを扱うことができない。
2. 結果は初期解に強く依存し、また最終的な解も最適解の保証がない。
3. マトリックスの左上方部に"1"が集まりやすくなるが、それ以外の部分に関しては、ブロックの形成度が弱い。
4. 例え、解の導き易い(ブロックが形成され易い)問題であったとしても、必ずしも最適解を導き出すわけではない。
5. ボトルネックマシンとボトルネックパーツは、設計者の任意で決めなければならない。