ビンパッキング問題

ビンパッキング問題^{[1] [2] [3] [4]}は最適化問題であり、異なるサイズのアイテムを、それぞれ一定の容量を持つ有限個のビンまたはコンテナに、使用するビンの数を最小限に抑える方法で詰め込む必要があります。この問題は、コンテナをいっぱいにする、重量容量の制約があるトラックに荷物を積み込む、メディアにファイルのバックアップを作成する、ネットワークプレフィックスを複数のサブネットに分割する、^{[5] 、} FPGA 半導体チップ設計 におけるテクノロジマッピングなど、多くの用途があります。

計算上、この問題はNP 困難であり、対応する決定問題、つまりアイテムが指定された数のビンに収まるかどうかを決定する問題はNP 完全である。最悪のケースの困難さにもかかわらず、この問題の非常に大きなインスタンスに対する最適解は、洗練されたアルゴリズムで生成することができる。さらに、多くの近似アルゴリズムが存在する。たとえば、ファーストフィットアルゴリズムは、各アイテムをそれが収まる最初のビンに配置するという、高速だがしばしば最適ではない解を提供する。これにはΘ ( n  log  n ) 時間が必要であり、nはパックするアイテムの数である。最初にアイテムのリストを降順に並べ替える(ファーストフィット減少アルゴリズムと呼ばれることもある) ことで、アルゴリズムをはるかに効率的にすることができるが、それでも最適な解が保証されるわけではなく、リストが長いとアルゴリズムの実行時間が長くなる可能性がある。ただし、ファーストフィットが最適解を生成できるアイテムの順序が少なくとも 1 つは常に存在することがわかっている。^[6]

この問題には、2D パッキング、線形パッキング、重量によるパッキング、コストによるパッキングなど、さまざまなバリエーションがあります。ビンパッキング問題は、カッティングストック問題の特殊なケースと見ることもできます。ビンの数が 1 に制限され、各アイテムが体積と値の両方で特徴付けられている場合、ビンに収まるアイテムの価値を最大化する問題は、ナップザック問題として知られています。

実際に発生するビンパッキングのバリエーションは、アイテムがビンにパックされるときにスペースを共有できる場合です。具体的には、アイテムのセットを一緒にパックすると、個々のサイズの合計よりも少ないスペースを占める可能性があります。このバリエーションは、^仮想マシン(VM) がサーバーにパックされると、VM によって共有され、一度だけ保存する必要があるページのために、VM の合計メモリ要件が減少するため、VM パッキング [7] として知られています。アイテムが任意の方法でスペースを共有できる場合、ビンパッキング問題は近似することさえ困難です。ただし、仮想マシンでのメモリ共有の場合のように、スペース共有が階層に適合する場合は、ビンパッキング問題を効率的に近似できます。

実際に興味深いビンパッキングの別のバリエーションは、いわゆるオンラインビンパッキングです。ここでは、異なる容量のアイテムが順番に到着することになっており、意思決定者は現在観察しているアイテムを選択してパッキングするか、そうでなければそのままにするかを決定する必要があります。各決定はリコールされません。対照的に、オフラインビンパッキングでは、追加のアイテムが到着したときにより良いパッキングが実現されることを期待してアイテムを再配置できます。もちろん、再配置するアイテムを保管するための追加のストレージが必要です。

Computers and Intractability ^{[8] : 226}でGareyとJohnsonは参考文献[SR1]の下にビンパッキング問題を挙げている。彼らはその決定変種を次のように定義している。

インスタンス: アイテムの有限集合、それぞれのサイズ、正の整数のビン容量、および正の整数。 ${\displaystyle I}$${\displaystyle s(i)\in \mathbb {Z} ^{+}}$${\displaystyle i\in I}$${\displaystyle B}$${\displaystyle K}$

質問:を、各項目のサイズの合計が以下となるような、互いに素な集合に分割することはできますか? ${\displaystyle I}$ ${\displaystyle I_{1},\dots ,I_{K}}$${\displaystyle I_{j}}$${\displaystyle B}$

