Palabras clave
Genotipo-Fenotipo
Algoritmos Genéticos
Metaheurística
Algoritmo de colocación.
Cómo citar
Resumen
Dado un conjunto de piezas rectangulares con ancho fijo y con longitud infinita, el problema de strip-packing (SPP) de dos dimensiones, con una rotación de las piezas de 90°, consiste en la colocación ortogonal de todas las piezas en la tira, sin sobreponerlas, a fin de minimizar la altura de la tira usada. Se han propuesto varios algoritmos para resolver este problema, pero los genéticos constituyen uno de los enfoques más populares, debido a su eficacia en la solución en problemas NP-hard. En este trabajo se presentan tres representaciones binarias, una operación crossover clásica y operadores de mutación. Las tres representaciones binarias se comparan en un subconjunto de instancias de benchmarking. La representación R2 supera los resultados obtenidos por la representación R1 y R3. De hecho, se mejoran algunos de los mejores resultados encontrados por los trabajos publicados anteriormente.
[2] R. Álvarez-Valdés, F. Parreño, and J. M. Tamarit, “Reactive grasp for the strip-packing problem,” Computers & Operations Research, vol. 35, no. 4, pp. 1065-1083, 2008.
[3] T. Buchwald and G. Scheithauer, “Upper bounds for heuristic approaches to the strip packing problem,” International Transactions in Operational Research, vol. 23, no. 1-2, pp. 93- 119, 2014.
[4] A. Lodi, S. Martello, and D. Vigo, “Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems,” INFORMS Journal on Computing, vol. 11, no. 4, pp. 345-357, 1999.
[5] M. Kenmochi, T. Imamichi, K. Nnobe, M. Yagiura, and H. Nagamochi, “Exact algorithms for the 2-dimensional strip packing problem with and without rotations,” European Journal of Operational Research, vol. 198, no. 1, pp. 73-83, 2009.
[6] R. Álvarez-Valdés, F. Parreno, and J. Tamarit, “A branch and bound algorithm for the strip packing problem,” OR Spectrum, vol. 31, no. 2, pp. 431-459, 2009.
[7] Y. Arahori, T. Imamichi, and H. Nagamochi, “An exact strip packing algorithm based on canonical forms,” Computers & Operations Research, vol. 39, no. 12, pp. 2991-3011, 2012.
[8] S. C. Leung, D. Zhang, and K. M. Sim, “A two-stage intelligent search algorithm for the two-dimensional strip packing problem,” European Journal of Operational Research, vol. 215, no. 1, pp. 57-69, 2011.
[9] D. Chen, Y. Fu, M. Shang, and W. Huang, “A quasi-human heuristic algorithm for the 2D rectangular strip packing problem,” in Information Science and Engineering, 2008. ISISE’08. International Symposium on, vol. 2, pp. 392-396, IEEE, 2008.
[10] L. Wei, W.C. Oon, W. Zhu, and A. Lim, “A skyline heuristic for the 2D rectangular packing and strip packing problems,” European Journal of Operational Research, vol. 215, no. 2, pp. 337-346, 2011.
[11] R. Álvarez-Valdés, F. Parreño, and J. M. Tamarit, “A Tabu search algorithm for a twodimensional non-guillotine cutting problem,” European Journal of Operational Research, vol. 183, no. 3, pp. 1167-1182, 2007.
[12] G. Gómez-Villouta, J.-P. Hamiez, and J.-K. Hao, “Tabu search with consistent neighbourhood for strip packing,” in Trends in Applied Intelligent Systems. New York: Springer, 2010, pp. 1-10.
[13] E. Hopper and B. C. Turton, “An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem,” European Journal of Operational Research, vol. 128, no. 1, pp. 34-57, 2001.
[14] E. K. Burke, M. R. Hyde, and G. Kendall, “A squeaky wheel optimisation methodology for two-dimensional strip packing,” Computers & Operations Research, vol. 38, no. 7, pp. 1035-1044, 2011.
[15] G. Belov, G. Scheithauer, and E. Mukhacheva, “One-dimensional heuristics adapted for two-dimensional rectangular strip packing,” Journal of the Operational Research Society, vol. 59, no. 6, pp. 823- 832, 2008.
[16] S. Yang, S. Han, and W. Ye, “A simple randomized algorithm for two-dimensional strip packing,” Computers & Operations Research, vol. 40, no. 1, pp. 1-8, 2013.
[17] E. G. Talbi, Metaheuristics: From Design to Implementation, vol. 74. New York: John Wiley & Sons, 2009.
[18] E. Hopper and B. Turton, “A genetic algorithm for a 2D industrial packing problem,” Computers & Industrial Engineering, vol. 37, no. 1, pp. 375-378, 1999.
[19] S. Jakobs, “On genetic algorithms for the packing of polygons,” European Journal of Operational Research, vol. 88, no. 1, pp. 165-181, 1996.
[20] D. E. Goldberg, Genetic algorithms in search, optimization, and machine learning. Boston: Addison Wesley, 1989.
[21] G. Syswerda, “Schedule optimization using genetic algorithms,” in Handbook of Genetic Algorithms, New York: Van Nostrand Reinhold, 1991.
[22] A. Bortfeldt, “A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces,” European Journal of Operational Research, vol. 172, no. 3, pp. 814-837, 2006.
[23] M. Affenzeller, S. Wagner, S. Winkler, and A. Beham, Genetic Algorithms and Genetic Programming: Modern Concepts and Practical Applications. Boca Raton: CRC Press, 2009.
[24] A. Bortfeldt, Ein Genetischer Algorithmus fur das Zweidimensionale Strip-Packing-Problem. Planen, Lernen: Optimieren, 2003.
[25] R. García-Cáceres, C. Vega-Mejía, and J. Caballero-Villalobos, Integral Optimization of the Container Loading Problem. INTECH Open Access Publisher, 2011.
[26] K. He, Y. Jin, and W. Huang, “Heuristics for two-dimensional strip packing problema with 90 rotations,” Expert Systems with Applications, vol. 40, no. 14, pp. 5542-5550, 2013.
[27] R. Harren, K. Jansen, L. Pradel, and R. Van Stee, “A (5/3+ ε) - approximation for strip packing,” Computational Geometry, vol. 47, no. 2, pp. 248-267, 2014.
[28] J. L. da Silveira, E. C. Xavier, and F. K. Miyazawa, “Two-dimensional strip packing with unloading constraints,” Discrete Applied Mathematics, vol. 164, pp. 512-521, 2014.
[29] J. Thomas and N. S. Chaudhari, “A new metaheuristic genetic-based placement algorithm for 2D strip packing,” Journal of Industrial Engineering International, vol. 10, no. 1, pp. 1-16, 2014.
[30] S. Grandcolas and C. Pinto, “A new search procedure for the two- dimensional ortogonal packing problem,” Journal of Mathematical Modelling and Algorithms in Operations Research, pp. 1-19, 2015.
[31] E. Falkenauer, Genetic Algorithms and Grouping Problems. New York: John Wiley & Sons, 1998.
[32] E. Alba, Parallel Metaheuristics: A New Class of Algorithms. New Jersey: John Wiley & Sons, 2005.
[33] F. Rothlauf, “Representations for genetic and evolutionary algorithms,” Journal of Operational Research Society, vol. 54, no. 10, pp. 1112-1112, 2003.
[34] E. K. Burke, G. Kendall, and G. Whitwell, “A new placement heuristic for the ortogonal stock-cutting problem,” Operations Research, vol. 52, no. 4, pp. 655-671, 2004.
[35] V. Mancapa, T. Van Niekerk, and T. Hua, “A genetic algorithm for two dimensional strip packing problems,” South African Journal of Industrial Engineering, vol. 20, no. 2, pp. 145- 162, 2009.
[36] M. Matayoshi, “The 2D strip packing problem: a new approach with verification by EA,” in Systems Man and Cybernetics (SMC), 2010 IEEE International Conference on, pp. 2492-2499, IEEE, 2010.
[37] V. M. Kotov and D. Cao, “A heuristic algorithm for the non-oriented 2D rectangular strip packing problem,” Buletinul Academiei de Stiinte a Republicii Moldova. Matematica, no. 2, pp. 81-88, 2011.
[38] S. P. Coy, B. L. Golden, G. C. Runger, and E. A. Wasil, “Using experimental design to find effective parameter settings for heuristics,” Journal of Heuristics, vol. 7, no. 1, pp. 77-97, 2001.
[39] W. Huang and D. Chen, “An efficient heuristic algorithm for rectangle - packing problem,” Simulation Modelling Practice and Theory, vol. 15, no. 10, pp. 1356-1365, 2007.
Una vez aceptado un trabajo para publicación la revista podrá disponer de él en toda su extensión, tanto directamente como a través de intermediarios, ya sea de forma impresa o electrónica, para su publicación ya sea en medio impreso o en medio electrónico, en formatos electrónicos de almacenamiento, en sitios de la Internet propios o de cualquier otro editor. Este uso tiene como fin divulgar el trabajo en la comunidad científica y académica nacional e internacional y no persigue fines de lucro. Para ello el autor o los autores le otorgan el permiso correspondiente a la revista para dicha divulgación mediante autorización escrita.
Todos los articulos aceptados para publicación son sometidos a corrección de estilo. Por tanto el autor /los autores autorizan desde ya los cambios sufridos por el artículo en la corrección de estilo.
El autor o los autores conservarán los derechos morales y patrimoniales del artículo.