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

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

• 最初は空である、開いているビンのリストを保持します。
• 商品が到着したら、その商品が収まる 最初のビン（ある場合）を探します。
  • そのようなビンが見つかった場合、新しいアイテムはその中に配置されます。
  • それ以外の場合は、新しいビンが開かれ、その中に新しいアイテムが配置されます。

FF(L) は First-Fit で使用されるビンの数、OPT(L) はリスト L で可能な最適なビンの数を表します。FF(L) の分析はいくつかのステップで実行されました。

• FFの上限は1971年にUllman ^[1]によって初めて証明されました。${\displaystyle FF(L)\leq 1.7\mathrm {OPT} +3}$
• 1972年に、この上限はGarey、Graham、Ullman、^[2] Johnson、Demersによって改善されました。^[3]${\displaystyle FF(L)\leq 1.7\mathrm {OPT} +2}$
• ^{1976年にGarey、Graham、Johnson、Yao、Chi-Chih [4]}によってに改良され、との整式性によりと等しくなった。${\displaystyle FF(L)\leq \lceil 1.7\mathrm {OPT} \rceil }$${\displaystyle FF(L)\leq 1.7\mathrm {OPT} +0.9}$${\displaystyle FF(L)}$${\displaystyle \mathrm {OPT} }$
• ^{2010年にXiaとTan [5]}が行った次の改良では、上限が まで引き下げられました。${\displaystyle FF(L)\leq 1.7\mathrm {OPT} +0.7}$
• 最終的に、2013年に、この境界はDósaとSgallによってまで改良されました。 ^[6]彼らはまた、 がこの境界に一致する入力リストの例も提示しています。${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$${\displaystyle L}$${\displaystyle FF(L)}$

以下に証明の考え方を説明します。

漸近比が最大 2 であることの証明を次に示します。合計が 1/2 未満の FF ビンがある場合、残りのすべてのアイテムのサイズは 1/2 より大きいため、後続のすべてのビンの合計は 1/2 より大きくなります。したがって、最大 1 つを除くすべての FF ビンの合計は少なくとも 1/2 になります。すべての最適なビンの合計は最大 1 であるため、すべてのサイズの合計は最大 OPT です。したがって、FF ビンの数は最大 1+OPT/(1/2) = 2*OPT+1 です。

まず、すべてのアイテムのサイズが最大で 1/2 である特殊なケースを考えます。合計が 2/3 未満の FF ビンがある場合、残りのすべてのアイテムのサイズは 1/3 より大きくなります。サイズが最大で 1/2 であるため、後続のすべてのビン (最後のビンを除く) には少なくとも 2 つのアイテムがあり、合計は 2/3 より大きくなります。したがって、最大で 1 つを除くすべての FF ビンの合計は少なくとも 2/3 であり、FF ビンの数は最大で 2+OPT/(2/3) = 3/2*OPT+1 です。

「問題のある」アイテムとは、サイズが 1/2 より大きいアイテムです。したがって、分析を改善するために、1/2 より大きいすべてのアイテムにR のボーナスを与えましょう。アイテムの重量を、そのサイズとボーナスの合計として定義します。アイテム セットの重量を、その内容の重量の合計として定義します。

ここで、1 つのアイテム (最大 1 つを除く) を含む各 FF ビンの重みは少なくとも 1/2+R であり、2 つ以上のアイテム (最大 1 つを除く) を含む各 FF ビンの重みは 2/3 です。R=1/6 とすると、すべての FF ビンの重みは少なくとも 2/3 になります。

一方、最適梱包の各ビンの重量は最大で 1+R = 7/6 です。これは、各ビンには 1/2 より大きいアイテムが最大で 1 つあるためです。したがって、すべてのアイテムの合計重量は最大で 7/6*OPT であり、FF ビンの数は最大で 2+(7/6*OPT/(2/3)) = 7/4*OPT+2 です。

以下の証明は^{[6]から引用したものです。 : sec.1.2}入力アイテムの重みをアイテムサイズ×以下のように計算されたボーナスとして定義します。

${\displaystyle bonus(x):={\begin{cases}0&x\leq 1/6\\x/2-1/12&1/6<x<1/3\\1/12&1/3\leq x\leq 1/2\\1/3&1/2<x\end{cases}}}$

${\displaystyle 重み(x):=x+ボーナス(x)}$。

漸近近似比は、次の 2 つの主張から導かれます。

1. 最適な梱包では、各ビンの重量は最大で 17/12 になります。
2. First-Fit パッキングでは、各ビンの平均重量は少なくとも 5/6 = 10/12 になります。

したがって、漸近的には、FF パッキング内のビンの数は最大で 17/10 * OPT である必要があります。

主張1については、合計が1以下の任意の集合Bに対して、ボーナス( B )が5/12以下であること を証明すれば十分である。実際、

• Bに 1/2 より大きい項目がない場合、1/6 より大きい項目は最大で 5 つあり、それぞれのボーナスは最大で 1/12 です。
• B に1/2 より大きいアイテムがあり、[1/3,1/2] にアイテムがない場合、(1/6,1/3) には最大で 2 つのアイテムを配置できる余地があり、それらのボーナスの合計は最大で (1/2 / 2 - 1/6) = 1/12 なので、合計ボーナスは 4/12+1/12=5/12 になります。
• B に1/2 より大きいアイテムと [1/3,1/2] 内のアイテムがある場合、1/6 より大きいサイズのアイテムを配置する余地はもうないため、合計ボーナスは再び 4/12+1/12 = 5/12 になります。

したがって、 Bの重みは最大で 1+5/12 = 17/12 になります。

クレーム2については、まず1つのアイテムを持つ FFビンBを検討します。

• sum( B )<1/2 の場合、FF の仕組みにより、Bの後に処理されるすべての項目は 1/2 より大きくなければなりません (そうでない場合は、 Bに挿入されます)。したがって、sum<1/2 となる FF ビンは最大で 1 つ存在します。
• ここで、合計( B )>1/2となる単一のアイテムを含む他のすべてのビンBについて考えます。これらのすべてのビンについて、重み( B )>1/2+1/3 = 5/6となります。

ここで、2 つ以上のアイテムを含む FF ビンBについて考えます。

• sum( B )<2/3 の場合、FF の仕組みにより、Bの後に処理されるすべての項目は 1/3 より大きくなければなりません (そうでない場合は、 Bに挿入されます)。したがって、2 つ以上の項目を含む後続のビンはすべて 2/3 より大きくなります。したがって、2 つ以上の項目があり、sum<2/3 である FF ビンは最大で 1 つ存在します。
• ここで、2 つ以上のアイテムがあり、合計が 2/3 を超える他のすべてのビンについて考えます。これらを、開かれる順序で B[1]、B[2]、...B[k] と表記します。1 、...、k内の各iについて、 B[i] の合計と B[i+1] のボーナスが少なくとも 5/6 であることを証明します。つまり、合計 (B[i]) + ボーナス (B[i+1]) ≥ 5/6 です。実際、合計 (B[i]) ≥ 5/6 の場合、不等式は自明です。それ以外の場合は、合計 (B[i]) := 1 - xとします。合計 (B[i]) が 2/3 から 5/6 の間であるため、 x は1/6 から 2/6 の間であることに注意してください。B[i+1]はB[i]の後に開かれるので、B[i+1]にはB[i]に収まらない少なくとも2つの項目、たとえばc 1とc 2が含まれます。つまり、c1,c2 > 1-sum(B[i]) = x > 1/6です。この場合、c1とc2のそれぞれのボーナスは少なくともx/2 - 1/12です。したがって、B[i+1]のボーナスは少なくともx-1/6なので、sum(B[i]) + bonus(B[i+1]) ≥ (1-x)+(x-1/6) = 5/6となります。
• 上記の不等式を連続するペアに適用すると、sum(B[1]) + bonus(B[2]) + sum(B[2]) + bonus(B[3]) + ... + sum(B[k-1]) + bonus(B[k]) ≥ 5/6*(k-1) となります。

したがって、すべての FF ビンの合計重みは少なくとも 5/6*(FF - 3) になります (ここで、合計が 1/2 未満の単一の 1 項目ビン、合計が 2/3 未満の単一の 2 項目ビン、および合計が 2/3 以上の 2 項目ビンから k-1 を減算します)。

全体として、17/12*OPT ≥ 5/6*(FF-3) となり、FF ≤ 17/10*OPT+3 となります。

DósaとSgall ^[6]は、 3を取り除いたより厳密な分析を提示し、FF≤17/10*OPTとなることを明らかにした。

1.7OPTのパフォーマンス境界が厳しいインスタンスがあります。次の例は、次のものに基づいています。^{[7] [8]}ビン容量は101で、

• 順序は、6 (x7)、10 (x7)、16 (x3)、34 (x10)、51 (x10) です。
• 最適なパッキングには10 個のビンが含まれます: [51+34+16] (x3)、[51+34+10+6] (x7)。すべてのビンの合計は 101 です。
• ファーストフィットパッキングには17個のビンが含まれています: [6 (x7) + 10 (x5)], [10 (x2) + 16 (x3)], [34+34] (x5)、[51] (x10)。
  • ビンの合計は、92、68、68 (x5)、51 (x10) です。
  • 報酬（101 に正規化）は 0、0、16.8（x5）、33.7（x10）です。
  • 合計重み（101 に正規化）は、92、68、84.8（x5）、84.7（x10）です。ほぼすべての重みが 101*5/6=84.1 に近いことがわかります。

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

Refined-First-Fit（RFF）はビンパッキングのための別のオンラインアルゴリズムであり、以前に開発されたFFアルゴリズムを改良したものである。これはAndrew Chi-Chih Yaoによって発表された。^[10]

アイテムは、サイズに応じて 4 つのクラスに分類されます (ビンの容量は 1 です)。

• ${\displaystyle A}$-ピース-サイズインチ。${\displaystyle (1/2,1]}$
• ${\displaystyle B_{1}}$-ピース-サイズインチ。${\displaystyle (2/5,1/2]}$
• ${\displaystyle B_{2}}$-ピース-サイズインチ。${\displaystyle (1/3,2/5]}$
• ${\displaystyle X}$-ピース-サイズインチ。${\displaystyle (0,1/3]}$

同様に、ビンは 1、2、3、4 の 4 つのクラスに分類されます。

を固定整数とします。次の項目は、次のビンに割り当てられます。 ${\displaystyle m\in \{6,7,8,9\}}$${\displaystyle i\in L}$

• クラス1、が- ピースの場合、${\displaystyle i}$${\displaystyle A}$
• クラス2、が - ピースの場合、${\displaystyle i}$${\displaystyle B_{1}}$
• クラス 3、任意の整数に対して、 が -ピースであるが、これまでに見た番目の-ピースではない場合。${\displaystyle i}$${\displaystyle B_{2}}$${\displaystyle (mk)}$${\displaystyle B_{2}}$${\displaystyle k\geq 1}$
• クラス1、 がこれまでに見た番目の作品である場合、${\displaystyle i}$${\displaystyle (mk)}$${\displaystyle B_{2}}$
• クラス 4、が - ピースの場合。${\displaystyle i}$${\displaystyle X}$

アイテムのクラスが選択されると、ファーストフィットビンパッキングを使用してそのクラスのビン内に配置されます。

RFF は、現在のアイテムが (別のクラスの) 開いているビン内に収まるにもかかわらず、新しいビンを開く可能性があるため、Any-Fit アルゴリズムではないことに注意してください。

RFFは の近似保証を持つ。に対してとなるリストの族が存在する。^[10]${\displaystyle RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5}$${\displaystyle L_{k}}$${\displaystyle RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3}$${\displaystyle \mathrm {OPT} (L)=6k+1}$

• First-Fit-Decreasing (FFD)は、First-Fit のオフライン版です。すべての入力項目を受け入れ、降順で並べ替えて、First-Fit を呼び出します。漸近近似比ははるかに優れており、1.7 ではなく約 1.222 です。

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