Solução rasterizada para o problema de empacotamento de fita irregular utilizando a Montanha Voronoi.

Autor(es)

André Kubagawa Sato

• Tipo de documento: Tese de Doutorado
• Imprenta: São Paulo.
• Instituição: Universidade de São Paulo (USP). Escola Politécnica (EP/BC)
• Data de defesa: 2015-08-14

Membros da banca

Marcos de Sales Guerra Tsuzuki; Silvio Alexandre de Araujo; António Miguel da Fonseca Fernandes Gomes; Plácido Rogerio Pinheiro; Thiago Alves de Queiroz

• Orientador: Marcos de Sales Guerra Tsuzuki; Thiago de Castro Martins

Resumo

O empacotamento irregular de fita é um grupo de problemas na área de corte e empacotamento, cuja aplicação é observada nas indústrias têxtil, moveleira e construção naval. O problema consiste em definir uma configuração de itens irregulares de modo que o comprimento do contêiner retangular que contém o leiaute seja minimizado. A solução deve ser válida, isto é, não deve haver sobreposição entre os itens, que não devem extrapolar as paredes do contêiner. Devido a aspectos práticos, são admitidas até quatro orientações para o item. O volume de material desperdiçado está diretamente relacionado à qualidade do leiaute obtido e, por este motivo, uma solução eficiente pressupõe uma vantagem econômica e resulta em um menor impacto ambiental. O objetivo deste trabalho consiste na geração automática de leiautes de modo a obter níveis de compactação e tempo de processamento compatíveis com outras soluções na literatura. A fim de atingir este objetivo, são realizadas duas propostas de solução. A primeira consiste no posicionamento sequencial dos itens de modo a maximizar a ocorrência de posições de encaixe, que estão relacionadas à restrição de movimento de um item no leiaute. Em linhas gerais, várias sequências de posicionamentos são exploradas com o objetivo de encontrar a solução mais compacta. Na segunda abordagem, que consiste na principal proposta deste trabalho, métodos rasterizados são aplicados para movimentar itens de acordo com uma grade de posicionamento, admitindo sobreposição. O método é baseado na estratégia de minimização de sobreposição, cujo objetivo é a eliminação da sobreposição em um contêiner fechado. Ambos os algoritmos foram testados utilizando o mesmo conjunto de problemas de referência da literatura. Foi verificado que a primeira estratégia não foi capaz de obter soluções satisfatórias, apesar de fornecer informações importantes sobre as propriedades das posições de encaixe. Por outro lado, a segunda abordagem obteve resultados competitivos. O desempenho do algoritmo também foi compatível com outras soluções, inclusive em casos nos quais o volume de dados era alto. Ademais, como trabalho futuro, o algoritmo pode ser estendido de modo a possibilitar a entrada de itens de geometria genérica, o que pode se tornar o grande diferencial da proposta. (AU)

• 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