• 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
 
 
Dissertação de Mestrado
DOI
10.11606/D.3.2011.tde-28022011-151901
Documento
Autor
Nome completo
André Kubagawa Sato
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2011
Orientador
Banca examinadora
Tsuzuki, Marcos de Sales Guerra (Presidente)
Carvalho, Jonas de
Martins, Thiago de Castro
Título em português
Proposta de algoritmo para a determinação da região livre de colisão e sua aplicação na solução de leiautes bidimensionais irregulares com recozimento simulado.
Palavras-chave em português
Empacotamento
Otimização
Recozimento simulado
Resumo em português
O problema de empacotamento consiste em arranjar um conjunto de itens em um contêiner, a fim de maximizar sua utilização. Este campo de estudos tem impacto em diversas indústrias, incluindo as indústrias têxtil, moveleira e naval. Neste trabalho, dois problemas de empacotamento de itens irregulares são estudados. O primeiro, chamado primal, é o caso em que os itens possuem rotação livre e o contêiner de dimensões fixas pode ser representado por um polígono qualquer, podendo ser não convexo. O segundo problema, denominado dual, consiste em posicionar os itens, que possuem apenas algumas orientações possíveis, em um contêiner retangular em que uma das dimensões é considerada infinita. Assim, o objetivo é obter o menor contêiner, variando a dimensão não fixa, no qual todos os itens podem ser posicionados sem sobreposição. Em ambos problemas, a solução é representada por uma lista ordenada de itens e uma regra de posicionamento é aplicada para se obter o leiaute. Neste caso, sobreposições não são permitidas. Para se garantir leiautes factíveis (sem sobreposição), é adotado o conceito de região livre de colisão. A região livre de colisão representa todas as translações possíveis para inserir um novo item em um contêiner com itens já posicionados. A região livre de colisão é obtida através de operações Booleanas envolvendo polígonos de obstrução e de posicionamento interno. Devido às propriedades dos conceitos envolvidos, o cálculo da região livre de colisão deve ser feito utilizando operações Booleanas não regularizadas. Um novo algoritmo de operação Booleana não regularizada de união e subtração é desenvolvido a partir da implementação de um algoritmo de operações Booleanas regularizadas. Um algoritmo de recozimento simulado é utilizado para controlar a posição, o ângulo (ou orientação) e a seqüência dos itens. Cada item só pode ser posicionado no vértice da região livre de colisão. Com a finalidade de melhorar o desempenho computacional do algoritmo, um método de paralelização do cálculo da região livre de colisão é proposto. Para comparação, são adotados dois algoritmos seriais. Através dos resultados, é possível afirmar que o algoritmo primal foi capaz de resolver problemas do tipo quebra-cabeça, incluindo contêineres convexos e com furos. O algoritmo apresentou melhora significativa no desempenho quando comparado com trabalhos anteriores. Para o caso dual foi proposto um algoritmo de dois níveis, em que o externo controla o comprimento do contêiner e o interno é semelhante ao primal. Este algoritmo foi testado com problemas existentes na literatura e apresentou soluções competitivas, obtendo alguns leiautes mais compactos. A paralelização apresentou ganho de desempenho apenas nos problemas com grande número de itens. Foi constatado que o custo computacional de operações Booleanas não regularizadas é fortemente dependente do número de vértices e intersecções dos polígonos de entrada da operação.
Título em inglês
Algorithm for the determination of the collision freee region and its application for the two-dimensional irregular packing problem using simulated annealing.
Palavras-chave em inglês
Optimization
Packing problems
Simulated annealing
Resumo em inglês
The irregular shape packing problem is an optimization problem that consists of arranging items on a container in order to maximize the utility rate of the sheet stock. This work investigates two problems. In the first problem, the single bin packing, the items can rotate freely and the container with fixed dimension can be any polygon, convex or non-convex. The second problem, the open dimension problem, consists of arranging items that have few admissible orientations in a container with fixed width and variable length. The objective is to find a feasible layout of the set of items that minimizes the length of the container. The solution is always represented as an ordered list of items to be packed and a placement heuristic is applied in order to generate a layout. To ensure feasible layouts, the concept of collision free region is adopted. It represents all the positions that a new item can be placed inside the container, without colliding with already placed items. The collision free region is obtained through non manifold Boolean operations applied to no-fit polygon and the inner-fit polygon. The simulated annealing algorithm controls the position, rotation and placement order of the items. Each item is is exclusively placed on collision free region's vertex. To improve the computational cost performance of the algorithm, a parallelization method to determine the collision free region is proposed. The speed of this algorithm is compared with two different serial methods of determing the collision free region. From the results, it can be observed that the solutions for the single bin packing problem are very competitive with previous works and can achieve optimal solution for puzzles with irregular shaped containers and containers with holes. The algorithm for the open dimension has two hierarchical levels: a core level with a simulated annealing algorithm, and the external level controlling the container length. This algorithm was tested with literature problems and obtained very competitive results, some which are more compact. The results showed that the parallelized version is better than the sequential approach only for datasets with very large number of items. The computational cost of the non manifold Boolean operation algorithm is strongly dependent on the number of vertices and intersections of the original polygons.
 
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
2011-04-19
 
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., et al. Translational Placement Using Simulated Annealing and Collision Free Region with Parallel Processing [doi:10.1109/INDUSCON.2010.5740071]. In 9th IEEE/IAS International Conference on Industry Applications, São Paulo, 2010. Proceedings of the 9th IEEE/IAS International Conference on Industry Applications.São Paulo : IEEE, 2010.
  • Sato, A. K., Martins, T. C., and Tsuzuki, M. S. G. A Simulated Annealing Based Algorithm with Collision Free Region for the Irregular Shape Packing Problem [doi:10.3182/20110828-6-IT-1002.00563]. In 18th IFAC Wold Congress, Milão, 2011. Proceedings of the 18th IFAC Wold Congress.Milão : IFAC, 2011.
  • Sato, A. K., Martins, T. C., and Tsuzuki, M. S. G. Irregular Placement Problem Solved with a 2-Level Algorithm and Collision Free Region. In 8th International Conference on Informatics in Control, Automation and Robotics, Noordwijkerhout, 2011. Proceedings of the 8th International Conference on Informatics in Control, Automation and Robotics., 2011.
  • Sato, A. K., Martins, T. C., and Tsuzuki, M. S. G. Rotational Placement using Simulated Annealing and Collision Free Region [doi:10.3182/20100701-2-PT-4011.00041]. In 10th IFAC Workshop on Intelligent Manufacturing Systems, Lisboa, 2010. 10th IFAC Workshop on Intelligent Manufacturing Systems (Preprints). : IFAC, 2010.
  • Sato, A. K., Martins, T. C., e Tsuzuki, M. S. G. Proposta de Algoritmo para o Problema de Empacotamento Bidimensional Utilizando Dois Níveis e Recozimento Simulado. In X Simpósio Brasileiro de Automação Inteligente, São João del Rei, 2011. Anais do X Simpósio Brasileiro de Automação Inteligente.São Paulo : SBA, 2011.
  • Sato, A. K., Martins, T. C., e Tsuzuki, M. S. G. Recozimento Simulado Aplicado ao Posicionamento Rotacional Utilizando Regiões Livres de Colisão. In XVIII Congresso Brasileiro de Automática, Bonito, 2010. Anais do XVIII Congresso Brasileiro de Automática.Bonito : SBA, 2010.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2019. Todos os direitos reservados.