Un método de optimización proximal al problema de anidamiento de piezas irregulares utilizando arquitecturas en paralelo

Juan P. D'Amato; Matias Mercado; Alejandro Heiling; Virginia Cifuentes

doi:10.1016/j.riai.2016.01.003

Autores/as

Juan P. D'Amato Universidad Nacional del Centro de la Provincia de Buenos Aires
Matias Mercado Universidad Nacional del Centro de la Provincia de Buenos Aires
Alejandro Heiling Universidad Nacional del Centro de la Provincia de Buenos Aires
Virginia Cifuentes Universidad Nacional del Centro de la Provincia de Buenos Aires

DOI:

https://doi.org/10.1016/j.riai.2016.01.003

Palabras clave:

Optimización, corte, industria textil, heurística, paralelización

Resumen

Se presenta un modelo discreto que resuelve el problema bidimensional de corte y ubicación, generalmente llamado nesting (anidamiento), de gran interés en las industrias textiles. El problema consiste en minimizar el remanente o desperdicio de un material a través de la ordenación de moldes geométricamente irregulares. Como solución se propone un algoritmo heurístico polinomial, flexible porque permite evaluar distintas condiciones y restricciones del problema, y paralelizable en arquitecturas de múltiples núcleos de bajo costo. La metodología propuesta se evaluó con casos de estudio de la literatura del área y se comparan los tiempos de cómputo con una herramienta comercial del sector, obteniéndose muy buenos resultados. Además, se logra una aceleración del procesamiento de hasta 4X con respecto a la versión secuencial.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

Abbasi, J., Sahir, M. Development of Optimal Cutting Plan using Linear Programming Tools and MATLAB Algorithm – Int. J. of Innovation, Management and Technology, Vol. 1, No. 5, pp.483-492, 2010.

Alba E. and Tomassini M., Parallelism and evolutionary algorithms. IEEE Transaction on Evolutionary Computation, 6(5):443–462, 2002.

Albano, A. A Method to Improve Two-Dimensional Layout. Computer Aided Design, 9, 1977.

ASNS Nesting Software for optimum use of materials, LLC Technos, 2013.

Bąk S., Błażewicz, J., Pawlak G., Płaza, M., Burke, E., and Kendall G., A Parallel Branch-and-Bound Approach to the Rectangular Guillotine Strip Cutting Problem. Journal on Computing Winter, 23(1), 2011.

Baker B., Coffman E. Jr., and Rivest R. Orthogonal packing in two dimensions. SIAM Journal on Computing, 9(4):846–855, 1980.

Burke, E., Kendall K., and Whitwell G, A Simulated Annealing Enhancement of the Best-Fit Heuristic for the Orthogonal Stock-Cutting Problem, Journal on Computing ,21(1), pp.505-516, 2009.

Chazelle B. The botton-left bin-packing heuristic: An efficient implementation. IEEE Transactions on Computers, 32(8):697–707, 1983.

Cheng C.H., Feiring, B.R., Cheng, T.C.E. The Cutting Stock Problem – A Survey, Int. J. of Production Economics, 36/3: 291–305, 1994.

Cheng, S.K., Rao, K.P, Large-scale Nesting of Irregular Patterns Using Compact Neighborhood Algorithm, Journal of Materials Processing Technology, 103:135– 140, 2000.

Chu, C., Kim, S., Lin Y., Yu, Y., Bradski, G., Ng, A. and Olukotun, A. MapReduce for machine learning on multicore. Neural Information Processing Systems, 2007.

Cui, Y., D. He, and X. Song, Generating Optimal Two-Sectional Cutting Patterns for Rectangular Blanks. Journal of Computers & Operations Research, 2006. 33(1), pp. 1505-1520, 2006.

Dagli,C. Cutting Stock Problem: Combined Use of Heuristics and Optimization Methods, Recent Developments in Production Research Amsterdam, pp. 500-506, 1988.Dowsland, K.A., Vaid, S., Dowsland, W.B. An Algorithm for Polygon Placement Using a Bottom-left Strategy, European Journal of Operational Research, 141:371–381, 2002.

Dyckho H. and Finke, U. Cutting and Parking in Production and Distribution. Physica-Verlag, 1992.

