基于关键工序的全局随机机器选择和改进GA求解FJSP

doi:10.11949/j.issn.0438-1157.20161625

化工学报 ›› 2017, Vol. 68 ›› Issue (3): 1073-1080.DOI: 10.11949/j.issn.0438-1157.20161625

基于关键工序的全局随机机器选择和改进GA求解FJSP

徐文星¹, 王琴^1,2, 边卫斌^1,2, 王万红^1,2, 董轶群¹

1 北京石油化工学院信息工程学院, 北京 102617;
2 北京化工大学信息科学与技术学院, 北京 100029

收稿日期:2016-11-16 修回日期:2016-11-26 出版日期:2017-03-05 发布日期:2017-03-05
通讯作者: 董轶群,dongyq@bipt.edu.cn
基金资助:
国家自然科学基金项目（61304217）；北京市教育委员会科技计划项目（KM201510017003）。

Improved GA and global random machine selection based on key operation to solve FJSP

XU Wenxing¹, WANG Qin^1,2, BIAN Weibin^1,2, WANG Wanhong^1,2, DONG Yiqun¹

1 College of Information Engineering, Beijing Institute of Petrochemical Technology, Beijing 102617, China;
2 College of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029, China

Received:2016-11-16 Revised:2016-11-26 Online:2017-03-05 Published:2017-03-05
Contact: 10.11949/j.issn.0438-1157.20161625
Supported by:
supported by the National Natural Science Foundation of China (61304217) and the Scientific Research Common Program of Beijing Municipal Commission of Education (KM201510017003).

摘要/Abstract

摘要：

以FJSP的最大完工时间作为优化目标，在考虑同一工件的工序顺序约束的同时，为提高初始种群的多样性，针对FJSP的机器选择问题采用堆栈方式存储工序。P-FJSP中只有一台机器可选的关键工序能直接影响机器总负荷和工件加工时间，进而提出了一种基于关键工序的全局随机选择（GRS）初始化方法。为了避免基本遗传算法在求解FJSP时陷入局部极优而停滞，在GA算法中加入再激活（re-activation）机制，旨在重新激活种群，增加种群的多样性。最后，针对FJSP基准测试算例进行数值分析，通过初始机器选择部分的性能对比实验、不同初始方式下遗传算法求解FJSP对比实验分别验证了GRS初始化机制的有效性和所提改进算法的可靠性。

关键词: 柔性作业车间调度, 优化, 种群多样性, 机器选择, GRS初始化机制, 再激活机制, 遗传算法, 数值分析

Abstract:

In order to improve the diversity of initial population and consider the operation sequence constraints of the same artifact at the same time, the stack was used to storage all operations in the view of the FJSP machine selection problem, in which the makespan was the optimization objective. Global random initialization method based on the key operation was proposed to solve the machine selection problem of FJSP, in which the key operation containing the only optional machine can directly affect the total load machine and processing time. To avoid the basic genetic algorithm trapped in local optimum when solving FJSP, re-activation mechanism was added to the GA algorithm, by which the diversity of population can be increased. Finally, in the view of the FJSP benchmark examples, the effectiveness of the GRS initialization mechanism and the reliability of the proposed improved algorithm were verified respectively by analyzing the performance comparison of the initial machine selection parts and the experimental results of solving FJSP by the genetic algorithm with different initializations.

Key words: flexible job-shop scheduling, optimization, species diversity, machine selection, GRS initialization mechanism, re-activation mechanism, genetic algorithm, numerical analysis

中图分类号:

徐文星, 王琴, 边卫斌, 王万红, 董轶群. 基于关键工序的全局随机机器选择和改进GA求解FJSP[J]. 化工学报, 2017, 68(3): 1073-1080.

XU Wenxing, WANG Qin, BIAN Weibin, WANG Wanhong, DONG Yiqun. Improved GA and global random machine selection based on key operation to solve FJSP[J]. CIESC Journal, 2017, 68(3): 1073-1080.

参考文献 30

