Research on multi-agent genetic algorithm based on tabu search for the job shop scheduling problem.

Area of Science:

• Operations Research
• Artificial Intelligence
• Computational Optimization

Background:

• The job shop scheduling problem (JSSP) is crucial for enterprise efficiency.
• JSSP is a non-deterministic polynomial-hard problem, requiring advanced algorithms.

Purpose of the Study:

• To propose a novel algorithm, MAGATS, for solving JSSPs under makespan constraints.
• To improve resource utilization and production efficiency through optimized scheduling.

Main Methods:

• Developed a multi-agent genetic algorithm (MAGA) with a specialized grid environment.
• Designed neighbor interaction, neighborhood-based mutation, and self-learning operators.
• Integrated the MAGA with a tabu search algorithm to create MAGATS.

Main Results:

• Tested MAGATS on 43 benchmark JSSP instances.
• Compared MAGATS performance against four other established algorithms.
• Demonstrated superior optimization performance of MAGATS.

Conclusions:

• The proposed MAGATS algorithm effectively solves JSSPs.
• MAGATS offers significant improvements in optimization performance for scheduling problems.
• The algorithm's effectiveness is validated through rigorous testing and analysis.