T. Buchwald and G. Scheithauer
A note on ''Relations between capacity utilization and minimal bin number''
Abstract
In the paper ''Relations between capacity utilization and minimal bin number'' (Hoffmann/Scheithauer 2012) the following two-dimensional bin packing problem (BPP) is considered: given a set $K$ of rectangular items of sizes $\ell_i \times w_i$ and bins of size $L \times W$. Rotation of the items is not permitted. It is shown, if every item fits into the given bin and if the total area of the items does not exceed the area of the bin then at most three bins are needed to pack all items. The bound three is tight. Furthermore, it is shown that if $\ell_i \le L/3$ and $w_i \le W/3$ for all $i \in K$ then at most two bins are necessary to pack all items. In this note we give another, simpler proof of the latter result which is based on properties of the FFDH-heuristic (instead of using NFDH-heuristic as in (Hoffmann/Scheithauer 2012)) and we improve it to if $\ell_i \le L/2$ and $w_i \le W/3$ for all $i \in K$ then at most two bins are necessary.
PDF, (Preprint MATH-NM-05-2012, TU Dresden, August. 2012)
Back