文献では、各 に対しておよび となる同等の表記法がしばしば使用されていることに注意してください。さらに、研究では主に の可能な限り小さい値を求める最適化バリアントに関心があります。が最小である場合、ソリューションは最適です。アイテムのセットに対する最適ソリューションの -値は、アイテムのセットがコンテキストから明らかな場合は または単にで表されます。${\displaystyle B=1}$${\displaystyle s(i)\in \mathbb {Q} \cap (0,1]}$${\displaystyle i\in I}$${\displaystyle K}$${\displaystyle K}$${\displaystyle K}$${\displaystyle I}$${\displaystyle \mathrm {OPT} (I)}$${\displaystyle \mathrm {OPT} }$

この問題の 可能な整数線形計画法の定式化は次のようになります。

ここで、if binが使用され、itemがif binに格納される。^[9]${\displaystyle y_{j}=1}$${\displaystyle j}$${\displaystyle x_{ij}=1}$${\displaystyle i}$${\displaystyle j}$

ビンパッキング問題は強くNP完全である。これは強くNP完全な3分割問題をビンパッキングに還元することで証明できる。^[8]

さらに、でない限り、絶対近似比が より小さい近似アルゴリズムは存在しません。これは、分割問題からの還元によって証明できます。^[10]すべての入力数の合計が である Partition のインスタンスが与えられた場合、ビンサイズがTであるビンパッキングのインスタンスを構築します。入力の均等分割が存在する場合、最適なパッキングには 2 つのビンが必要です。したがって、近似比が より小さいすべてのアルゴリズムは、${\displaystyle {\tfrac {3}{2}}}$${\displaystyle {\mathsf {P}}={\mathsf {NP}}}$${\displaystyle 2T}$3/2⁠ は3 未満のビンを返す必要があり、2 つのビンである必要があります。対照的に、入力が均等に分割されていない場合は、最適なパッキングには少なくとも 3 つのビンが必要です。

一方、ビンパッキングは、ビンの数Kが固定されていれば擬似多項式時間で解くことができ、ビンの容量Bが固定されていれば多項式時間で解くことができる。^[8]

近似アルゴリズムの性能を測定するために、文献では2つの近似比が考慮されています。与えられた項目のリストに対して、数はアルゴリズムがリストに適用されたときに使用されるビンの数を示し、数はこのリストの最適な数を示します。アルゴリズムの絶対的な最悪の場合の性能比は次のように定義されます。 ${\displaystyle L}$${\displaystyle A(L)}$${\displaystyle A}$${\displaystyle L}$${\displaystyle \mathrm {OPT} (L)}$${\displaystyle R_{A}}$${\displaystyle A}$

${\displaystyle R_{A}\equiv \inf\{r\geq 1:A(L)/\mathrm {OPT} (L)\leq r{\text{すべてのリスト}}L\}に対して。}$

一方、漸近的最悪ケース比は次のように定義される。 ${\displaystyle R_{A}^{\infty }}$

${\displaystyle R_{A}^{\infty }\equiv \inf\{r\geq 1:\exists N>0,A(L)/\mathrm {OPT} (L)\leq r{\text{ すべてのリスト }}L{\text{ で }}\mathrm {OPT} (L)\geq N\} が存在する。}$

同様に、定数Kが存在し、すべてのリストLに対して次の式を満たす最小の数である: ^[4]${\displaystyle R_{A}^{\infty }}$

${\displaystyle A(L)\leq R_{A}^{\infty }\cdot \mathrm {OPT} (L)+K}$。

さらに、すべての項目のサイズが最大 であるリストのみに制限することもできます。このようなリストの場合、制限されたサイズのパフォーマンス比は およびと表されます。 ${\displaystyle \alpha}$${\displaystyle R_{A}({\text{size}}\leq \alpha )}$${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )}$

