第2期 裴小兵，等：改进区块遗传算法解决分布式车间调度问题 ·305· 工的工件可以在任意车间内加工完成，且加工所 Cmx≥C,YH (7) 需的时间是相同的；不考虑工资水平、运输距离 式(8(10)为决策变量。 等因素。在工件加工过程中，已经分配到加工车 Ci≥0N# (8) 间的工件禁止转移到其他车间加工，因为工件在 车间之间的交叉加工将增加成本和技术难度。 Ya∈{0,1，Va (9) DJSP的约束条件为：1)每个工件只能分配到一个 Xa∈{0,1，Vjk-j (10) 车间内，且每个工件都由特定的车间加工；2)每 在实际的分布式车间调度问题中，安排到每 台机器只能同时加工一个零件，每个零件只能同 个车间的工件数n应该远远大于机器台数m,这 时由一台机器加工；3)分配到同一车间内的工件 样才能使得机器的生产能力得到有效的应用，缩 都在该车间内顺序加工；4)n件工件的最大完工 短平均加工时间。 时间就是个车间中完工时间最长的车间的最大 完工时间。则DSP整数线性规划模型为： 2改进区块遗传算法 模型中用到的参数为：n表示工件数，j,k={1, 为适应分布式车间调度问题的特征，对传统 2,…,n}:m表示车间内机器数，i,={1,2,…,m:f表 遗传算法进行了改进，将基因交叉过程中重叠的 示车间数，={1,2，…，乃；P:表示工件j在机器i上 工件放入重组工件基因池中，再重新插入到解序 的加工时间；au:如果工作j在机器u上加工完 列中进行重组。在遗传算法中注人基于区块的高 之后立即在机器i上进行加工，则a=1,否则 质量的人工染色体增加解的多样性；从挑选的精 am=O;M为一个较大的正数。 决策变量为：X取0,1值，如果机器u在加 英染色体中统计出工件-车间分配矩阵和工件 工完工件k之后加工工件j,则X=1,否则 -机器位置矩阵，然后根据概率矩阵挖掘区块，运 用两种组合机制构建人工染色体，协调工作车间 Xm=0。Y取0,1值，如果工件j在车间r加工， 和车间内机器的工作量，优化搜索路径。算法步 则Y=l,否则Y=0。C:工件j在机器i上累计加 骤如下： 工时间的连续变量。 1)生成初始解。为保证初始解的质量和多样 整体线性规划模型为： 性，本文运用NEH和随机性两种方式，按照最早 式(1)是目标函数，寻找最小化的最大完工 完工的原则初始化种群。 时间： Minimize Cmax (1) 2)计算适应度并挑选精英染色体。计算每 个染色体的适应值，并使适应度按从小到大的顺 Subject to: 式(2)表示将每个工件都安排到唯一的车间 序进行排序，挑选出前30%的染色体作为精英染 内进行加工： 色体。 3)更新概率矩阵。分别建立工件-车间分配 y=1￥ (2) 矩阵和工件-机器排序矩阵，并随着迭代过程不 断地更新概率矩阵中的信息。 式(3)表示工件的完成时间大于该工件的加 4)组合区块。根据概率矩阵中的信息，组合 工时间： 区块。 Cn≥P,Hj (3) 5)构建人工染色体。根据区块库和概率矩阵 式(4)表示在同一时间内，一个工件最多能在 中的信息，运用轮盘赌的方式构建人工染色体。 一台机器上加工。 6)对分布式车间调度问题的解序列进行重 Ca≥C1+P,Hew=l (4) 组。将父代的染色体以某一车间中工件加工的解 式（⑤）和(6)表示在同一工厂内，一台机器最 序列片段为单位进行重组。 多能同时加工一个工件；当且仅当X=1时，式 7筛选优精英染色体。将从重组后的染色体 (5)和(6)才能够同时成立，换而言之，同 与原父代的染色体进行融合，筛选出新的精英染 一工厂的机器i加工完成工件k之后才能加工工 色体作为下一次迭代的父代。 件j。 MBGA算法流程图（见图1）中，△R为概率 Ch Cki+pji-M(3-Xkji-Yir-Yk).Vriken.jpk (5) 模型迭代计数器，R为概率模型迭代的门槛值， Cki Cji+pui-M(2+Xkji-Yir-Ykr),Vriken.jpk (6 △A和Ae分别为构成人工染色体的计数器和门 式(7表示最大完工时间： 槛值。工的工件可以在任意车间内加工完成，且加工所 需的时间是相同的；不考虑工资水平、运输距离 等因素。在工件加工过程中，已经分配到加工车 间的工件禁止转移到其他车间加工，因为工件在 车间之间的交叉加工将增加成本和技术难度。 DJSP 的约束条件为：1）每个工件只能分配到一个 车间内，且每个工件都由特定的车间加工；2）每 台机器只能同时加工一个零件，每个零件只能同 时由一台机器加工；3）分配到同一车间内的工件 都在该车间内顺序加工；4）n 件工件的最大完工 时间就是 f 个车间中完工时间最长的车间的最大 完工时间。则 DJSP 整数线性规划模型为： pj,i aj,i,u aj,i,u aj,i,u 模型中用到的参数为：n 表示工件数, j, k={1, 2,…,n}；m 表示车间内机器数, i，u={1,2,…,m}；f 表 示车间数, r={1,2,…, f}； 表示工件 j 在机器 i 上 的加工时间； ：如果工作 j 在机器 u 上加工完 之后立即在机器 i 上进行加工，则 =1，否则 =0；M 为一个较大的正数。 Xk, j,u Xk, j,u Xk, j,u Yj,r Yj,r Yj,r Cj,i 决策变量为： 取 0，1 值，如果机器 u 在加 工完工 件 k 之后加工工 件 j ， 则 = 1 ，否则 =0。 取 0，1 值，如果工件 j 在车间 r 加工， 则 =1，否则 =0。 ：工件 j 在机器 i 上累计加 工时间的连续变量。 整体线性规划模型为： 式 (1) 是目标函数，寻找最小化的最大完工 时间： Minimize Cmax (1) Subject to: 式 (2) 表示将每个工件都安排到唯一的车间 内进行加工： ∑ f r=1 Yj,r = 1,∀j (2) 式 (3) 表示工件的完成时间大于该工件的加 工时间： Cj,i ⩾ pj,i ,∀j ,i (3) 式 (4) 表示在同一时间内，一个工件最多能在 一台机器上加工。 Cj,i ⩾ Cj,l + pj,i ,∀j,i,l,i|aj,i,l=1 (4) Xk, j,i= 1 式 (5) 和 (6) 表示在同一工厂内，一台机器最 多能同时加工一个工件；当且仅当 时，式 ( 5 ) 和 ( 6 ) 才能够同时成立，换而言之，同 一工厂的机器 i 加工完成工件 k 之后才能加工工 件 j。 Cj,i ⩾ Ck,i + pj,i − M(3− Xk, j,i −Yj,r −Yk,r),∀r,i,k<n, j>k (5) Ck,i ⩾ Cj,i + pk,i − M(2+ Xk, j,i −Yj,r −Yk,r),∀r,i,k<n, j>k (6) 式 (7) 表示最大完工时间: Cmax ⩾ Cj,i ,∀j,i (7) 式 (8)~(10) 为决策变量。 Cj,i ⩾ 0∀j,i (8) Yj,i ∈ {0,1},∀j,i (9) Xk, j,i ∈ {0,1},∀j<n,k>j,i (10) 在实际的分布式车间调度问题中，安排到每 个车间的工件数 n 应该远远大于机器台数 m，这 样才能使得机器的生产能力得到有效的应用，缩 短平均加工时间。 2 改进区块遗传算法 为适应分布式车间调度问题的特征，对传统 遗传算法进行了改进，将基因交叉过程中重叠的 工件放入重组工件基因池中，再重新插入到解序 列中进行重组。在遗传算法中注入基于区块的高 质量的人工染色体增加解的多样性；从挑选的精 英染色体中统计出工件−车间分配矩阵和工件 −机器位置矩阵，然后根据概率矩阵挖掘区块，运 用两种组合机制构建人工染色体，协调工作车间 和车间内机器的工作量，优化搜索路径。算法步 骤如下： 1) 生成初始解。为保证初始解的质量和多样 性，本文运用 NEH 和随机性两种方式，按照最早 完工的原则初始化种群。 2) 计算适应度并挑选精英染色体。计算每 个染色体的适应值，并使适应度按从小到大的顺 序进行排序，挑选出前 30% 的染色体作为精英染 色体。 3) 更新概率矩阵。分别建立工件−车间分配 矩阵和工件−机器排序矩阵，并随着迭代过程不 断地更新概率矩阵中的信息。 4) 组合区块。根据概率矩阵中的信息，组合 区块。 5) 构建人工染色体。根据区块库和概率矩阵 中的信息，运用轮盘赌的方式构建人工染色体。 6) 对分布式车间调度问题的解序列进行重 组。将父代的染色体以某一车间中工件加工的解 序列片段为单位进行重组。 7) 筛选优精英染色体。将从重组后的染色体 与原父代的染色体进行融合，筛选出新的精英染 色体作为下一次迭代的父代。 ∆R Rthe ∆A Athe MBGA 算法流程图 (见图 1) 中 ， 为概率 模型迭代计数器， 为概率模型迭代的门槛值， 和 分别为构成人工染色体的计数器和门 槛值。 第 2 期 裴小兵，等：改进区块遗传算法解决分布式车间调度问题 ·305·