Aplicação de metaheurísticas para o problema de programação da produção em ambiente Assembly Flowshop com três estágios e tempos de preparação dependentes da sequência

• Ano de defesa: 2015
• Autor(a) principal: Campos, Saulo Cunha
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Viçosa
• Palavras-chave em Português: Assembler (Linguagem de programação de computador); Algorítmicos; Metaheurísticas; Ciência da Computação
• Link de acesso: http://www.locus.ufv.br/handle/123456789/6666

Este trabalho aborda o problema Assembly flowshop de três estágios, onde existem m máquinas paralelas no primeiro estágio, uma máquina de transporte no segundo estágio e uma máquina de montagem no terceiro estágio. No primeiro estágio, diferentes partes do produto são fabricadas de forma independente nas máquinas paralelas. No segundo estágio, as peças fabricadas são coletadas e transferidas para o próximo estágio. No terceiro estágio as peças são montadas obtendo o produto final. Este problema possui muitas aplicações em indústrias de manufatura e pertence a classe de problemas de otimização combinatória NP-difícil. Para resolução deste problema é realizada uma abordagem mono-objetivo e uma multi-objetivo, onde a primeira visa encontrar uma sequência de n tarefas que minimize o atraso total, enquanto a segunda busca encontrar uma sequência de n tarefas para minimização simultânea do tempo total de fluxo e do atraso total. Para abordagem mono-objetivo são propostos quatro diferentes algoritmos baseados nas metaheurísticas: o GRASP-RVND, que corresponde a aplicação conjunta das metaheurísticas GRASP (Greedy Randomized Adaptive Search Procedure) e RVND (Random Variable Neighborhood Descent), o ILS (Iterated Local Search), o IG (Iterated Greedy) e o ILS-IG (que corresponde a aplicação conjunta das metaheurísticas ILS e IG). Foram realizados experimentos computacionais para comparar a eficiência dos algoritmos e os resultados obtidos são comparados com os resultados de um algoritmo PSA (Simulated Annealing Híbrido) da literatura. Nos experimentos foram usadas instâncias de pequeno e grande porte. Os resultados dos algoritmos também foram comparados com os resultados obtidos por um modelo de Programação Linear Inteira (MILP) para instâncias de pequeno porte. Os resultados foram analisados estatisticamente e os testes mostram que os algoritmos propostos foram superiores ao PSA em todas as classes de instâncias. Para a abordagem multiobjetivo são propostos dois algoritmos genéticos híbridos, obtidos a partir da aplicação combinada das metaheurísticas NSGA-II (Non-dominated Sorting Genetic Algorithm-II) e IG, sendo que, um deles utiliza uma busca local para melhorar as soluções dominantes. Os algoritmos foram comparados com o algoritmo tradicional NSGA-II. A análise estatística aplicada sobre os resultados obtidos mostra que houve grande melhoria em relação aos resultados gerados pelo NSGA-II.