Please wait a minute...
浙江大学学报(工学版)
J4  2012, Vol. 46 Issue (4): 629-635    DOI: 10.3785/j.issn.1008-973X.2012.04.009
能源与机械工程     
柔性车间调度的改进遗传算法
方水良, 姚嫣菲, 赵诗奎
浙江大学 机械工程学系,浙江 杭州 310027
Improved genetic algorithm for flexible job shop scheduling
FANG Shui-liang, YAO Yan-fei, ZHAO Shi-kui
Department of Mechanical Engineering, Zhejiang University, Hangzhou 310027, China
 全文: PDF 
摘要：

针对柔性车间调度提出改进遗传算法,采用机器分配链和工序顺序链的双链结构编码；对机器分配链设计基于拟水平均匀设计的初始化方法,对相应的工序顺序链采用剩余时间最短的启发式初始化方法；采用新生策略改进新一代种群的生成；有针对性地对个体的瓶颈工序进行交叉操作；基于极限最优适应度值和当前最优适应度值对种群个体选择性解码.针对常用的典型算例进行多方面的实验计算,并对实验结果进行对比分析,验证了改进遗传算法的有效性.
关键词： 柔性车间调度;  遗传算法;  瓶颈工序;  拟水平均匀设计;  启发式初始化    
Abstract:

An improved genetic algorithm was proposed for flexible job shop scheduling. Double chains structure with machines’allocation chain and operations’sequence chain was used to encode the chromosomes. Population’s machine-allocation-chains were initialized with quasi-level uniform design, and their operation-sequence-chains were heuristically initialized with longest remaining processing time first rule. New population was produced with some new-born chromosomes. Population crossover was improved with bottleneck-operation oriented method. Chromosome’s decoding was controlled with two rules based on the extreme fitness and the current optimal fitness. Multi-aspects case studies based on some typical benchmark examples from the literature were conducted, and the experimental results were compared. Results showed a quicker evolution speed and powerful optimizing capability.
Key words: flexible job shop scheduling    genetic algorithm    bottleneck operation    quasi-level uniform design    heuristic population initiation
出版日期: 2012-05-02
:  TP 301.6  
基金资助:

浙江省制造业信息化重大科技攻关项目（2006C11234）；国家“863”高技术研究发展计划资助项目（2011AA040601）.
作者简介: 方水良(1964—),男,副教授,从事制造执行系统、系统仿真、产品建模等研究.E-mail: me_fangsl@zju.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　

引用本文:

方水良, 姚嫣菲, 赵诗奎. 柔性车间调度的改进遗传算法[J]. J4, 2012, 46(4): 629-635.

FANG Shui-liang, YAO Yan-fei, ZHAO Shi-kui. Improved genetic algorithm for flexible job shop scheduling. J4, 2012, 46(4): 629-635.

链接本文:

http://www.zjujournals.com/xueshu/eng/CN/10.3785/j.issn.1008-973X.2012.04.009    或    http://www.zjujournals.com/xueshu/eng/CN/Y2012/V46/I4/629

