求解多目标PFSP的改进遗传算法  

Improved genetic algorithm for multi-objective of PFSP

作　　者：齐学梅[1,2] 王宏涛[1,2] 陈付龙[1,2] 罗永龙[1,2] 

机构地区：[1]安徽师范大学数学计算机科学学院,安徽芜湖241003 [2]安徽师范大学网络与信息安全工程技术研究中心,安徽芜湖241003

出　　处：《计算机工程与应用》2015年第11期242-247,共6页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61370050);安徽省自然科学基金(No.1308085QF118);安徽省高等学校质量工程项目(No.2012JYXM104);安徽师范大学创新基金(No.2013CXJJ01)

摘　　要：针对多目标置换流水车间调度问题(PFSP)提出了一种改进的遗传算法,用于优化最大完工时间和总完工时间。该算法采用启发式算法和随机算法相结合产生初始种群,以保持种群多样性;通过选择、交叉、变异操作以及群体更新策略完成进化过程;当种群进化停滞时,引入群体重新初始化机制恢复多样性。此外,设计了一种变邻域搜索算法,加速种群收敛并跳出局部最优。通过基准测试问题实验以及与其他几个优化算法比较,结果表明,提出的算法无论在求解质量还是稳定性方面都优于其他算法。An improved genetic algorithm is proposed for multi-objective of Permutation Flowshop Scheduling Problem（PFSP）to optimize the makespan and total flow time. In order to keep the diversity of the population, the initial population is generated by combining heuristic algorithm and random algorithm in the proposed algorithm. The procedure of evolution is completed with selection, crossover, mutation operation and update strategy. When population evolutionary stagnated, the re-initialization mechanism is introduced to restore diversity. In addition, a variable neighborhood search algorithm is designed to accelerate population convergence and jump out of local optimum. Compared with several other optimization algorithms through experiment on the benchmarks, the results show that the proposed algorithm in both solution quality and stability is superior to other algorithms.

关 键 词：多目标 置换流水车间调度 遗传算法 变邻域搜索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]