Abstract:

To solve the hybrid flow-shop scheduling problem, an improved discrete cuckoo search algorithm is proposed. Aiming at the disadvantage that conventional decoding method is difficult to obtain the optimal solution, an improved decoding method is proposed, which is based on the number of workpieces and parallel machines, and assigns machines randomly according to the probability. According to the core ideas of two kinds of location update strategies of Lévy flight and brood parasitic behavior in standard cuckoo algorithm, the discrete Lévy flight based on position crossover and individual distance is proposed, and the brood parasitic strategy based on optimal insertion and optimal exchange is designed. Finally, the comparison results of the examples show that the average value of the results obtained from the discrete cuckoo algorithm based on the improved decoding method is the minimum, which verifies that the improved decoding method can generate better solutions. All the test results of the examples obtain the current optimal solutions, which verifies the superiority of the improved discrete cuckoo algorithm in solving this kind of problem.

Key words: hybrid flow-shop scheduling, cuckoo search, decoding method, minimizing makespan

摘要：

为求解混合流水车间调度问题，提出一种离散布谷鸟算法。针对常规解码方法难以获得最优解的缺点，提出一种改进的解码方法，基于工件数与并行机数，按概率随机分配机器；根据标准布谷鸟算法中莱维飞行和巢寄生行为两种位置更新策略的核心思想，提出基于位置交叉和个体距离的离散莱维飞行，设计基于最优插入和最优交换的巢寄生策略。最后算例对比实验结果显示，采用基于改进解码方法的离散布谷鸟算法求解所得结果的平均值最小，验证了改进解码方法能提高解的质量；实例测试所得结果均获得了当前最优解，验证了离散布谷鸟算法求解该类问题的优越性。

关键词: 混合流水车间调度, 布谷鸟算法, 解码方法, 最小化最大完工时间