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

Abstract

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.

This paper addresses the Assembly flowshop problem with three stages, where there are m parallel machines in the first stage, a transport machine in the second period and an assembly machine in the third stage. In the first stage, different parts of the product are produced independently in parallel machines. In the second stage, the manufactured parts are collected and transferred to the next stage. In the third stage the parts are assembled to give the final product. This problem has many applications in manufacturing industries and belongs to the class of combinatorial optimization problems NP-hard. In order to solvie this problem, mono- objective and multi-objective approach are proposed, where the first aims to find a n task sequence that minimizes the total tardiness, while the second attempts to find a sequence for simultaneous minimization of the total flow time and the total tardiness. For the mono-objective approach is proposed four different algorithms are proposed based on metaheuristics: GRASP- RVND, which is the combined application of metaheuristics GRASP (Greedy Randomized Adaptive Search Procedure) and RVND (Random Variable Neighborhood Descent), the ILS (Iterated Local Search ), IG (Iterated Greedy) and the ILS-IG (which corresponds to the combined application of the metaheuristics ILS and IG). We performed computational experiments to compare the efficiency of the proposed algorithms, and the obtained results are compared with the results of a PSA (Simulated Annealing Hybrid) literature algorithm. In our experiments we use small and large instances. The results of the algorithms were also compared with the results obtained by an Integer Linear Programming Model (MILP) for small instances. The results were analyzed statistically and the tests show that the proposed algorithms are superior to PSA in all classes of instances. For a multi-objective approach, we propose two hybrid genetic algorithms, obtained from the combined application of the metaheuristics NSGA-II (Non-dominated Sorting Genetic Algorithm-II) and IG. One of these algorithms uses a local search for improve the dominant solutions. The algorithms were compared with the traditional algorithm NSGA-II. The statistical analysis applied to the obtained results shows that there was a great improvement with relation to the results generated by the NSGA-II.