Abstract: To solve the permutation flow-shop scheduling problem with the objective to minimize makespan more effectively,a New Hybrid Crow Search Algorithm (NHCSA) was proposed.A NEH-based heuristic was modified,based on which a new method was put forward to ameliorate the quality and diversity of the initial population.Then,the Smallest-Position-Value (SPV) rule was adopted to enable the algorithm to deal with discrete scheduling problems.For the iterated greedy algorithm,a method was come up with to adjust the range of re-inserted jobs automatically,a Tie-Breaking (TB) mechanism was embedded,and the improved iterated greedy algorithm was incorporated as a local search scheme for the best job permutation to improve the searching accuracy of the proposed algorithm.Simulations based on the well-known benchmarks were carried out,and the results validated the optimization ability and stability.Especially in the comparisons for Rec19 and Rec25 test cases,only NHCSA achieved the current optimal solutions,which further proves its superiority.

Key words: crow search algorithm, permutation flow-shop, population initialization, local search

摘要： 为了更加有效地求解以最大完工时间最小化为目标的置换流水车间调度问题,提出一种新混合乌鸦搜索算法(NHCSA)。首先,对一种基于NEH的启发式算法进行了改进,在此基础上提出新的方法以改善初始种群的质量和多样性;其次,采用SPV(Smallest-Position-Value)规则进行编码,使算法能够处理离散的调度问题;最后,针对迭代贪婪算法,提出了自动调整重插入工件范围的方法、引入了TB机制,并采用改进的迭代贪婪算法对最佳工件排序进行局部搜索,以提升算法收敛的精度。基于典型测试集进行了仿真测试,结果验证了所提算法的寻优能力和稳定性。尤其是在针对Rec19和Rec25算例的比较中,仅NHCSA取得了当前最优解,进一步证明了其优越性。

关键词: 乌鸦搜索算法, 置换流水车间, 种群初始化, 局部搜索