ビンパッキングの近似アルゴリズムは、次の 2 つのカテゴリに分類できます。

1. オンライン ヒューリスティック。指定された順序でアイテムを検討し、ビン内に 1 つずつ配置します。これらのヒューリスティックは、この問題のオフライン バージョンにも適用できます。
2. オフライン ヒューリスティック。アイテムをサイズ順に並べ替えるなどして、指定されたアイテムのリストを変更します。これらのアルゴリズムは、この問題のオンライン版には適用できなくなりました。ただし、時間計算量が小さいという利点は維持しながら、近似値の保証が向上しています。オフライン ヒューリスティックのサブカテゴリは、漸近近似スキームです。これらのアルゴリズムは、に依存する可能性のある定数に対して という形式の近似値の保証を備えています。 が任意に大きい場合、これらのアルゴリズムは に任意に近づきます。ただし、これにはヒューリスティックなアプローチと比較して、時間計算量が (大幅に) 増加するという代償が伴います。${\displaystyle (1+\varepsilon )\mathrm {OPT} (L)+C}$${\displaystyle 1/\varepsilon }$${\displaystyle \mathrm {OPT} (L)}$${\displaystyle \mathrm {OPT} (L)}$

ビンパッキング問題のオンライン版では、アイテムが次々に到着し、次のアイテムが何であるか、あるいはさらに別のアイテムがあるかどうかを知る前に、アイテムをどこに置くかという（不可逆な）決定を下さなければなりません。ビンパッキングに関するオフラインおよびオンラインの多様なヒューリスティックは、David S. Johnsonによって博士論文で研究されています。^[11]

次の一般的なスキームを使用する単純なアルゴリズムは多数あります。

• 入力リスト内の各項目について:
  1. アイテムが現在開いているビンの 1 つに収まる場合は、これらのビンの 1 つに配置します。
  2. それ以外の場合は、新しいビンを開いて、そこに新しいアイテムを入れます。

アルゴリズムは、ステップ 1 で新しいアイテムのオープン ビンを選択する基準が異なります (詳細については、リンクされたページを参照してください)。

