Scheduling in semi parallel flow shop with a final synchronizing operation - Irce Fernandes Gomes Guimaraes (2019)
Este estudo trata de uma variante do problema do flow shop motivado por uma situação prática. Neste ambiente, existe uma linha de montagem composta por duas semi-linhas paralelas em operações independentes. A primeira semi-linha tem número q1 de máquinas e a segunda tem número q2 de máquinas. No final das duas semi-linhas, existe uma máquina encarregada pela união dos semi-produtos manufaturados pelas duas semi-linhas. Cada semi-linha é dedicada a diferentes tarefas, uma vez que cada tarefa exige operações em cada máquina das semi-linhas com diferentes tempos de processamento. As tarefas de uma semi-linha não dependem da conclusão das tarefas da outra semi-linha, de modo que uma tarefa é processada em paralelo em cada semi-linha. A sequência das tarefas em cada semilinha paralela deve ser a mesma, embora a primeira tarefa em cada semi-linha não precise iniciar ao mesmo tempo. A operação de sincronização final só pode ser iniciada quando as operações nas semi-linhas forem concluídas. A solução para este problema é determinar uma possível sequência de tarefas que otimizem uma dada medida de desempenho. Nesse sentido, o objetivo deste estudo é modelar o flow shop no ambiente de produção proposto e resolvê-lo com algoritmos especializados. Em uma primeira abordagem, definiu-se um modelo de programação linear inteira mista, e em vista da complexidade do problema, ele também foi resolvido pela regra de Johnson, heurísticas de NEH e pelas metaheurísticas Iterated Local Search-(ILS), Simulated Annealing-(SA) e Greedy Randomized Adaptive Search Procedure-(GRASP). Finalmente, uma extensa experimentação computacional foi realizada e uma comparação entre os métodos propostos foi feita. O método híbrido que utilizou o algoritmo NEH com a metaheurística GRASP apresentou qualidade superior aos outros métodos propostos.