Actas de congresos
Parallel Layout Construction Algorithm for Irregular Shape Packing Problems
Fecha
2014-03-14Autor
Sato, André Kubagawa
Martins, Thiago de Castro
Tsuzuki, Marcos de Sales Guerra
Institución
Resumen
Cutting and packing problems arise in a variety of
industries, including garment, wood and shipbuilding. Irregular
shape packing is a special case which admits irregular items and
is much more complex due to the geometry of items. In order
to ensure that items do not overlap and no item from the layout
protrudes from the container, the collision free region concept
was adopted. It represents all possible translations for a new
item to be inserted into a container with already placed items.
To construct a feasible layout, collision free region for each item
is determined through a sequence of Boolean operations over
polygons. In order to improve the speed of the algorithm, a
parallel version of the layout construction was proposed and it
was applied to a simulated annealing algorithm used to solve bin
packing problems. Tests were performed in order to determine
the speed improvement of the parallel version over the serial algorithm