• Next Fit (NF) は常に 1 つの開いたビンを保持します。新しいアイテムがそのビンに収まらない場合、現在のビンを閉じて新しいビンを開きます。その利点は、メモリ内に 1 つの開いたビンのみを保持する必要があるため、境界スペース アルゴリズムであることです。その欠点は、漸近近似比が 2 であることです。特に、、およびそれぞれに対して、およびとなるリストL が存在します。 ^[11]その漸近近似比は、アイテムのサイズに基づいていくらか改善できます。すべてに対して、およびすべてに対してです。AnyFit アルゴリズムである各アルゴリズムAに対して、 が成り立ちます。${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$${\displaystyle N\in \mathbb {N} }$${\displaystyle \mathrm {OPT} (L)=N}$${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$${\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}$${\displaystyle R_{A}^{\infty }({\text{size}}\leq \alpha )\leq R_{NF}^{\infty }({\text{size}}\leq \alpha )}$
• Next-k-Fit (NkF)は Next-Fit の変形ですが、1 つのビンだけを開いたままにするのではなく、最後のk個のビンを開いたままにして、アイテムが収まる最初のビンを選択します。そのため、k 制限空間アルゴリズムと呼ばれます。 [ 12 ^] NkF は NF の結果と比較して改善された結果をもたらしますが、 k を2より大きい定数に、最悪の場合の動作ではアルゴリズムはそれ以上改善されません。アルゴリズム A が AlmostAnyFit アルゴリズムである場合、 . [11 ^]${\displaystyle k\geq 2}$${\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}$
• ファーストフィット（FF）は、すべてのビンを、開かれた順に開いたままにします。新しいアイテムを、それが収まる最初のビンに配置しようとします。その近似比は でありに入力リストの族Lがあります。 ^[13]${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$${\displaystyle FF(L)}$
• ベストフィット （BF）も、すべてのビンを開いたままにしておきます。ただし、新しいアイテムをそれぞれ、それが収まる最大の負荷でビンに配置しようとします。その近似率はFFと同じです。つまりこの境界に入力リストの族Lがあります。 ^[14]${\displaystyle BF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$${\displaystyle BF(L)}$
• ワーストフィット（WF）は、各新しいアイテムを最小負荷でビンに入れようとします。これは、ネクストフィットと同じくらい悪い動作をする可能性があり、その最悪のケースのリストでそうするでしょう。さらに、それは成り立ちます。WFはAnyFitアルゴリズムなので、となるAnyFitアルゴリズムが存在します。^[11]${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$${\displaystyle R_{WF}^{\infty }({\text{size}}\leq \alpha )=R_{NF}^{\infty }({\text{size}}\leq \alpha )}$${\displaystyle R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )}$
• ほぼ最悪適合（AWF）は、各新しいアイテムを2番目に空いているオープンビン（または、そのようなビンが2つある場合は最も空いているビン）に配置しようとします。それが収まらない場合は、最も空いているビンを試します。漸近的な最悪ケース比はです。^[11]${\displaystyle {\tfrac {17}{10}}}$

これらの結果を一般化するために、ジョンソンは、any-fitアルゴリズムとalmost-any-fitアルゴリズムと呼ばれる2つのオンラインヒューリスティックスを導入しました。^{[4] : 470}

• AnyFit (AF)アルゴリズムでは、現在の空でないビンがB ₁、...、B _jの場合、現在のアイテムは、B ₁、...、B _jのいずれにも収まらない場合を除き、B _{j +1}にパックされません。FF、WF、BF、および AWF アルゴリズムはこの条件を満たします。ジョンソンは、任意の AnyFit アルゴリズム A および任意の について、次のことを証明しました。 ${\displaystyle \alpha }$

  ${\displaystyle R_{FF}^{\infty }(\alpha )\leq R_{A}^{\infty }(\alpha )\leq R_{WF}^{\infty }(\alpha )}$。

• AlmostAnyFit (AAF)アルゴリズムでは、現在の空でないビンがB ₁、...、B _jであり、これらのビンのうちB _{k が}最小の負荷を持つ唯一のビンである場合、現在のアイテムは、その左側のどのビンにも収まらない場合を除き、 B _kにパックされません。FF、BF、および AWF アルゴリズムはこの条件を満たしますが、 WF は満たしません。ジョンソンは、任意の AAF アルゴリズム A および任意のαについて、次のことを証明しました。

  ${\displaystyle R_{A}^{\infty }(\alpha )=R_{FF}^{\infty }(\alpha )}$ 特に：。${\displaystyle R_{A}^{\infty }=1.7}$

AnyFit 以外のヒューリスティックを使用すると、より近似比率を高めることができます。これらのヒューリスティックでは通常、さまざまなサイズ範囲のアイテム専用のオープン ビンのクラスがいくつか保持されます (詳細については、リンクされたページを参照してください)。

• 洗練されたファーストフィットビンパッキング（RFF）は、アイテムのサイズを、、、 の。同様に、ビンは 4 つのクラスに分類されます。次のアイテムは、まず対応するクラスに割り当てられます。そのクラス内で、ファーストフィット を使用してビンに割り当てられます。このアルゴリズムは、現在のアイテムが開いているビンに収まるにもかかわらず、新しいビンを開く可能性があるため、Any-Fit アルゴリズムではないことに注意してください。このアルゴリズムは、Andrew Chi-Chih Yao ^[15]によって初めて発表されました。彼は、 の近似保証があることを証明しに対してのリストの族を発表しました。${\displaystyle \left({\frac {1}{2}},1\right]}$${\displaystyle \left({\frac {2}{5}},{\frac {1}{2}}\right]}$${\displaystyle \left({\frac {1}{3}},{\frac {2}{5}}\right]}$${\displaystyle \left(0,{\frac {1}{3}}\right]}$${\displaystyle i\in L}$${\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}$
• 調和 k は、調和数列に基づいてサイズの区間を および となる部分に分割します。このアルゴリズムは、Lee と Lee によって初めて説明されました。 ^[16] 時間計算量は でありアイテムを配置するために使用できるオープンビンは最大でk 個あります。つまり、これはk制限空間アルゴリズムです。 の場合、その近似比は を満たし、漸近的にタイトです。${\displaystyle (0,1]}$${\displaystyle k-1}$${\displaystyle I_{j}:=\left({\frac {1}{j+1}},{\frac {1}{j}}\right]}$${\displaystyle 1\leq j<k}$${\displaystyle I_{k}:=\left(0,{\frac {1}{k}}\right]}$${\displaystyle \bigcup _{j=1}^{k}I_{j}=(0,1]}$${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$${\displaystyle k\rightarrow \infty }$${\displaystyle R_{Hk}^{\infty }\approx 1.6910}$
• Refined-harmonic は、 Harmonic-k のアイデアとRefined-First-Fitのアイデアを組み合わせたものです。Refined-First-Fit と同様に より大きいアイテムを配置し、小さいアイテムは Harmonic-k を使用して配置します。この戦略の直感は、 よりもちょうど大きいピースを含むビンの膨大な無駄を減らすことです。このアルゴリズムは、Lee と Lee によって初めて説明されました。 ^[16]彼らは に対してが成り立つ ことを証明しました。${\displaystyle {\tfrac {1}{3}}}$${\displaystyle {\tfrac {1}{2}}}$${\displaystyle k=20}$${\displaystyle R_{RH}^{\infty }\leq 373/228}$

ヤオ^[15]は1980年に漸近的競争比率が より小さいオンラインアルゴリズムは存在しないことを証明した。ブラウン^[17]とリアン^[18]はこの境界を次のように改良した。${\displaystyle {\tfrac {3}{2}}}$1.536 35。その後、この境界は次のように改善された。1.540 14 by Vliet. ^[19] 2012年に、この下限値はBékésiとGalambos ^[20]によって再び改善され、となった。 ${\displaystyle {\tfrac {248}{161}}\approx 1.54037}$

ビンパッキングのオフライン バージョンでは、アルゴリズムはビンへの配置を開始する前にすべてのアイテムを確認できます。これにより、近似率が向上します。

オフライン近似スキームで使用される最も単純な手法は次のとおりです。

• 入力リストをサイズの降順で並べ替えます。
• 順序付けられたリストに対してオンライン アルゴリズムを実行します。

ジョンソン^[11]は、降順リスト上で実行される任意のAnyFitスキームAは、漸近近似比が

${\displaystyle 1.22\approx {\frac {11}{9}}\leq R_{A}^{\infty }\leq {\frac {5}{4}}=1.25}$。

このファミリーの一部のメソッドは次のとおりです (詳細についてはリンクされたページを参照してください)。

• ファーストフィット減少法（FFD）は、アイテムをサイズの降順で並べ、次にファーストフィットを呼び出します。その近似比は であり、これは厳密です。 ^[23]${\displaystyle FFD(I)={\frac {11}{9}}\mathrm {OPT} (I)+{\frac {6}{9}}}$
• Next-fit-decreasing (NFD)は、アイテムをサイズの降順で並べ替えてからNext-Fitを呼び出します。その近似比率は、最悪の場合でも1.7よりわずかに小さくなります。 ^[24]また、確率的に分析されています。 ^[25] Next-Fitは、リストとその逆を同じ数のビンにパックします。したがって、Next-Fit-IncreasingはNext-Fit-Decreasingと同じパフォーマンスを発揮します。 ^[26]
• 修正ファーストフィット減少法（MFFD）^[27]は、FFDを改良したもので、アイテムをサイズによって大、中、小、極小の4つのサイズクラスに分類し、それぞれサイズが1/2ビン超、1/3ビン超、1/6ビン超、およびそれより小さいアイテムに対応させます。その近似保証はです。 ^[28]${\displaystyle MFFD(I)\leq {\frac {71}{60}}\mathrm {OPT} (I)+1}$

Fernandez de la Vega と Lueker ^[29]はビンパッキングのPTAS を発表しました。 あらゆる に対して、彼らのアルゴリズムは最大でサイズが である解を見つけ、 の時間で実行されます 。ここで、は のみに依存する関数を表します。 このアルゴリズムのために、彼らは適応入力丸めの方法を発明しました。入力数値はグループ化され、各グループの最大値に切り上げられます。 これにより、異なるサイズの少数のインスタンスが生成され、構成線形計画法を使用して正確に解くことができます。^[30]${\displaystyle \varepsilon >0}$${\displaystyle (1+\varepsilon )\mathrm {OPT} +1}$${\displaystyle {\mathcal {O}}(n\log(1/\varepsilon ))+{\mathcal {O}}_{\varepsilon }(1)}$${\displaystyle {\mathcal {O}}_{\varepsilon }(1)}$${\displaystyle 1/\varepsilon }$

Karmarkar -Karp ビン パッキング アルゴリズムは、最大で のサイズのソリューションを見つけ、 nの多項式時間で実行されます(多項式の次数は高く、少なくとも 8 です)。 ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log ^{2}(\mathrm {OPT} ))}$

Rothvoss ^[31]は、最大でビン数を持つ解を生成するアルゴリズムを提示した。 ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} )\cdot \log \log(\mathrm {OPT} ))}$

