[1]许晓栋,李从心.免疫遗传算法在车间作业调度中的应用[J].东南大学学报(自然科学版),2006,36(3):437-441.[doi:10.3969/j.issn.1001-0505.2006.03.022]
 Xu Xiaodong,Li Congxin.Application of immune genetic algorithm in job-shop scheduling problem[J].Journal of Southeast University (Natural Science Edition),2006,36(3):437-441.[doi:10.3969/j.issn.1001-0505.2006.03.022]
点击复制

免疫遗传算法在车间作业调度中的应用()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
36
期数:
2006年第3期
页码:
437-441
栏目:
自动化
出版日期:
2006-05-20

文章信息/Info

Title:
Application of immune genetic algorithm in job-shop scheduling problem
作者:
许晓栋 李从心
上海交通大学塑性成形工程系, 上海 200030
Author(s):
Xu Xiaodong Li Congxin
Department of Plasticity Technology, Shanghai Jiaotong University, Shanghai 200030, China
关键词:
免疫遗传算法 车间作业调度 疫苗
Keywords:
immunegenetic algorithm job shop scheduling vaccine
分类号:
TP278
DOI:
10.3969/j.issn.1001-0505.2006.03.022
摘要:
为了求解车间作业调度(JSP)这一典型的NP难题,提出了基于免疫遗传算法(IGA)的JSP问题求解方法.在该求解方法中,结合免疫原理和遗传算法提出了应用于JSP问题的IGA算法流程; 算法采用基于工序的编码方式、自适应交叉和变异; 同时为了改善交叉算子的性能提出了一种改进的基于工序编码的交叉算子.另外,采用车间作业中“最短处理时间原则”作为IGA算法的免疫疫苗,同时给出了免疫算子的设计方法.最后,通过“Muth and Thompson”基准问题的仿真实验验证了IGA算法在JSP问题求解中的有效性.
Abstract:
To solve the job-shop scheduling problem(JSP)more efficiently, a method based on immune genetic algorithm(IGA)is proposed. In this method, the IGA flow structure is presented via combining the immune theory and the genetic algorithm. The encoding scheme based on processes and the adaptive probabilities of crossover and mutation are adopted, while a modified precedence operation crossover is also proposed to improve the performance of the crossover operator. On the other hand, the “shortest processing time” principle is selected to be the vaccine of IGA and the design method of the immune operator is given at the same time. Finally, the efficiency of IGA is validated by applying the IGA to Muth and Thompson’s benchmark problem.

参考文献/References:

[1] Garey M R,Johnson D S,Sethi R.The complexity of flow-shop and job-shop scheduling [J].Math Oper Res,1976,1(2):117-129.
[2] Jain A S,Meeran S.Deterministic job-shop scheduling:past,present and future [J].European Journal of Research,1999,113(2):390-434.
[3] Lenstra J K,Rinnooy Kan A H G,Brucker P.Complexity of machine scheduling problem[J].Ann Discr Math,1997(1):343-362.
[4] van Laarhoven P J M,Aarts E H L,Lenstra J K.Job shop scheduling by simulated annealing [J].Operation Research,1992,40(1):113-125.
[5] Nowicki E,Smutnicki C.A fast taboo search algorithm for the job shop problem [J].Management Science,1996,42(6):797-813.
[6] 赵虎,李睿.蚂蚁算法在车间作业调度问题中的应用[J].计算机工程与应用,2000(22):6-8.
  Zhao Hu,Li Rui.Application of ant algorithm to job shop scheduling problem[J].Computer Engineering and Applications,2000(22):6-8.(in Chinese)
[7] Carlier J,Pinson F.An algorithm for solving the job-shop problem[J].Management Science,1989,35(2):164-176.
[8] Jiao Licheng,Wang Lei.A novel genetic algorithm based on immunity[J].IEEE Transactions on Systems,Man,and Cybernetics,2000,30(5):552-561.
[9] 王筠,马柯,冯涛.自适应免疫遗传算法在混合流程车间调度中的应用[J].西安工程科技学院学报,2005,19(1):79-81.
  Wang Jun,Ma Ke,Feng Tao.The application of adaptive immune genetics algorithms on hybrid-process job-shop schedule[J].Journal of Xian University of Engineering Science and Technology,2005,19(1):79-81.(in Chinese)