［1］ 魏巍,谭建荣,冯毅雄,等.柔性工作车间调度问题的多目标优化方法研究［J］.计算机集成制造系统,2009,15(8): 1592-1598.
WEI Wei, TAN Jianrong, FENG Yixiong, et al. Multiobjective optimization method research on flexible job shop scheduling problem ［J］. Computer Integrated Manufacturing Systems, 2009, 15(8): 1592-1598.
［2］ 刘志勇,吕文阁,谢庆华,等.应用改进蚁群算法求解柔性作业车间调度问题［J］.工业工程与管理,2010,15(3): 115-119.
LIU Zhiyong, LV Wenge, XIE Qinghua, et al. Solving flexible jobshop scheduling problem based on an improved ant colony optimization algorithm ［J］. Industrial Engineering and Management, 2010, 15(3): 115-119.
［3］ 张超勇,饶运清,李培根,等.柔性作业车间调度问题的两级遗传算法［J］.机械工程学报,2007,43(4): 119-124.
ZHANG Chaoyong, RAO Yunqing, LI Peigen, et al. Bilevel genetic algorithm for the flexible jobshop scheduling problem ［J］. Chinese Journal of Mechanical Engineering, 2007, 43(4): 119-124.
［4］ 袁坤,朱剑英.一种求解多目标柔性Job Shop调度的改进遗传算法［J］.中国机械工程,2007,18（2）：156-160.
YUAN Kun, ZHU Jianying. Improved genetic algorithm for the flexible jobshop scheduling with multiobject ［J］. China Mechanical Engineering, 2007, 18(2): 156-160.
［5］ BAGHERI A, ZANDIEH M, MAHDAVI I, et al. An artificial immune algorithm for the flexible jobshop scheduling problem ［J］. Future Generation Computer Systems, 2010, 26(4): 533-541.
［6］ YAZDANI M, AMIRI M, ZANDIEH M. Flexible jobshop scheduling with parallel variable neighborhood search algorithm ［J］. Expert Systems with Applications, 2010, 37(1): 678-687.
［7］ XING Lining, CHEN Yingwu, WANG Peng, et al. A knowledgebased ant colony optimization for flexible job shop scheduling problems ［J］. Applied Soft Computing, 2010, 10(3): 888-896.
［8］ 方水良,姚嫣菲,赵诗奎.基于遗传算法的柔性车间多目标优化调度［J］.机电工程,2011,28(3): 269-274.
FANG Shuiliang, YAO Yanfei, ZHAO Shikui. Flexible jobshop scheduling with multiobjective based on genetic algorithm ［J］. Journal of Mechanical and Electrical Engineering,2011, 28(3): 269-274.
［9］ 方开泰.均匀设计及其应用［J］.数理统计与管理,1994,13（3）： 52-55.
FANG Kaitai. Uniform design and its application ［J］. Mathematical Statistics and Management, 1994, 13(3): 52-55.
［10］ KACEM I, HAMMADI S, BORNE P. Approach by localization and multiobjective evolutionary optimization for flexible jobshop scheduling problem ［J］. IEEE Transactions on Systems, Man and CyberneticsPart C: Application and Reviews, 2002, 32(1): 1-13.
［11］ KACEM I, HAMMADI S, BORNE P. Paretooptimality approach for flexible jobshop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic ［J］. Mathematics and Computers in Simulation, 2002, 60(3/4/5): 245-276.
［12］ XIA Weijun, WU Zhiming. An effective hybrid optimization approach for multiobjective flexible jobshop scheduling problems ［J］. Computers and Industrial Engineering, 2005, 48(2): 409-425.
［13］ BAGHERI A, ZANDIEH M, MAHDAVI I, et al. An artificial immune algorithm for the flexible jobshop scheduling problem ［J］. Future Generation Computer Systems, 2010, 26(4): 533-541.
[1] 赵斌, 张松, 李剑峰. 基于零件摩擦学性能的磨削参数优化[J]. 浙江大学学报(工学版), 2018, 52(1): 16-23.
[2] 张玄武, 郑耀, 杨波威, 张继发. 基于级联前向网络的翼型优化设计[J]. 浙江大学学报(工学版), 2017, 51(7): 1405-1411.
[3] 张丽娜, 余阳. 海量O2O服务组合的优化[J]. 浙江大学学报(工学版), 2017, 51(6): 1259-1268.
[4] 苏亮, 宋明亮, 董石麟, 罗尧治. 循环遗传聚类法稳定图自动分析[J]. 浙江大学学报(工学版), 2017, 51(3): 514-523.
[5] 张俊红,郭迁,王健,徐喆轩,陈孔武. 塑料机油冷却器盖加强筋参数的多目标优化[J]. 浙江大学学报(工学版), 2016, 50(7): 1360-1366.
[6] 司恩波, 王晶, 靳其兵, 周靖林. 工业无线网络链路选择与时隙分配的同步优化[J]. 浙江大学学报(工学版), 2016, 50(6): 1203-1213.
[7] 王树朋,黄凯,严晓浪. 基于遗传算法的覆盖率驱动测试产生器[J]. 浙江大学学报(工学版), 2016, 50(3): 580-588.
[8] 李清,胡志华. 基于多目标遗传算法的灾后可靠路径选择[J]. 浙江大学学报(工学版), 2016, 50(1): 33-40.
[9] 刘扬,鲁乃唯,蒋友宝. 结构体系可靠度分析的改进支持向量回归[J]. 浙江大学学报(工学版), 2015, 49(9): 1692-1699.
[10] 高史义, 罗小华, 卢宇峰, 刘富春, 张晨秋. 基于遗传算法的功能覆盖率收敛技术[J]. 浙江大学学报(工学版), 2015, 49(8): 1509-1515.
[11] 赵琼,童水光,钟崴,葛俊旭. 基于GA-FEA的门座起重机变幅机构优化设计[J]. 浙江大学学报(工学版), 2015, 49(5): 880-886.
[12] 苗峰,谢安桓,王富安,喻峰,周华. 多阶段可替换分组并行机调度问题的求解[J]. 浙江大学学报(工学版), 2015, 49(5): 866-872.
[13] 艾小祥,俞慈君,方强,陈磊,方伟,沈立恒. 基于遗传算法的机翼壁板扫描路径优化[J]. 浙江大学学报(工学版), 2015, 49(3): 448-456.
[14] 过海,倪益华,王进,陆国栋. 车用空调冷凝器性能多目标优化方法[J]. 浙江大学学报(工学版), 2015, 49(1): 142-159.
[15] 肖文生,崔俊国,刘健,吴晓东,黄红胜. 直驱采油用永磁同步电机削弱齿槽转矩优化[J]. 浙江大学学报(工学版), 2015, 49(1): 173-180.