A study on GPU acceleration applied to 2D irregular packing problems

ABSTRACT

Irregular packing problems are an important subject of study in C&P problems. An efficient solution can have a great economic and environmental impact. The main objective is to obtain a feasible layout, a configuration whereby items are completely placed inside one or more containers without overlap. Although many solutions in the literature are capable of achieving high density solutions for benchmark instances, they are limited to small and medium problems. The best packing algorithms adopt the overlap minimization approach, in which the overlap restriction is relaxed by adopting an overlap function. Thus, a study of parallel implementation is proposed to accelerate the overlap minimization solution and reduce the processing time, potentially allowing for the solution of more complex instances. The results showed high speedups for the parallelization of the local search algorithm, achieving an acceleration of up to 16x. Then, by applying this accelerated method to a packing algorithm, speedups of up to 4.5 were observed. Due to their stochastic nature, the tests were repeated several times for each instance and the average results were computed. These results demonstrated the potential for GPU application with irregular packing, which can be extended to achieve its full capability.

KEYWORDS:

• Cutting & packing
• irregular nesting problem/ GPU parallelization

Acknowledgments

A. K. Sato was supported by Coordenação de Aperfeiçoamento de Pessoal de Nível Superior/PNPD. M. S. G. Tsuzuki and T. C. Martins were partially supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico (Grants 305.959/2016–6 and 306.415/2012–7). The research has the support from Conselho Nacional de Desenvolvimento Científico e Tecnológico (Grant 456.180/2014-1), from Fundação de Amparo à Pesquisa do Estado de São Paulo (Grant 2013/26532-9), and Coordenação de Aperfeiçoamento de Pessoal de Nível Superior/PROAP - convênio 817.757/ 38.860.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the CAPES [PNPD]; Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPQ) [305.959/2016,306.415/2012–7,456.180/2014-1]; São Paulo Research Foundation Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) [2013/26532-9]; Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) [PROAP - convênio 817.757/ 38.860].