[1]	BRANDIMARTE P. Routing and scheduling in a flexible job shop by tabu search[J]. Ann. Oper. Res., 1993, 41(3):157-183.
[2]	MASTROLOLLI M, GAMBBARDELLA L M. Effective neighborhood functions for the flexible job shop problem[J]. Journal of Scheduling, 2002, 3(1):3-20.
[3]	LI J Q, PAN Q K, SUGANTHAN P N, et al. A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2011, 52(52):683-697.
[4]	HO N B, TAY J C. GENACE:an efficient cultural algorithm for solving the flexible job-shop problem[C]//Proceedings of the 2004 Congress on Evolutionary Computation. Washington, D.C,USA:IEEE, 2004:1759-1766.
[5]	李铁克, 王伟玲, 张文学. 基于文化遗传算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2010, 16(4):861-866. LI T K, WANG W L, ZHANG W X. Solving flexible Job Shop scheduling problem based on cultural genetic algorithm[J]. Computer Integrated Manufacturing Systems, 2010, 16(4):861-866.
[6]	李修琳, 鲁建厦, 柴国钟, 等. 混合蜂群算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2011, 17(7):1495-1500. LI X L, LU J S, CHAI G Z, et al. Hybrid bee colony algorithm for flexible job shop scheduling problem[J]. Computer Integrated Manufacturing System, 2011, 17(7):1495-1500.
[7]	GAO K Z, SUGANTHAN P N, CHUA T J, et al. A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion[J]. Expert Systems with Applications, 2015, 42(21):7652-7663.
[8]	YUAN Y, XU H, YANG J D. A hybrid harmony search algorithm for the flexible job shop scheduling problem[J]. Applied Soft Computing, 2013, 13(7):3259-3272.
[9]	宋存利. 求解柔性作业调度问题的协同进化粒子群算法[J]. 计算机工程与应用, 2013, 49(21):15-18. SONG C L. Co-evolution particle swarm optimization algorithm for flexible job-shop scheduling problem[J]. Computer Engineering and Applications, 2013, 49(21):15-18.
[10]	SINGH M R, MAHAPATRA S S. A quantum behaved particle swarm optimization for flexible job shop scheduling[J]. Computers & Industrial Engineering, 2016, 93:36-44.
[11]	吴秀丽, 张志强, 杜彦华, 等. 改进细菌觅食算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2015, 21(5):1262-1270. WU X L, ZHANG Z Q, DU Y H, et al. Improved bacteria foraging optimization algorithm for flexible job shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2015, 21(5):1262-1270.
[12]	董蓉, 何卫平. 求解FJSP的混合遗传-蚁群算法[J]. 计算机集成制造系统, 2012, 18(11):2492-2501. DONG R, HE W P. Hybrid genetic algorithm-ant colony optimization for FJSP solution[J]. Computer Integrated Manufacturing Systems, 2012, 18(11):2492-2501.
[13]	ISHHIKAWA S, KUBBOA R, HORIO K. Effective hierarchical optimization by a hierarchical multi-space competitive genetic algorithm for the flexible job-shop scheduling problem[J]. Expert Systems with Applications, 2015, 42(24):9434-9440.
[14]	赵诗奎. 求解柔性作业车间调度问题的两极领域搜索混合算法[J]. 机械工程学报, 2015, 14:175-184. ZHAO S K. Bilevel neighborhood search hybrid algorithm for the flexible job shop scheduling problem[J]. Journal of Mechanial Engineering, 2015, 14:175-184.
[15]	CHANG H, CHEN Y, LIU T, et al. Solving the flexible job scheduling problem with makespan optimization by using a hybrid taguchi-genetic algorithm[J]. Access IEEE, 2015, 3:1740-1754.
[16]	LI X, GAO L. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J]. International Journal of Production Economics, 2016, 174:93-110.
[17]	ZHOU W, YAN-PING B U, ZHOU Y Q. An improved genetic algorithm for solving flexible job shop scheduling problem[C]//Control and Decision Conference. 2013:4553-4558.
[18]	CHANG H C, TAI H T, LIU T K. Application of genetic algorithm to optimize unrelated parallel machines of flexible job-shop scheduling problem[C]//IEEE International Conference on Control & Automation. IEEE, 2014:596-599.
[19]	MOGHADAM A M, WONG K Y, PIROOZFARD H. An efficient genetic algorithm for flexible job-shop scheduling problem[C]//IEEE International Conference on Industrial Engineering and Engineering Management. IEEE, 2015:1031-1044.
[20]	XU L, SUN W, MING H. Flexible job shop scheduling based on multi-population genetic-variable neighborhood search algorithm[C]//International Conference on Computer Science and Network Technology. IEEE, 2015:244-248.
[21]	ZHANG M, WU K. An improved genetic algorithm for the re-entrant and flexible job-shop scheduling problem[C]//Chinese Control and Decision Conference. IEEE, 2016:3399-3404.
[22]	REN H, XU H, SUN S. Immune genetic algorithm for multi-objective flexible job-shop scheduling problem[C]//Chinese Control and Decision Conference. IEEE, 2016.
[23]	WU X L, LI S J. Mass variety and small batch scheduling in the flexible job shop[C]//International Conference on Biomedical Engineering and Informatics, Bmei 2009. Tianjin, China, 2009:1-7.
[24]	张国辉, 高亮, 李培根, 等. 改进遗传算法求解柔性作业车间调度问题[J]. 机械工程学报, 2009, 45(7):145-151. ZHANG G H, GAO L, LI P G, et al. Improved genetic algorithm for the flexible job-shop scheduling problem[J]. Journal of Mechanial Engineering, 2009, 45(7):145-151.
[25]	张国辉. 柔性作业车间调度方法研究[D]. 武汉:华中科技大学, 2009. ZHANG G H. Research on methods for flexible job shop scheduling problems[D]. Wuhan:Huazhong University of Science and Technology, 2009.
[26]	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.
[27]	SHI Y, ZHANG G H, GAO L, et al. A novel initialization method for solving flexible job-shop scheduling problem[C]//Proceedings of International Conference on Computers & Industrial Engineering. Washington, D, C, USA:IEEE, 2009.
[28]	赵诗奎, 方水泉, 顾新建. 基于极限调度完工时间最小化的机器选择及FJSP求解[J]. 计算机集成制造系统, 2014, 20(4):854-865. ZHAO S K, FANG S Q, GU X J. Machine selection and FJSP solution based on limit scheduling completion time minimization[J]. Computer Integrated Manufacturing Systems, 2014, 20(4):854-865.
[29]	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:Applications and Reviews, 2002, 32(1):1-13.
[30]	KACEM I. Genetic algorithm for the flexible job-shop scheduling problem[J]. IEEE International Conference on Systems Man and Cybernetics, 2003, 4:3464-3469.

