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 (2011)
- Authors:
- Autor USP: SATO, ANDRÉ KUBAGAWA - EP
- Unidade: EP
- Sigla do Departamento: PMR
- Subjects: OTIMIZAÇÃO COMBINATÓRIA; EMPACOTAMENTO E COBERTURA; HEURÍSTICA
- Language: Português
- Abstract: 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 sequê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.
- Imprenta:
- Data da defesa: 02.02.2011
-
ABNT
SATO, André Kubagawa. 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. 2011. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2011. Disponível em: http://www.teses.usp.br/teses/disponiveis/3/3152/tde-28022011-151901/. Acesso em: 07 fev. 2026. -
APA
Sato, A. K. (2011). 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 (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/3/3152/tde-28022011-151901/ -
NLM
Sato AK. 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 [Internet]. 2011 ;[citado 2026 fev. 07 ] Available from: http://www.teses.usp.br/teses/disponiveis/3/3152/tde-28022011-151901/ -
Vancouver
Sato AK. 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 [Internet]. 2011 ;[citado 2026 fev. 07 ] Available from: http://www.teses.usp.br/teses/disponiveis/3/3152/tde-28022011-151901/ - Solução rasterizada para o problema de empacotamento de fita irregular utilizando a Montanha Voronoi
- A separation and compaction algorithm for the two-open dimension nesting problem using penetration-fit raster and obstruction map
- GPU implementation of an incomplete Cholesky conjugate gradient solver for a FEM-generated system using full kernel consolidation
- Multiresolution based overlap minimization algorithm for irregular packing problems
- Irregular packing overlap minimization using discrete voronoi mountain
- Análise de perfusão pulmonar em imagens de RM com elevada concentração de Gd
- Registro múltiplo de sequências temporais coronais e sagitais obtidas por ressonância magnética baseada em transformada de Hough
- Placement heuristics for irregular packing to create layouts with exact placements for two moveable items
- Mechanical Ventilator VENT19
- Development of a complete methodology to reconstruct, optimize, analyze and visualize Francis turbine Runners
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
