Repositório de Outras Coleções Abertas (ROCA): Desenvolvimento de um algoritmo genético para resolução do problema de sequenciamento de produção em job shops flexíveis
Use este identificador para citar ou linkar para este item: http://repositorio.roca.utfpr.edu.br/jspui/handle/1/10534
Título: Desenvolvimento de um algoritmo genético para resolução do problema de sequenciamento de produção em job shops flexíveis
Referência: RIGO, Paola Mantoani. Desenvolvimento de um algoritmo genético para resolução do problema de sequenciamento de produção em job shops flexíveis. 2018. 59 f. Trabalho de Conclusão de Curso (Graduação) - Universidade Tecnológica Federal do Paraná, Londrina, 2018.
Resumo: O sequenciamento de produção é uma atividade essencial ao processo produtivo, pois é responsável por indicar a sequência de pedidos a serem produzidos, e as máquinas às quais os mesmos são designados. Um dos tipos de problemas de sequenciamento mais comum é chamado problema do sequenciamento job shop flexível (FJSP), no qual existem m máquinas disponíveis para sequenciar n ordens de produção, em que o problema é dividido em duas partes: indicar a sequência de produção dos itens, e eleger qual máquina, dentre as disponíveis, será responsável por realizar cada uma das operações. Uma das formas de encontrar soluções para o problema, é utilizando uma metaheurística chamada Algoritmos Genéticos (AG), a qual se baseia no cruzamento genético dos indivíduos, para gerar filhos com modificações genéticas. Dessa forma, foi desenvolvido um algoritmo para solução do FJSP, utilizando os princípios de AG, testando sua eficácia com a solução de diversas instâncias encontradas na literatura. Após o teste do algoritmo, constatou-se que este é capaz de encontrar soluções competitivas em pouco tempo computacional, e para instâncias pequenas e pouco complexas, encontra soluções ótimas; porém, encontra resultados distantes do ótimo global para problemas mais complexos, indicando que necessita de algumas modificações para melhorar seu desempenho. Diante disso, foi feita uma modificação para melhoria das soluções no algoritmo, a qual apresentou melhorias satisfatórias nos testes das instâncias, e foram propostas diversas melhorias que podem ser aplicadas futuramente.
Abstract: Production scheduling is an essential activity in the production process, as it is responsible for indicating the sequence of orders to be produced, and the machines to which they will be assigned. One of the most common types of scheduling problems is called flexible job shop problem (FJSP), in which there are 𝑚 machines available to sequence 𝑛 production orders, where the problem is divided into two parts: indicate the production sequence of the items, and select which machine, among those available, will be responsible for performing each one of the operations. One of the ways to find solutions to this problem is to use a metaheuristic called Genetic Algorithms (GA), which is based on the genetic crossing of individuals, to generate children with genetic modifications. For this purpose, an algorithm for FJSP solution was developed, using GA principles, testing its effectiveness with the solution of several instances found in the literature. After testing the algorithm, it was found that it is able to find competitive solutions in a short computational time, and for small and no complex instances, it finds optimal solutions; however, it finds results far from the global optimum for more complex problems, indicating that it needs some modifications to improve its performance. Therefore, a modification was made to improve the solutions in the algorithm, which presented satisfactory improvements during the tests of the instances, and several improvements were proposed that can be applied in the future.