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

Abstract

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 & 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.