Hybrid Tabu Search Algorithm for bi-criteria No-idle permutation flow shop scheduling problem

A novel Hybrid Tabu Search Algorithm (HTS) is proposed for solving bi-criteria No-idle permutation Flow Shop Scheduling Problem in this paper. Two objectives, i.e. the maximum completion time (makespan) and the total flow time (TFT), are considered at the same time. The initial solution of the Tabu Search Algorithm is generated by the famous NEH heuristic. A speed-up method is introduced both in NEH and HTS to improve the efficiency of the algorithm. Then the dynamic feature of the tabu list length is applied to improve the robustness of the algorithm. And a local search method is embedded in the HTS to improve the exploitation capability of the algorithm. It is proved by the extensive computational experiments that the HTS algorithm is superior to the existing algorithms both in computing effectiveness and searching ability.