Abstract: According to the characteristics of Hybrid Flow-shop Scheduling Problem (HFSP),a random iteration list decoding method was proposed,and the effectiveness of this random iteration list decoding method was proved by comparing it with the permutation decoding method and the original list decoding method,and then a two-stage decoding method was proposed.For solving this method,Migrating Birds Optimization (MBO) algorithm was used,and an improved MBO algorithm based on two-stage decoding method was proposed.In this algorithm,the leader and followers were evolved through the optimal insertion operation or the optimal exchange operation,and four neighborhood structures were designed to perform local search for followers.24 harder benchmark testing problems were solved with the proposed algorithm,and the best results of these instances were obtained.The proposed algorithm was used to solve 10 larger-size testing problems and a better result was obtained,which verified the effectiveness of the proposed algorithm.

Key words: hybrid flow-shop scheduling, migrating birds optimization algorithm, decoding methods, makespan

摘要： 针对混合流水车间调度问题的特点,提出一种随机迭代排列解码方法,并与置换解码方法和原始排列解码方法对比,验证所提解码方法的有效性,同时设计了一种两阶段解码方法。首次提出采用候鸟优化算法求解该问题,设计了基于该两阶段解码方法的候鸟优化算法。在所提算法中,领飞鸟和跟飞鸟通过最优插入操作或最优交换操作进行进化,设计了4种邻域结构仅对跟飞鸟进行局部搜索。最后,采用基于两阶段解码方法的候鸟算法求解标准问题中的24个较难算例,获得了所有实例的当前最好解。采用所提算法对10个大规模标准算例进行求解,得到一个新的最好解,验证了提出算法的有效性。

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