HobergとRothvoss ^[32]はこのアルゴリズムを改良し、最大でビン数nの解を生成できるようにした。このアルゴリズムはランダム化されており、実行時間はnの多項式である。 ${\displaystyle \mathrm {OPT} +{\mathcal {O}}(\log(\mathrm {OPT} ))}$

MartelloとToth ^[34]は、 1次元ビンパッキング問題に対するMTPと呼ばれる正確なアルゴリズムを開発した。より高速な代替案は、2002年にKorf ^[35]によって提案され、後に改良されたビン補完アルゴリズムである。^[36]

2013年にシュライバーとコルフはさらなる改良を発表しました。^[37]新しい改良ビン補完アルゴリズムは、100個のアイテムを持つ非自明な問題ではビン補完よりも最大5桁高速であることが示されており、最適解が20個未満のビンを持つ問題ではベロフとシェイトハウアーによるBCP（branch-and-cut-and-price）アルゴリズムよりも優れています。どのアルゴリズムが最もよく機能するかは、アイテム数、最適なビン数、最適解の未使用スペース、値の精度などの問題の特性によって異なります。

ビンパッキングの特殊なケースは、異なるアイテムのサイズが少数d個ある場合です。各サイズには、多くの異なるアイテムが存在する可能性があります。このケースは、高多重度ビンパッキングとも呼ばれ、一般的な問題よりも効率的なアルゴリズムが許容されます。

