HEURÍSTICAS PARA PROBLEMAS DE SEQUENCIAMENTO DA PRODUÇÃO EM AMBIENTE OPEN SHOP

II Encontro de Iniciação Acadêmica

Vitor Hugo Lopes Costa Lima, Bruno de Athayde Prata

Na indústria, um menor tempo de produção acarreta em menores gastos; assim, métodos para otimizar o tempo dos processos industriais operados por máquinas são de grande importância. Os problemas de sequenciamento são uma classe de problemas de Pesquisa Operacional e dentro desse campo existem diversas formas de organizar as operações em máquinas. O Open Shop Scheduling Problem é um ambiente de produção realizada por m máquinas, onde todas as máquinas podem realizar todas as n tarefas existentes, em que cada máquina possui um tempo específico para realizar cada tarefa. Tendo em vista que o Open Shop é um problema pertencente à classe NP-Completo, o uso de algoritmos aproximativos é de grande valia para obtenção de soluções de qualidade em tempo computacional admissível. O objetivo deste trabalho é avaliar o desempenho de heurísticas para resolução do Open Shop considerando como função de avaliação a minimização do tempo total de processamento onde todas as máquinas realizam todas as tarefas (makespan). Para esse trabalho foi utilizado a linguagem de programação Python e através dela foram implementados os algoritmos de três métodos heurísticos existentes na bibliografia. Foram testadas os conjuntos de instâncias propostos por Guerét &amp; Prins e Taillard. Os resultados dos algoritmos implementados foram comparados com as melhores soluções conhecidas, reportadas na literatura. O método que gerou resultados mais próximos das melhores soluções conhecidas foi a heurística LAPT (Longest Alternate Processing Time first), com um desvio percentual relativo médio de 12,6%. Selecionado esse método, poderá ele ser usado para gerar a solução inicial de algoritmos mais eficazes, como metaheurísticas, de forma a obter melhores resultados.

Palavras-chave: Sequenciamento da Produção. Pesquisa Operacional. Otimização Combinatória. Open Shop.

Encontros Universitários da UFC, Fortaleza, v. 2, 2017

5200