计算机工程与应用 ›› 2021, Vol. 57 ›› Issue (19): 274-281.DOI: 10.3778/j.issn.1002-8331.2006-0067

• 工程与应用 • 上一篇    下一篇

基于改进NSGA-II的车间排产优化算法研究

周原令,胡晓兵,江代渝,李航   

  1. 四川大学 机械工程学院,成都 610065
  • 出版日期:2021-10-01 发布日期:2021-09-29

Research on Optimization Algorithm of Workshop Scheduling Based on Improved NSGA-II

ZHOU Yuanling, HU Xiaobing, JIANG Daiyu, LI Hang   

  1. College of Mechanical Engineering, Sichuan University, Chengdu 610065, China
  • Online:2021-10-01 Published:2021-09-29

摘要:

针对NSGA-II算法在处理车间排产优化问题中出现的子代种群多样性差、收敛能力差等问题,提出了一种改进NSGA-II的车间排产优化算法。改进NSGA-II算法主要对传统NSGA-II算法的交叉和变异环节,提出新的改进自适应交叉和变异算子,通过对个体拥挤度与种群平均拥挤度进行对比,并结合种群迭代进化过程,将遗传概率与种群个体及种群进化迭代次数关联,避免盲目导向性,提高种群的收敛速度;提出新的均匀进化精英保留策略,通过自适应分层次选取种群个体,解决子代种群多样性差的问题。针对车间排产问题,选择“最大化最小交货提前期”和“最小化最大理想加工时间偏差”作为目标函数,运用改进NSGA-II算法进行实际工程的仿真分析,对比改进前后算法优化的结果,验证了算法的有效性,同时证明了其应用于实际生产排产调度问题的价值参考性。

关键词: 改进NSGA-II算法, 自适应交叉和变异算子, 均匀进化精英保留策略, 排产优化

Abstract:

Aiming at the problems of poor population diversity and convergence ability of the progeny of NSGA-II algorithm in dealing with shop floor scheduling optimization, an improved NSGA-II algorithm is proposed. The new algorithm mainly proposes the new improved adaptive crossover and mutation operators for the crossover. It compares the individual crowding degree with the population average crowding degree, and combines with the population iterative evolution process. The genetic probability is associated with the population individual and the population evolution iteration times. So it avoids blind guidance and improves the convergence speed of the population. The new algorithm proposes the new uniform evolution elite retention strategy. Through choosing the population individuals via the adaptive hierarchy, it solves the problem of the poor diversity of the population of the offspring. Finally, it regards “maximize the minimum delivery lead time” and “minimize the maximum ideal processing time deviation” as the objective function. In the light of the problem of shop floor scheduling, it uses the improved NSGA-II algorithm to carry out the simulation analysis of the actual project. And by comparing the results of the algorithm optimization before and after the improvement, the effectiveness of the algorithm is verified. Its value parameter applied to the actual production scheduling problem examination is also proved.

Key words: improved NSGA-II algorithm, adaptive crossover and mutation operator, uniform evolutionary elitist retention strategy, scheduling optimization