断片化を伴うビンパッキングまたは断片化可能なオブジェクトビンパッキングは、ビンパッキング問題の変形であり、アイテムをパーツに分割し、各パーツを別々に別のビンに配置することができます。アイテムをパーツに分割すると、ビンの総数を最小限に抑えるなど、全体的なパフォーマンスを向上させることができます。さらに、最適化変数の一部が連続的になるため、最適なスケジュールを見つける計算問題が容易になる可能性があります。一方、アイテムを分割するとコストがかかる場合があります。この問題は、Mandal、Chakrabary、Ghose によって最初に導入されました。^[38]

この問題には主に 2 つの種類があります。

1. 最初のバリエーションは、サイズが増加するフラグメンテーションによるビンパッキング( BP-SIF ) と呼ばれ、各項目が断片化される可能性があり、オーバーヘッド ユニットが各フラグメントのサイズに追加されます。
2. 2 番目のバリエーションは、サイズ保存フラグメンテーションによるビンパッキング( BP-SPF ) と呼ばれ、各アイテムにはサイズとコストがあります。アイテムをフラグメント化するとコストは増加しますが、サイズは変わりません。

Mandal、Chakrabary、Ghose ^[38]はBP-SPFがNP困難であることを証明した。

MenakermanとRom ^[39]は、BP-SIFとBP-SPFはどちらもNP困難であることを示した。困難であるにもかかわらず、彼らはいくつかのアルゴリズムを提示し、その性能を調査している。彼らのアルゴリズムは、 next-fitやfirst-fit declineingのようなビンパッキングの古典的なアルゴリズムを基礎として使用している。

