Desenvolvimento de um algoritmo genético para resolução do problema de sequenciamento de produção em job shops flexíveis

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 m machines available to sequence n 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.