A Modified Genetic Algorithm with Local Search Strategies and Multi-Crossover Operator for Job Shop Scheduling...

Area of Science:

• Operations Research
• Computer Science
• Artificial Intelligence

Background:

• NP-Hard problems, such as the Job Shop Scheduling Problem (JSSP), often lack analytical solutions, necessitating meta-heuristic approaches.
• Genetic Algorithms (GAs) are common for JSSP but suffer from premature convergence and local optima.
• Existing research focuses on local search and improved GA operators to enhance performance.

Purpose of the Study:

• To propose a novel Genetic Algorithm (GA) designed to overcome the limitations of traditional JSSP solution methods.
• To enhance the effectiveness of meta-heuristic approaches for NP-Hard optimization problems.

Main Methods:

• Development of a new GA incorporating a generalized massive local search operator.
• Integration of local search strategies into the traditional mutation operator.
• Introduction of a novel multi-crossover operator, ensuring all operators possess local search capabilities.

Main Results:

• The proposed GA demonstrated superior effectiveness in solving 58 JSSP instances across three case studies.
• The enhanced operators successfully mitigated issues of premature convergence and local optima.
• The new method outperformed traditional JSSP solution techniques.

Conclusions:

• The developed GA offers a more robust and effective approach to solving the Job Shop Scheduling Problem.
• The integration of advanced local search functionalities significantly improves meta-heuristic performance for NP-Hard problems.
• This research contributes a valuable advancement in the field of optimization and scheduling.