Analysis of Genetic Algorithms for solving the 2D Orthogonal Strip Packing Problem

M.M. Glybovets, N.M. Gulayeva, I.O. Morozov

Abstract


A class of genetic algorithms for solving the 2D Strip Packing Problem is investigated. The theoretical analysis of the complexity of implementing decoders MERA and BLF is done. Original implementations of these MERA and BLF decoders enhanced with a number of heuristic optimizations are proposed. Genetic algorithm for solving the 2D Strip Packing Problem for special cases (allowed/forbidden objects rotation by 90°) with the use of MERA/BLF decoders is proposed. Extensive computational experiments with well-known instances are performed to analyze different configurations of basic parameters of proposed genetic algorithm. The comparison of the obtained algorithm with other known algorithms is given.

Problems in programming 2016; 4: 104-116


Keywords


genetic algorithm; packing problem; decoder; MERA; BLF

References


Stoyan Y.G., Yakovlev S.V. Mathematical models and optimization methods of the geometric projection. - Kiev: Scientific thought. - 1986. - 268 p.

Glibovets M.M., Gulayeva N.M. Evolutionary algorithms: a textbook. - NaUKMA, 2013. - P. 334-357.

Mukhacheva E.A., Mukhacheva A.S. L.V. Kantorovich and problems of cutting-package, new approaches to combinatorial problems of linear cutting and rectangular package // Notes of POMI scientific seminars. - 2004. - Vol. 312. - P. 239-255.

Fowler R.J., Paterson M.S., Tatimoto S.L. Optimal packing and covering in the plane are NP-complete // Information Processing Letters. - 1981 - N 12. - P. 133-137.

https://doi.org/10.1016/0020-0190(81)90111-3

Grebennik I.V., Pankratov A.V., Chugai A.M., Baranov A.V. Packaging n-dimensional parallelepipeds with the ability to change their orthogonal orientation in n-dimensional parallelepiped // Cybernetics and Systems Analysis. - 2010. - N 5. - P. 122-131.

https://doi.org/10.1007/s10559-010-9260-8

Gulayeva N.M. Analysis of the parameters of the genetic algorithm solving the problem of orthogonal package / Gulayeva N.M., Shchur O.P. // Scientific notes NaUKMA. - 2012. - Vol 138: Computer science. - P. 6-14.

Chekanin V.A. Modified evolutionary algorithms and programmatic solving of the problem of orthogonal packing of objects // Abstract. Dis. on the scientific degree of Ph.D. : 05.13.17. - Moscow: USATU, 2011. - 14 p.

Lesh.N., Marks J., Mc. Mahon A. Exhaustive approaches to 2D rectangular perfect packings. Information Processing Letters - 2004. - P. 7-14.

https://doi.org/10.1016/j.ipl.2004.01.006

Baker B.S., Coffman E.G., Rivest R.L. Orthogonal packings in two dimensions // SIAM Journal on computing

Chazelle B. The bottom left bin packing heuristic: an efficient implementation // IEEE Transaction on computers. - 1983 - N 32. - P. 697-707.

https://doi.org/10.1109/TC.1983.1676307

Lesh N., Mitzenmacher M. Bubble search: a simple heuristic for improving priority-based greedy algorithms // Information processing letters. - 2006. - P. 161-169.

https://doi.org/10.1016/j.ipl.2005.08.013

Bortfeldt A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. European Journal of Operational Research. - 2006. - P. 814-837.

https://doi.org/10.1016/j.ejor.2004.11.016

Ahmad, Abdul-Rahim, An Intelligent Expert System for Decision Analysis and Support in Multi-Attribute Layout Optimization, PhD thesis, University of Waterloo, Ontario, Canada, 2005. - 207 p.

Hopper E., Turton B.C.H. Problem generators for rectangular packing problems // Computers in Engineering. - 2000. - P. 123-135.

Riff M.C., Bonnaire X., Neveu B. A revision of recent approaches for two-dimensional strip-packing problems // Engineering application of Artificial Intelligence. - 2009.

https://doi.org/10.1016/j.engappai.2008.10.025

Araya I., Neveu B., Riff M.C. An Efficient Hyperheuristic for Strip Packing problem // Book Adaptive and Multilevel Heuristics, Series Studies in Computational Intelligence. - Springer. - 2008. - P. 61-76.

https://doi.org/10.1007/978-3-540-79438-7_3

Hopper E., B. C. H. Turton. An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem. Eur. J. Oper. Res. - 2000. - Vol. 128. - P. 34-57.

https://doi.org/10.1016/S0377-2217(99)00357-4




DOI: https://doi.org/10.15407/pp2016.04.104

Refbacks

  • There are currently no refbacks.