中文摘要：

利用迭代变化邻域搜索算法（IVNS）求解最小化总完工时间的有准备时间无等待流水车间调度问题．设计局部搜索算法需要考虑3个关键因素：所用邻域、解评估和局部最优的克服．因此，定义了3个较大规模邻域以扩大搜索范围．为加速解评估，利用目标增量来避免重新计算每个解的目标函数值，使相邻解比较只需常量时间，NEH插入算法的时间复杂度降低一阶．IVNS通过切换邻域和扰动重启，来克服局部搜索易于陷入局部最优解的缺点．通过与求解该问题的当前最好算法在5400个标准算上，以相同CPU时间进行的实算比较，实验结果统计分析验证了IVNS的寻优性能明显优于参照算法．

英文摘要：

A new local search algorithm called IVNS （iterated variable neighborhood search） is proposed for the no-wait flowshop scheduling problem with setup time to minimize the total completion time. Three key factors are taken into consideration when designing local search algorithms like IVNS： neighborhoods, neighboring solution evaluations and strategies for escaping local optima. Firstly, three new neighborhoods with larger sizes are introduced to enhance the chance of finding high quality solutions. The neighborhoods are based on job block exchange and have sizes of O（n^3） or O（n^4） , larger than the commonly-used insertion and exchange neighborhoods. Secondly, an objective increment method is adopted to speed up the evaluation of neighboring solutions in the neighborhoods, leading to two neighboring solutions compared in constant time and the neighborhoods completely explored in times proportional to their sizes. The objective increment method also reduces the time complexity of the famous NEH algorithm by one order. Finally, IVNS tries to escape local optima by switching between different neighborhoods as well as restarting from perturbation of local optima. IVNS is compared with the best known algorithms for the considered problem on 5400 benchmark instances under identical CPU times. Statistic analysis of the experiment results verifies that IVNS remarkably outperforms the reference algorithms in average solution quality.