A Hybrid Crow Search Algorithm for Solving Permutation Flow Shop Scheduling Problems

Abstract

The permutation flow shop scheduling problem (PFSP) is a renowned problem in the scheduling research community. It is an NP-hard combinatorial optimization problem that has useful real-world applications. In this problem, finding a useful algorithm to handle the massive amounts of jobs required to retrieve an actionable permutation order in a reasonable amount of time is important. The recently developed crow search algorithm (CSA) is a novel swarm-based metaheuristic algorithm originally proposed to solve mathematical optimization problems. In this paper, a hybrid CSA (HCSA) is proposed to minimize the makespans of PFSPs. First, to make the CSA suitable for solving the PFSP, the smallest position value rule is applied to convert continuous numbers into job sequences. Then, the HCSA uses a Nawaz–Enscore–Ham (NEH) technique to create a population with the required levels of quality and diversity. We apply a local search to enhance the quality of the solutions and avoid premature convergence; simulated annealing enhances the local search of a method based on a variable neighborhood search. Computational tests are used to evaluate the algorithm using PFSP benchmarks with job sizes between 20 and 500. The tests indicate that the performance of the proposed HCSA is significantly superior to that of other algorithms.

Keywords

• permutation flow shop scheduling
• NEH heuristic
• crow search algorithm
• smallest position value
• makespan