Por favor, use este identificador para citar o enlazar este ítem: http://repositorio.ufc.br/handle/riufc/13102
Tipo: Artigo de Evento
Título : Problemas de otimização combinatória: uma abordagem distribuída
Autor : Vieira, Francisca Emanuelle Rocha
Silva, José Lassance de Castro
Palabras clave : Problema de otimização combinatória;Computação distribuída;Algoritmos genéticos
Fecha de publicación : 2-sep-2008
Editorial : Simpósio Brasileiro de Pesquisa Operacional
Citación : 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.
Resumen en portugués brasileño: 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
Aparece en las colecciones: GESLOG - Trabalhos apresentados em eventos

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
2008_eve_jlcsilva.pdf368,11 kBAdobe PDFVisualizar/Abrir


Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.