FSS em problemas de otimização com restrição – Aplicação em problemas de linhas de balanceamento (ALBP)

Resumo

Esse trabalho tem como objetivo aplicar o Fish School Search (FSS), desenvolvido na Universidade de Pernambuco, pelos professores Dr. Fernando Buarque de Lima Neto e Dr. Carmelo José Albanez Bastos Filho na solução de problemas em linhas de balanceamento conhecidos como Assembly Line Balancing Problems (ALBP). Tais problemas se encaixam na classe NP – hard de otimização de problemas combinatoriais e lidam com a alocação de tarefas ao longo das estações de trabalho de maneira que as relações de precedência não sejam violadas, e a função objetivo dada seja otimizada. Nesse trabalho, o foco foram os problemas pertencentes ao Simple Assembly Line Problem (SALBP), especificamente o SALBP–1 que tem como objetivo minimizar o número de estações com uma taxa de produção fixa. O Fish School Search é um algoritmo de busca inspirado no comportamento dos peixes enquanto procuram por comida. Três versões do FSS foram desenvolvidas visando o melhoramento do algoritmo original para situações ocasionadas pela natureza do problema, como a formação de platores.  As versões propostas foram: FSS Stagnation Avoidance Routine (FSS–SAR), FSS-NF (FSS–Normalized Feeding) e FSS-NPSS (FSS–Not Penalizing Static Success). O desempenho dos algoritmos propostos foi avaliado em comparação a técnicas já bastante conhecidas e consagradas na solução de problemas combinatoriais como o Genetic Algorithm (GA), Ant Colony Optimization (ACO) e o Particle Swarm Optimization (PSO). Com base na literatura revisada, esta é a primeira aplicação do FSS para resolver SALBP–1. Assim, não há nenhuma referência indicando os parâmetros estabelecidos a fim de aplicar o FSS nesse problema específico. Foi necessário fazer uma seleção de parâmetros e a metodologia escolhida para selecionar tais valores foi inspirada na técnica de análise fatorial com dois níveis. Seus testes envolveram simulações em MATLAB com diferentes instâncias de problemas, alternando o nível de dificuldade das soluções.  Após a primeira etapa de seleção de parâmetros, os algoritmos foram comparados entre si por meio de testes estatísticos como o ANOVA e o WILCOXON. Os critérios usados na análise dos resultados foram, além da própria função objetivo, o ‘smoothness’ e o número de iterações até a convergência. Especificamente em relação às versões do FSS, o FSS–SAR–NPSS, uma versão incluindo o comportamento elitista, bem como habilidades exploratórias, obteve melhor desempenho quando comparado com a versão original do algoritmo produzindo os melhores resultados em todas as três instâncias de problemas utilizados para a avaliação. No entanto, o FSS –SAR–NPSS não foi capaz de alcançar os melhores resultados obtidos pelo GA, ACO e PSO em alguns dos ensaios realizados. Quando comparado com o PSO, o FSS–SAR–NPSS foi capaz de atingir resultados equivalentes na instância mais difícil, mas uma convergência mais rápida na instância mediana indica que o algoritmo fica preso em um ótimo local. O mesmo pode ser observado na comparação com GA. Em geral, o FSS–SAR–NPSS converge mais rápido, mas não é capaz de atingir resultados equivalentes para a função objetivo. Para trabalhos futuros, esta comparação pode abranger mais metheurísticas em um conjunto mais amplo de instâncias de problemas, bem como versões de problemas, a fim de fornecer uma base de dados de referência confiável para a comunidade de pesquisa de linhas de balanceamento. PALAVRAS-CHAVES: Assembly Line; Fish School Search; Metheurísticas