Parallel Layout Construction Algorithm for\ud Irregular Shape Packing Problems

Cutting and packing problems arise in a variety of\ud industries, including garment, wood and shipbuilding. Irregular\ud shape packing is a special case which admits irregular items and\ud is much more complex due to the geometry of items. In order\ud to ensure that items do not overlap and no item from the layout\ud protrudes from the container, the collision free region concept\ud was adopted. It represents all possible translations for a new\ud item to be inserted into a container with already placed items.\ud To construct a feasible layout, collision free region for each item\ud is determined through a sequence of Boolean operations over\ud polygons. In order to improve the speed of the algorithm, a\ud parallel version of the layout construction was proposed and it\ud was applied to a simulated annealing algorithm used to solve bin\ud packing problems. Tests were performed in order to determine\ud the speed improvement of the parallel version over the serial algorithmA K Sato was supported by FAPESP (Grant 2010/19646-0). M S G Tsuzuki was partially supported by the CNPq (Grant 309.570/2010–7). This research was supported by FAPESP (Grants 2008/13127–2 and 2010/18913–4)