Massive parallelization accelerated solution for the 2D irregular nesting problem

摘要

One important field of operations research are the cutting and packing problems, which often have significant environmental and economical impacts and are reoccurring in the wood, textile and shipbuilding industry, among others. They consist of generating a layout of non-overlapping items which are bounded by a single or multiples larger objects, usually referred as containers. The bi-dimensional irregular nesting involves placing irregular shaped items inside a single rectangular container with variable length. Due to the geometric complexity, heuristic solutions are often employed to solve instances with more than a dozen items. Relaxing the overlap constraint is an efficient strategy to obtain more compact layout, however it is usually computationally costly. If the placement is restricted by a grid of points, known as the dotted board model, the overlap evaluation can be reduced to matrix operations, which can be accelerated by massive parallelization using the graphics processing unit (GPU). So as to aid the overlap evaluation and minimization, the obstruction map is adopted as a geometric tool to perform the guided local search. In this work, a parallel GPU implementation of the obstruction map is compared with the serial variant. Results show acceleration of over 10 times for cases with a very refined placement grid. Moreover, analysis of tests with 12 benchmark cases gives guidelines to determine whether it is beneficial to use the parallel implementation for a generic instance.