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  HTML
摘要:

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

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.

出版日期: 2012-05-17
:  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/eng/CN/10.3785/j.issn.1008-973X.2012.04.009        http://www.zjujournals.com/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]. J4, 2014, 48(1): 113-117.
[2] 赵诗奎, 方水良, 顾新建. 柔性车间调度的新型初始机制遗传算法[J]. J4, 2013, 47(6): 1022-1030.
[3] 张俊超, 岳茂雄, 刘华锋. 结构先验约束的动态PET图像重建[J]. J4, 2012, 46(6): 961-966.
[4] 刘加海,杨茂林. 基于多核处理器平台的公平调度算法[J]. J4, 2011, 45(9): 1566-1570.