Algoritmos evolutivos aplicados aos problemas de leiaute de facilidades com áreas diferentes e escalonamento de tarefas sem espera

Abstract

Este trabalho aborda os seguintes problemas: Problema Quadrático de Alocação (PQA), Problema de Leiaute de Facilidades com Áreas Diferentes (PLFAD) e o Problema Job Shop Sem Espera (PJSSE). O PQA é um clássico problema de otimização combinatória, cujo objetivo é minimizar a soma das distâncias entre pares de locais distintos, ponderadas pelos fluxos entre as facilidades neles alocadas. O objetivo desta parte do trabalho é investigar técnicas heurísticas da literatura com base num conjunto de instâncias de referência do PQA. Os experimentos relatadosenvolveramAlgoritmosMeméticos(AM),técnicasdediversidadeadaptativa,algoritmos ILS (Iterated Local Search), busca locais 2-exchange e cadeia de ejeção (Ejection Chain). Doze algoritmos foram testados em 37 instâncias de referência obtidas da QAPLIB levando à escolha da combinação de técnicas mais adequada ao problema. A partir das observações obtidas do estudo anterior, decidiu-se abordar o PLFAD, de natureza semelhante ao PQA. No PLFAD, o objetivo é dimensionar e localizar facilidades retangulares em um espaço ilimitado e contínuo, sem sobreposição, de modo a minimizar a soma das distâncias entre facilidades ponderada pelos fluxos de manuseio de material. Porém, a pesquisa mostrou que devido a estrutura amarrada apresentada pelas soluções do PLFAD, métodos tradicionais de busca local tornam o problema caro computacionalmente, principalmente pelo tratamento da inviabilidade, devido a sobreposição. Duas abordagens algorítmicas são então introduzidas para tratar o problema: um Algoritmo Genético (GA) básico e um GA combinado com uma estratégia de decomposiçãoviadesconstruçãoereconstruçãoparcialdasolução. Paradecomporeficientemente o problema, uma estrutura especial é imposta às soluções impedindo que as facilidade cruzem os eixos X ou Y. Embora esta restrição possa deteriorar o valor da melhor solução encontrada, ela também aumenta muito a capacidade de busca do método em problemas de médio e grande porte. Comomostradopelosexperimentos,oalgoritmoresultanteproduzsoluçõesdealtaqualidadepara doisgruposdeinstânciasclássicasdaliteratura,melhorando6das8melhoressoluçõesconhecidas do primeiro grupo e todas as instâncias de médio e grande porte do segundo grupo. Para algumas das maiores instâncias do segundo grupo, com 90 ou 100 facilidades, a melhora média das soluções ficou em torno de6%ou7%quando comparado aos algoritmos anteriores, com menor tempo de CPU. Para tais instâncias, métodos exatos atuais são impraticáveis. Finalmente é apresentado o PJSSE, escolhido devido às suas soluções apresentarem uma natureza semelhante àquelas do PLFAD. Uma algoritmo baseado em GA, cuja construção da solução é efetuada por um algoritmo guloso eficiente, é proposto para resolver instâncias de referência da literatura obtendo resultados promissores e com menor tempo computacional comparado com abordagens anteriores, principalmente em instâncias de grande porte.