[1]韩忠华,朱一行,史海波,等.柔性流水车间排产问题的一种协同进化CGA求解方法[J].智能系统学报编辑部,2015,10(4):562-568.[doi:10.3969/j.issn.1673-4785.201503045]
　HAN Zhonghua,ZHU Yihang,SHI Haibo,et al.A co-evolution CGA solution for the flexible flow shop scheduling problem[J].CAAI Transactions on Intelligent Systems,2015,10(4):562-568.[doi:10.3969/j.issn.1673-4785.201503045]
点击复制

柔性流水车间排产问题的一种协同进化CGA求解方法

《智能系统学报》编辑部[ISSN 1673-4785/CN 23-1538/TP] 卷: 10 期数: 2015年第4期 页码: 562-568 栏目: 学术论文—智能系统 出版日期: 2015-08-25
Title:
A co-evolution CGA solution for the flexible flow shop scheduling problem
作者:
韩忠华1,2,3, 朱一行1, 史海波2,3, 林硕1, 董晓婷1
1. 沈阳建筑大学 信息与控制工程学院, 辽宁 沈阳 110168;
2. 中国科学院 沈阳自动化研究所, 辽宁 沈阳 110016;
3. 中国科学院 网络化控制系统重点实验室, 辽宁 沈阳 110016
Author(s):
HAN Zhonghua1,2,3, ZHU Yihang1, SHI Haibo2,3, LIN Shuo1, DONG Xiaoting1
1. Faculty of Information and Control Engineering, Shenyang Jianzhu University, Shenyang 110168, China;
2. Shenyang Institute of Automation, CAS, Shenyang 110016, China;
3. Key Laboratory of Networked Control System, CAS, Shenyang 110016, China
关键词:
双概率模型; 动态协同进化; 最优个体继承策略; 紧致遗传算法; 柔性流水车间
Keywords:
bi-probabilistic models; dynamic co-evolution; optimal individual inheritance strategy; compact genetic algorithm; flexible flow shop
分类号:
TH186
DOI:
10.3969/j.issn.1673-4785.201503045
文献标志码:
A
摘要:
为了解决柔性流水车间排产优化问题(flexible flow shop scheduling problem, FFSP),设计了一种动态协同进化紧致遗传算法(dynamic co-evolution compact genetic algorithm, DCCGA)作为全局优化算法。DCCGA算法基于FFSP特点,构建了描述问题解空间分布的概率模型,并对标准紧致遗传算法(compact genetic algorithm, CGA)的进化机制以及个体选择方式进行了改进。在其进化过程中,2个概率模型结合最优个体继承策略协同进化,并以一定的频率进行种群基因分布信息的交流,提高了算法进化过程中的种群基因信息多样性,增强了优良进化趋势的稳定性以及算法持续进化的能力。设计实验对DCCGA算法中新引入的重要参数进行了分析和探讨,确定了最佳参数值。最后,采用不同规模的FFSP实例对DCCGA算法进行测试,与已有算法进行对比分析,验证了DCCGA算法对于解决FFSP的有效性。
Abstract:
In order to solve the flexible flow shop scheduling problem (FFSP), a dynamic co-evolution compact genetic algorithm (DCCGA) is designed as the global optimization algorithm. In DCCGA, a probabilistic model is constructed to describe the distribution of solutions of the problem, and two modifications are incorporated in the standard compact genetic algorithm (CGA) for improving the evolutionary mechanism and individual selection method. DCCGA’s evolutionary process is led by two probabilistic models, which contains the optimal individual inheritance strategy, and communicates with each other at a certain frequency with the population genetic information. Hence, the diversity of the population genetic information is improved during the process, and also the stability of good evolutionary trend and the capacity of continuous evolution are greatly strengthened at the same time. Moreover, the suitable parameter value is suggested based on relative experiments. And, DCCGA is measured by the benchmark problems with comparison of several effective algorithm s. The results show that DCCGA is feasible for solving FFSP.
参考文献/References:
[1] RUIZ R, VáZQUEZ-RODRíGUEZ J A. The hybrid flow shop scheduling problem[J]. European Journal of Operational Research, 2010, 205(1): 1-18.
[2] JOHNSON S M. Optimal two-and three-stage production schedules with setup times included[J]. Naval Research Logistics Quarterly, 1954, 1(1): 61-68.
[3] HOOGEVEEN J A, LENSTRA J K, VELTMAN B. Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard[J]. European Journal of Operational Research, 1996, 89(1): 172-175.
[4] SRISKANDARAJAH C, SETHI S P. Scheduling algorithms for flexible flowshops: worst and average case performance[J]. European Journal of Operational Research, 1989, 43(2): 143-160.
[5] ENGIN O, CERAN G, YILMAZ M K. An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems[J]. Applied Soft Computing, 2011, 11(3): 3056-3065.
[6] SINGH M R, MAHAPATRA S S. A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks[J]. The International Journal of Advanced Manufacturing Technology, 2012, 62(1/2/3/4): 267-277.
[7] XU Y, WANG L, WANG S Y, et al. An effective immune algorithm based on novel dispatching rules for the flexible flow-shop scheduling problem with multiprocessor tasks[J]. The International Journal of Advanced Manufacturing Technology, 2013, 67(1/2/3/4): 121-135.
[8] 王圣尧, 王凌, 许烨. 求解相同并行机混合流水线车间调度问题的分布估计算法[J]. 计算机集成制造系统, 2013, 19(6): 1304-1312. WANG Shengyao, WANG Ling, XU Ye. Estimation of distribution algorithm for solving hybrid flow-shop scheduling problem with identical parallel machine [J]. Computer Integrated Manufacturing Systems, 2013, 19 (6): 1304-1312.
[9] 王圣尧, 王凌, 方晨,等. 分布估计算法研究进展 [J]. 控制与决策, 2012, 27(7): 961-966, 974. WANG Shengyao, WANG Ling, FANG Chen, et al. Advances in estimation of distribution algorithms [J]. Control and Decision, 2012, 27(7): 961-966, 974.
[10] HARIK G R, LOBO F G, GOLDBERG D E. The compact genetic algorithm[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 287-297.
[11] DELAOSSA L, GáMEZ J A, MATEO J L, et al. Avoiding premature convergence in estimation of distribution algorithms[C]//IEEE Congress on Evolutionary Computation, 2009. Trondheim: IEEE, 2009: 455-462.
[12] LEE J Y, KIM M S, LEE J J. Compact Genetic Algorithms using belief vectors[J]. Applied Soft Computing, 2011, 11(4): 3385-3401.
[13] GALLAGHER J C, VIGRAHAM S, KRAMER G. A family of compact genetic algorithms for intrinsic evolvable hardware[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(2): 111-126.
[14] MORENO-ARMENDáRIZ M A, CRUZ-CORTéS N, DUCHANOY C A, et al. Hardware implementation of the elitist compact Genetic Algorithm using Cellular Automata pseudo-random number generator[J]. Computers & Electrical Engineering, 2013, 39(4): 1367-1379.
[15] NAKATA M, LANZI P L, TAKADAMA K. Simple compact genetic algorithm for XCS[C]//2013 IEEE Congress on Evolutionary Computation (CEC). Cancun: IEEE, 2013: 1718-1723.
[16] 刘昶, 李冬, 彭慧,等. 求解混合流水生产线调度问题的变量相关 EDA 算法[J]. 计算机集成制造系统, 2014:(1):15-18. LIU Chang, LI Dong, PENG Hui, et al. An EDA algorithm with correlated variables for solving hybrid flow-shop scheduling problem [J]. Computer Integrated Manufacturing Systems, 2014:(1):15-18.
[17] CARLIER J, NéRON E. An exact method for solving the multi-processor flow-shop[J]. RAIRO-Operations Research, 2000, 34(1): 1-25.

备注/Memo

收稿日期:2015-03-29;改回日期:。
基金项目:中科院重点实验室开放课题资助;国家重大科技专项资助项目(2011ZX02601-005).
作者简介:韩忠华,男,1977年生,教授,博士,主要研究方向为生产与运作管理、企业自动化系统集成技术、车间排产与生产调度算法,主持和参与国家、省、市科研项目40余项。获得辽宁省科学技术奖二等奖1项,沈阳市科技进步一等奖2项,辽宁省自然学术成果奖二等奖2项,沈阳市自然学术成果奖二等奖1项,沈阳市自然学术成果奖三等奖2项。发表学术论文100余篇,被EI收录40余篇。参编著作4部;朱一行,男,1990年生,硕士研究生,主要研究方向为生产排产与生产调度优化算法;史海波,男,1966年生,研究员,博士生导师,博士,主要研究方向为生产与运作管理理论、制造过程建模与仿真技术,主持并参与多项国家863项目、国家重点科技攻关项目和中国科学院知识创新工程重大项目。曾获机械部科技进步特等奖1项,省部级科技进步二等奖1项,发表学术论文20余篇。
通讯作者:朱一行.E-mail:zhuyihang1123@hotmail.com.

更新日期/Last Update: 2015-08-28
Copyright © 《 智能系统学报》 编辑部
地址：（150001）黑龙江省哈尔滨市南岗区南通大街145-1号楼 电话：0451- 82534001、82518134　邮箱：tis@vip.sina.com