zbMATH — the first resource for mathematics

Two-dimensional finite bin-packing algorithms. (English) Zbl 0611.90079
Given a set of rectangular pieces, the two-dimensional bin-packing problem is to place the pieces into an open-ended bin of infinite height such that the heigt of the resulting packing is minimized. In this paper we analyze the performance of two-dimensional bin-packing heuristics when applied to the special case of packing into finite bins. We develop new bin-packing heuristics by adapting the bottom-left packing methd and the next-fit, first-fit and best-fit level-oriented packing heuristics to the finite-bin case. We present our implementation of these algorithms, and compare them to other finite-bin heuristics. Our computational results indicate that the heuristics presented in this paper are suitable for practical use, and behave in a manner which reflects the proven worst- case bounds for the two-dimensional open-ended bin-packing problem.

90C27 Combinatorial optimization
65K05 Numerical mathematical programming methods
Full Text: DOI