Active Local Search Approach in Non-Delayed Solutions for the Job Shop Scheduling Problem

Resumo

This paper presents a computational approach for solving task sequencing problems in production environments, known as the Job Shop Scheduling Problem (JSSP). This problem is recognized as difficult within the field of Operations Research and is classified as NP-hard, with direct applications in the optimization of production processes. In the current literature, metaheuristics have been widely used to address this problem, particularly Genetic Algorithms, as they enable the discovery of high-quality solutions with acceptable computational cost. Generally, however, metaheuristics require the combined use of solution refinement techniques, known as local search methods. While these techniques enhance the performance of metaheuristics, they also increase the computational cost of the approach. This work contributes to this context by proposing a method to refine solutions obtained through the random-key genetic algorithm (RKGA). The RKGA is configured so that the search for a solution occurs solely within the space of non-delayed solutions, which is considerably smaller than the space of active solutions. The best solutions found are subsequently refined using a mechanism that identifies non-critical operations and introduces incremental delays to them. The initial search by RKGA within the reduced space of non-delayed solutions allows for a reduction in computational cost, followed by a refinement process in which small delays are introduced in selected operations to improve the makespan (total execution time). Results using classical academic benchmarks—particularly those defined by Fisher and Thompson (1963) and Lawrence (1984)—show that suboptimal non-delayed solutions are often improved through the proposed refinement method, achieving better results than conventional Genetic Algorithm implementations. Therefore, it is concluded that the results obtained from this set of benchmark instances validate the proposed approach, demonstrating its superiority in obtaining more efficient outcomes.