###
DOI:
Journal of Software:2010.21(12):3082-3093

基于记忆库拉马克进化算法的作业车间调度
夏柱昌,刘芳,公茂果,戚玉涛
()
Memory Based Lamarckian Evolutionary Algorithm for Job Shop Scheduling Problem
XIA Zhu-Chang,LIU Fang,GONG Mao-Guo,QI Yu-Tao
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3495   Download 3497
Received:June 23, 2008    Revised:July 06, 2009
> 中文摘要: 多种群遗传算法相比遗传算法在性能上能够有所提高,但对具有较多局部最优解的作业车间调度问题,多种群遗传算法仍然难以改善易陷入局部最优解和局部搜索能力差的缺点.因此,提出了一种求解作业车间调度问题的新算法MGA-MBL(multi-population genetic algorithm based on memory-base and Lamarckian evolution for job shop scheduling problem).MGA-MBL在多种群遗传算法的基础上通过引入记忆库策略,不但使子种群间的个体可以进行信息交换,而且有利于保持整个种群的多样性;通过构造基于拉马克进化机制的局部搜索算子来提高多种群遗传算法中子种群进化的局部搜索能力.由于MGA-MBL采用了全局寻优能力较强的模拟退火算法对记忆库中的个体进行优化,从而缓解了多种群遗传算法易陷入局部最优解的问题,并提高了算法求解作业车间调度问题的性能.对著名的benchmark数据进行测试,实验结果证实了MGA-MBL在求解作业车间调度问题上的有效性.
Abstract:Compared with the Genetic Algorithm, a multi-population genetic algorithm has an enhancement in performance, but for a job shop scheduling problem, which has a lot of local optima, it also has the shortcomings of an easy-to-fall into local optima and a poor ability of local search. Therefore, an effective algorithm is proposed to solve job shop scheduling problem. The proposed algorithm, based on multi-population genetic algorithm, involves the strategy of memory-base and a mechanism of the Lamarckian evolution. Not only does the memory-base make individuals between sub-populations exchange information, but it can maintain the diversity of the population. The local search operator, based on Lamarckian evolution, is adupted to enhance the individual’s ability of local search. The simulated annealing algorithm that has a stronger ability to jump out local optima than the genetic algorithm is used, thus, alleviated the problem and enhances the performance of the algorithm for job shop scheduling. The experimental results on the well-known benchmark instances show the proposed algorithm is very effective in solving job shop scheduling problems.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60703107, 60703108, 60803098, 60803706, 60872135 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant Nos.20060101Z1119, 2009AA12Z210 (国家高技术研究发展计划(863)); the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant Nos.20060701007, 20070701022 (国家教育部博士点基金); the Key Scientific and Technological Innovation Special Projects of Shaanxi “13115” of China under Grant No.2008ZDKG-37 (陕西省“13115”科技创新工程重大科技专项项目); the Program for Cheung Kong Scholars and Innovative Research Team in University of China under Grant No.IRT0645 (国家教育部长江学者和创新团队支持计划); the China Postdoctoral Science Foundation Funded Project under Grant Nos.200801426, 20080431228 (中国博士后科学基金资助项目) Supported by the National Natural Science Foundation of China under Grant Nos.60703107, 60703108, 60803098, 60803706, 60872135 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant Nos.20060101Z1119, 2009AA12Z210 (国家高技术研究发展计划(863)); the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant Nos.20060701007, 20070701022 (国家教育部博士点基金); the Key Scientific and Technological Innovation Special Projects of Shaanxi “13115” of China under Grant No.2008ZDKG-37 (陕西省“13115”科技创新工程重大科技专项项目); the Program for Cheung Kong Scholars and Innovative Research Team in University of China under Grant No.IRT0645 (国家教育部长江学者和创新团队支持计划); the China Postdoctoral Science Foundation Funded Project under Grant Nos.200801426, 20080431228 (中国博士后科学基金资助项目)
Foundation items:
Author NameAffiliation
XIA Zhu-Chang  
LIU Fang  
GONG Mao-Guo  
QI Yu-Tao  
Reference text:

夏柱昌,刘芳,公茂果,戚玉涛.基于记忆库拉马克进化算法的作业车间调度.软件学报,2010,21(12):3082-3093

XIA Zhu-Chang,LIU Fang,GONG Mao-Guo,QI Yu-Tao.Memory Based Lamarckian Evolutionary Algorithm for Job Shop Scheduling Problem.Journal of Software,2010,21(12):3082-3093