1次元Bin Packingアルゴリズムを活用した作業配分最適化_2.アルゴリズム(2)

2.6。アイテムサイズで降順ソートを適用する

これまで、Next Fit、First Fit、Worst Fit、Best Fitの各アルゴリズムの動作方法と実行結果を見てきました。入力データのサイズが一定の順序で並べられていない状態でランダムな順序で処理されるときと並べられた状態での処理は結果が異なります。サイズの大きいアイテムを最初に埋めることは一般的に良い結果が得られるので、アイテムのサイズで最初に降順に並べ替えて処理する方法を考えてみることができる。

まず、入力資料とこれを降順に並べた資料は次の通りである。

#入力データ26 57 18 8 45 16 22 29 5 11 8 27 54 13 17 21 63 14 16 45 6 32 57 24 18 27 54 35 12 43 36 9 26 41 15 41 68

#降順ソート入力データ72 68 63 59 57 57 54 54 46 45 45 43 42 41 41 36 35 32 29 28 27 27 27 26 26 24 22 4 4 13 12 11 11 8 8 6 5 3

降順にソートした資料を入力で各アルゴリズムを実行した結果を見てみよう。

2.7。降順ソートを適用したNext Fit

全空間は1,840（Bin一つ当たりサイズ80*Bin個数23）であり、残余空間合計は488で空間非効率は約26.52%（488/1,840）である。

2.8。降順ソートを適用した First Fit

全空間は1,440（Bin一つ当たりサイズ80*Bin個数18）であり、残余空間合計は88で空間非効率は約6.11%（88/1,440）である。

2.9。降順ソートを適用したワーストフィット

全空間は1,440（Bin一つ当たりサイズ80*Bin個数18）であり、残余空間合計は88で空間非効率は約6.11%（88/1,440）である。

2.10。降順ソートを適用したベストフィット

全空間は1,440（Bin一つ当たりサイズ80*Bin個数18）であり、残余空間合計は88で空間非効率は約6.11%（88/1,440）である。

2.11。アルゴリズム適用結果の比較

 上記のケースで最も非効率の大きいNext Fitを除いて、First Fit、Worst Fit、Best Fitの残余空間合計と空間非効率の両方が同じ結果が出ており、各Binに充填されたitemは互いに異なって構成された。

参考までに、同じ結果が出たのは、このケースの入力データと制約事項に基づいて発生した偶然です。入力データと制約事項が異なると、残余空間合計と空間非効率、Binのitem構成リストなどは互いに異なることがある。

ソートしていない結果とソートした結果を比較すると、次のようになります。

▼ Next Fit

▼ First Fit

▼ワーストフィット

▼Best Fit

以下は、各アルゴリズムの実行で計算された定量的情報です。

アルゴリズム	アイテム	ソート前	ソート後	比較
Next Fit	比較回数	44	44	変化なし
	全空間	1,840	1,840
	残余空間合計	488	488
	空間非効率	26.525	26.525
First Fit	比較回数	330	448	比較回数は増えましたが、空間非効率が減少して改善されました
	全空間	1,520	1,440
	残余空間合計	168	88
	空間非効率	11.05%	6.11%
ワーストフィット	比較回数	465	643
	全空間	1,680	1,440
	残余空間合計	328	88
	空間非効率	19.52%	6.11%
ベストフィット	比較回数	428	643
	全空間	1,520	1,440
	残余空間合計	168	88
	空間非効率	11.05%	6.11%

上表の比較回数は、次に紹介するExcel VBAベースのツールでおおよその測定した数値です。上記を見ると、itemのサイズに降順順に並べた後、Bin Packingを実行した結果が空間非効率が減少し、より細かく埋められたことが確認できる。これにより、最初にソートしてアルゴリズムを適用すると、より最適化された結果が得られることがわかります。

いつもBest Fitが最適とは言えません。各アルゴリズムの実行結果を検討し、その時の状況に合った最適な結果を選択することが望ましい。

---

ここまでBin Packingアルゴリズムについて詳しく見てきました。次に、このアルゴリズムを実装したツールについて見ていきます。

---

<< 関連記事のリスト >>

• 1次元Bin Packingアルゴリズムを活用した作業配分の最適化_1.概要
• 1次元Bin Packingアルゴリズムを活用した作業配分最適化_2.アルゴリズム(1)
• 1次元Bin Packingアルゴリズムを活用した作業配分最適化_2.アルゴリズム(2)
• 1次元Bin Packingアルゴリズムを活用した作業配分最適化_3.実装(1)
• 1次元Bin Packingアルゴリズムを活用した作業配分最適化_3.実装(2)
• 1次元Bin Packingアルゴリズムを活用した作業配分の最適化_4。
• 1次元Bin Packingツール最近の変更（2021-03-21基準）
• 1次元Bin Packingアルゴリズムを活用した作業配分最適化ツール