Bee Colony Optimization Applied to the Bin Packing Problem

Authors: Kenza Aida Amara, Bachir Djebbar

Abstract:

We treat the two-dimensional bin packing problem which involves packing a given set of rectangles into a minimum number of larger identical rectangles called bins. This combinatorial problem is NP-hard. We propose a pretreatment for the oriented version of the problem that allows the valorization of the lost areas in the bins and the reduction of the size problem. A heuristic method based on the strategy first-fit adapted to this problem is presented. We present an approach of resolution by bee colony optimization. Computational results express a comparison of the number of bins used with and without pretreatment.

Keywords: Bee colony optimization, bin packing, heuristic algorithm, pretreatment.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1129159

References:

[1] Lee J, kim B,. Johnson A L. A two-dimensional bin packing problem with size changeable items for the production of wind turbine flanges in the open die forging industry. IIE Transactions, 2013; 45, 12, 1332-1344
[2] Lodi A, Martello S, Vigo D. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS Journal on Computing 1999;11:345–57.
[3] Lodi A, Martello S, Vigo D. Recent advances on two-dimensional bin-packing problems. Discrete Applied Mathematics 2002;123:379–96.
[4] Berkey JO,Wang PY. Two-dimensional finite bin-packing algorithms. Journal of Operational Research Society 1987;38:423–9.
[5] Faroe O, Pisinger D, Zachariasen M. Guided local search for the three-dimensional bin-packing problem. INFORMS Journal on Computing 2003;15:267–83.
[6] Carlier J, Clautiaux F, Moukrim A. New reduction procedures and lower bounds for the two-dimensional bin-packing problem with fixed orientation. Computers & Operations Research.2006.
[7] Boschetti MA, Mingozzi A. The two-dimensional finite bin-packing problem. Part I: new lower bounds for the oriented case. 4OR 2003; 1:27–42.
[8] Martello S, Vigo D. Exact solution of the two-dimensional finite bin-packing problem. Management Science 1998;44:388–99.
[9] Fekete S, Schepers J. A general framework for bounds for higher-dimensional orthogonal packing problems. Mathematical Methods of Operations Research 2004;60:311–29
[10] Boschetti MA, Mingozzi A. The two-dimensional finite bin-packing problem. Part I: new lower and upper bounds. 4OR 2003;1:135–47
[11] Harwig J, Barnes J. An adaptive tabu search approach for 2-dimensional orthogonal packing problems. Military Operations Research, 2006,in press.
[12] Chazelle B. The bottom-left bin-packing heuristic: an efficient implementation. IEEE Transactions on Computers 1983;C-32:697–707.
[13] K. Jansen and S. Öhring. Approximation algorithms for time constrained scheduling. Information and Computation, 1997; 132(2); 85–108.