Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/13102
Title in Portuguese: Problemas de otimização combinatória: uma abordagem distribuída
Author: Vieira, Francisca Emanuelle Rocha
Silva, José Lassance de Castro
Keywords: Problema de otimização combinatória
Computação distribuída
Algoritmos genéticos
Issue Date: 2-Sep-2008
Publisher: Simpósio Brasileiro de Pesquisa Operacional
Citation: Vieira, F. E. R. ; SILVA, J. L. C. Problemas de otimização combinatória: uma abordagem distribuída. In: SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL, 40., 2008, João Pessoa. Anais... João Pessoa: 2008. p. 2842-49.
Abstract in Portuguese: O Problema atacado neste artigo trata da resolução dos Problemas de Otimização Combinatória, representado aqui pelo Problema de Corte e Empacotamento Tri-Dimensional cujo objetivo é empacotar ortogonalmente um conjunto de itens (caixas retangulares) dentro de um número mínimo de bins (conteineres). O Problema é NP-difícil no sentido forte e extremamente difícil de ser resolvido na prática. Apresentamos um algoritmo de computação paralela para resolver o problema específico que pode ser aplicado sem nenhuma dificuldade na resolução dos Problemas de Otimização Combinatória. Duas meta-heurísticas foram usadas no modelo paralelo: AGEE e HPEE. AGEE é baseada nos Algoritmos Genéticos enquanto HPEE é uma heurística sofisticada que evita o travamento do método em um mínimo local. Ambos os algoritmos geram diversificação na busca dentro do conjunto de soluções viáveis. No modelo usamos também uma heurística HVEE que faz a intensificação na melhor solução corrente de cada iteração. Usamos critérios para empacotar todos os itens com estabilidade estática. Extensivos experimentos computacionais são descritos para instâncias com até 90 itens e os resultados são comparados com aqueles encontrados da literatura.
Abstract: The problem addressed in this paper is that of solver the combinatorial Optimization Problems, represented by 3D Bin Packing Problem that orthogonally packing a given set of box-shaped items into the minimum number of three-dimensional rectangular and equal bins. The problem is NP-hard in the strong sense and extremely difficult to be solved in the practice. We present a parallel computer algorithm to solver the problem. Two metaheuristics went used in the parallel model, AGEE and HPEE. AGEE is based in the genetics algorithms while HPEE is a sophisticated heuristics that avoids to join in local minimum, both algorithms generating diversification on the search of the feasible solution. In the model, we also use an heuristic HVEE which make a intensification in the best current solution of each iteration. We used criterions to pack every items with static stability. Extensive computational experiments are reported for instances with up to 90 items, and the results are compared with those obtained from the literature.
URI: http://www.repositorio.ufc.br/handle/riufc/13102
metadata.dc.type: Artigo de Evento
Appears in Collections:GESLOG - Trabalhos apresentados em eventos

Files in This Item:
File Description SizeFormat 
2008_eve_jlcsilva.pdf368,11 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.