A Hybrid Evolutionary Algorithm Using Two Solution Representations for Hybrid Flow-Shop Scheduling Problem.

Area of Science:

• Operations Research
• Computer Science
• Industrial Engineering

Background:

• The hybrid flow-shop scheduling problem (HFSP) is a complex, flexible, and challenging problem common in large-scale industrial production.
• Existing evolutionary algorithms struggle with limited solution space exploration, leading to suboptimal performance in later stages.
• Classical encoding and decoding strategies often fail to adequately address the HFSP's complexity.

Purpose of the Study:

• To propose a novel hybrid evolutionary algorithm (HEA) for makespan minimization in the hybrid flow-shop scheduling problem.
• To enhance solution space exploration by combining permutation-based encoding with Tabu search.
• To improve the efficiency and effectiveness of solving challenging HFSP instances.

Main Methods:

• A hybrid evolutionary algorithm (HEA) employing two solution representations: permutation-based encoding and disjunctive graph representation.
• Integration of heuristic decoding methods and a Tabu search (TS) procedure for expanded solution space searching.
• Extension of critical path neighborhood structures to backward schedules for generating candidate solutions within the TS.

Main Results:

• The proposed HEA demonstrated superior performance compared to state-of-the-art algorithms across 567 HFSP benchmark instances.
• New best solutions were identified for 285 difficult HFSP instances.
• The HEA effectively balances exploration and exploitation for improved makespan minimization.

Conclusions:

• The proposed hybrid evolutionary algorithm offers a significant advancement in solving the hybrid flow-shop scheduling problem.
• The dual representation and enhanced search strategy effectively overcome limitations of traditional methods.
• This approach provides a robust and efficient tool for industrial production scheduling optimization.