求解置换流水车间调度问题的Memetic算法

Memetic Algorithm for Permutation Flow Shop Scheduling Problems

针对以最小化最大完工时间为目标的置换流水车间调度问题,建立了0-1型混合整数线性规划模型。在对模型进行Benders分解的基础上,提出了问题的求解策略,进而设计了一种Memetic调度算法,并探讨了基于组合规则的种群初始化方法和混合遗传操作。为了提高算法的搜索效率,采用了更加高效的适应度值计算方法以及两种邻域搜索方法。最后,基于Benchmark算例的仿真实验结果表明了该算法的有效性,可以找到26个算例中的17个最优解(65.38%),且其平均相对误差的均值仅为0.88%。

A 0-1 mixed-integer linear programming model was established for the permutation flow shop scheduling with makespan criterion. Based on Benders＇ decomposition, a problem solving strategy was proposed, and a Memetic algorithm designed. In designing the algorithm, a combinatorial population initialization method and a hybrid genetic operation were discussed. Further, a more efficient fitness value computation and two neighborhood search algorithms were adopted to improve searching efficiency. The final results of benchmark simulation verify the effectiveness of the proposed algorithm,which solves 17 of the 26instances（ 65. 38%） with the mean value of average relative error standing at only 0. 88%.