采用精英进化策略的JSP-DCPT混合求解算法  

JSP-DCPT hybrid algorithm by elitism evolution strategy

作　　者：赵小磊[1,2] 孙树栋[1,2] 牛刚刚 

机构地区：[1]西北工业大学系统集成与工程管理研究所,陕西西安710072 [2]西北工业大学现代设计与集成制造技术教育部重点实验室,陕西西安710072 [3]IBM中国研究院,北京100193

出　　处：《计算机集成制造系统》2013年第10期2493-2502,共10页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(51075337)~~

摘　　要：为解决加工时间离散可控作业车间调度问题,提出一种基于非支配排序遗传算法和禁忌搜索算法的混合算法。由于资源配置是工序优化的前提,该算法采用先求解控制方案再求解加工方案的分解策略;采用非支配排序遗传算法进行种群全局优化,采用禁忌算法对种群中引入的新个体进行局部优化;设计了一种扩展的基于优先列表的编码方式进行染色体编码,采用精英进化策略,在精英保留的基础上使精英个体参与遗传进化操作,加快获取最优解;消除非支配排序遗传算法非支配性排序时对种群个体的重复比较,降低了算法的时间复杂度。通过仿真实验,验证了该算法的可行性和有效性。To solve Job-shop Scheduling Problem with Discretely Controllable Processing Times （JSP-I^PT）, a Non-dominated Sorting Genetic Algorithm II （NSGA-II） and Tabu Search（TS） algorithm based hybrid algorithm NSGAII-TS was put forward. On the premise of resources allocation, the decomposition strategy of solving control scheme first and then solving process plan was used in NSGAII-TS. NSGA-II was used for global optimization of population, and TS algorithm was used for local optimization of the new individuals in population. An extended cod- ing method based on preferred list was presented, and elitism evolution strategy was adopted to participate in genetic evolution operation based on elitism preservation so that the optimum solution was obtained. The duplicate compari- son of individuals in fast non-dominated sorting approach of NSGA-II was eliminated so that the time complexity of NSGA-II would be reduced. The simulation experiments indicated the effectiveness of NSGAII-TS algorithm.

关 键 词：加工时间离散可控 非支配排序遗传算法 禁忌搜索 分解策略 精英进化 

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