Parallel Layout Construction Algorithm for Irregular Shape Packing Problems

Autor(es)

Sato, Andre Kubagawa ; Martins, Thiago de Castro ; Guerra Tsuzuki, Marcos de Sales ; IEEE

• Tipo de documento: Artigo Científico
• Fonte: 6TH INTERNATIONAL CONFERENCE ON SOFT COMPUTING AND INTELLIGENT SYSTEMS, AND THE 13TH INTERNATIONAL SYMPOSIUM ON ADVANCED INTELLIGENT SYSTEMS; v. N/A, p. 6-pg., 2012-01-01.

Resumo

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. (AU)

• Processo FAPESP: 10/18913-4 - Estudo sobre translações aplicadas a polígonos de obstrução para que operações booleanas não regularizadas criem regiões de obstrução degeneradas
• Beneficiário: Marcos de Sales Guerra Tsuzuki
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 10/19646-0 - Translações Aplicadas a Polígonos de Obstrução para que Regiões Livres de Colisão Degeneradas Sejam Criadas por Operações Booleanas Não Regularizadas
• Beneficiário: André Kubagawa Sato
• Modalidade de apoio: Bolsas no Brasil - Doutorado