。1070 北京科技大学学报 第31卷 敛性和多样性上具有更大的优势.本文采用的 3.2交叉和变异 Pareto遗传算法包括交叉、变异、选择、离散变量圆 为了保证优秀个体不会因为交叉变异被破坏， 整算子、小生境算子和Pareto解集过滤器六个算 采用精英保留策略，使当前群体中适应度最高的 子.其中，小生境能够阻止种群的早熟收敛，使个体 Pareto解个体不参与交叉和变异.为了保证Pareto 均匀分布在Pareto前沿，从而维持种群的多样性. 解的多样性，每代进化过程中对适应度非常接近的 Pareto解集过滤器能过滤出每一代的非劣解，最终 个体采用小生境技术处理：因为在运算过程中，人工 形成均匀分布的Pareto解集14 群体规模有限和算子产生的随机误差导致基因漂移 3.1编码与解码 现象.小生境技术能防止基因漂移，使群体均匀地 可重入生产调度模型不仅要确定工序的加工顺 分布在Pareto最优解集中坶 序，还需为每道工序选择一台合适的机器，因此仅采 3.3终止条件 用基于工序的传统编码方法不能得到问题的解.为 设定：种群规模P,最大进化代数T,当运行代 适应可重入生产系统的特殊性，采用染色体两层编 数达到T时，进化终止 码方案1月.第1层编码为各工序的优先权随机数， 4应用算例与仿真结果分析 1,Q]中产生，其中Q表示总的工序数.第2层 编码是各工序所选择的加工机器，从原始数据表中 在可重入钢管生产中，假设工件经组批计划得 随机选出对应机器.对于编码方案的解码主要是排 到四批待加工钢管，分别是形、W2、W3和W4,可 定工序加工的顺序，将各工件的加工工序看作关键 重入生产系统为三个加工站，五台机器(J1为2台， 路径网络图上的顶点.结合各工序的优先权随机数 J2为2台，J3为1台)，计为M11、M12、M21、M22和 对关键路径网络图进行拓扑排序后得到每个工件的 M31,其主要数据如表1所示.根据上文所述的轧批 最后完成时间. 排序计划求解最优化排序. 表1工序加工时间表 Table I Pmduct ion time of each process 工件 工序号V 加工时间（机器号） 交货期窗口[a,勾 工件工序号1 加工时间（机器号） 交货期窗口e。lg Vi 4(Mn).5(Mp) Va 2(M1,3(M12 Vie 6(Mu),5(Mn) V32 4(M21,3(M22 ViB 4(M) Va3 5(M3i) Via 5(Mm,3(Me) 【28.30 3 V 4M1i,5(M12) 【20.2☑ V12 3(Ma).4(M) V 5M2i,4(M22J Vis 1(M) V23 3(M3 V2u 3(Mi,5(M Vat 6(M1,4(M12 V22 3(M),5(Mm) Vaz 7(M2iJ,5(M22) V23 1(M) Vas 5(M3) [25,27 4 [27,29 V22 3(Mu),3(Mp) Ve 5(M1i,3(M12) V22 5(Mu,2(M2J Ve 4M2,3(M22) V28 3(M) Ves 2(M3) 根据上述算法设计，采用MATLAB编程遗传 表2最优化结果 算法中的运行参数为：群体大小M=100,终止代数 Table 2 Optimal solutions T=3000.交叉概率P=0.7,变异概率Pm=0.01. 优化算法 最后完工时间/h交货期满意度机器总负荷 设客户满意度函数中提前，拖期惩罚权重a1、a2各 基于Pareto的 29 0 78 为05.当三个目标同时优化时，由于Pareto最优 GA SPT规则 29 78 解集构成曲面，无法通过图直观显示，从解集中可获 取一个Pareto最优解，如表2所示，图3为Pareto最 从基于Pareto的遗传算法得到的最优解及 优解对应的甘特图.相应地，用最短加工时间 SPT规则得到的解，各工件的最后完工时间c。如表 (SPT)规则进行优化，其结果如表2所示. 3所示.从表2、表3可知，在该案例的优化中，基于敛性和多样性上具有更大的优势.本文采用的 Pareto 遗传算法包括交叉、变异、选择、离散变量圆 整算子 、小生境算子和 Pareto 解集过滤器六个算 子.其中, 小生境能够阻止种群的早熟收敛, 使个体 均匀分布在 Pareto 前沿, 从而维持种群的多样性 . Pareto 解集过滤器能过滤出每一代的非劣解, 最终 形成均匀分布的 Pareto 解集[ 14] . 3.1 编码与解码 可重入生产调度模型不仅要确定工序的加工顺 序, 还需为每道工序选择一台合适的机器, 因此仅采 用基于工序的传统编码方法不能得到问题的解 .为 适应可重入生产系统的特殊性, 采用染色体两层编 码方案[ 15] .第 1 层编码为各工序的优先权随机数, 在[ 1, Q] 中产生, 其中 Q 表示总的工序数 .第 2 层 编码是各工序所选择的加工机器, 从原始数据表中 随机选出对应机器.对于编码方案的解码主要是排 定工序加工的顺序, 将各工件的加工工序看作关键 路径网络图上的顶点, 结合各工序的优先权随机数 对关键路径网络图进行拓扑排序后得到每个工件的 最后完成时间. 3.2 交叉和变异 为了保证优秀个体不会因为交叉变异被破坏, 采用精英保留策略, 使当前群体中适应度最高的 Pareto 解个体不参与交叉和变异.为了保证 Pareto 解的多样性, 每代进化过程中对适应度非常接近的 个体采用小生境技术处理;因为在运算过程中, 人工 群体规模有限和算子产生的随机误差导致基因漂移 现象 .小生境技术能防止基因漂移, 使群体均匀地 分布在 Pareto 最优解集中[ 14] . 3.3 终止条件 设定 :种群规模 P, 最大进化代数 T, 当运行代 数达到 T 时, 进化终止. 4 应用算例与仿真结果分析 在可重入钢管生产中, 假设工件经组批计划得 到四批待加工钢管, 分别是 W1 、W2 、W3 和 W4, 可 重入生产系统为三个加工站, 五台机器( J 1 为 2 台, J 2 为 2 台, J 3 为 1 台), 计为 M11 、M12 、M21 、M22和 M31, 其主要数据如表1 所示.根据上文所述的轧批 排序计划求解最优化排序. 表 1 工序加工时间表 Table 1 Production time of each process 工件 工序号 Vok i 加工时间( 机器号) 交货期窗口[ eo, lo] V 111 4( M 11) , 5( M 12) V 112 6( M 21) , 5( M 22) 1 V 113 4( M 31 ) [ 28, 30] V 121 5( M 11 ) , 3( M 12 ) V 122 3( M 21 ) , 4( M 22 ) V 123 1( M 31 ) V 211 3( M 11 ) , 5( M 12 ) V 212 3( M 21 ) , 5( M 22 ) 2 V 213 1( M 31 ) [ 25, 27] V 221 3( M 11) , 3( M 12) V 222 5( M 21) , 2( M 22) V 223 3( M 31) 工件 工序号 Vok i 加工时间( 机器号) 交货期窗口[ eo, l o] V 311 2( M11) , 3( M12) V 312 4( M21) , 3( M22) 3 V 313 5( M31 ) [ 20, 22] V 321 4( M11 ) , 5( M12 ) V 322 5( M21 ) , 4( M22 ) V 323 3( M31 ) V 411 6( M11 ) , 4( M12 ) V 412 7( M21 ) , 5( M22 ) 4 V 413 5( M31 ) [ 27, 29] V 421 5( M11) , 3( M12) V 422 4( M21) , 3( M22) V 423 2( M31) 根据上述算法设计, 采用 MAT LAB 编程, 遗传 算法中的运行参数为:群体大小 M =100, 终止代数 T =3 000, 交叉概率 Pc =0.7, 变异概率 Pm =0.01 . 设客户满意度函数中提前 、拖期惩罚权重 a1 、a2 各 为 0.5 .当三个目标同时优化时, 由于 Pareto 最优 解集构成曲面, 无法通过图直观显示, 从解集中可获 取一个Pareto 最优解, 如表 2 所示, 图3 为 Pareto 最 优解对 应的甘特图 .相应地, 用 最短加工时 间 ( SPT)规则进行优化, 其结果如表 2 所示. 表 2 最优化结果 Table 2 Optimal solutions 优化算法 最后完工时间/ h 交货期满意度 机器总负荷 基于 Pareto 的 29 0 78 GA S PT 规则 29 1 78 从基于 Pareto 的遗传算法得到的最优解及 SPT 规则得到的解, 各工件的最后完工时间 co 如表 3 所示 .从表 2 、表 3 可知, 在该案例的优化中, 基于 · 1070 · 北 京 科 技 大 学 学 报 第 31 卷