A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem

A novel hybrid tabu search algorithm with a fast public critical block neighborhood structure (TSPCB) is proposed in this paper to solve the flexible job shop scheduling problem with the criterion to minimize the maximum completion time (makespan). First, a mix of four machine assignment rules and four operation scheduling rules is developed to improve the quality of initial solutions to empower the hybrid algorithm with good exploration capability. Second, an effective neighborhood structure to conduct local search in the machine assignment module is proposed, which integrates three adaptive approaches. Third, a speedup local search method with three kinds of insert and swap neighborhood structures based on public critical block theory is presented. With the fast neighborhood structure, the TSPCB algorithm can enhance its exploitation capability. Simulation results based on the well-known benchmarks and statistical performance comparisons are provided. It is concluded that the proposed TSPCB algorithm is superior to several recently published algorithms in terms of solution quality, convergence ability, and efficiency.