第2期 裴小兵，等：改进区块遗传算法解决分布式车间调度问题 ·307· 2.2构建概率矩阵模型 置的机会，将概率矩阵中每个位置的概率值增加 精英染色体是筛选出来的高适应度解序列。 0.01；在构建人工染色体的时，每个位置可以选到 为了有效地挖掘区块，MBGA依据迭代过程中筛 剩余工件的任意一个，增加了样本的多样性，避 选的精英染色体构建了两个概率矩阵：一个是工 免缩小搜索空间。 件-车间分配矩阵，另一个是工件-机器排序矩 阵。工件一车间排序矩阵强调的是工件和车间之 精英染色体 间的关系，工件一机器排序矩阵强调的是工件在 8216 工 工厂 4375 2 12 车间内机器上的加工顺序。 3/52/5 本文采用世代累加的方式建立概率模型，统 82 6 2/53/5 4375 计工件在机器上加工的频次，构建工件-机器排 3352/5 序矩阵。在构建和更新矩阵的过程中，工件被 43 86 4253/5 7512 51/54/5 分配到车间”，工件-车间分配矩阵中相应位置的 64/515 频次就会增加1。工件k和工件j分配到同一车 85 77 入N 0 1 间，且在机器上先后加工，工件-机器排序矩阵中 必 810 的相应位置增加1。然后，将相应的频次转化为 8136 概率矩阵，并随着迭代不断更新。 5742 工件-车间分配矩阵的迭代公式为 图2工件-车间分配概率矩阵示意 足：位 如果工件在工厂 Fig.2 Schematic diagram of job-shop assignment probab- (12) ility matrix i=1,2,…,r=1,2,…,fk=1,2,…, 精英染色体 T0=70-1+2xi=1,2…,m 8216 位置 位置 (13) 4375 4 1234 k=1 r=1,2,…,ft=1,2,…,G;k=1,2,…,s 8216 0 11/51/5350 4 201/5045 4375 式(12)和(13)中，X表示工件i分配到车间 30252515 r;k代表解序列号码；n代表工件数目；s代表精 4386 4351/5150 7512 5/5251/5/5 英染色体的个数；1代表当前迭代数；G代表总 6 0 4 8512 600/545 迭代次数；T0表示工件i分配到车间r的累加 2210 725251/50 7463 次数。 件83110 件835闪0 8136 工件-机器排序矩阵的迭代公式为 5742 龙=化买程工件在机 (14) 图3工件-位置排序矩阵示意 i=1,2,…,j=1,2,…,mk=1,2,…,m Fig.3 Schematic diagram of job-position sorting matrix 2.3区块挖掘 T0=T-1）+∑Xi=12…,i 精英染色体的解序列中拥有相似的解序列片 k=1 (15) 段，算法以区块的形式将这部分信息进行挖掘用 j=1,2,…,n:t=1,2,…,G:k=1,2,…,s 于构建高质量的人工染色体。区块是高适应度解 式中：表示工件i在机器j上的总加工次数。 序列中的部分片段，由精英染色体中的高频率的 具体的工件-车间分配矩阵的更新过程如图2 基因链接组成。区块将不同机器上加工时间互补 所示，假设C,C2,…,C3为5个用于更新分配矩阵 的工件组合起来，用于平衡工件在机器上的加工 的精英染色体；以工件5为例，有1个精英染色体 时间，优化同一车间内工件的排序过程，并确定 将工件5分配到车间1，有4个精英染色体将工工件的分配过程。高质量的区块保证了人工染色 件5分配到车间2，因此工件5分配到车间1的概 体的优势，又降低了排序的复杂程度。区块的规 率为1/5，分配到车间2的概率为4/5。工件-机器 模越大，构建人工染色体的过程就越简单，但由 排序矩阵的更新原理同分配矩阵的更新原理相 于工件-车间分配矩阵和工件-机器排序矩阵中 同（如图3） 的概率都小于1（图4中的Pock为挖掘该区块的 为确保工件j拥有分配到每个车间中每个位 频率)，所以区块规模越大，挖掘该区块的概率就2.2 构建概率矩阵模型 精英染色体是筛选出来的高适应度解序列。 为了有效地挖掘区块，MBGA 依据迭代过程中筛 选的精英染色体构建了两个概率矩阵：一个是工 件−车间分配矩阵，另一个是工件−机器排序矩 阵。工件−车间排序矩阵强调的是工件和车间之 间的关系，工件−机器排序矩阵强调的是工件在 车间内机器上的加工顺序。 本文采用世代累加的方式建立概率模型，统 计工件在机器上加工的频次，构建工件−机器排 序矩阵。在构建和更新矩阵的过程中，工件 j 被 分配到车间 r，工件−车间分配矩阵中相应位置的 频次就会增加 1。工件 k 和工件 j 分配到同一车 间，且在机器上先后加工，工件−机器排序矩阵中 的相应位置增加 1。然后，将相应的频次转化为 概率矩阵，并随着迭代不断更新。 工件−车间分配矩阵的迭代公式为 X k ir = { 1, 如果工件i在工厂r 0, 其他 i = 1,2,··· ,n; r = 1,2,··· , f ; k = 1,2,··· ,s (12) Tir(t) = Tir(t−1)+ ∑m k=1 X k ir,i = 1,2,··· ,n; r = 1,2,··· , f ;t = 1,2,··· ,G; k = 1,2,··· ,s (13) X k ir Tir(t) 式 (12) 和 (13) 中， 表示工件 i 分配到车间 r；k 代表解序列号码；n 代表工件数目；s 代表精 英染色体的个数；t 代表当前迭代数；G 代表总 迭代次数； 表示工件 i 分配到车间 r 的累加 次数。 工件-机器排序矩阵的迭代公式为 X k ir = { 1, 如果工件i在机器j 0, 其他 i = 1,2,··· ,n; j = 1,2,··· ,n; k = 1,2,··· ,m (14) Ti j(t) = Ti j(t−1)+ ∑m k=1 X k i j,i = 1,2,··· ,n; j = 1,2,··· ,n;t = 1,2,··· ,G; k = 1,2,··· ,s (15) X k 式中： i j 表示工件 i 在机器 j 上的总加工次数。 具体的工件−车间分配矩阵的更新过程如图 2 所示，假设 C1 ,C2 ,…,C5 为 5 个用于更新分配矩阵 的精英染色体；以工件 5 为例，有 1 个精英染色体 将工件 5 分配到车间 1，有 4 个精英染色体将工 件 5 分配到车间 2，因此工件 5 分配到车间 1 的概 率为 1/5，分配到车间 2 的概率为 4/5。工件−机器 排序矩阵的更新原理同分配矩阵的更新原理相 同 (如图 3)。 为确保工件 j 拥有分配到每个车间中每个位 置的机会，将概率矩阵中每个位置的概率值增加 0.01；在构建人工染色体的时，每个位置可以选到 剩余工件的任意一个，增加了样本的多样性，避 免缩小搜索空间。 8 6 4 5 2 3 7 1 8 6 4 5 2 3 7 1 C1 C2 4 6 7 2 3 5 1 8 C3 8 2 7 3 5 4 6 1 C4 8 6 5 2 1 7 4 3 C5 1 2 1 3 2 4 6 5 7 3 2 2 3 3 2 2 3 1 4 4 1 0 5 8 5 0 工厂 工件 1 2 1 3 2 4 6 5 7 3/5 2/5 2/5 3/5 3/5 2/5 2/5 3/5 1/5 4/5 4/5 1/5 0 1 8 1 0 工厂 工件 精英染色体 图 2 工件−车间分配概率矩阵示意 Fig. 2 Schematic diagram of job-shop assignment probab￾ility matrix 8 6 4 5 2 73 1 8 6 4 5 2 73 1 C1 C2 4 6 7 2 3 15 8 C3 8 2 7 3 5 64 1 C4 8 6 5 2 1 47 3 C5 1 2 1 3 2 4 6 5 7 1 1 0 1 0 2 3 1 1 2 0 0 2 2 8 3 1 位置 工件 精英染色体 3 4 3 0 0 4 2 1 1 0 1 1 1 4 1 0 1 0 1 2 1 3 2 4 6 5 7 1/5 1/5 0 1/5 0 2/5 3/5 1/5 1/5 2/5 0 0 2/5 2/5 8 3/5 1/5 位置 工件 3 4 3/5 0 0 4/5 2/5 1/5 1/5 0 1/5 1/5 1/5 4/5 1/5 0 1/5 0 图 3 工件−位置排序矩阵示意 Fig. 3 Schematic diagram of job-position sorting matrix 2.3 区块挖掘 精英染色体的解序列中拥有相似的解序列片 段，算法以区块的形式将这部分信息进行挖掘用 于构建高质量的人工染色体。区块是高适应度解 序列中的部分片段，由精英染色体中的高频率的 基因链接组成。区块将不同机器上加工时间互补 的工件组合起来，用于平衡工件在机器上的加工 时间，优化同一车间内工件的排序过程，并确定 工件的分配过程。高质量的区块保证了人工染色 体的优势，又降低了排序的复杂程度。区块的规 模越大，构建人工染色体的过程就越简单，但由 于工件−车间分配矩阵和工件−机器排序矩阵中 的概率都小于 1(图 4 中的 Pblock 为挖掘该区块的 频率)，所以区块规模越大，挖掘该区块的概率就 第 2 期 裴小兵，等：改进区块遗传算法解决分布式车间调度问题 ·307·