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

doi:10.12052/gdutxb.210001

English Version Journal Login

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2026-05-27

- A Research on Improved Genetic Algorithm for Flexible Job Shop Scheduling Problem Based on MPN
- Vol. 38, Issue 5, Pages: 24-32(2021)
- 作者机构：
  
  广东工业大学信息工程学院,广东,广州,510006
- 作者简介：
- 基金信息：
- DOI：10.12052/gdutxb.210001
  CLC： F224.32
- Online First：10 September 2021，
  
  Published：2021
- 稿件说明：
移动端阅览
王美林, 曾俊杰, 成克强, 陈晓航. 改进遗传算法求解基于MPN混流制造车间调度问题[J]. 广东工业大学学报, 2021, 38(5): 24-32.

Wang Mei-lin, Zeng Jun-jie, Cheng Ke-qiang, et al. A Research on Improved Genetic Algorithm for Flexible Job Shop Scheduling Problem Based on MPN[J]. 2021, 38(5): 24-32.
王美林, 曾俊杰, 成克强, 陈晓航. 改进遗传算法求解基于MPN混流制造车间调度问题[J]. 广东工业大学学报, 2021, 38(5): 24-32. DOI： 10.12052/gdutxb.210001.

Wang Mei-lin, Zeng Jun-jie, Cheng Ke-qiang, et al. A Research on Improved Genetic Algorithm for Flexible Job Shop Scheduling Problem Based on MPN[J]. 2021, 38(5): 24-32. DOI： 10.12052/gdutxb.210001.

摘要

大规模混流制造系统存在规模大、资源约束多的特点

造成在作业调度时产生维数灾难

从而产生搜索求解难的问题。本文针对此类问题

在基于(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.

关键词

Keywords

references

GUPTA J N D. Two-stage, hybrid flowshop scheduling problem[J]. Journal of the Operational Research Society, 1988, 39: 359-364.

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.

王秀萍. 一种面向柔性作业车间调度的启发式算法[J]. 电脑知识与技术, 2017, 13(23): 216-218.

HE T. Research on flexible shop scheduling algorithm for intelligent manufacturing [J]. Productivity Research, 2019(8): 132-135, 154.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Fuzzy Graph Neural Network-based Industrial Internet Service Component Orchestration Method

Collaborative Treatment Scheduling Algorithm Based on Intelligent Optimization

Cable-stayed Bridge Steel GirderMaintenance Strategy with Multiple Constraints Optimization Based on Genetic Algorithm

Genetic Operator Based on the Idea of Universal Gravitation

On Multi-constrained Application Layer Multicast Algorithm

Related Author

Wang Tao

Cheng Lianglun

Liu Anxin

Li Min

Duan Yu-hui

Xu Wan-sen

Hu Xiao-min

Zhao Xiao-jian

Related Institution

School of Computer Science and Technology, Guangdong University of Technology

School of Automation, Guangdong University of Technology

Guangdong Expressway Co., Ltd. 1

AI问答

⁰