Palabras clave
cúmulo de partículas
recocido simulado
Cómo citar
Resumen
Los problemas de empaquetamiento y corte óptimo son considerados clásicos dentro de la investigación de operaciones, debido a su gran espectro de aplicación en la industria y su alta complejidad tanto matemática como computacional. En este trabajo se presenta el problema de empaquetamiento óptimo bidimensional irrestricto de piezas rectangulares en una sola placa, con pesos asociados a las piezas y sin estos, al tiempo que se considera la posibilidad de rotar 90° las piezas y con restricciones de corte tipo guillotina (problema de la mochila bidimensional irrestricta guillotinada). Se describe el modelo matemático aplicado por diferentes grupos de investigación que estudian esta temática. Se propone, además, un tipo de codificación para aplicarla en este problema y se resuelve mediante un algoritmo de optimización que combina las principales características de cúmulo de partículas, recocido simulado y algoritmos genéticos. Para comprobar la eficiencia de la metodología presentada se tomaron casos de prueba de la literatura especializada, se analizan y comparan los métodos de solución presentados con los últimos avances del problema y se obtienen resultados de excelente calidad y nunca antes reportados en la literatura especializada.
BEN, S.; CHU, C. y ESPINOUSE, M. L. Characterization and modelling of guillotine constraints. European Journal of Operational Research, 2008, vol. 191, pp. 112-126.
CHRISTOFIDES, N. y WHITLOCK, C. An algorithm for two-dimensional cutting problems. Operations Research, 1977, vol. 25, pp. 30-44.
CUI, Y. An exact algorithm for generating homogenous T-shape cutting patterns. Computers & Operations Research, 2007, vol. 34, pp. 1107-1120.
GALLEGO, R.; ESCOBAR, A. H. y ROMERO, R. A. Programación lineal entera. Pereira: Universidad Tecnológica de Pereira, 2007.
GALLEGO, R.; ESCOBAR, A. H. y TORO, E. M. Técnicas metaheurísticas de optimización. Pereira: Universidad Tecnológica de Pereira, 2008.
G, Y.-G. y KANG, M.-K. A new upper bound for unconstrained two-dimensional cutting and packing. Journal of the Operational Research Society, 2002, vol. 53, pp. 587-591.
G, Y.-G.; KANG, M.-K. y SEONG, J. A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems. Operations Research Letters, 2003, vol. 31, pp. 301-307.
GILMORE, P. C. y GOMORY, R. E. Multistage cutting problems of two and more dimensions. Operations Research, 1965, vol. 13, pp. 94-120.
GILMORE, P. C. y GOMORY, R. E. The theory and computation of knapsack functions. Operational Research, 1966, vol. 14, pp. 1045-1074.
HERZ, J. C. A recursive computing procedure for two-dimensional stock cutting. IBM Journal of Research and Development, 1972, vol. 16, pp. 462-469.
HIFI, M. Exact algorithms for the guillotine strip cutting/packing problem. Computers & Operations Research, 1998, vol. 25, pp. 925-940.
HIFI, M. Exact algorithms for large-scale unconstrained two and three staged cutting problems. Computational Optimization and Applications, 2001, vol. 18, pp. 63-88.
HIFI, M. Problem instances for the 2D Cutting/Packing Problems [web en línea], 1997. <ftp://cermsem.univ-paris1.fr/pub/CERMSEM/hifi/2Dcutting/> [Consultado 07-09-2010].
HIFI, M y ZISSIMOPOULOS, V. A recursive exact algorithm for weighted two-dimensional cutting. European Journal of Operational Research, 1996, vol. 91, pp. 553-564.
TORO, E.; GARCÉS, A. y RUIZ, H. Solución al problema de empaquetamiento bidimensional usando un algoritmo híbrido constructivo de búsqueda en vecindad variable y recocido simulado. Revista Facultad de Ingeniería de la Universidad de Antioquia, 2008, vol. 46, pp. 119-131.
WONG, D. F.; LEONG, H. W. y LIU, C. L. Simulated annealing for VLSI design. New York: Kluwer Academic Publishers, 1988.
ZHI-HUI, Z.; JUN, Z.; YUN, L. y HENRY, S. Adaptive Particle swarm optimization. IEEE Transactions on Systems, Man and Cybernetics, 2009, vol. 39, pp. 1362-1381.
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.