A hybridization of evolution strategies with iterated greedy algorithm for no-wait flow shop scheduling problems

Area of Science:

• Operations Research
• Computer Science
• Computational Intelligence

Background:

• The no-wait flow shop scheduling problem is a complex, NP-hard combinatorial optimization challenge.
• Existing algorithms often struggle with finding optimal solutions efficiently for this problem.
• Hybridization of algorithms can leverage complementary strengths to overcome individual limitations.

Purpose of the Study:

• To develop and evaluate a novel hybrid algorithm (HES-IG) for the no-wait flow shop scheduling problem.
• To optimize the makespan, a critical objective function in scheduling.
• To improve upon the performance of existing scheduling algorithms.

Main Methods:

• A hybrid algorithm (HES-IG) combining Evolution Strategies (ES) and Iterated Greedy (IG) was developed.
• ES utilizes (1+5)-ES reproduction and (µ+λ)-ES selection with insertion mutation.
• IG employs a destruction-construction operator and a single insertion local search with constant temperature acceptance criteria.

Main Results:

• The HES-IG algorithm achieved 15 new lower bound values on Reeves benchmark problems.
• The HES-IG algorithm achieved 30 new lower bound values on Taillard benchmark problems.
• Computational results demonstrate that HES-IG outperforms other state-of-the-art algorithms across all tested problem sizes.

Conclusions:

• The proposed HES-IG algorithm is highly effective for the no-wait flow shop scheduling problem.
• Hybridization of ES and IG provides a robust approach for complex scheduling tasks.
• The HES-IG algorithm establishes a new benchmark in performance for this scheduling problem.