Please wait a minute...
浙江大学学报(工学版)
J4  2012, Vol. 46 Issue (4): 629-635    DOI: 10.3785/j.issn.1008-973X.2012.04.009
    
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
Download:   PDF(0KB) HTML
Export: BibTeX | EndNote (RIS)      

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.

Published: 17 May 2012
CLC:  TP 301.6  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

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

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2012.04.009     OR     http://www.zjujournals.com/eng/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] LIU Jia-hai, YANG Mao-lin, LEI Hang, LIAO Yong. Multicore real-time task allocation algorithms with shared resource constraints[J]. J4, 2014, 48(1): 113-117.
[2] ZHAO Shi-kui, FANG Shui-liang, GU Xin-jian. Genetic algorithm with new initialization mechanism for flexible job shop scheduling[J]. J4, 2013, 47(6): 1022-1030.
[3] ZHANG Jun-chao, YUE Mao-xiong, LIU Hua-feng. Dynamic PET image reconstruction with Geometrical structure
prior constraints[J]. J4, 2012, 46(6): 961-966.
[4] LIU Jia-hai, YANG Mao-lin. Fair scheduling algorithm on multi-core platforms based platforms[J]. J4, 2011, 45(9): 1566-1570.