Please wait a minute...
浙江大学学报(工学版)
J4  2013, Vol. 47 Issue (6): 1022-1030    DOI: 10.3785/j.issn.1008-973X.2013.06.013
    
Genetic algorithm with new initialization mechanism for flexible job shop scheduling
ZHAO Shi-kui, FANG Shui-liang, GU Xin-jian
Institute of Modern Manufacture Engineering, Zhejiang University, Hangzhou 310027, China
Download:   PDF(0KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

A novel initialization method for machine chains was proposed based on short time and workloads balancing strategies to improve the quality of initial population for the flexible job shop scheduling genetic algorithm（GA-Ⅰ）. The uniform design principle was applied to combine alternative machines with the shortest processing time for each operation uniformly, and the initial population of machine chains optimization genetic algorithm（GA-Ⅱ） was constructed. Different weights were designed based on uniform design method, and the machine chains optimization fitness function with different weighted-combinations of total machine load and its variance was constituted. The optimized machine distribution chains were selected as the machine chains initial population for flexible job shop scheduling problem genetic algorithm（GA-Ⅰ）. Hybrid cross and mutation were operated on job and operation levels, thus an efficient algorithm for flexible job shop scheduling problem was achieved. Finally, the feasibility and validity of the proposed method was demonstrated with typical examples.

Published: 22 November 2013
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:

ZHAO Shi-kui, FANG Shui-liang, GU Xin-jian. Genetic algorithm with new initialization mechanism for flexible job shop scheduling. J4, 2013, 47(6): 1022-1030.

URL:

http://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2013.06.013     OR     http://www.zjujournals.com/eng/Y2013/V47/I6/1022


柔性车间调度的新型初始机制遗传算法

为了提高柔性作业车间调度求解遗传算法（GA-Ⅰ）的初始种群质量,提出一种基于短用时和设备均衡策略的机器链优化初始方法.运用均匀设计原理对每道工序的具有最短加工时间的可选机器进行均匀组合,形成机器分配链优化遗传算法（GA-Ⅱ）的初始群体|采用均匀设计法构造不同权值,形成机器总负荷和机器负荷方差的不同加权组合以构造机器链优化的适应度函数|通过GA-Ⅱ计算产生定量优化的机器分配链群体.将上述机器分配链优化群体作为柔性作业车间调度问题遗传算法（GA-Ⅰ）的机器链初始群体,并利用混合方式的交叉与变异在工件和工序级尺度上进行遗传操作,实现了FJSP的高效求解算法.通过典型算例验证了该方法的可行性和有效性.

［1］ SAIDI-MEHRABAD M,FATTAHI P. Flexib-le job shop scheduling by tabu search algori-thms［J］. The International Journal of Advanced Manufacturing Technology,2007,32: 563-570.

［2］ 李丹,高立群,马佳,等.基于动态双种群粒子群算法的柔性工作车间调度［J］.东北大学学报：自然科学版,2007,28（9）： 1238-1242.

LI Dan,GAO Li-qun,MA Jia,et al. A dynamic double-population particle swarm optimization algorithm for flexible job-shop scheduling［J］. Journal of Northeastern University: Natural Science,2007,28（9）： 1238-1242.

［3］ GAO J,SUN L Y,GEN M. A hybrid genetic and variable neighborhood descent for flexible job shop scheduling problems［J］. Computers & Operations Research,2008,35: 2892-2907.

［4］ 张维存,郑丕谔,吴晓丹.蚁群遗传算法求解能力约束的柔性作业车间调度问题［J］.计算机集成制造系统,2007,13（2）： 333-337,362.

ZHANG Wei-cun,ZHENG Pi-e,WU Xiao-dan. Solution to flexible job shop scheduling problems with capacitated constraints based on ant colony & genetic algorithms［J］. Computer Integrated Manufacturing Systems,2007,13（2）： 333-337,362.

［5］ 王云,冯毅雄,谭建荣,等.柔性作业车间分批调度多目标优化方法［J］.浙江大学学报：工学版,2011,45（4）： 719-726,764.

WANG Yun,FENG Yi-xiong,TAN Jian-rong,et al. Multi-objective optimization method of flexible job-shop lot-splitting scheduling［J］. Journal of Zhejiang University: Engineering Science,2011,45（4）： 719-726,764.

［6］ KACEM I,HAMMADI S,BORNE P. Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems［J］. IEEE Transactions on Systems,Man and Cybernetics,Part C: Applications and Reviews,2002,32（1）： 1-13.

［7］ ZHANG G H,GAO L,SHI Y. An effective genetic algorithm for the flexible job-shop scheduling problem［J］. Expert Systems with Applications,2011,38（4）： 3563-3573.

［8］ 张国辉,高亮,李培根,等.改进遗传算法求解柔性作业车间调度问题［J］.机械工程学报,2009,45（7）： 145-151.

ZHANG Guo-hui,GAO Liang,LI Pei-gen,et al. Improved genetic algorithm for the flexible job-shop scheduling problem［J］. Journal of Mechanical Engineering,2009,45（7）： 145-151.

［9］ XIA W J,WU Z M. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems［J］. Computers & Industrial Engineering,2005,48: 409-425.

［10］ 何大阔,王福利,贾明兴.遗传算法初始种群与操作参数的均匀设计［J］.东北大学学报：自然科学版,2005,26（9）： 828-831.

HE Da-kuo,WANG Fu-li,JIA Ming-xing. Uniform design of initial population and operational parameters of genetic algorithm［J］. Journal of Northeastern University: Natural Science,2005,26（9）：828-831.

［11］ 姚嫣菲. 基于改进遗传算法的车间作业调度问题研究［D］.杭州：浙江大学,2011.

YAO Yan-fei. Research on job-shop schedu-ling problem based on improved genetic algorithm［D］. Hangzhou: Zhejiang University,2011.

［12］ 方开泰. 均匀设计与均匀设计表［M］. 北京：科学出版社,1994.

［13］ 方开泰. 均匀设计［EB/OL］. ［2011-12-01］. http:∥www.math.hkbu.edu.hk/UniformDesign/.

［14］ 唐启义.DPS数据处理系统：实验设计、统计分析及数据挖掘［M］.北京：科学出版社,2010: 250-257.

［15］ 程方晓.基于自适应保持多样性遗传算法的汽车动力传动系多目标优化［D］.吉林：吉林大学,2011.

CHENG Fang-xiao. Multi-objective optimization of automotive powertrain based on adaptive maintain diversity genetic algorithm［D］. Jilin: Jilin University,2011.

［16］ 谷峰,陈华平,卢冰原.基于均匀设计的多目标遗传算法在柔性工作车间调度中的应用［J］.系统工程理论方法与应用,2006,15（6）： 548-551.

GU Feng,CHEN Hua-ping,LU Bing-yuan. Multi-objective genetic algorithm based on uniform design for flexible job shop scheduling［J］. Systems Engineering-Theory Methodology Applications,2006,15（6）： 548-551.

［17］ 邬文尧,蔡鸿明,姜丽红.柔性作业车间调度中的组合遗传优化研究［J］.计算机工程与应用.2009,45（22）： 183-186.

WU Wen-yao,CAI Hong-ming,JIANG Li-hong.Integrated genetic algorithm for flexible job-shop scheduling problem［J］. Computer Engineering and Applications,2009,45（22）： 183-186.

［18］ 王凌.车间调度及其遗传算法［M］.北京：清华大学出版社,2003.

［19］ 张超勇,饶运清,刘向军,等.基于POX交叉的遗传算法求解Job-Shop调度问题［J］.中国机械工程,2004,15（23）： 2149-2153.

ZHANG Chao-yong,RAO Yun-qing,LIU Xiang-jun,et al. An improved genetic algorithm for the job shop scheduling problem［J］. China Mechanical Engineering,2004,15（23）： 2149-2153.

［20］ ZHANG H P,GEN M. Multistage-based genetic algorithm for flexible job-shop scheduling problem［J］. Journal of Complexity International, 2005, 11: 223-232.

［21］ 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] 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.
[3] FANG Shui-liang, YAO Yan-fei, ZHAO Shi-kui. Improved genetic algorithm for flexible job shop scheduling[J]. J4, 2012, 46(4): 629-635.
[4] LIU Jia-hai, YANG Mao-lin. Fair scheduling algorithm on multi-core platforms based platforms[J]. J4, 2011, 45(9): 1566-1570.