Fast local neighborhood search algorithm for the no-wait flow shop scheduling with total flow time minimization
提出一种快速局部邻域搜索算法，用于解决无等待流水车间调度中最小化总完工时间的NP难问题，实验表明该算法在质量和鲁棒性上优于现有主流算法。
A fast local neighbourhood search (FLNS) algorithm is proposed in this paper to minimise the total flow time in the no-wait flow shop scheduling problem, which is known to be NP-hard for more than two machines. In this work, an unscheduled job sequence is constructed firstly according to the total processing time and standard deviation of jobs on the machines. This job sequence is undergone an initial optimisation using basic neighbourhood search algorithm. Then, an innovative local neighbourhood search scheme is designed to search for the partial neighbourhood in each iterative processing and calculate the neighbourhood solution with an objective increment method. This not only improves the solution quality significantly, but also speeds up the convergence of the solution of the algorithm. Moreover, a probabilistic acceptance criterion is adopted to help our method escape from the local optima. Based on Taillard’s benchmarks, the experimental results show that the proposed FLNS algorithm is superior to major existing algorithms (IHA, IBHLS, GA-VNS and DHS) in terms of both quality and robustness, and can provide best upper bounds. The in-depth statistical analysis demonstrates that the promising performance of our proposed algorithm is also statistically significant.