ファーストフィット減少ビンパッキング

ファーストフィット減少 (FFD)は、ビンパッキングのアルゴリズムです。入力は、異なるサイズのアイテムのリストです。出力はパッキングです。パッキングとは、各ビンのアイテムのサイズの合計が最大で容量以下になるように、アイテムを固定容量のビンに分割することです。理想的には、ビンの数はできるだけ少なくしたいのですが、ビンの数を最小化することは NP 困難な問題であるため、近似的に最適なヒューリスティックを使用します。

FFD アルゴリズムは次のように動作します。

• アイテムを最大から最小の順に並べます。
• 新しい空のビン（ビン #1）を開きます。
• 最大から最小までの各アイテムについて、アイテムが収まる 最初のビン（存在する場合）を見つけます。
  • そのようなビンが見つかった場合は、そこに新しいアイテムを入れます。
  • それ以外の場合は、新しい空のビンを開いて、そこに新しいアイテムを入れます。

簡単に言うと、FFD はアイテムをサイズの降順で並べ、次にファーストフィット ビン パッキングを呼び出します。

FFD アルゴリズムの同等の説明は次のとおりです。

• アイテムを最大から最小の順に並べます。
• 残りアイテムは:
  • 新しい空のビンを開きます。
  • 各項目について、最大から最小まで:
    • 現在のビンに収まる場合は、挿入します。

標準的な説明では、アイテムを 1 回ループしますが、多くのビンを開いたままにします。同等の説明では、アイテムを何度もループしますが、そのたびに 1 つのビンのみを開いたままにします。

FFD のパフォーマンスはいくつかのステップで分析されました。以下は、入力セットSに対して FFD が使用するビンの数とビン容量 C を 示しています。${\displaystyle FFD(S,C)}$

• 1973年、DSジョンソンは博士論文^[1]の中で、任意のインスタンスSと容量Cについて証明しました。${\displaystyle FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+4}$
• 1985年にBSバッカー^[2]はやや単純な証明を与え、加法定数が3以下であることを示した。
• Yue Minyi ^[3]は1991年にそれを証明し、1997年にLi Rongheng ^{[4]と共同でこの分析を改良しました。}${\displaystyle FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+1}$${\displaystyle FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+7/9}$
• 2007年にGyörgy Dósa ^[5]は厳密な境界を証明し、その例を示した。${\displaystyle FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+6/9}$${\displaystyle FFD(S,C)=11/9\mathrm {OPT} (S,C)+6/9}$

Dósa によって示された下限の例は次のとおりです。2 つのビン構成を検討します。

• ${\displaystyle B_{1}:=\{1/2+\バレプシロン ,1/4+\バレプシロン ,1/4-2\バレプシロン \}}$  ;
• ${\displaystyle B_{2}:=\{1/4+2\バレプシロン ,1/4+2\バレプシロン ,1/4-2\バレプシロン ,1/4-2\バレプシロン \}}$ 。

最適解に の コピーが 4 つ、 のコピーが 2 つある場合、FFD は次のビンを計算します。${\displaystyle B_{1}}$${\displaystyle B_{2}}$

• 4つのビン構成、${\displaystyle \{1/2+\varepsilon ,1/4+2\varepsilon \}}$
• 構成付きビン1個、${\displaystyle \{1/4+\varepsilon ,1/4+\varepsilon ,1/4+\varepsilon \}}$
• 構成付きビン1個、${\displaystyle \{1/4+\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}}$
• 構成付きビン1個、${\displaystyle \{1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}}$
• 1 構成付きの最終ビン1つ、${\displaystyle \{1/4-2\varepsilon \}}$

つまり、合計 8 つのビンがありますが、最適値には 6 つのビンしかありません。したがって、上限は厳密です。 ${\displaystyle 11/9\cdot 6+6/9=72/9=8}$

この例は、のすべてのサイズに拡張できます。^[5]最適な構成では、9 k +6 個のビンがあります。6 k +4 はタイプ B ₁で、3 k +2 はタイプ B ₂です。しかし、FFD では少なくとも 11 k +8 個のビンが必要であり、これは です。 ${\displaystyle {\text{OPT}}(S,C)}$${\displaystyle {\frac {11}{9}}(6k+4)+{\frac {6}{9}}}$

ビンパッキングの重要な特殊なケースは、アイテムのサイズが割り切れるシーケンス（因数分解とも呼ばれる）を形成する場合です。割り切れるアイテムサイズの特殊なケースは、アイテムのサイズがすべて2の累乗であるコンピュータシステムのメモリ割り当てで発生します。この場合、FFDは常に最適なパッキングを見つけます。^{[6] : Thm.2}

