A path relinking with tabu search algorithm for solving hybrid flow shop scheduling problem considering multiple critical paths

The hybrid flow shop scheduling is a challenging problem due to its high complexity and widespread applications in industrial production systems. In this paper, we propose a hybrid method that integrates path relinking with tabu search (PRTS) to solve this problem with the objective of minimizing the makespan. PRTS utilizes permutation-based encoding to effectively find some promising areas. Subsequently, it transitions to complete encoding representation to guarantee the inclusion of all feasible semiactive schedules. Building upon this, the path relinking procedure helps to increase diversity and enhance global exploration, while tabu search contributes to local exploitation. Two effective neighborhood structures are modified by considering multiple critical paths, and a rapid evaluation method is designed. The proposed algorithm is tested on two benchmarks that comprise 250 instances and is compared to some state-of-the-art algorithms. The results demonstrate the superiority of PRTS over existing methods and provide new best solutions for 102 challenging instances.