广东工业大学学报 ›› 2021, Vol. 38 ›› Issue (05): 24-32.doi: 10.12052/gdutxb.210001

• • 上一篇    下一篇

改进遗传算法求解基于MPN混流制造车间调度问题

王美林, 曾俊杰, 成克强, 陈晓航   

  1. 广东工业大学 信息工程学院，广东 广州 510006
  • 收稿日期:2021-01-05 出版日期:2021-09-10 发布日期:2021-07-13
  • 通信作者: 曾俊杰(1996–)，男，硕士研究生，主要研究方向为动态生产调度、制造物联网等，E-mail：1277742051@qq.com E-mail:1277742051@qq.com
  • 作者简介:王美林(1975–)，男，副教授，主要研究方向为制造物联网和工业互联网使能技术、生成过程调度与优化等
  • 基金资助:
    国家自然科学基金资助项目(U1701266)；广东省知识产权与大数据重点实验室项目(2018B030322016)；广东省科技计划项目(2019A050513011，2017B090901056)；广州市科技计划项目(202002030386)

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)

2464

摘要： 大规模混流制造系统存在规模大、资源约束多的特点, 造成在作业调度时产生维数灾难, 从而产生搜索求解难的问题。本文针对此类问题, 在基于(Manufacturing Petri Net, MPN)模型的基础上, 提出一种改进遗传算法进行求解。首先, 重新定义了染色体的结构, 并采用染色体安排段压缩求解的搜索空间。其次, 在染色体交叉环节用粒子群优化(Particle Swarm Optimization, PSO)优化机制引导染色体优化方向, 在染色体变异环节用模拟退火算法(Simulated Annealing Algorithm, SAA)的机制防止遗传算法的过早收敛。然后, 在每一次种群迭代后对当前最优个体采用邻域搜索机制尝试拔高最优个体的适应度。实验数据表明, 改进遗传算法在求解的最优性方面有了较大改进。

关键词: 遗传算法, 混合流水车间, 最短完工时间

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

中图分类号: 

  • 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, 栗波, 谢胜利. 地球流体动力学模型恢复的长短期记忆网络渐进优化方法[J]. 广东工业大学学报, 2021, 38(06): 1-8.
[2] 杨兴雨, 刘伟龙, 井明月, 张永. 基于模糊收益率的分散化投资组合调整策略[J]. 广东工业大学学报, 2020, 37(05): 13-21.
[3] 赵晓健. 基于遗传算法的多约束叠合梁斜拉桥钢梁维护策略优化[J]. 广东工业大学学报, 2018, 35(04): 75-80.
[4] 李云, 王志红, 王琦, 漆文光, 李斌, 吉瑞博, 龙志宏. 改进NSGA-Ⅱ算法在水质监测点多目标优化研究中的应用[J]. 广东工业大学学报, 2018, 35(02): 35-40.
[5] 许青林, 徐峰, 肖红, 刘沧生, 熊梦琪, 王志. 网络运维中现场作业任务调度的研究[J]. 广东工业大学学报, 2016, 33(04): 18-22.
[6] 何勇，温洁嫦，黄美华. 基于遗传算法的三层大规模应急救援物资配置策略[J]. 广东工业大学学报, 2016, 33(02): 37-41.
[7] 李松芳, 刘伟. 基于万有引力思想的遗传算子[J]. 广东工业大学学报, 2015, 32(1): 121-127.
[8] 韩广, 刘海林. 多约束的应用层组播算法研究[J]. 广东工业大学学报, 2015, 32(04): 118-122.
[9] 李松芳, 刘伟, 徐怀祥. 一种基于漂移和波动思想的遗传算法[J]. 广东工业大学学报, 2014, 31(1): 40-45.
[10] 汤雅连，蔡延光，郭帅，乐峰. 单车场关联物流运输调度问题的混沌遗传算法[J]. 广东工业大学学报, 2013, 30(3): 53-57.
[11] 郭佩珍，胡刚，傅惠. 基于随机时间的车辆导航路径规划研究[J]. 广东工业大学学报, 2012, 29(1): 35-38.
[12] 涂井先,刘伟. 基于辅助种群分类的遗传算法[J]. 广东工业大学学报, 2012, 29(1): 39-42.
[13] 徐李超，张祺. 一种仿人机器人步态优化的新方法研究[J]. 广东工业大学学报, 2012, 29(1): 50-54.
[14] 涂井先, 刘伟. 基于最速方向搜索的混合遗传算法[J]. 广东工业大学学报, 2011, 28(4): 34-37.
[15] 秦思良, 王庆国, 曲兆明. 基于遗传算法的宽带薄层电磁防护材料研究[J]. 广东工业大学学报, 2011, 28(3): 30-32.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2017 《广东工业大学学报》编辑部
地址：广州市东风东路729号广东工业大学 邮编：510090
电话：020-37626653,020-37626139,020-37626396
邮箱：xbzrb@gdut.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发