基于改进精英策略的PCA-NSGAⅡ的高维目标调度优化

Many-objectives scheduling optimization based on PCA-NSGAⅡwith improved elite strategy

为提高制造系统中高维目标调度优化算法的求解性能,更好地在收敛性和分布性之间保持平衡,提出一种改进精英策略的PCA-NSGAⅡ算法。根据实际生产的需求,建立以最小化生产总成本、最大完工时间、提前/拖期惩罚和制造过程碳排放为目标的调度优化模型。针对现有高维目标调度优化领域采用基于权重化函数的算法求解质量差、搜索效率低等问题,将理论研究中基于主成分分析(PCA)的占优机制引入高维目标调度优化领域;设计了一种PCA-NSGAⅡ算法,为提高算法的求解质量和收敛性能,提出一个外部种群多样性维护方法来改进精英策略,将优秀个体纳入外部种群,丰富种群结构。通过算例分析,并与其他3种算法的结果进行对比,所提算法在求解质量和收敛性能上均具有优势;验证了基于PCA占优机制的高维目标处理方法能够在考虑所有目标特征的同时增大选择压力,有效地解决高维目标调度优化问题。

To improve the performances of many-objectives scheduling optimization algorithm in a manufacturing system and balance performances between convergences and diversities,a Principal Component Analysis-fast elitist Non-dominated Sorting Genetic Alogorithm(PCA-NSGAⅡ)with an improved elitist strategy was proposed.To meet demands of actual production scheduling problems,a many-objectives scheduling optimization model was proposed to minimize total production cost,makespan,earliness/tardiness penalty and carbon emissions in manufacturing processes.Currently almost all researches on many-objectives scheduling optimization used algorithms based on weight functions,which would lead to poor solution quality or low efficiency of researching.A dominance mechanism based on Principal Component Analysis(PCA)that had been proposed and used on theoretical researches of many-objectives optimization was first adopted to solve many-objectives scheduling optimization problems.A PAC-NSGAⅡalgorithm was designed.To improve solution qualities and convergences of the algorithm,a method to ensure diversities of external populations was proposed to improve its elite strategy.A case study was analyzed,and results were compared with that of other three algorithms.The result showed that the proposed algorithm had advantages in both solution qualities and convergences.It could consider features of all objectives and increase selection pressures,and could effectively solve many-objectives scheduling problems.