ネクストフィットビンパッキング

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

• 最初は空である現在のビンを保持します。
• アイテムが到着すると、そのアイテムが現在のビンに収まるかどうかを確認します。
  • 収まる場合はその中に入れます。
  • それ以外の場合は、現在のビンが閉じられ、新しいビンが開かれ、新しいアイテムがこの新しいビン内に配置されます。

Next-Fit は境界空間アルゴリズムです。つまり、常に 1 つの部分的に満たされたビンが開いている必要があります。このアルゴリズムは、 1973 年にDavid S. Johnsonによって博士論文^[1]で研究されました。

NextFitの実行時間は（リスト内のアイテム数）で制限されます。^[2]${\displaystyle {\mathcal {O}}(n)}$${\displaystyle n}$

NextFit で使用されるビンの数を NF(L) で表し、リスト L で可能な最適なビンの数を OPT(L) で表します。

すると、各リスト について、となります。証明の直観は次のようになります。このアルゴリズムで使用されるビンの数は、最適なビンの数の 2 倍以下です。言い換えると、2 つのビンが最大で半分しか埋まっていないということはあり得ません。なぜなら、そのような可能性があるということは、ある時点で、ちょうど 1 つのビンが最大で半分しか埋まっておらず、最大 のサイズのアイテムを収容するために新しいビンが開かれたことを意味するからです。しかし、最初のビンには少なくとも のスペースがあるため、アルゴリズムは、サイズが最大 のアイテムに対して新しいビンを開きません。ビンが を超えるアイテムで満たされるか、 を超えるサイズのアイテムが到着した場合にのみ、アルゴリズムは新しいビンを開くことができます。したがって、ビンがある場合、少なくとも 個のビンが半分以上埋まっています。したがって、 です。は最適値 の下限であるため、 となり、したがって となります。^{[3] : 74}${\displaystyle L}$${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$${\displaystyle B/2}$${\displaystyle B/2}$${\displaystyle B/2}$${\displaystyle B/2}$${\displaystyle B/2}$${\displaystyle K}$${\displaystyle K-1}$${\displaystyle \sum _{i\in I}s(i)>{\tfrac {K-1}{2}}B}$${\displaystyle {\tfrac {\sum _{i\in I}s(i)}{B}}}$${\displaystyle \mathrm {OPT} }$${\displaystyle K-1<2\mathrm {OPT} }$${\displaystyle K\leq 2\mathrm {OPT} }$

各 に対して、かつ となるリストが存在します。 ${\displaystyle N\in \mathbb {N} }$${\displaystyle L}$${\displaystyle \mathrm {OPT} (L)=N}$${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$

が成り立つリストの族は、で与えられます。このリストの最適解には、サイズ の項目を 2 つ含むビンと、サイズ の項目を含むビンが 1 つあります(つまり、ビンの合計は です)。一方、NF によって生成される解には、サイズ の項目を 1 つ含むビンと、サイズ の項目を 1 つ含むビンがあります。 ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$${\displaystyle L:=\left({\frac {1}{2}},{\frac {1}{2(N-1)}},{\frac {1}{2}},{\frac {1}{2(N-1)}},\dots ,{\frac {1}{2}},{\frac {1}{2(N-1)}}\right)}$${\displaystyle |L|=4(N-1)}$${\displaystyle N-1}$${\displaystyle 1/2}$${\displaystyle 2(N-1)}$${\displaystyle 1/2(N-1)}$${\displaystyle N}$${\displaystyle 2(N-1)}$${\displaystyle 1/2}$${\displaystyle 1/(2(N-1))}$

アイテムの最大サイズが の場合、漸近近似比は次式を満たします。 ${\displaystyle \alpha }$${\displaystyle R_{NF}^{\infty }}$

• ${\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 2}$すべてに対して;${\displaystyle \alpha \geq 1/2}$
• ${\displaystyle R_{NF}^{\infty }({\text{size}}\leq \alpha )\leq 1/(1-\alpha )}$すべてに対して。${\displaystyle \alpha \leq 1/2}$

Next-Fitはリストとその逆リストを同じ数のビンにパックします。^[4]

Next-k-Fit は Next-Fit のバリエーションですが、1 つのビンだけを開いたままにするのではなく、アルゴリズムは最後のビンを開いたままにして、アイテムが適合する最初のビンを選択します。 ${\displaystyle k}$

の場合、NkF は NF の結果と比較して改善された結果をもたらしますが、より大きい定数に増加しても、最悪の場合の動作ではアルゴリズムはそれ以上改善されません。 アルゴリズムが AlmostAnyFit アルゴリズムである場合、となります。^[1]${\displaystyle k\geq 2}$${\displaystyle k}$${\displaystyle 2}$${\displaystyle A}$${\displaystyle m=\lfloor 1/\alpha \rfloor \geq 2}$${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{N2F}^{\infty }({\text{size}}\leq \alpha )=1+1/m}$

• Next-fit-decreasing (NFD)は Next-Fit のオフライン版です。すべての入力項目を受け入れ、降順で並べ替えて Next-Fit を呼び出します。漸近近似比は 2 ではなく 1.7 未満と、はるかに優れています。