一种求解双目标job shop问题的混合进化算法  

A hybrid evolutionary algorithm for bi-objective job shop scheduling problems

作　　者：师瑞峰[1] 周一民[1] 周泓[2] 

机构地区：[1]北京航空航天大学计算机学院,北京100083 [2]北京航空航天大学经济管理学院,北京100083

出　　处：《控制与决策》2007年第11期1228-1234,共7页Control and Decision

基　　金：国家自然科学基金项目(70771003;70521001);新世纪优秀人才支持计划项目(NCET)

摘　　要：提出一种求解双目标job shop排序问题的混合进化算法.该算法采用改进的精英复制策略,降低了计算复杂性;通过引入递进进化模式,避免了算法的早熟;通过递进过程中的非劣解邻域搜索,增强了算法局部搜索性能.采用该算法和代表性算法NSGA-Ⅱ,MOGLS对82个标准双目标job shop算例进行优化对比,所得结果验证了该算法求解双目标job shop排序问题的有效性.Aiming at solving bi-objective job shop scheduling problems, a hybrid evolutionary algorithm is proposed. An improved elite duplication strategy is applied, which reduces computational cost of the algorithm. An escalating evolutionary strategy is introduced into the algorithm, which is designed to overcome premature convergence. Besides, by applying a variable neighborhood search strategy to achieve Pareto solutions during the population escalation, the algorithm＇s local search ability is enhanced. Numerical experiments, which employ the proposed algorithm, together with other two typical algorithms NSGA-Ⅱ and MOGLS, is made to solve 82 bi-objective job shop scheduling problems. The optimization results show the effectiveness of the algorithm proposed here on solving bi-objective job shop scheduling problems.

关 键 词：多目标优化 递进进化 JOB SHOP 进化算法 

分 类 号：F406.6[经济管理—产业经济]