Genetic Programming with Tabu List for Dynamic Flexible Job Shop Scheduling.

Area of Science:

• Operations Research
• Artificial Intelligence
• Computer Science

Background:

• Dynamic flexible job shop scheduling (DFJSS) is a complex combinatorial optimization problem.
• Genetic programming (GP) is a common hyper-heuristic for DFJSS but suffers from rapid diversity loss.
• Weak exploration ability limits GP's effectiveness in finding optimal scheduling heuristics.

Purpose of the Study:

• To propose an effective GP algorithm with tabu lists to enhance exploration for DFJSS.
• To improve the exploration ability of GP by guiding it to unexplored areas.
• To enhance the overall effectiveness of GP for solving DFJSS problems.

Main Methods:

• Utilized phenotypic characterization to represent GP individuals as vectors for DFJSS.
• Developed tabu lists to store phenotypic characterizations of explored individuals.
• Implemented a mechanism to discard offspring if their phenotypic characterizations are found in tabu lists, promoting exploration of unseen solutions.

Main Results:

• The proposed GP algorithm with tabu lists outperformed compared algorithms in most tested scenarios.
• The algorithm successfully maintained a diverse and well-distributed population throughout the evolutionary process.
• Demonstrated that the algorithm explores a larger search space to identify effective scheduling heuristics.

Conclusions:

• The proposed GP algorithm with tabu lists is effective in enhancing exploration for DFJSS.
• The method improves population diversity and leads to the discovery of superior scheduling heuristics.
• This approach offers a promising direction for improving hyper-heuristic performance in dynamic scheduling environments.