Keywords
particle swarm optimization
simulated annealing
How to Cite
Abstract
Cutting and packing problems are common in operations research, due to their big spectrum of application in the industry and its highly mathematical and computational complexity for the academy. In this study we present the unconstrained twodimensional cutting stock problem of rectangular items, with and without weights associated to the items, bearing in mind the possibility to rotate items at 90°, and with guillotine cuts (also known as unconstrained two-dimensional guillotineable single knapsack problem). For this problem, we describe the mathematical model recognized by the academic community. We develop an appropriate encoding of the problem so it is possible to work on it using metaheuristic hybrid algorithm particle swarm optimization and simulated annealing. To check the efficiency of this methodology, case studies were taken from specialized literature, where the presented solution method could be analyzed and compared with current problems. The results obtained had an excellent quality and had never been reported.
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.
This journal is registered under a Creative Commons Attribution 4.0 International Public License. Thus, this work may be reproduced, distributed, and publicly shared in digital format, as long as the names of the authors and Pontificia Universidad Javeriana are acknowledged. Others are allowed to quote, adapt, transform, auto-archive, republish, and create based on this material, for any purpose (even commercial ones), provided the authorship is duly acknowledged, a link to the original work is provided, and it is specified if changes have been made. Pontificia Universidad Javeriana does not hold the rights of published works and the authors are solely responsible for the contents of their works; they keep the moral, intellectual, privacy, and publicity rights.
Approving the intervention of the work (review, copy-editing, translation, layout) and the following outreach, are granted through an use license and not through an assignment of rights. This means the journal and Pontificia Universidad Javeriana cannot be held responsible for any ethical malpractice by the authors. As a consequence of the protection granted by the use license, the journal is not required to publish recantations or modify information already published, unless the errata stems from the editorial management process. Publishing contents in this journal does not generate royalties for contributors.