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

Read full text Summarise with VIRAT
Authors: David Betoni, Fabio Henrique Perira
Cited by: 0
References: 9

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

Abstract

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.

Fields of Study & Subjects

Scheduling and Optimization Algorithms Advanced Manufacturing and Logistics Optimization Assembly Line Balancing Optimization

Publication details

Journal / source
Anais do ... Congresso Ibero-Latino-Americano de Métodos Computacionais em Engenharia
Volume
5
Publication date
18 March 2026
Language
EN