An improved genetic algorithm with dynamic neighborhood search for job shop scheduling problem

Area of Science:

• Operations Research
• Computer Science
• Artificial Intelligence

Background:

• The job shop scheduling problem (JSP) is a complex combinatorial optimization challenge with significant practical implications.
• Minimizing the makespan (total time to complete all jobs) is a primary objective in JSP.

Purpose of the Study:

• To introduce an Improved Genetic Algorithm (IGA) designed to effectively solve the job shop scheduling problem.
• To enhance the performance of genetic algorithms for JSP by incorporating dynamic neighborhood search and novel genetic operators.

Main Methods:

• Development of an IGA incorporating dynamic neighborhood search.
• Introduction of an idle time-based inserted operation during decoding.
• Presentation of an improved Permutation with Operations Crossover (POX) operator.
• Design of a novel mutation operation for neighborhood solution exploration.
• Implementation of a new genetic recombination strategy using a dynamic gene bank.
• Application of an elite retention strategy.

Main Results:

• The IGA was evaluated using several standard JSP benchmarks.
• Computational results indicate that the IGA achieves promising and competitive makespan minimization outcomes.
• The proposed enhancements contribute to improved performance in solving JSP.

Conclusions:

• The developed IGA offers an effective approach for addressing the job shop scheduling problem.
• The novel components of the IGA, including dynamic neighborhood search and improved genetic operators, enhance its problem-solving capabilities.
• The algorithm's performance on benchmark instances validates its potential for practical applications in scheduling.