基于贪婪元胞遗传算法的工序排序优化问题  

The Optimization Problem of Operation Sequencing Based on Greedy Cellular Genetic Algorithm

作　　者：邓燕兰 熊菊霞[1] 郑宏宇 姚光磊 DENG Yanlan;XIONG Juxia;ZHENG Hongyu;YAO Guanglei(School of Mathematics and Physics,Guangxi University for Nationalities,Nanning 530006,China)

机构地区：[1]广西民族大学数学与物理学院,广西南宁530006

出　　处：《广西民族大学学报（自然科学版）》2021年第4期79-86,共8页Journal of Guangxi Minzu University ：Natural Science Edition

基　　金：2019年广西自然科学基金面上项目(2019GXNSFAA185033);2021年广西高校中青年教师科研基础能力提升项目(2021KY0168);2020年广西民族大学引进人才科研启动项目(2020KJQD05)

摘　　要：工序排序优化问题是一类以最小化总成本为目标,工序受到优先关系约束的NP问题。为了寻求此类问题的最优解,在元胞遗传算法的基础上提出了一种贪婪元胞遗传算法(GCGA)。该算法首先使用拓扑排序算法生成初始方案的工序顺序;然后引入贪婪算法生成初始可行工序序列的加工资源;最后分别在交叉和变异后设置精英个体保留策略。GCGA算法能够使初始种群的工序顺序满足优先关系的约束,降低初始方案的总成本,保持迭代过程中加工方案的可行性,提高收敛速度和收敛精度。为了验证算法的有效性,将算法应用于实际案例,与7种典型算法进行对比。实验结果表明:该算法获得的解的平均质量优于已知对比算法。The optimization problem of operation sequencing is a NP⁃hard problem with the objective of minimizing the total cost and the operation constrained by the priority relation.In order to find the optimal solution of this problem,a greedy cellular genetic algorithm(GCGA)is proposed based on cellular genetic algorithm.This algorithm first uses the topological sorting algorithm to generate the operation sequence of the initial scheme,then introduces the greedy algorithm to generate the processing resources of the initial feasible operation sequence,and finally sets the elite individual retention strategy after crossover and mutation respectively.GCGA can make the operation sequence of the initial population which can satisfy the constraints of the priority relation,reduce the total cost of the initial scheme,maintain the feasibility of the processing plan in the iterative process,and improve the convergence speed and convergence accuracy.In order to evaluate the effectiveness of the algorithm,the algorithm is applied to a practical case and compared with seven typical algorithms.Experimental results show that the average quality of the solutions obtained by this algorithm is better than that of the comparison algorithm.

关 键 词：工序排序优化问题 元胞遗传算法 拓扑排序算法 贪婪算法 精英个体保留策略 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TH162.1[自动化与计算机技术—计算机科学与技术]