求解置换流水车间调度问题的改进遗传算法  

Improved genetic algorithm for solving permutation flow shop scheduling problem

作　　者：李小缤[1] 白焰[1] 耿林霄[2] 

机构地区：[1]华北电力大学控制与计算机工程学院,北京102206 [2]西安热工研究院有限公司,西安710032

出　　处：《计算机应用》2013年第12期3576-3579,共4页journal of Computer Applications

摘　　要：目前求解置换流水车间调度问题的遗传算法中,加工顺序编码方法导致交叉、变异算子复杂,且子代与父代不相似,算法易陷入局部最优。为解决以上问题,提出了一种基于优先权值编码并含有限优算子的改进遗传算法。利用各工件的优先权值进行编码,避免遗传算子中不合法编码的出现;加入限优算子限制种群中最优个体的繁殖数量,防止种群陷入局部最优点,改善寻优质量。实验结果表明,该算法中的编码方法可行且易于应用于求解紧急工件优先加工的实际问题;同时用基准算例验证了具有限优算子的改进算法求解结果相对误差小且求解稳定性高。In the existing genetic algorithms tbr permutation flow shop scheduling problem, the crossover and mutation operator is complex because of the processing sequence, the offspring is not similar to parent, and the algorithm easily falls into local optimum. To solve these problems, an improved genetic algorithm with priority-based value coding method and optimum limited operator was proposed. The coding method based on the priority values of the workpieces could avoid illegal coding, and the optimum limited operator could limit the propagation of the best individual to prevent falling into local optimum. The experiments show that this coding method is feasible and it can solve the practical problem when urgent workpieces must be processed firstly. The simulation results on benchmarks demonstrate that the proposed algorithm has superiority of smaller relative error and higher stable solution quality.

关 键 词：置换流水车间调度 遗传算法 优先权值 最大完工时间 局部收敛 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]