Journal of Guangdong University of Technology ›› 2021, Vol. 38 ›› Issue (05): 24-32.doi: 10.12052/gdutxb.210001

Previous Articles     Next Articles

A Research on Improved Genetic Algorithm for Flexible Job Shop Scheduling Problem Based on MPN

Wang Mei-lin, Zeng Jun-jie, Cheng Ke-qiang, Chen Xiao-hang   

  1. School of Information Engineering, Guangdong University of Technology, Guangzhou 510006, China
  • Received:2021-01-05 Online:2021-09-10 Published:2021-07-13

HTML

PDF (PC)

2543

Abstract: The large-scale HFS (Hybrid Flow Shop) system has the characteristics of large scale and many resource constraints, which causes dimension disasters during job scheduling, which results in difficult search and solution problems. Addressing such problems, an improved genetic algorithm is proposed, based on the MPN (Manufacturing Petri Net) model, with the makespan as the optimization goal. Firstly, the structure of the chromosome is redefined, and the corresponding algorithm of chromosome arrangement segment used to compress the search space. Secondly, the particle swarm optimization (PSO) optimization mechanism is used to guide the direction of chromosome optimization in the chromosome crossover operator, and the simulated annealing algorithm (SAA) mechanism used in the chromosome mutation operator to prevent the premature convergence of the genetic algorithm, and then after each population iteration, the current maximum individual uses the neighborhood search mechanism to try to improve the fitness of the best individual. Finally, the experimental data shows that the improved genetic algorithm has made great improvements in the optimization of the solution.

Key words: genetic algorithm, hybrid flow shop, makespan

CLC Number: 

  • F224.32
