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

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

作　　者：王美林[1] 曾俊杰 成克强[1] 陈晓航 Wang Mei-lin;Zeng Jun-jie;Cheng Ke-qiang;Chen Xiao-hang(School of Information Engineering,Guangdong University of Technology,Guangzhou 510006,China)

机构地区：[1]广东工业大学信息工程学院,广东广州510006

出　　处：《广东工业大学学报》2021年第5期24-32,共9页Journal of Guangdong University of Technology

基　　金：国家自然科学基金资助项目(U1701266);广东省知识产权与大数据重点实验室项目(2018B030322016);广东省科技计划项目(2019A050513011,2017B090901056);广州市科技计划项目(202002030386)。

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

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

分 类 号：F224.32[经济管理—国民经济]