• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tese de Doutorado
DOI
10.11606/T.3.2016.tde-14062016-150022
Documento
Autor
Nome completo
André Kubagawa Sato
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2015
Orientador
Banca examinadora
Tsuzuki, Marcos de Sales Guerra (Presidente)
Araujo, Silvio Alexandre de
Gomes, António Miguel da Fonseca Fernandes
Pinheiro, Plácido Rogerio
Queiroz, Thiago Alves de
Título em português
Solução rasterizada para o problema de empacotamento de fita irregular utilizando a Montanha Voronoi.
Palavras-chave em português
Empacotamento e cobertura
Heurística
Otimização combinatória
Resumo em português
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.
Título em inglês
Raster solution for the irregular nesting problem using the Voronoi Mountain.
Palavras-chave em inglês
Combinatorial optimization
Heuristic
Packing
Resumo em inglês
Irregular nesting belongs to the area of cutting and packing problems and are employed in the textile, wood and shipbuilding industries. The problem consists in determining a configuration for a set of irregular items which minimizes the length of the rectangular container in which the layout is located. The solution must be feasible, i.e., items must not overlap nor protrude the container walls. Due to practical reasons, up to four orientations are allowed for an item. The volume of wasted material is directly affected by the quality (density) of the layout. Thus, an efficient solution produces a positive economic and environmental impact. In this work, the objective is to automatically obtain layouts such that their density and the performance of the algorithm are competitive with other solutions in literature. So as to achieve this goal, two approaches are proposed. The first method uses a special sequential placement heuristic such that the algorithm maximizes exact placements, which consist of constrained positions for items. In general terms, a search is performed in the placement sequence in order to obtain a compact layout. In the second approach, which is the main subject of this work, raster methods are employed to guide the translation of items, which are free to move within the layout, and may overlap other items. The method is based on overlap minimization techniques, in which the objective is to eliminate the overlap in a fixed dimensions container. Both algorithms were tested using benchmark problems from the literature. The first strategy yielded unsatisfactory results, though it provided important information about the properties of exactly fitting placements. On the other hand, the main approach was able to produce competitive solutions. The performance was also compatible with other solutions, even in cases which the data volume was high. Moreover, as a future work, an extension for the algorithm can be developed such that items with generic geometry can be considered, which would be an important advance in research terms.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2016-06-15
 
AVISO: O material descrito abaixo refere-se a trabalhos decorrentes desta tese ou dissertação. O conteúdo desses trabalhos é de inteira responsabilidade do autor da tese ou dissertação.
  • Sato, A. K., Martins, T. C., and Tsuzuki, M. S. G. An Algorithm for the Strip Packing Problem Using Collision Free Region and Exact Fitting Placement [doi:10.1016/j.cad.2012.03.004]. Computer Aided Design [online], 2012, vol. 44, p. 766-777.
  • Sato, A. K., Tsuzuki, M. S. G., and Martins, T. C. Collision free region determination by modified polygonal Boolean operations [doi:10.1016/j.cad.2013.03.003]. Computer Aided Design [online], 2013, vol. 45, p. 1029-1041.
  • Sato, A. K., et al. Determination of Translations to Create Layouts with Exact Placements for Two Moveable Items [doi:10.3182/20120523-3-RO-2023.00097]. In 14th IFAC Symposium on Information Control Problems in Manufacturing, Bucareste, 2012. Proceedings of the 14th IFAC Symposium on Information Control Problems in Manufacturing.Bucareste : IFAC, 2012.
  • Sato, A. K., Martins, T. C., and Tsuzuki, M. S. G. Collision Free Region Determined Using Non-Regularized Boolean Operation and its Application in the Irregular Placement Problem [doi:10.2316/P.2012.777-026]. In The 15th IASTED International Conference on Artificial Intelligence and Soft Computing, Napoles, 2012. Proceedings of the IASTED International Conference (2012) Artificial Intelligence and Soft Computing ASC.Alberta : IASTED, 2012.
  • Sato, A. K., Martins, T. C., and Tsuzuki, M. S. G. Parallel Layout Construction Algorithm for Irregular Shape Packing Problems [doi:10.1109/SCIS-ISIS.2012.6505041]. In The 6th International Conference on Soft Computing and Intelligent Systems, Kobe, 2012. Proceedings of the 6th International Conference on Soft Computing and Intelligent Systems.Kobe : IEEE, 2012.
  • Sato, A. K., Martins, T. C., and Tsuzuki, M. S. G. Placement Heuristics for Irregular Packing to Create Layouts with Exact Placements for Two Moveable Items [doi:10.3182/20130522-3-BR-4036.00027]. In 11th IFAC Workshop on Intelligent Manufacturing Systems, São Paulo, 2013. Proceedings of the 11th IFAC Workshop on Intelligent Manufacturing Systems.São Paulo : IFAC, 2013.
  • Luna, M. L., et al. Intersection of Line Segments in a Discrete Domain. In XXII International Congress of Mechanical Engineering, Ribeirão Preto, 2013. Proceedings of the XXII International Congress of Mechanical Engineering.Rio de Janeiro : ABCM, 2013.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2019. Todos os direitos reservados.