Bertazzi、Golden、Wang ^[40]は、分割ルールを備えたBP-SIFの変種を導入しました。これは、アイテムをそのサイズに応じて1つの方法でのみ分割できるというものです。これは、たとえば、車両ルーティング問題に役立ちます。彼らの論文では、この変種の最悪の場合のパフォーマンス境界を示しています。 ${\displaystyle 1-x}$

Shachnai、Tamir、Yehezkeli ^[41]は、BP-SIFとBP-SPFの近似スキームを開発しました。デュアルPTAS（問題のデュアルバージョン用のPTAS）、APTASと呼ばれる漸近PTAS、および両方のバージョン用のAFPTASと呼ばれるデュアル漸近FPTASです。

Ekici ^[42]は、いくつかの項目が競合し、競合する項目のフラグメントを同じビンに詰め込むことを禁止するBP-SPFの変種を導入した。彼らは、この変種もNP困難であることを証明した。

CassazzaとCeselli ^[43]は、コストとオーバーヘッドがなく、ビンの数が固定されている変種を紹介した。しかし、断片化の数は最小限に抑える必要があります。彼らは、正確な解と近似解の両方に対する数理計画法アルゴリズムを提示しています。

ペナルティ付き分数ナップザック問題は、Malaguti、Monaci、Paronuzzi、Pferschyによって提唱されました。^[44]彼らはこの問題に対するFPTASと動的プログラムを開発し、モデルのパフォーマンスを比較する広範な計算研究を示しました。分数ジョブスケジューリングも参照してください。

ビンパッキングの重要な特殊なケースは、アイテムのサイズが割り切れるシーケンス（因数分解とも呼ばれる）を形成することです。割り切れるアイテムサイズの特殊なケースは、アイテムのサイズがすべて2の累乗であるコンピュータシステムのメモリ割り当てで発生します。アイテムのサイズが割り切れる場合、ビンパッキングのヒューリスティックアルゴリズムのいくつかは最適なソリューションを見つけます。^[45]

ビンパッキングのバリエーションとして、ビンにカーディナリティ制約があるものがあります。各ビンには、ある固定整数kに対して最大k 個のアイテムを含めることができます。

• Krause、Shen、Schwetman ^[46]は、最適ジョブスケジューリングの変形としてこの問題を紹介しています。コンピュータにはk個のプロセッサがあります。単位時間(1)かかるn個のジョブがありますが、メモリ要件は異なります。各時間単位は1つのビンと見なされます。目標は、各ビンで最大k個のジョブが実行されるようにしながら、できるだけ少ないビン(=時間単位)を使用することです。彼らは、最大でビンの数でソリューションを見つけるいくつかのヒューリスティックアルゴリズムを提示しています。${\displaystyle 2\mathrm {OPT} }$
• KellererとPferschy ^[47]は、最大でビンの解を見つける実行時間 のアルゴリズムを提示している。彼らのアルゴリズムはOPTの二分探索を実行する。探索された値mごとに、アイテムを3m /2のビンに詰め込もうとする。${\displaystyle O(n^{2}\log {n})}$${\displaystyle \left\lceil {\frac {3}{2}}\mathrm {OPT} \right\rceil }$

