论文部分内容阅读
多目标流水车间调度问题是实际生产活动中经常应用的一类组合优化问题,其主要是在满足相关约束的条件下,对工件和加工机器进行合理地排列组合,以使最终的绩效指标整体最优化。不同于单目标车间调度问题,多目标需要同时考虑两个及两个以上的目标以使总体达到最优,大大增加了问题难度,使求解过程变得更为复杂。因此,对多目标流水车间调度进行研究具有一定的应用价值。目前求解多目标流水车间调度问题的算法很多,但是很多算法在求解大规模复杂问题时往往存在较多限制。两阶段子群遗传算法(Two PhaseSub PopulationGenetic Algorithm,TPSPGA)虽然在解的多样性上有很大的优势,但求解质量有待进一步提高。基于分解的多目标进化算法(Multi-Objective Evolutionary Algorithm based on Decomposition,MOEA/D)由于种群规模和权重向量一直不变,在解的多样性上存在不足。在进化机制方面,传统的进化方法由于交叉、变异等随机机制在后期会破坏优势解,导致解的质量下降。本文针对流水车间调度的最小化总完工时间与最小化最大流程时间两个目标,提出一种基于区块的两阶段进化算法(Block-based Two Phase Evolutionary Algorithm,BTPEA)来求解生产调度优化问题。该算法分为两个阶段,第一阶段将种群分为若干个子群体,对每个子群体权重赋值,第二阶段将子群体重新合并成一个大群体,采用且比雪夫分解策略对群体分解。该算法的进化机制是通过若干代的传统遗传算产生较优子代,借鉴蚂蚁信息素浓度的思想对子代建立位置信息素矩阵和相依信息素矩阵并根据两矩阵挖掘区块,将区块与非区块重组形成人工染色体。最后对染色体进行重组,提高染色体的质量并使用二元竞赛法保留优势染色体。为了比较的算法的求解性能,使用Taillard标准实例对BTPEA、TPSPGA、MOGA/D、NSGA-II、SPEA-II等多种算法测试,并对测试结果进行分析。在解的分布上,BTPEA均处于图的最左下方,即都取得了较优的解。在D1_R值上,BTPEA取得了最低值,说明了该算法在解的多样性和收敛性上具有较优的求解效果。在C指标上,在C(A,x)的值均等于1或略小于1(A表示BTPEA,X表示其它算法),证明了该算法求得的解的质量较高。在计算机的运行时间上,BTPEA的运行时间明显低于其他算法。