第3期 裴小兵，等：应用改进区块遗传算法求解置换流水车间调度问题 ·545· 的概率；CP:表示工件i的合并概率；W与W分别 表示区块的长度；P"表示第i条区块的第I个工 表示位置矩阵与相依矩阵的权重值，权重值会随 件的位置概率；CP表示第i个区块的第1个工件 着进化代数的增加不断改变。 的合并概率。 对最小长度外的位置进行工序选择时设立合 位置信息素矩阵 相依信息素矩阵 并概率最小阈值，作为筛选条件。当工件的合 并概率大于最小阈值时，选择该工件，否则停止 ---r 选择工件，本区块完成挖掘，如图9所示。因为当 区块包含的工件越多总体概率越低，组合错误的 概率越大，区块阈值将会保证区块的质量，同时 也将会导致挖掘出的区块长度也有所不同。挖掘 的区块均存放在区块资料库中。 CP=W(t/(+…+2)tW(ax+…+r》 CP=Wr2++atW(t+…ta》 3)区块竞争 区块竞争就是去除有重复信息的区块。将 CP=W(t/t+…+ra)tW(t(+…tt)》 假设CP,>CP>.…>CP选择 区块资料库中的区块的工序与位置进行比对，如 J.计算全局合并概率CP 果区块之间出现重复的工序或涵盖的位置重复， CP=W(t/《ti:+i+…+a)tW(t(rtr4t…+r)》 则通过比较平均概率的方式进行选择，平均概率 若CP大于國值，则选择 人.否则结束本区块 较大者保留至区块资料库，较小者则删除，举例 S:S:S; 如图10。平均概率的计算公式为 P+CPa 图9区块最小长度外的工件选择 i=2 1=1,2,…,n (7) Fig.9 Selection of workpieces outside the block minimum n 式中：i表示区块号；1表示区块的第1个位置；n length 区块资料库 新建区块资料库 位置1位置2位置3 位置5位置6位置7 位蜜1位置2位置3 选择 PG=0.66 PcG-0.55 P6=0.66 位置7位置8位置9 位置10位置11位置12 位置5位置6位置7 g P%=0.45 P%=0.42 J P=-0.55 图10区块竞争 Fig.10 Block competition 2.3组合染色体 位置顺序（由左到右），利用RWS方法根据合并概 本研究利用新建区块资料库中的区块和非区 率从剩余的工件中选择合适工件放入其中。例如 块资料库中的工件组合出较优染色体。先将区块 图11区块资料库中有2个区块，非区块资料库有 资料库中的所有区块复制到确定长度的空白染色 2个工件，合并概率CP6大于CP,选择J6放至位 体对应位置，对于尚未放入工序的空位置依照其 置5，剩下5放至位置9。 区块资料库 位置1位置2位置3位置4位置5位置6位置7位置8位置9 位置1位置2位置3位置4 位置6位置7位置8 C J: B2 通过RWS选择J6 非区块资料科库 L选择J 图11染色体组合 Fig.11 Chromosome combinationsCPi 的概率； 表示工件 i 的合并概率； W′ 与 W 分别 表示位置矩阵与相依矩阵的权重值，权重值会随 着进化代数的增加不断改变[14]。 对最小长度外的位置进行工序选择时设立合 并概率最小阈值[15] ，作为筛选条件。当工件的合 并概率大于最小阈值时，选择该工件，否则停止 选择工件，本区块完成挖掘，如图 9 所示。因为当 区块包含的工件越多总体概率越低，组合错误的 概率越大，区块阈值将会保证区块的质量，同时 也将会导致挖掘出的区块长度也有所不同。挖掘 的区块均存放在区块资料库中。 3) 区块竞争 区块竞争[16]就是去除有重复信息的区块。将 区块资料库中的区块的工序与位置进行比对，如 果区块之间出现重复的工序或涵盖的位置重复， 则通过比较平均概率的方式进行选择，平均概率 较大者保留至区块资料库，较小者则删除，举例 如图 10。平均概率的计算公式为 P AVG Bl = P dom B i l + ∑n i=2 CPB i l n , l = 1,2,··· ,n (7) 式中： i 表示区块号； l 表示区块的第 l 个位置；n P dow B i 1 i l CPB i l i l 表示区块的长度； 表示第 条区块的第 个工 件的位置概率； 表示第 个区块的第 个工件 的合并概率。 2.3 组合染色体 本研究利用新建区块资料库中的区块和非区 块资料库中的工件组合出较优染色体。先将区块 资料库中的所有区块复制到确定长度的空白染色 体对应位置，对于尚未放入工序的空位置依照其 CP6 CP5 J6 J5 位置顺序 (由左到右)，利用 RWS 方法根据合并概 率从剩余的工件中选择合适工件放入其中。例如 图 11 区块资料库中有 2 个区块，非区块资料库有 2 个工件，合并概率 大于 ，选择 放至位 置 5，剩下 放至位置 9。 位置信息素矩阵 … … … … … … … … … … … J1 J2 J3 … Jj - … - … - … … … … … … … … - CP2=W'* (τ ′ 32/(τ ′ 32+…+τ ′ i2 ))+W* (τ31/(τ31+…+τi1 )) CP3=W'* (τ ′ 42/(τ ′ 32+…+τ ′ i2 ))+W* (τ41/(τ31+…+τi1 )) CPi=W'* (τ ′ i2 /(τ ′ 32+…+τ ′ i2 ))+W* (τi1 /(τ31+…+τi1 )) CPT=W'* (τ ′ 33/(τ ′ 13+τ ′ 23+…+τ ′ i3 ))+W* (τ32/(τ32+τ42+…+τi1 )) … J1 J2 J3 S1 S2 S3 相依信息素矩阵 假设 CP3>CP4>…>CPi选择 J3，计算全局合并概率CPT 若 CPT 大于阈值，则选择 J3，否则结束本区块 S1 S2 S3 Sm J1 J2 J3 Ji τ ′ 11 τ ′ 21 τ ′ 12 τ ′ 13 τ ′ 22 τ ′ 23 τ ′ 31 τ ′ 32 τ ′ 33 τ ′ i1 τ ′ i2 τ ′ i3 J1 J2 J3 Ji τ ′ 21 τ ′ 12 τ ′ 13 τ ′ 1j τ ′ 2j τ ′ 3j τ ′ 23 τ ′ 31 τ ′ 32 τ ′ i1 τ ′ i2 τ ′ i3 τ ′ im τ ′ 3m τ ′ 2m τ ′ 1m 图 9 区块最小长度外的工件选择 Fig. 9 Selection of workpieces outside the block minimum length J1 J2 J3 位置1 位置2 位置3 J13 J9 J7 位置7 位置8 位置9 J8 J12 J11 位置5 位置6 位置7 J1 J5 J6 位置10 位置11 位置12 P AVG=0.45 B1 B2 P AVG=0.66 PB3 AVG B =0.55 1 B 2 B 3 B 4 PB4 AVG=0.42 区块资料库 新建区块资料库 选择 P AVG=0.55 B1 B3 P AVG=0.66 J1 J2 J3 位置1 位置2 位置3 J8 J12 J11 位置5 位置6 位置7 B 3 B 1 图 10 区块竞争 Fig. 10 Block competition Ci 位置5 Ci 通过 RWS 选择 J6 选择 J5 Ci J1 J2 J3 J4 J8 J7 J9 Ci B1 B2 区块资料库 位置1位置2位置3位置4 位置6位置7 位置8 J1 J2 J3 J4 J8 J7 J9 J1 J2 J3 J4 J6 J8 J7 J9 J1 J2 J3 J4 J6 J8 J7 J9 J5 非区块资料库 J5 J6 位置1位置2位置3位置4 位置6位置7位置8位置9 图 11 染色体组合 Fig. 11 Chromosome combinations 第 3 期 裴小兵，等：应用改进区块遗传算法求解置换流水车间调度问题 ·545·