Multi-population genetic algorithm with ER network for solving flexible job shop scheduling problems.

Area of Science:

• Computational Intelligence
• Optimization Algorithms
• Operations Research

Background:

• Standard genetic algorithms (GA) often suffer from premature convergence, limiting their effectiveness.
• Existing multi-population GAs typically overlook the impact of network structures and gene propagation rates on performance.
• The flexible job shop scheduling problem (FJSP) presents complex optimization challenges.

Purpose of the Study:

• To propose a novel multi-population GA incorporating an ER network (MPGA-ER) to address premature convergence.
• To investigate the influence of sub-population number, sub-population size, and gene propagation rate on MPGA-ER performance.
• To evaluate MPGA-ER's effectiveness using the flexible job shop scheduling problem (FJSP).

Main Methods:

• Development of a multi-population genetic algorithm with an Erdős-Rényi (ER) network structure (MPGA-ER).
• Systematic analysis of sub-population number, sub-population size, and gene propagation rate effects on MPGA-ER performance.
• Performance evaluation based on average optimal value and success rate for a fixed total individual number (TIN) in FJSP.

Main Results:

• MPGA-ER demonstrates significant performance improvements over traditional GA.
• Optimal performance is achieved with a specific sub-population number; exceeding this leads to rapid decline.
• Increasing sub-population size initially boosts performance, then plateaus.
• Gene propagation rate influences performance, with an initial rapid increase followed by a slow decrease.

Conclusions:

• The proposed MPGA-ER effectively mitigates premature convergence and enhances optimization performance.
• Parameter tuning, particularly sub-population size and gene propagation rate, is crucial for maximizing MPGA-ER effectiveness.
• MPGA-ER proves effective in solving complex FJSP instances, outperforming other existing algorithms.