今、4台の同形状同面積のマシンを一直線上にならべたい。
この時、いくつかのレイアウト案を評価する目安となるのが
ΣD・I
である。
| D | ：Distance（運搬距離） |
| I | ：Intensity（運搬回数） |
この値が小さければ、小さいほど、運搬コストが安くなり、
またリードタイムも短くなって、効率的な運搬が行なわれていることになる。
今、下の表のように各マシン間の運搬回数が与えられている
（この表のことをfrom-to chartという）。
| From/To | 1 | 2 | 3 | 4 |
| 1 | - | 50 | 5 | 70 |
| 2 | 20 | - | 70 | 90 |
| 3 | 190 | 40 | - | 10 |
| 4 | 30 | 5 | 60 | - |
今すべての隣合うマシン同士の距離を1とすると下のようなレイアウトの場合
| ΣD・I | ＝50（マシン1から2への運搬回数）×1（マシン1、2間の運搬距離） |
| | ＋5（マシン1から3への運搬回数）×2（マシン1、3間の運搬距離） |
| | ＋…＋60（マシン4から3への運搬回数）×1（マシン3、4間の運搬距離） |
| | ＝？ |
となる。
この時、4台のマシンをΣD・Iが最小になるようにレイアウトするアルゴリズムを示せ。
またそのアルゴリズムを用いて得られる答えを明記せよ。
例えば、「全部のレイアウトの組み合わせ（4！）を列挙する」というのも、
1つのアルゴリズムだが、問題の規模が大きくなるにつれて、計算時間が莫大にかかってしまい、
あまり良いアルゴリズムとは言えない。
もっとインテリジェンスなアルゴリズムを考えてもらいたい。
|
