Bin packing problem

A diverse set of offline and online heuristics for bin-packing have been studied by Johnson.[13] He introduced the following two characterizations for online heuristics. An algorithm is an any-fit (AF) algorithm if it fulfills the following property: A new bin is opened for a considered item, only if it does not fit into an already open bin. On the other hand, an algorithm is an almost-any-fit (AAF) algorithm if it has the additional property: If a bin is the unique bin with the lowest non-zero level, it cannot be chosen unless the item will not fit in any other bin with a non-zero level. He proved that each AAF-algorithm ${\displaystyle A}$ has an approximation guarantee of ${\displaystyle R_{NF}^{\infty }=17/10}$, meaning that it has an asymptotic approximation ratio of at most ${\displaystyle 17/10}$ and that there are lists for that it has an asymptotic approximation ratio of at least ${\displaystyle 17/10}$.

An online algorithm uses k-bounded space if, for each new item, the number of bins in which it may be packed is at most k.[14] Examples for these algorithms are Next-k-Fit and Harmonic-k.

Algorithm	Approximation guarantee	Worst case list ${\displaystyle L}$	Time-complexity
Next-fit (NF)	${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$[13]	${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$[13]	${\displaystyle {\mathcal {O}}(|L|)}$
First-fit (FF)	${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} (L)\rfloor }$[15]	${\displaystyle FF(L)=\lfloor 1.7\mathrm {OPT} (L)\rfloor }$[15]	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[13]
Best-fit (BF)	${\displaystyle BF(L)\leq \lfloor 1.7\mathrm {OPT} (L)\rfloor }$[16]	${\displaystyle BF(L)=\lfloor 1.7\mathrm {OPT} (L)\rfloor }$[16]	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[13]
Worst-Fit (WF)	${\displaystyle WF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$[13]	${\displaystyle WF(L)=2\cdot \mathrm {OPT} (L)-2}$[13]	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[13]
Almost-Worst-Fit (AWF)	${\displaystyle R_{AWF}^{\infty }\leq 17/10}$[13]	${\displaystyle R_{AWF}^{\infty }=17/10}$[13]	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[13]
Refined-First-Fit (RFF)	${\displaystyle RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5}$[8]	${\displaystyle RFF(L)=(5/3)\mathrm {OPT} (L)+1/3}$ (for ${\displaystyle \mathrm {OPT} (L)=6k+1}$)[8]	${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$[8]
Harmonic-k (Hk)	${\displaystyle R_{Hk}^{\infty }\leq 1.69103}$ for ${\displaystyle k\rightarrow \infty }$[17]	${\displaystyle R_{Hk}^{\infty }\geq 1.69103}$ [17]	${\displaystyle {\mathcal {O}}(|L|\log(|L|)}$[17]
Refined Harmonic (RH)	${\displaystyle R_{RH}^{\infty }\leq 373/228\approx 1.63597}$[17]		${\displaystyle {\mathcal {O}}(|L|)}$[17]
Modified Harmonic (MH)	${\displaystyle R_{MH}^{\infty }\leq 538/33\approx 1.61562}$[18]
Modified Harmonic 2 (MH2)	${\displaystyle R_{MH2}^{\infty }\leq 239091/148304\approx 1.61217}$[18]
Harmonic + 1 (H+1)		${\displaystyle R_{H+1}^{\infty }\geq 1.59217}$[19]
Harmonic ++ (H++)	${\displaystyle R_{H++}^{\infty }\leq 1.58889}$[19]	${\displaystyle R_{H++}^{\infty }\geq 1.58333}$[19]

Next Fit (NF) is a bounded space AF-algorithm with only one partially filled bin that is open at any time. The algorithm works as follows. It considers the items in an order defined by a list ${\displaystyle L}$. If an item fits inside the currently considered bin, the item is placed inside it. Otherwise, the current bin is closed, a new bin is opened and the current item is placed inside this new bin.

This algorithm was studied by Johnson in this doctoral thesis[13] in the year 1973. It has the following properties:

• The running time can be bounded by ${\displaystyle {\mathcal {O}}(n\log(n))}$, where ${\displaystyle n}$ is the number of items.[13]
• For each list ${\displaystyle L}$ it holds that ${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)-1}$ and hence ${\displaystyle R_{NF}=2}$.[13]
• For each ${\displaystyle N\in \mathbb {N} }$ there exists a list ${\displaystyle L}$ such that ${\displaystyle \mathrm {OPT} (L)=N}$ and ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$.[13]
• ${\displaystyle R_{NF}^{\infty }(\alpha )\leq 2}$ for all ${\displaystyle \alpha \geq 1/2}$.[13]
• ${\displaystyle R_{NF}^{\infty }(\alpha )\leq 1/(1-\alpha )}$ for all ${\displaystyle \alpha \leq 1/2}$.[13]
• For each algorithm ${\displaystyle A}$ that is an AF-algorithm it holds that ${\displaystyle R_{A}^{\infty }(\alpha )\leq R_{NF}^{\infty }(\alpha )}$.[13]

The intuition to the proof of the upper bound ${\displaystyle NF(L)\leq 2\cdot \mathrm {OPT} (L)}$ is the following: The number of bins used by this algorithm is no more than twice the optimal number of bins. In other words, it is impossible for 2 bins to be at most half full because such a possibility implies that at some point, exactly one bin was at most half full and a new one was opened to accommodate an item of size at most ${\displaystyle B/2}$. But since the first one has at least a space of ${\displaystyle B/2}$, the algorithm will not open a new bin for any item whose size is at most ${\displaystyle B/2}$. Only after the bin fills with more than ${\displaystyle B/2}$ or if an item with a size larger than ${\displaystyle B/2}$ arrives, the algorithm may open a new bin. Thus if we have ${\displaystyle K}$ bins, at least ${\displaystyle K-1}$ bins are more than half full. Therefore, ${\displaystyle \sum _{i\in I}s(i)>{\tfrac {K-1}{2}}B}$. Because ${\displaystyle {\tfrac {\sum _{i\in I}s(i)}{B}}}$ is a lower bound of the optimum value ${\displaystyle \mathrm {OPT} }$, we get that ${\displaystyle K-1<2\mathrm {OPT} }$ and therefore ${\displaystyle K\leq 2\mathrm {OPT} }$.[20]

The family of lists for which it holds that ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$ is given by ${\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)}$ with ${\displaystyle |L|=4(N-1)}$. The optimal solution for this list has ${\displaystyle N-1}$ bins containing two items with size ${\displaystyle 1/2}$ and one bin with ${\displaystyle 2(N-1)}$ items with size ${\displaystyle 1/2(N-1)}$ (i.e., ${\displaystyle N}$ bins total), while the solution generated by NF has ${\displaystyle 2(N-1)}$ bins with one item of size ${\displaystyle 1/2}$ and one item with size ${\displaystyle 1/(2(N-1))}$.

NkF works as NF, but instead of keeping only one bin open, the algorithm keeps the last ${\displaystyle k}$ bins open and chooses the first bin in which the item fits.

For ${\displaystyle k\geq 2}$ the NkF delivers results that are improved compared to the results of NF, however, increasing ${\displaystyle k}$ to constant values larger than ${\displaystyle 2}$ improves the algorithm no further in its worst-case behavior. If algorithm ${\displaystyle A}$ is an AAF-algorthm and ${\displaystyle m=\lfloor 1/\alpha \rfloor \geq 2}$ then ${\displaystyle R_{A}^{\infty }(\alpha )\leq R_{N2F}^{\infty }(\alpha )=1+1/m}$.[13]

First-Fit is an AF-algorithm that processes the items in a given arbitrary order ${\displaystyle L}$. For each item in ${\displaystyle L}$, it attempts to place the item in the first bin that can accommodate the item. If no bin is found, it opens a new bin and puts the item within the new bin.

The first upper bound of ${\displaystyle FF(L)\leq 1.7\mathrm {OPT} +3}$ for FF was proven by Ullman[21] in 1971. In 1972, this upper bound was improved to ${\displaystyle FF(L)\leq 1.7\mathrm {OPT} +2}$ by Garey et al.[22] In 1976, it was improved by Garey et al. [23] to ${\displaystyle FF(L)\leq \lceil 1.7\mathrm {OPT} \rceil }$, which equivalent to ${\displaystyle FF(L)\leq 1.7\mathrm {OPT} +0.9}$ due to the integrality of ${\displaystyle FF(L)}$ and ${\displaystyle \mathrm {OPT} }$. The next improvement, by Xia and Tan [24] in 2010, lowered the bound to ${\displaystyle FF(L)\leq 1.7\mathrm {OPT} +0.7}$. Finally 2013, this bound was improved to ${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$ by Dósa and Sgall.[15] They also present an example input list ${\displaystyle L}$, for that ${\displaystyle FF(L)}$ matches this bound.

Best-fit is an AAF-algorithm similar to First-fit. Instead of placing the next item in the first bin, where it fits, it is placed inside the bin that has the maximum load, where the item fits.

The first upper bound of ${\displaystyle BF(L)\leq 1.7\mathrm {OPT} +3}$ for BF was proven by Ullman[21] in 1971. This upper bound was improved to ${\displaystyle BF(L)\leq 1.7\mathrm {OPT} +2}$ by Garey et al.[22] Afterward, it was improved by Garey et al. [23] to ${\displaystyle BF(L)\leq \lceil 1.7\mathrm {OPT} \rceil }$. Finally this bound was improved to ${\displaystyle FF(L)\leq \lfloor 1.7\mathrm {OPT} \rfloor }$ by Dósa and Sgall.[16] They also present an example input list ${\displaystyle L}$, for that ${\displaystyle BF(L)}$ matches this bound.

This algorithm is similar to Best-fit. instead of placing the item inside the bin with the maximum load, the item is placed inside the bin with the minimum load.

This algorithm can behave as badly as Next-Fit and will do so on the worst-case list for that ${\displaystyle NF(L)=2\cdot \mathrm {OPT} (L)-2}$.[13] Furthermore, it holds that ${\displaystyle R_{WF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )}$. Since WF is an AF-algorithm, there exists an AF-algorithm such that ${\displaystyle R_{AF}^{\infty }(\alpha )=R_{NF}^{\infty }(\alpha )}$.[13]

AWF is an AAF-algorithm that considers the items in order of a given list ${\displaystyle L}$. It tries to fill the next item inside the second most empty open bin (or emptiest bin if there are two such bins). If it does not fit, it tries the most empty one, and if it does not fit there as well, the algorithm opens a new bin. As AWF is an AAF algorithm it has an asymptotic worst-case ratio of ${\displaystyle 17/10}$.[13]

The items are categorized in four classes. An item ${\displaystyle i}$ is called ${\displaystyle A}$-piece, ${\displaystyle B_{1}}$-piece, ${\displaystyle B_{2}}$-piece, or ${\displaystyle X}$-piece, if its size is in the interval ${\displaystyle (1/2,1]}$, ${\displaystyle (2/5,1/2]}$, ${\displaystyle (1/3,2/5]}$, or ${\displaystyle (0,1/3]}$ respectively. Similarly, the bins are categorized into four classes. Let ${\displaystyle m\in \{6,7,8,9\}}$ be a fixed integer. The next item ${\displaystyle i\in L}$ is assigned due to the following rules: It is placed using First-Fit into a bin in

• Class 1, if ${\displaystyle i}$ is an ${\displaystyle A}$-piece,
• Class 2, if ${\displaystyle i}$ is an ${\displaystyle B_{1}}$-piece,
• Class 3, if ${\displaystyle i}$ is an ${\displaystyle B_{2}}$-piece, but not the ${\displaystyle (mk)}$th ${\displaystyle B_{2}}$-piece seen so far, for any integer ${\displaystyle k\geq 1}$.
• Class 1, if ${\displaystyle i}$ is the ${\displaystyle (mk)}$th ${\displaystyle B_{2}}$-piece seen so far,
• Class 4, if ${\displaystyle i}$ is an ${\displaystyle X}$-piece.

Note that this algorithm is not an any-Fit algorithm since it may open a new bin despite the fact that the current item fits inside an open bin. This algorithm was first presented by Andrew Chi-Chih Yao,[8] who proved that it has an approximation guarantee of ${\displaystyle RFF(L)\leq (5/3)\cdot \mathrm {OPT} (L)+5}$ and presented a familie of lists ${\displaystyle L_{k}}$ with ${\displaystyle RFF(L_{k})=(5/3)\mathrm {OPT} (L_{k})+1/3}$ for ${\displaystyle \mathrm {OPT} (L)=6k+1}$.

The Harmonic-k algorithm partitiones the interval of sizes ${\displaystyle (0,1]}$ harmonically into ${\displaystyle k-1}$ pieces ${\displaystyle I_{j}:=(1/(j+1),1/j]}$ for ${\displaystyle 1\leq j<k}$ and ${\displaystyle I_{k}:=(0,1/k]}$ such that ${\displaystyle \bigcup _{j=1}^{k}I_{j}=(0,1]}$. An item ${\displaystyle i\in L}$ is called an ${\displaystyle I_{j}}$-item, if ${\displaystyle s(i)\in I_{j}}$. The algorithm divides the set of empty bins into ${\displaystyle k}$ infinite classes ${\displaystyle B_{j}}$ for ${\displaystyle 1\leq j\leq k}$, one bin type for each item type. A bin of type ${\displaystyle B_{j}}$ is only used for bins to pack items of type ${\displaystyle j}$. Each bin of type ${\displaystyle B_{j}}$ for ${\displaystyle 1\leq j<k}$ can contain exactly ${\displaystyle j}$ ${\displaystyle I_{j}}$-items. The algorithm now acts as follows: If the next item ${\displaystyle i\in L}$ is an ${\displaystyle I_{j}}$-item for ${\displaystyle 1\leq j<k}$, the item is placed in the first (only open) ${\displaystyle B_{j}}$ bin that contains fewer than ${\displaystyle j}$ pieces or opens a new one if no such bin exists. If the next item ${\displaystyle i\in L}$ is an ${\displaystyle I_{k}}$-item, the algorithm places it into the bins of type ${\displaystyle B_{k}}$ using Next-Fit.

This algorithm was first described by Lee and Lee.[17] It has a time complexity of ${\displaystyle {\mathcal {O}}(|L|\log(|L|))}$ and at each step, there are at most ${\displaystyle k}$ open bins that can be potentially used to place items, i.e., it is a k-bounded space algorithm. Furthermore, they studied its asymptotic approximation ratio. They defined a sequence ${\displaystyle \sigma _{1}:=1}$, ${\displaystyle \sigma _{i+1}:=\sigma _{i}(\sigma _{i}+1)}$ for ${\displaystyle i\geq 1}$ and proved that for ${\displaystyle \sigma _{l}<k<\sigma _{l+1}}$ it holds that ${\displaystyle R_{Hk}^{\infty }\leq \sum _{i=1}^{l}1/\sigma _{i}+k/(\sigma _{l+1}(k-1))}$. For ${\displaystyle k\rightarrow \infty }$ it holds that ${\displaystyle R_{Hk}^{\infty }\approx 1.6910}$. Additionally, they presented a family of worst-case examples for that ${\displaystyle R_{Hk}^{\infty }=\sum _{i=1}^{l}1/\sigma _{i}+k/(\sigma _{l+1}(k-1))}$

The Refined-Harmonic combines ideas from the Harmonic-k algorithm with ideas from Refined-First-Fit. It places the items larger than ${\displaystyle 1/3}$ similar as in Refined-First-Fit, while the smaller items are placed using Harmonic-k. The intuition for this strategy is to reduce the huge waste for bins containing pieces that are just larger than ${\displaystyle 1/2}$.

The algorithm classifies the items with regard to the following intervals: ${\displaystyle I_{1}:=(59/96,1]}$, ${\displaystyle I_{a}:=(1/2,59/96]}$, ${\displaystyle I_{2}:=(37/96,1/2]}$, ${\displaystyle I_{b}:=(1/3,37/96]}$, ${\displaystyle I_{j}:=(1/(j+1),1/j]}$, for ${\displaystyle j\in \{3,\dots ,k-1\}}$, and ${\displaystyle I_{k}:=(0,1/k]}$. The algorithm places the ${\displaystyle I_{j}}$-items as in Harmonic-k, while it follows a different strategy for the items in ${\displaystyle I_{a}}$ and ${\displaystyle I_{b}}$. There are four possibilities to pack ${\displaystyle I_{a}}$-items and ${\displaystyle I_{b}}$-items into bins.

• An ${\displaystyle I_{a}}$-bin contains only one ${\displaystyle I_{a}}$-item.
• An ${\displaystyle I_{b}}$-bin contains only one ${\displaystyle I_{b}}$-item.
• An ${\displaystyle I_{a}b}$-bin contains one ${\displaystyle I_{a}}$-item and one ${\displaystyle I_{b}}$-item.
• An ${\displaystyle I_{b}b}$-bin contains two ${\displaystyle I_{b}}$-items.

An ${\displaystyle I_{b}'}$-bin denotes a bin that is designated to contain a second ${\displaystyle I_{b}}$-item. The algorithm uses the numbers N_a, N_b, N_ab, N_bb, and N_b' to count the numbers of corresponding bins in the solution. Furthermore, N_c= N_b+N_ab

Algorithm Refined-Harmonic-k for a list L = (i_1, \dots i_n):
1. N_a = N_b = N_ab = N_bb = N_b' = N_c = 0
2. If i_j is an I_k-piece
       then use algorithm Harmonic-k to pack it
3.     else if i_j is an I_a-item
           then if N_b != 1, 
               then pack i_j into any J_b-bin; N_b--;  N_ab++;                
               else place i_j in a new (empty) bin; N_a++;
4.         else if i_j is an I_b-item
               then if N_b' = 1
                   then place i_j into the I_b'-bin; N_b' = 0; N_bb++;
5.                 else if N_bb <= 3N_c
                       then place i_j in a new bin and designate it as an I_b'-bin; N_b' = 1
                       else if N_a != 0
                           then place i_j into any I_a-bin; N_a--; N_ab++;N_c++
                           else place i_j in a new bin; N_b++;N_c++

This algorithm was first described by Lee and Lee.[17] They proved that for ${\displaystyle k=20}$ it holds that ${\displaystyle R_{RH}^{\infty }\leq 33/228}$.

This algorithm works analog to First-Fit. However, before starting to place the items, they are sorted in non-increasing order of their sizes. This algorithm can be implemented to have a running time of at most ${\displaystyle O(n\log(n))}$.

In 1973, D.S. Johnson proved in his doctoral theses[13] that ${\displaystyle FFD(I)\leq 11/9\mathrm {OPT} (I)+4}$. In 1985, B.S. Backer[29] gave a slightly simpler proof and showed that the additive constant is not more than 3. Yue Minyi[30] proved that ${\displaystyle FFD(I)\leq 11/9\mathrm {OPT} (I)+1}$ in 1991 and, in 1997, improved this analysis to ${\displaystyle FFD(I)\leq 11/9\mathrm {OPT} (I)+7/9}$ together with Li Rongheng.[31] In 2007 György Dósa[25] proved the tight bound ${\displaystyle FFD(I)\leq 11/9\mathrm {OPT} (I)+6/9}$ and presented an example for which ${\displaystyle FFD(I)=11/9\mathrm {OPT} (I)+6/9}$.

The lower bound example given in by Dósa[25] is the following: Consider the two bin configurations ${\displaystyle B_{1}:=\{1/2+\varepsilon ,1/4+\varepsilon ,1/4-2\varepsilon \}}$ and ${\displaystyle B_{2}:=\{1/4+2\varepsilon ,1/4+2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}}$. If there are 4 copies of ${\displaystyle B_{1}}$ and 2 copies of ${\displaystyle B_{2}}$ in the optimal solution, FFD will compute the following bins: 4 bins with configuration ${\displaystyle \{1/2+\varepsilon ,1/4+2\varepsilon \}}$, one bin with configuration ${\displaystyle \{1/4+\varepsilon ,1/4+\varepsilon ,1/4+\varepsilon \}}$, one bin with configuration ${\displaystyle \{1/4+\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}}$, one bin with configuration ${\displaystyle \{1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}}$, and one final bin with configuration ${\displaystyle \{1/4-2\varepsilon \}}$, i.e. 8 bins total, while the optimum has only 6 bins. Therefore, the upper bound is tight, because ${\displaystyle 11/9\cdot 6+6/9=72/9=8}$. This example can be extended to all sizes of ${\displaystyle OPT(I)}$.[25]

Modified first fit decreasing (MFFD)[27] improves on FFD for items larger than half a bin by classifying items by size into four size classes large, medium, small, and tiny, corresponding to items with size > 1/2 bin, > 1/3 bin, > 1/6 bin, and smaller items respectively. Then it proceeds through five phases:

1. Allot a bin for each large item, ordered largest to smallest.
2. Proceed forward through the bins. On each: If the smallest remaining medium item does not fit, skip this bin. Otherwise, place the largest remaining medium item that fits.
3. Proceed backward through those bins that do not contain a medium item. On each: If the two smallest remaining small items do not fit, skip this bin. Otherwise, place the smallest remaining small item and the largest remaining small item that fits.
4. Proceed forward through all bins. If the smallest remaining item of any size class does not fit, skip this bin. Otherwise, place the largest item that fits and stay on this bin.
5. Use FFD to pack the remaining items into new bins.

This algorithm was first studied by Johnson and Garey[27] in 1985, where they proved that ${\displaystyle MFFD(I)\leq (71/60)\mathrm {OPT} (I)+(31/6)}$. This bound was improved in the year 1995 by Yue and Zhang[26] who proved that ${\displaystyle MFFD(I)\leq (71/60)\mathrm {OPT} (I)+1}$.

The first asymptotic approximation scheme was described by Fernandez de la Vega and Lueker.[32] I has a time complexity of ${\displaystyle {\mathcal {O}}(n\log(1/\varepsilon ))+{\mathcal {O}}_{\varepsilon }(1)}$, where ${\displaystyle {\mathcal {O}}_{\varepsilon }(1)}$ denotes a function only dependent on ${\displaystyle 1/\varepsilon }$, and generates a solution with size at most ${\displaystyle (1+\varepsilon )\mathrm {OPT} +{\mathcal {O}}(1/\varepsilon ^{2})}$. The time complexity of this algorithm was improved by Karmarkar and Karp[33] to be polynomial in ${\displaystyle n}$ and ${\displaystyle 1/\varepsilon }$.