Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 0611.90079
Berkey, J.O.; Wang, P.Y.
Two-dimensional finite bin-packing algorithms. (English)
[J] J. Oper. Res. Soc. 38, 423-429 (1987). ISSN 0160-5682

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.

MSC 2000:: *90C27 Combinatorial programming
65K05 Mathematical programming (numerical methods)

Keywords: rectangular pieces; two-dimensional bin-packing; heuristics; finite bins

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]