New Pretreatment and Resolution Using the Bee Colony Optimization for the Two-Dimensional Bin Packing Problem

Amara, Aida Kenza; Djebbar, Bachir

doi:10.18052/www.scipress.com/BMSA.14.13

BMSA > BMSA Volume 14 > New Pretreatment and Resolution Using the Bee...

< Back to Volume

New Pretreatment and Resolution Using the Bee Colony Optimization for the Two-Dimensional Bin Packing Problem

Full Text PDF

Abstract:

The two-dimensional bin packing problem involves packing a given set of rectangles into a minimum number of larger identical rectangles called bins. In this paper, we propose and develop mathematically a new pretreatment for the oriented version of the problem in order to reduce its size, identify and value the lost spaces by increasing the size of some objects. A heuristic method based on the first-fit strategy adapted to this problem is proposed. We present an approach of resolution using the bee colony optimization. The computational results show the effectiveness of the pretreatment in reducing the number of bins.

Info:

Periodical:

Bulletin of Mathematical Sciences and Applications (Volume 14)

Pages:

13-22

DOI:

https://doi.org/10.18052/www.scipress.com/BMSA.14.13

Citation:

A. K. Amara and B. Djebbar, "New Pretreatment and Resolution Using the Bee Colony Optimization for the Two-Dimensional Bin Packing Problem", Bulletin of Mathematical Sciences and Applications, Vol. 14, pp. 13-22, 2016

Online since:

February 2016

Authors:

Aida Kenza Amara, Bachir Djebbar

Keywords:

Bee Colony Optimization, Bin Packing, Heuristic Algorithm, Pretreatment

Export:

RIS, BibTeX, Text

Distribution:

Open Access

This work is licensed under a
Creative Commons Attribution 4.0 International License

References:

[1] J. Lee, B. kim and A. L. Johnson . 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, 45, 12 (2013)pp.1332-1344.

DOI: https://doi.org/10.1080/0740817x.2012.725506

[2] A. Lodi,S. Martello and D. Vigo . Heuristic and metaheuristic approaches for a class of two dimensional bin packing problems. INFORMS Journal on Computing, 11 (1999) p.345–357.

DOI: https://doi.org/10.1287/ijoc.11.4.345

[3] A. Lodi, S. Martello and D. Vigo. Recent advances on two-dimensional bin-packing problems. Discrete Applied Mathematics , 123 (2002)p.379–96.

DOI: https://doi.org/10.1016/s0166-218x(01)00347-x

[4] J.O. Berkey and P.Y. Wang. Two-dimensional finite bin-packing algorithms. Journal of Operational Research Society , 38 (1987) p.423–429.

DOI: https://doi.org/10.1057/jors.1987.70

[5] O. Faroe, D . Pisinger and M . Zachariasen. Guided local search for the three-dimensional bin-packing problem. INFORMS Journal on Computing , 15 (2003) p.267–283.

DOI: https://doi.org/10.1287/ijoc.15.3.267.16080

[6] J . Carlier, F. Clautiaux, and A. Moukrim. New reduction procedures and lower bounds for the two-dimensional bin-packing problem with fixed orientation. Computers & Operations Research. (2006).

DOI: https://doi.org/10.1016/j.cor.2005.08.012

[7] M.A. Boschetti and A. Mingozzi. The two-dimensional finite bin-packing problem. Part I: new lower bounds for the oriented case. 4OR , 1 (2003) p.27–42.

DOI: https://doi.org/10.1007/s10288-002-0005-z

[8] S. Martello and D. Vigo. Exact solution of the two-dimensional finite bin-packing problem. Management Science, 44(1998)p.388–399.

DOI: https://doi.org/10.1287/mnsc.44.3.388

[9] S . Fekete and J. Schepers. A general framework for bounds for higher-dimensional orthogonal packing problems. Mathematical Methods of Operations Research, 60(2004)p.311–329.

DOI: https://doi.org/10.1007/s001860400376

[10] M. A . Boschetti and A. Mingozzi . The two-dimensional finite bin-packing problem. Part I: new lower and upper bounds. 4OR Quarterly Journal of Operational Research, 1 (2003) p.135–147.

DOI: https://doi.org/10.1007/s10288-002-0006-y

[11] J. Harwig and J . Barnes. An adaptive tabu search approach for 2-dimensional orthogonal packing problems. Military Operations Research, (2006).

DOI: https://doi.org/10.5711/morj.11.2.5

[12] B. Chazelle. The bottom-left bin-packing heuristic: an efficient implementation. IEEE Transactions on Computers , C-32 (1983) p.697–707.

DOI: https://doi.org/10.1109/tc.1983.1676307

[13] K. Jansen and S. Öhring. Approximation algorithms for time constrained scheduling. Information and Computation, 132(1997) p.85–108.

DOI: https://doi.org/10.1006/inco.1996.2616

Show More Hide

Cited By:

This article has no citations.