Elkeran, E. A New Approach for Sheet Nesting Problem Using Guided Cuckoo Search and Pairwise Clustering, European Journal of Operational Research, 231:757–769, 2013.

Gilmore G. and Gomory, R. Multistage cutting stock problems of two and more dimensions. European J. of Op. Research, 14(1): 94-120, 1965.

Hifi M. Exact algorithms for large-scale unconstrained two and three staged cutting problems. Computational Optimization and Applications, 18(1):63–88, 2001.

Hopper E., Turton, B. A genetic algorithm for a 2D industrial packing problem, Computers & Industrial Engineering 37(1), pp. 375–378, 1999.

Hopper E., Turton B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. European Journal of Operational Research, 128(1):34–57, 2001.

Jakobs S. On genetic algorithms for the packing of polygons. European Journal of Operational Research, 88:165–181, 1996.

Junior, B.A., Pinheiro, P.R., Saraiva, R.D. A Hybrid Methodology for Nesting Irregular Shape: Case Study on a Textile Industry, 6th IFAC Conference on M. and Control of Production and Logistics (Brazil), pp.15–20, 2013.

Lai, K., Chan, J. Developing a simulated annealing algorithm for the cutting stock problem, Journal of Computers ind. Engng, 32(1), pp. 115-127, 1997.

Lee, W.-C., Ma, H., Cheng, B.-W. A Heuristic for Nesting Problems of Irregular Shapes, Computer-Aided Design, 40/5: 625–633, 2008.

Lesh N., Marks H., Mc.Mahon A., and Mitzenmacher M.. New heuristic and inte- ractive approaches to 2D rectangular strip packing. ACM Journal of Experimental Algorithmics, 10:1–18, 2005.

Lesh N. and Mitzenmacher M. Bubble search: a simple heuristic for improving priority-based greedy algorithms. Information Processing Letters, 97:161–169, 2006.

Liton, C. A frecuency approach to the one dimensional cutting problem for carpet rolls. Operation Research Quartelly, 28(1), pp. 927-938, 1997.

Liu D. and Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. European Journal of Operational Research, 112:413–420, 1999.

Mollá R., Quirós R., Vivó R. Fixed Point Digital Differential Analyzer Proceedings of Compugraphics´92, pp. 1-5. 14-17, 1992.

OFA - Optimizer For Anyshape - Samtec Solutions - Website http://www.samtecsolutions.com/

Parada, V., Gómes, A. and De Diego, J. Exact solutions for constrained twodimensional cutting stock problems. European Journal of Operation Research, 84(1), pp. 633-644, 1995.

Rodrigo, W., Daundasekera, W. and Perera A. Pattern Generation for Two Dimensional Cutting Stock Problem - International Journal of Mathematics Trends and Technology, 3(2), pp.54-62, 2012.

Ross, P., Schulenburg, S., Marín-Blázquez, J. G., & Hart, E. Hyper-heuristics: learning to combine simple heuristics in bin-packing problems. In LNCS. Conference on genetic and evolutionary computation, pp. 942–948, 2002.

Rui Liu, Xianlong Hong, Sheqin Dong, Yici Cai, Jun Gu, and Chung-Kuan Cheng. Module placement with boundary constraints using o-tree representation. IEEE Int. Symposium on Circuits and Systems (ISCAS2002), 2:871–874, 2002.

Savio, G., Menneghello, R., Conceri, G. A Heuristic Approach for Nesting of 2D Shapes, in: Proceedings of the 37th Int. MATADOR Conference (Springer), pp.49–53, 2012.

Siasos A., Vosniakos G. Optimal directional nesting of planar profiles on fabric bands for composites manufacturing. CIRP Journal of Manufacturing Science and Technology, vol 7, pp. 283-297, 2014.

Tay, F., Chong, F. and Lee,F. Pattern nesting on irregular-shaped stock using Genetic Algorithms. Engineering Applications of Artificial Intelligence, 15(1), pp. 551-558, 2002.

Weng, W.-C., Kuo, H.-C. Irregular Stock Cutting System Based on AutoCAD, Advances in Engineering Software, 42/9: 634–643, 2011.