Aplicações de atribuição quadrática e projeto de layout

XXIV ENEGEP Florianópolis, SC, Brasil, 03 a 05 de novembro de 2004

Colônia de Formigas: Uma Abordagem Promissora para Aplicações de Atribuição Quadrática e Projeto de Layout
Leandro dos Santos Coelho (PUCPR) [e-mail] Roberto Fernandes Tavares Neto (PUCPR) [e-mail]

Resumo Um procedimento de otimização baseado em colônia de formigas é uma meta-heurística baseada em uma população de agentes (formigas) que faz uso de mecanismos de adaptação, cooperação e paralelismo visando a obtenção de um procedimento para resolução de problemas de otimização combinatória, estes relevantes para resolução de problemas de projeto de fábrica e layout. Este artigo apresenta um estudo do projeto dos parâmetros de configuração do algoritmo de colônia de formigas. Os estudos de caso de otimização abordados neste artigo são problemas de atribuição quadrática (quadratic assignment problems) propostos por Nugent, Vollmann e Ruml, em 1968. Os resultados de simulação mostraram que a otimização por colônia de formigas pode ser uma abordagem promissora e competitiva com outras apresentadas na literatura para resolução de problemas de atribuição quadrática de pequeno porte desde que a colônia de formigas seja projetada de forma apropriada. Palavras chave: problema de atribuição quadrática, pesquisa operacional, colônia de formigas, otimização de sistemas produtivos, métodos heurísticos. 1. Introdução O problema de atribuição quadrática ou quadratic assignment problem (QAP) é um problema relevante na teoria e na prática, implicando que, em geral, é um problema de difícil solução (que caracterizam-se por serem problemas do tipo NP-Hard), ou seja, não existe algoritmo capaz de encontrar a solução ótima de um problema de grandes proporções em tempo polinomial. O QAP de ordem n consiste de procurar pela melhor alocação de n facilidades para as n locações (ou localizações), onde o termo atividade e localização devem ser considerados em seu sentido mais geral. O QAP foi