Programação da produção : desenvolvimento de um algoritmo de swarm intelligence para o problema do job shop scheduling

Abstract

Resumo : A Programação da Produção desempenha um papel crucial nas empresas, sendo responsável por definições importantes dentro do sistema produtivo: quanto, quando e em que ordem produzir, entre outras atribuições. Este estudo aborda o problema de scheduling em um ambiente produtivo no formato job shop, conhecido na literatura como o problema do Job Shop Scheduling. Devido à sua complexidade computacional, meta-heurísticas têm sido frequentemente empregadas para sua solução. No entanto, alcançar um desempenho comparável ao estado da arte depende de uma exploração eficiente das características do espaço de soluções deste problema. Algoritmos meta-heurísticos se destacam por desenvolverem diversas soluções e mesclar as melhores características de cada uma para a busca de uma solução com melhor fitness (características que se aproximem ao objetivo estabelecido) ao problema, no caso o menor makespan (instante de tempo que a última operação que compõe o roteiro produtivo foi concluída). Porém, métodos já existentes analisam apenas um cenário estático, dificultando sua aplicabilidade em contextos reais. Este estudo visou desenvolver um algoritmo de Swarm Intelligence (SI) para o problema do Job Shop Scheduling (JSSP), com o objetivo de buscar soluções de diversos cenários para prevenção de imprevistos que ocorrem no cotidiano das empresas. Foram gerados algoritmos para a busca de um ótimo local, servindo como um ponto de partida para o algoritmo de SI buscar novas soluções, um algoritmo no CPLEX para o JSSP foi desenvolvido para a comparação dos resultados junto ao ótimo global de todas as instâncias. Os efeitos alcançados pelo estudo foram satisfatórios, o algoritmo proposto obteve êxito no agendamento em todas as instâncias testadas, e, em comparação a outros algoritmos, apresentou um custo computacional baixo, exibindo um tempo de processamento de 0,3 segundos por iteração, considerado mediano em comparação à outros algoritmos e utilizando 17% da capacidade total do equipamento nas instâncias maiores, e apresentando o menor custo de processamento por iteração em comparação a todos os outros algoritmos testados ao longo da pesquisa requerendo apenas 0,00408 GB por iteração do processador

Abstract : Production Scheduling plays a crucial role in companies, as it is responsible for key decisions within the production system: how much, when and in what order to produce, among other tasks. This study addresses the scheduling problem in a job shop production environment, commonly referred to in the literature as the Job Shop Scheduling Problem. Due to its computational complexity, metaheuristics have often been employed to solve it. However, achieving performance comparable to the state of-the-art depends on efficiently exploring the solution space's characteristics for this problem. Metaheuristic algorithms stand out by generating diverse solutions and combining the best characteristics of each one to find a solution with improved fitness (features closer to the established objective). For this problem, the objective is the minimization of the makespan (the time when the last operation in the production sequence is completed). Nevertheless, existing methods typically analyze only a static scenario, which limits their applicability in real-world contexts. This study aimed to develop a Swarm Intelligence (SI) algorithm for the Job Shop Scheduling Problem (JSSP), in order to seek solutions for different scenarios to prevent unforeseen events that occur in the daily routine of companies. Algorithms were generated to search for a local optimum, serving as a starting point for the SI algorithm to search for new solutions, an algorithm in CPLEX for the JSSP was developed to compare the results with the global optimal of all instances. The effects of this study were satisfactory: the proposed algorithm successfully scheduled all tested instances. Compared to other algorithms, it showed a low computational cost, with a processing time of 0.3 seconds per iteration and using 17% of the system's total capacity in larger instances, demonstrating the lowest processing cost per iteration compared to all other algorithms tested throughout the research, requiring only 0.00408 GB of processor memory per iteration