1

1D ビン パッキング問題の解決に取り組んでおり、初期集団として、MBS のジェネレーター パーティクルから始めます。MBS' (最小ビン スラック) アルゴリズムをネットで探していましたが、見つかりませんでした。誰か助けてください。

4

1 に答える 1

1

MBS は、次の手順に基づくMBS ( Minimum Bin Slack ) ヒューリスティックの改善です。

  • 各ステップで、ビンの容量にできるだけ適合するアイテムのセット (梱包) を見つけようとします。
  • この意味で、MBS は組立ラインのバランシング問題を解決するためのホフマンのアルゴリズムに似ています。
  • 各段階で、これまでビンに割り当てられていない n' 個のアイテムのリスト I' が、サイズの降順でソートされて保持されます。
  • パッキングが決定されるたびに、関連するアイテムがビンに配置され、ソート順を維持して I' から削除されます。
  • プロセスは I'= I で始まり、リスト I' が空になると終了します。
  • 各パッキングは、ビンの容量に最大限に適合するリストＩ'上のアイテムのすべての可能なサブセットをテストする検索手順で決定される。
  • 最小のスラックを残すサブセットが採用されます。アルゴリズムがビンを完全に埋めるサブセットを見つけた場合、検索は中止され、この状態ではこれ以上のパッキングはできません。
  • 検索は、より大きなサイズのアイテムから、つまり I' の先頭から開始されます。これは、比較的大きなサイズのアイテムは通常、ビンに詰めるのが難しいため、最初にそれらを詰める試みを行う必要があるためです。

【MBSアルゴリズム】 http://i.stack.imgur.com/jUltR.png

MBS' :

  • アルゴリズムを高速化する初期化手順を使用することを除いて、MBS と同じです。
  • MBS に対する次の変更が提案されています。1 パッキング検索手順が呼び出される前に、アイテム (シード) が選択され、パッキングに永続的に固定されます。
  • とにかくすべてのアイテムをビンに入れる必要があるため、これを行うことができます。
  • シードの適切な選択は、最大サイズの項目、つまりリスト Z' の最初の項目です。
  • これにより、検索中に埋めるビン内のスペースが最小になり、処理時間が短縮されます。
  • さらに、解決プロセスは、より大きなアイテムを使用することを余儀なくされ、そのため、よりトラブルの原因となるアイテムを最初に使用することになります。
于 2013-07-25T13:54:24.580 に答える