直感に反して、はCの単調関数ではありません。^{[7] ：図4}同様に、はS内のアイテムのサイズの単調関数ではありません。アイテムのサイズが縮小しても、ビンの数が増加する可能性があります。 ${\displaystyle FFD(S,C)}$${\displaystyle FFD(S,C)}$

しかし、FFDアルゴリズムには「漸近単調性」という特性があり、次のように定義される。^{[7] : Lem.2.1}

• あらゆるインスタンスSと整数mに対して、MinCap( S,m )を最小の容量Cとし、${\displaystyle OPT(S,C)\leq m}$
• すべての整数mについて、 MinRatio( m ) を、すべての入力セットSについて、となる数r ≥1 の最小値とします。これは、FFD が最適なビン数を達成できるようにビンを「膨張」させる必要がある量です。${\displaystyle FFD(S,r\cdot {\text{MinCap}}(S,m))\leq m}$
• すると、すべての入力Sとすべてのr ≥ MinRatio( m )に対して、となります。これは特に、上記の定義の最小値を最小値に置き換えることができることを示しています。${\displaystyle FFD(S,r\cdot {\text{MinCap}}(S,m))\leq m}$

たとえば、入力が次のとおりであるとします。

44、24、24、22、21、17、8、8、6、6。

容量 60 の FFD には 3 つのビンがパックされています。

• 44、8、8;
• 24、24、6、6;
• 22、21、17。

しかし、容量が 61 の FFD には 4 つのビンがパックされています。

• 44、17;
• 24、24、8;
• 22、21、8、6;
• 6.

これは、容量が 61 であるため、17 が最初のビンに収まり、次の 8、8 への道を塞ぐためです。

別の例として、^{[8] : 例5.1}入力が51、28、28、28、27、25、12、12、10、10、10、10、10、10、10、10、10であるとします。容量75の場合、FFDは4つのビンをパックします。

• 51、12、12
• 28、28、10
• 28、27、10、10
• 25、10、10、10、10、10、10

しかし、容量が 76 の場合、5 つのビンが必要です。

• 51、25
• 28、28、12
• 28、27、12
• 10、10、10、10、10、10、10、10
• 10

容量が 60 である上記の例を考えてみましょう。17 が 16 になると、結果のパッキングは次のようになります。

• 44、16;
• 24、24、8;
• 22、21、8、6;
• 6.

修正ファーストフィット減少法（MFFD）^[9]は、 FFDを改良して、アイテムをサイズ別に大、中、小、極小の4つのサイズクラスに分類します。これは、それぞれ、ビンの半分より大きいアイテム、ビンの1/2より大きいアイテム、ビンの1/3より大きいアイテム、ビンの1/6より大きいアイテム、ビンの1/2より小さいアイテムに対応します。その後、5つのフェーズに進みます。

1. 大きなアイテムごとに、最大から最小の順にビンを割り当てます。
2. ビンを順に進み、各ビンで、残っている中サイズのアイテムのうち最小のものが収まらない場合は、このビンをスキップします。収まる場合は、収まる最大の中サイズのアイテムを配置します。
3. 中サイズのアイテムが入っていないビンを逆方向に進めます。各ビンについて、残っている最小の 2 つの小さなアイテムが収まらない場合は、このビンをスキップします。それ以外の場合は、収まる最小の残りの小さなアイテムと最大の残りの小さなアイテムを配置します。
4. すべてのビンを順に進み、どのサイズ クラスでも残っている最小のアイテムが収まらない場合は、このビンをスキップします。それ以外の場合は、収まる最大のアイテムをこのビンに置きます。
5. FFD を使用して、残りのアイテムを新しいビンにパックします。

^{このアルゴリズムは1985年にジョンソンとガリー[9]}によって初めて研究され、 であることが証明されました。この境界は1995年にユエとチャン^[10]によって であることが証明され、改善されました。 ${\displaystyle MFFD(S,C)\leq (71/60)\mathrm {OPT} (S,C)+(31/6)}$${\displaystyle MFFD(S,C)\leq (71/60)\mathrm {OPT} (S,C)+1}$

ベストフィット減少 (BFD)は FFD と非常に似ていますが、リストがソートされた後にベストフィットビンパッキングによって処理される点が異なります。その漸近近似比は FFD と同じで、11/9 です。

• Python: prtpy パッケージには、first-fit declines の実装が含まれています。

• マルチフィット アルゴリズム- FFD をサブルーチンとして使用する同一マシン スケジューリングのアルゴリズム。