基于关键工序的全局随机机器选择和改进GA求解FJSP

Improved GA and global random machine selection based on key operation to solve FJSP

PDF (PC)

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献 30

相关文章 15

编辑推荐

Metrics

本文评价

[1]	杨欣, 王文, 徐凯, 马凡华. 高压氢气加注过程中温度特征仿真分析[J]. 化工学报, 2023, 74(S1): 280-286.
[2]	陈哲文, 魏俊杰, 张玉明. 超临界水煤气化耦合SOFC发电系统集成及其能量转化机制[J]. 化工学报, 2023, 74(9): 3888-3902.
[3]	齐聪, 丁子, 余杰, 汤茂清, 梁林. 基于选择吸收纳米薄膜的太阳能温差发电特性研究[J]. 化工学报, 2023, 74(9): 3921-3930.
[4]	何松, 刘乔迈, 谢广烁, 王斯民, 肖娟. 高浓度水煤浆管道气膜减阻两相流模拟及代理辅助优化[J]. 化工学报, 2023, 74(9): 3766-3774.
[5]	邢雷, 苗春雨, 蒋明虎, 赵立新, 李新亚. 井下微型气液旋流分离器优化设计与性能分析[J]. 化工学报, 2023, 74(8): 3394-3406.
[6]	张曼铮, 肖猛, 闫沛伟, 苗政, 徐进良, 纪献兵. 危废焚烧处理耦合有机朗肯循环系统工质筛选与热力学优化[J]. 化工学报, 2023, 74(8): 3502-3512.
[7]	诸程瑛, 王振雷. 基于改进深度强化学习的乙烯裂解炉操作优化[J]. 化工学报, 2023, 74(8): 3429-3437.
[8]	陈国泽, 卫东, 郭倩, 向志平. 负载跟踪状态下的铝空气电池堆最优功率点优化方法[J]. 化工学报, 2023, 74(8): 3533-3542.
[9]	刘文竹, 云和明, 王宝雪, 胡明哲, 仲崇龙. 基于场协同和耗散的微通道拓扑优化研究[J]. 化工学报, 2023, 74(8): 3329-3341.
[10]	文兆伦, 李沛睿, 张忠林, 杜晓, 侯起旺, 刘叶刚, 郝晓刚, 官国清. 基于自热再生的隔壁塔深冷空分工艺设计及优化[J]. 化工学报, 2023, 74(7): 2988-2998.
[11]	吴文涛, 褚良永, 张玲洁, 谭伟民, 沈丽明, 暴宁钟. 腰果酚生物基自愈合微胶囊的高效制备工艺研究[J]. 化工学报, 2023, 74(7): 3103-3115.
[12]	汤晓玲, 王嘉瑞, 朱玄烨, 郑仁朝. 基于Pickering乳液的卤醇脱卤酶催化合成手性环氧氯丙烷[J]. 化工学报, 2023, 74(7): 2926-2934.
[13]	邵远哲, 赵忠盖, 刘飞. 基于共同趋势模型的非平稳过程质量相关故障检测方法[J]. 化工学报, 2023, 74(6): 2522-2537.
[14]	江锦波, 彭新, 许文烜, 门日秀, 刘畅, 彭旭东. 泵出型螺旋槽油气密封泄漏特性及参数影响研究[J]. 化工学报, 2023, 74(6): 2538-2554.
[15]	孙永尧, 高秋英, 曾文广, 王佳铭, 陈艺飞, 周永哲, 贺高红, 阮雪华. 面向含氮油田伴生气提质利用的膜耦合分离工艺设计优化[J]. 化工学报, 2023, 74(5): 2034-2045.