Commenced in January 2007
Paper Count: 30101
Bee Colony Optimization Applied to the Bin Packing Problem
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.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1129159Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 618
 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
 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.
 Lodi A, Martello S, Vigo D. Recent advances on two-dimensional bin-packing problems. Discrete Applied Mathematics 2002;123:379–96.
 Berkey JO,Wang PY. Two-dimensional finite bin-packing algorithms. Journal of Operational Research Society 1987;38:423–9.
 Faroe O, Pisinger D, Zachariasen M. Guided local search for the three-dimensional bin-packing problem. INFORMS Journal on Computing 2003;15:267–83.
 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.
 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.
 Martello S, Vigo D. Exact solution of the two-dimensional finite bin-packing problem. Management Science 1998;44:388–99.
 Fekete S, Schepers J. A general framework for bounds for higher-dimensional orthogonal packing problems. Mathematical Methods of Operations Research 2004;60:311–29
 Boschetti MA, Mingozzi A. The two-dimensional finite bin-packing problem. Part I: new lower and upper bounds. 4OR 2003;1:135–47
 Harwig J, Barnes J. An adaptive tabu search approach for 2-dimensional orthogonal packing problems. Military Operations Research, 2006,in press.
 Chazelle B. The bottom-left bin-packing heuristic: an efficient implementation. IEEE Transactions on Computers 1983;C-32:697–707.
 K. Jansen and S. Öhring. Approximation algorithms for time constrained scheduling. Information and Computation, 1997; 132(2); 85–108.