[1] GUPTA J N D. Two-stage, hybrid flowshop scheduling problem[J]. Journal of the Operational Research Society, 1988, 39: 359-364.
[2] 何军红, 马国伟, 刘赛, 等. MES柔性作业车间调度优化算法的研究[J]. 工业仪表与自动化装置, 2020(1): 26-32.
HE J H, MA G W, LIU S, et al. Research on MES flexible job shop scheduling optimization algorithm [J]. Industrial Instrumentation & Automation, 2020(1): 26-32.
[3] 王秀萍. 一种面向柔性作业车间调度的启发式算法[J]. 电脑知识与技术, 2017, 13(23): 216-218.
[4] 何涛. 面向智能制造的柔性车间调度算法研究[J]. 生产力研究, 2019(8): 132-135, 154.
HE T. Research on flexible shop scheduling algorithm for intelligent manufacturing [J]. Productivity Research, 2019(8): 132-135, 154.
[5] 黄亚平, 王万良, 熊婧. 基于改进蚁群算法的智能调度系统设计与开发[J]. 浙江工业大学学报, 2010, 38(3): 251-256.
HUANG Y P, WANG W L, XIONG J. Design and implementation of intelligent scheduling system based on improved ant colony algorithm [J]. Journal of Zhejiang University of Technology, 2010, 38(3): 251-256.
[6] 田松龄, 陈东祥, 王太勇, 等. 一种异步蚁群算法求解柔性作业车间调度问题[J]. 天津大学学报, 2016, 49(9): 920-928.
TIAN S L, CHEN D X, WANG T Y, et al. An asynchronous parallel ant colony optimization for flexible job-shop scheduling problem [J]. Journal of Tianjin University, 2016, 49(9): 920-928.
[7] 白俊峰, 贾志浩, 白一辰. 基于改进遗传算法的车间调度问题研究[J]. 现代制造技术与装备, 2019(12): 198-200.
BAI J F, JIA Z H, BAI Y C. Research on job shop scheduling problem based on improved genetic algorithm [J]. Modern Manufacturing Technology and Equipment, 2019(12): 198-200.
[8] 余璇, 梁工谦, 董仲慧. 基于混合遗传禁忌搜索算法的多目标柔性作业车间调度[J]. 机械制造, 2016, 54(8): 90-93.
YU X, LIANG G Q, DONG Z H. Multi-objective & flexible job-shop scheduling based on hybrid genetic tabu search algorithm [J]. Machinery, 2016, 54(8): 90-93.
[9] 吴大立, 郑中祥, 尹项根, 等. 基于Petri网和多种群遗传算法的海洋核动力平台电力系统网络重构[J]. 电力自动化设备, 2020, 40(8): 160-166.
WU D L, ZHENG Z X, YIN X G, et al. Network reconstruction of offshore nuclear power platform power system based on Petri net and multi-population genetic algorithm [J]. Electric Power Automation Equipment, 2020, 40(8): 160-166.
[10] 田海霖, 洪良, 王艺翔, 等. 基于量子遗传算法优化粗糙-Petri网的电网故障诊断[J]. 西安工程大学学报, 2018, 32(6): 678-684.
TIAN H L, HONG L, WANG Y X, et al. Optimization of power grid fault diagnosis of rough-Petri network based on quantum genetic algorithm [J]. Journal of Xi'an Polytechnic University, 2018, 32(6): 678-684.
[11] WANG M L, ZHONG R Y, DAI Q Y, et al. A MPN-based scheduling model for IoT-enabled hybrid flow shop manufacturing [J]. Advanced Engineering Informatics, 2016, 30(4): 728-736.
[12] GHOLAMI O, SOTSKOV Y N, WERNER F, et al. A genetic algorithm for hybrid job-shop scheduling problems with minimizing the makespan or mean flow time [J]. Journal of Advanced Manufacturing Systems, 2018, 17(4): 461-486.
[13] LIN C S, LEE I L, WU M C, et al. Merits of using chromosome representations and shadow chromosomes in genetic algorithms for solving scheduling problems [J]. Robotics and Computer-integrated Manufacturing, 2019, 58: 196-207.
[14] 张国辉, 胡一凡, 孙靖贺. 改进遗传算法求解多时间约束的柔性作业车间调度问题[J]. 工业工程, 2020, 23(2): 19-25.
ZHANG G H, HU Y F, SUN J H. An improved genetic algorithm for flexible job shop scheduling problem with multiple time constraints [J]. Industrial Engineering Journal, 2020, 23(2): 19-25.
[15] 谢志强, 张伟涛, 杨静. 前移存在调整时间综合调度工序的算法[J]. 机械工程学报, 2012, 48(12): 169-177.
XIE Z Q, ZHANG W T, YANG J. Algorithm of moving integrated scheduling procedures with set-up time forward [J]. Journal of Mechanical Engineering, 2012, 48(12): 169-177.
[16] DAI M, TANG D, GIRET A, et al. Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints [J]. Robotics & Computer Integrated Manufacturing, 2019, 59: 143-157.
[1] Gary Yen, Li Bo, Xie Sheng-li. An Evolutionary Optimization of LSTM for Model Recovery of Geophysical Fluid Dynamics [J]. Journal of Guangdong University of Technology, 2021, 38(06): 1-8.
[2] Yang Xing-yu, Liu Wei-long, Jing Ming-yue, Zhang Yong. A Diversified Portfolio Selection Strategy Based on Fuzzy Return Rate [J]. Journal of Guangdong University of Technology, 2020, 37(05): 13-21.
[3] Zhao Xiao-jian. Cable-stayed Bridge Steel GirderMaintenance Strategy with Multiple Constraints Optimization Based on Genetic Algorithm [J]. Journal of Guangdong University of Technology, 2018, 35(04): 75-80.
[4] Li Yun, Wang Zhi-hong, Wang Qi, Qi Wen-guang, Li Bin, Ji Rui-bo, Long Zhi-hong. A Study of Multi-objective Optimal Placement of Water Quality Monitoring Stations Based on Improved NSGA-Ⅱ Algorithm [J]. Journal of Guangdong University of Technology, 2018, 35(02): 35-40.
[5] HE Yong, WEN Jie-Chang, HUANG Mei-Hua. The Three Layers of Large-scale Emergency Material Allocation Strategy Based on the GA [J]. Journal of Guangdong University of Technology, 2016, 33(02): 37-41.
[6] LI Song-Fang, LIU Wei. Genetic Operator Based on the Idea of Universal Gravitation [J]. Journal of Guangdong University of Technology, 2015, 32(1): 121-127.
[7] HAN Guang, LIU Hai-Lin. On Multi-constrained Application Layer Multicast Algorithm [J]. Journal of Guangdong University of Technology, 2015, 32(04): 118-122.
[8] LI Song-Fang, LIU Wei, XU Huai-Xiang. A New Genetic Algorithm Based on Drift and Wave Thought [J]. Journal of Guangdong University of Technology, 2014, 31(1): 40-45.
[9] Tang Ya-lian， Cai Yan-guang， Guo Shuai， Le Feng. SingleDepot Incident Vehicle Routing Problem Based on Chaos Genetic Algorithm [J]. Journal of Guangdong University of Technology, 2013, 30(3): 53-57.
[10] Guo Peizhen, Hu Gang, Fu Hui. Research on Path Planning with Random Time for Vehicle Navigation [J]. Journal of Guangdong University of Technology, 2012, 29(1): 35-38.
[11] Tu Jingxian， Liu Wei. A Genetic Algorithm Based on the Classification of the Auxiliary Group [J]. Journal of Guangdong University of Technology, 2012, 29(1): 39-42.
[12] Xu Lichao, Zhang Qi. Gait Optimizing of Humanoid Robots Using a New Method [J]. Journal of Guangdong University of Technology, 2012, 29(1): 50-54.
[13] TU Jing-Xian, LIU Wei. A Hybrid Genetic Algorithm Based on the Search Algorithm of the Steepest Direction [J]. Journal of Guangdong University of Technology, 2011, 28(4): 34-37.
[14] QIN Si-Liang, WANG Qing-Guo, QU Zhao-Ming-. A Study of Broadband, ThinLayer Electromagnetic Protection Materials Based on Genetic Algorithms [J]. Journal of Guangdong University of Technology, 2011, 28(3): 30-32.
[15] WEN Jin-Bao, CAI Yan-Guang. On the Optimization of Logistics Distribution Route Based on Self-adaption Niche Genetic Algorithm [J]. Journal of Guangdong University of Technology, 2011, 28(1): 20-23.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © 2017 Journal of Guangdong University of Technology
Add：729 East Dongfeng RD., Guangzhou PRC. Postcode: 510090
Tel：020-37626653,020-37626139,020-37626396
Email：xbzrb@gdut.edu.cn
Supported:Beijing Magtech