[10] Muth J F,Thompsong L.Industrial scheduling[M].New Jersey:Prentice-Hall,Englewood Cliffs,1963:120-150.
[11] 王凌.车间调度及其遗传算法[M].北京:清华大学出版社,2003:1-200.
[12] Goldberg D E.Genetic algorithms in search,optimization and machine learning[M].New York:Addison-Wesley,1989:1-100.
[13] Srinivas M,Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithm [J].IEEE Trans Systems Man and Cybernetics,1994,24(4):656-667.
[14] Guoyong S,Hitoshi Ⅱ M A,Nobuo S.A new encoding scheme for Job Shop problems by Genetic Algorithm[C] //Proceedings of the 35th Conference on Decision and Control.Kobe,Japan,1996:4395-4400.
[15] Chen Xiong,Kong Qingsheng,Wu Qidi.Hybrid algorithm for job-shop scheduling problem[C] //Proceeding of the 4th Congress on Intelligent Control and Automation.Shanghai:East China Univ of S & T Press,2002:1739-1743.
[16] 张超勇,饶运清,李培根,等.求解作业车间调度问题的一种改进遗传算法[J].计算机集成制造系统,2004,10(8):966-970.
  Zhang Chaoyong,Rao Yunqing,Li Peigen,et al.An improved genetic algorithm for job-shop scheduling[J].Computer Integrated Manufacturing Systems,2004,10(8):966-970.(in Chinese)
[17] 云庆夏.进化算法[M].北京:冶金工业出版社,2000:1-200.
[18] Yamada T,Rosen B E,Nakano R.A simulated annealing approach to job shop scheduling using critical block transition operators[C] //Proc IEEE Int Conf on Neural Networks.Orlando,Florida,1994:4687-4692.
[19] Davidor Y,Yamada T,Nakano R.The ecological framework Ⅱ:improving ga performance at virtually zero cost[C] //5th International Conference on Genetic Algorithms,1993:171-176.
[20] Mattfeld D C,Kopfer H,Bierwirth C.Control of parallel population dynamics by social-like behavior of ga-individuals[C] //3rd International Conference on Parallel Problem Solving from Nature,Jerusalem,Isr,1994:16.
[21] Yamada T,Nakano R.A genetic algorithm with multi-step crossover for Job-shop scheduling problems[C] //First IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems:Innovations and Applications.Sheffield,UK:Inst of Electrical Engineers,1995:146-151.

相似文献/References:

[1]林金星,沈炯,肖国涛,等.一种基于分层模糊控制的免疫遗传优化算法[J].东南大学学报(自然科学版),2005,35(1):46.[doi:10.3969/j.issn.1001-0505.2005.01.010]
 Lin Jinxing,Shen Jiong,Xiao Guotao,et al.Immune genetic optimization algorithm based on multilayer fuzzy control[J].Journal of Southeast University (Natural Science Edition),2005,35(3):46.[doi:10.3969/j.issn.1001-0505.2005.01.010]
[2]朱红霞,沈炯,王培红,等.基于免疫遗传算法的模糊优化控制及其仿真[J].东南大学学报(自然科学版),2005,35(1):64.[doi:10.3969/j.issn.1001-0505.2005.01.014]
 Zhu Hongxia,Shen Jiong,Wang Peihong,et al.Fuzzy optimization control based on immune genetic algorithm and its simulating study[J].Journal of Southeast University (Natural Science Edition),2005,35(3):64.[doi:10.3969/j.issn.1001-0505.2005.01.014]
[3]潘杨,李小平.地铁终点站的实时调度算法[J].东南大学学报(自然科学版),2010,40(1):47.[doi:10.3969/j.issn.1001-0505.2010.01.009]
 Pan Yang,Li Xiaoping.Real time scheduling algorithms for metro terminals[J].Journal of Southeast University (Natural Science Edition),2010,40(3):47.[doi:10.3969/j.issn.1001-0505.2010.01.009]

备注/Memo

备注/Memo:
基金项目: 上海市信息化示范资助项目(沪经技(2002)578号).
作者简介: 许晓栋(1980—),男,博士生; 李从心(联系人),男,博士,教授,博士生导师,cxli@sjtu.edu.cn.
更新日期/Last Update: 2006-05-20