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

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.

Abstract

In this paper, a discrete model that solves the two-dimensional cutting problem, usually called nesting, of great interest in the textile industries is presented. The problem consists in finding the best position and orientation of irregularly shaped molds on a material without overlapping, in order to minimize the residual or waste. We propose an adaptive heuristic that evaluates various conditions and constraints of the problem, with a polynomial computational complexity that can be accelerated using multi-core architectures. The proposed methodology is evaluated using known cases of the literature of the area and the resolution times are compared with a commercial tool sector, obtaining very good results. Furthermore, it achieves acceleration up to 4X processing respect to its sequential version.

Referencias no citadas

Abbasi and Sahir, 2010, Alba and Tomassini, 2002, Albano, 1977, Asns, 2013, Bąk et al., 2011, Baker and Coffman, 1980, Burke et al., 2009, Chazelle, 1983, Cheng et al., 1994, Cheng and Rao, 2000, Chu et al., 2007, Cui et al., 2006, Dagli, 2002, Dyckho and Finke, 1992, Elkeran, 2013, Gilmore and Gomory, 1965, Hifi, 2001, Hopper and Turton, 1999, Hopper and Turton, 2001, Jakobs, 1996, Junior et al., 2013, Lai and Chan, 1997, Lee and Ma, 2008, Lesh et al., 2005, Lesh and Mitzenmacher, 2006, Liton, 1997, Liu and Teng, 1999, Mollá et al., 1992, Ofa, 2016, Parada et al., 1995, Rodrigo et al., 2012, Ross et al., 2002, Rui Liu et al., 2002, Savio et al., 2012, Siasos and Vosniakos, 2014, Tay et al., 2002 and Weng and Kuo, 2011.