ビンパッキング モデルをより一般的なコストおよび負荷関数に拡張する方法はいくつかあります。

• Anily、Bramel、Simchi-Levi ^[48]は、ビンのコストがビン内のアイテム数の凹関数である設定を研究しています。目的は、ビンの数ではなく、総コストを最小化することです。彼らは、次適合増加ビンパッキングが、凹型で単調なコスト関数に対して、絶対的な最悪ケース近似比が最大で7/4、漸近的な最悪ケース比が1.691に達することを示しています。
• Cohen、Keller、Mirrokni、Zadimoghaddam ^{[49] は、}アイテムのサイズが事前にはわからないがランダム変数である設定を研究しています。これは、クラウドコンピューティング環境では特に一般的です。特定のユーザーが必要とするリソースの量には上限がありますが、ほとんどのユーザーは容量よりもはるかに少ない量を使用します。そのため、クラウドマネージャーは、わずかなオーバーコミットメントで大きな利益を得ることができます。これにより、偶然の制約を伴うビンパッキングのバリエーションが誘発されます。つまり、各ビンのサイズの合計が最大でBである確率は、少なくともpである必要があります。ここで、 pは固定定数です (標準的なビンパッキングはp =1 に対応します)。彼らは、緩い仮定の下で、この問題がサブモジュラービンパッキング問題と同等であることを示しており、この問題では、各ビンの「負荷」はアイテムの合計ではなく、その特定のサブモジュラー関数に等しくなります。

ビンパッキング問題では、ビンのサイズは固定されており、ビンの数は増やすことができます (ただし、可能な限り小さくする必要があります)。

対照的に、多方向数分割問題では、ビンの数は固定されており、そのサイズを拡大することができます。目的は、ビンのサイズが可能な限り等しくなる分割を見つけることです (マルチプロセッサ スケジューリング問題または最小メイクスパン問題と呼ばれる変種では、最大のビンのサイズを最小化することが特に目標です)。

逆ビンパッキング問題^[50]では、ビンの数とサイズは固定されていますが、アイテムのサイズは変更できます。目的は、アイテムサイズベクトルへの摂動を最小限に抑え、すべてのアイテムを規定の数のビンに詰め込むことです。

最大資源ビンパッキング問題^[51]では、目標は使用されるビンの数を最大化することであり、ビンの順序によっては、後のビンのアイテムが前のビンに収まらないようにすることです。双対問題では、ビンの数は固定されており、目標はビンに配置されるアイテムの合計数または合計サイズを最小化することであり、残りのアイテムが満たされていないビンに収まらないようにします。

ビンカバーリング問題では、ビンのサイズは下から制限されます。目標は、各ビンの合計サイズが少なくとも指定されたしきい値になるように、使用するビンの数 を最大化することです。

公平な分割不可能な家事割り当て問題（公平なアイテム割り当ての変形）では、アイテムは家事を表し、さまざまな人がそれぞれの家事に異なる難易度を割り当てます。目標は、各人に難易度の合計値の上限を持つ家事セットを割り当てることです（したがって、各人はビンに対応します）。ビンパッキングの多くのテクニックもこの問題で使用されます。^[52]

ギロチン切断問題では、アイテムと「ビン」は両方とも 1 次元の数字ではなく 2 次元の長方形であり、端から端までの切断を使用してビンからアイテムを切り取る必要があります。

利己的ビンパッキング問題では、各アイテムはコストを最小化したいプレイヤーです。^[53]

ビンパッキングのバリエーションとして、最小化すべきコストがビンの数ではなく、各ビン内のアイテム数の特定の凹関数であるものもあります。 ^[48]

その他のバリエーションとしては、2次元ビンパッキング、^[54] 3次元ビンパッキング、^[55] デリバリー付きビンパッキング、^[56]

• BPPLIB - 調査、コード、ベンチマーク、ジェネレーター、ソルバー、参考文献のライブラリ。