Computer Engineering and Applications ›› 2019, Vol. 55 ›› Issue (13): 260-265.DOI: 10.3778/j.issn.1002-8331.1809-0246

Previous Articles     Next Articles

Improved NSGA for Multi-Objective Flexible Job-Shop Scheduling Problem

JU Luyan1, YANG Jianjun2, ZHANG Jianbing1, GUO Longlong1, LI Suobin1   

  1. 1.College of Mechanical Engineering, Xi’an Shiyou University, Xi’an 710065, China
    2.School of Mechanical and Automotive Engineering, Qingdao University of Technology, Qingdao, Shandong 266520, China
  • Online:2019-07-01 Published:2019-07-01



  1. 1.西安石油大学 机械工程学院,西安 710065
    2.青岛理工大学 机械与汽车工程学院,山东 青岛 266520

Abstract: During the evaluation process of the job-shop scheduling problem, the algorithm and multi-objective optimization are very important. Therefore, an improved genetic algorithm based on NSGA is proposed and the corresponding matrix coding, decoding and crossover operators are designed. To reduce the computational complexity and improve the performance of the algorithm, a novel non-dominated sorting method, adaptive mutation operators and elite retention strategies are introduced. The simulation experiments show that this non-dominated sorting method can get the Pareto optimal solutions quickly and correctly by dividing the whole population into three parts. This algorithm can make full use of the global searching ability of traditional genetic algorithm, prevent the occurrence of precocious phenomenon, and change the mutation probability according to the diversity of the population.

Key words: flexible job-shop scheduling problem, multi-objective optimization, non-dominated sorting genetic algorithm

摘要: 在多目标柔性车间作业调度问题的研究中,求解算法与多目标处理至关重要。因此,基于非支配排序遗传算法提出了改进遗传算法求解该问题,设计了相应的矩阵编码、交叉算子,改进了非劣前沿分级方法,并提出了基于Pareto等级的自适应变异算子以及精英保留策略。实例计算表明,该算法可以利用传统遗传算法全局搜索能力的同时可以防止早熟现象的发生。改进非劣前沿分级方法可以快速得到Pareto最优解集,进一步减小了计算复杂度,而且可以根据种群的多样性改变变异概率,有利于保持种群多样性、发掘潜力个体。

关键词: 柔性车间作业调度, 多目标优化, 非劣前沿分级遗传算法