Abordagem de busca local ativa em soluções não atrasadas para o problema de job shop scheduling baseado no algoritmo genético de chaves aleatórias

Abstract

In this work, a computational approach is presented for solving production task se-quencing problems, known as Job Shop Scheduling. It is an optimization problem that seeks to define the ideal sequence of operations for different tasks (jobs) across a variety of machines, with the objective of minimizing the total production time (makespan). In current literature, the use of metaheuristics has been widely adopted to solve this type of problem, especially Genetic Algorithms, as they enable the achievement of high-quality solutions. In general, however, metaheuristics require the joint use of solution refinement techniques. Among these techniques, Local Search methods stand out, aiming to improve the results obtained by the metaheuristics. This work fits into this context by proposing a two-stage hybrid approach. Initially, a variation of the Genetic Algorithm, known as the Random-Key Genetic Algorithm (RKGA), is used to generate a high-quality initial solu¬tion. Then, after the conclusion of the evolutionary process—that is, without incorporating local search mechanisms during the execution of the genetic algorithm—an independent refinement stage based on Local Search is applied. This second stage acts on the solution generated by the RKGA, exploring the reduced space of non-delay solutions, with the ob¬jective of improving the total production time. The results, obtained from standardized benchmark problem sets widely used in the literature, show that suboptimal non-delay solutions are frequently improved by the proposed refinement method, achieving results superior to those of the conventional genetic algorithm implementation. It is concluded, therefore, that the obtained results validate the proposed approach, demonstrating its effectiveness in achieving more efficient solutions.