第2期 裴小兵，等：改进区块遗传算法解决分布式车间调度问题 ·309 组合机制2，先将工件-车间区块库中的区块 8326 8516 随机地复制到人工染色体中的空白位置，具体位 4751 254732 置由区块中首个工件分配到车间的概率和在机器 上排序的概率决定；然后根据分配和排序矩阵， 将未分配的工件插入到人工染色体的空白位置。 Pf8326 P68516 首先，随机地将区块516复制到染色体中的空 P64732 P4751 白位置（如图7）具体位置应该根据首个工件（工 件1)在各个位置的概率，运用轮盘赌来确定。剩 6 3.2 6 余的工件，还是分为两个阶段根据工件-车间和 1,5 47 工件-机器的概率矩阵用轮盘赌进行排序，直到 重组工件池 所有的工件都排序完成。 8516 236 区块库 区块库 4723 751 6 图8基因交叉 6 473 Fig.8 Gene crossing 3计算结果与分析 为了测试和验证MBGA的求解能力，在Mi- crosoft Visual Studio2012中的C++上编写该算法 8516 程序，并在Window8、32位系统、主频3.40的酷 4732 睿CPU、4GB内存的电脑上运行完成测试。本文 测试所用的数据来自Taillard中的生产车间调度 图7第2种组合机制 Fig.7 The second combination mechanism 问题的基准实例，选取工件个数为15、20、30和 机器台数为15、20共50个组合进行比较分析。 2.5基因重组 比较标准是相对百分比偏差(relative percentage 通过基因重组发现改良的染色体，直到生成 deviation,RPD),计算公式为 最优的染色体，MBGA改进了基因重组中的交叉 RPD=Alg-Min ×100 产生新的子代。染色体中每行的解序列片段是某 Min 一车间内的工件加工顺序，所有工件恰好在间 式中：AIg表示运用MBGA获得最优的最大完工 车间内加工完成。在基因交叉的过程中，以每个 时间：Min表示基准实例所给出的最小化的最大 车间内的工件加工序列（即每行的解序列片段） 完工时间。 从Taillard中选择50种具有代表性的例题测 为交换单位，既能保留父代和每个车间的有效信 息，又能搜索每个车间的所有可能解。 试该算法的寻优性能。表3中是在不同的n、 m以及加工顺序下生成的50种实例组合下，每个 适应DJSP的MBGA中，基因交叉的例子如 组合的平均RPD是对不同车间数户2，仁3，=4 图8所示，挑选两个染色体为父代(P,P),从一个 户5的最优RPD平均值。有一半以上的平均RPD 父代的解序列中随机选取2行解序列片段，剩余 为0，证明一半以上的测算实例达到了目前已知 的2行解序列片段从另一个父代中选取，按照原 的最大完工时间的下限值。 行数重新构造解序列(G),剩余的解序列片段恰 为进一步证明算法的准确性，将例题测算结 好构成另一个子代(G)。在两个新构造的解序列 果文献[I4]提出的模拟退火算法(simulated an- 中，挖出解序列中重复加工的工件放进重组工件 nealing,.SA)、启发式模拟退火算法(heuristic simu- 池，再将重组工件池中的工件分别、依次插入到 lated annealing,HAS)和文献[22]总结的遗传算法 总加工时间最短的行内，直到所有的工件都被插 得出的结果进行比较。表4给出了MBGA的平 入到解序列中。重组工件池中的工件都是两个同 均PRD与其他算法的平均PRD的数值，MBGA 时存在的，在选取工件时，应同时将两个工件分 的平均PRD数值最小为0.21。相较于GA、SA和 别插入到两个构造的解序列中。 HAS,MBGA得出的最大完工时间最小。5 1 6 组合机制 2，先将工件−车间区块库中的区块 随机地复制到人工染色体中的空白位置，具体位 置由区块中首个工件分配到车间的概率和在机器 上排序的概率决定；然后根据分配和排序矩阵， 将未分配的工件插入到人工染色体的空白位置。 首先，随机地将区块 复制到染色体中的空 白位置 (如图 7) 具体位置应该根据首个工件 (工 件 1) 在各个位置的概率，运用轮盘赌来确定。剩 余的工件，还是分为两个阶段根据工件−车间和 工件−机器的概率矩阵用轮盘赌进行排序，直到 所有的工件都排序完成。 区块库 2 4 5 8 6 3 区块库 5 1 6 4 7 3 8 6 4 2 5 7 3 1 6 4 5 7 3 1 图 7 第 2 种组合机制 Fig. 7 The second combination mechanism 2.5 基因重组 通过基因重组发现改良的染色体，直到生成 最优的染色体，MBGA 改进了基因重组中的交叉 产生新的子代。染色体中每行的解序列片段是某 一车间内的工件加工顺序，所有工件恰好在 f 间 车间内加工完成。在基因交叉的过程中，以每个 车间内的工件加工序列 (即每行的解序列片段) 为交换单位，既能保留父代和每个车间的有效信 息，又能搜索每个车间的所有可能解。 适应 DJSP 的 MBGA 中，基因交叉的例子如 图 8 所示，挑选两个染色体为父代 (P1 ,P2 )，从一个 父代的解序列中随机选取 f/2 行解序列片段，剩余 的 f/2 行解序列片段从另一个父代中选取，按照原 行数重新构造解序列 (G1 )，剩余的解序列片段恰 好构成另一个子代 (G2 )。在两个新构造的解序列 中，挖出解序列中重复加工的工件放进重组工件 池，再将重组工件池中的工件分别、依次插入到 总加工时间最短的行内，直到所有的工件都被插 入到解序列中。重组工件池中的工件都是两个同 时存在的，在选取工件时，应同时将两个工件分 别插入到两个构造的解序列中。 8 6 4 1 3 7 5 2 8 6 4 2 5 7 3 f 1 1 f2 f1 f2 8 6 4 2 3 7 3 2 8 6 4 1 5 7 5 1 P1 P2 P1 f1 P2 f2 P2 f1 P1 f2 8 6 4 7 8 6 4 7 3,2 1,5 重组工件池 8 6 4 7 8 6 4 7 G1 G2 5 2 5 1 2 3 1 3 图 8 基因交叉 Fig. 8 Gene crossing 3 计算结果与分析 为了测试和验证 MBGA 的求解能力，在 Mi￾crosoft Visual Studio 2012 中的 C++上编写该算法 程序，并在 Window8、32 位系统、主频 3.40 的酷 睿 CPU、4 GB 内存的电脑上运行完成测试。本文 测试所用的数据来自 Taillard 中的生产车间调度 问题的基准实例，选取工件个数为 15、20、30 和 机器台数为 15、20 共 50 个组合进行比较分析。 比较标准是相对百分比偏差 (relative percentage deviation, RPD)，计算公式为 RPD = Alg−Min Min ×100 式中：Alg 表示运用 MBGA 获得最优的最大完工 时间；Min 表示基准实例所给出的最小化的最大 完工时间。 从 Taillard 中选择 50 种具有代表性的例题测 试该算法的寻优性能[22]。表 3 中是在不同的 n、 m 以及加工顺序下生成的 50 种实例组合下，每个 组合的平均 RPD 是对不同车间数 f=2, f=3, f=4, f=5 的最优 RPD 平均值。有一半以上的平均 RPD 为 0，证明一半以上的测算实例达到了目前已知 的最大完工时间的下限值。 为进一步证明算法的准确性，将例题测算结 果文献 [14] 提出的模拟退火算法 (simulated an￾nealing，SA)、启发式模拟退火算法 (heuristic simu￾lated annealing，HAS) 和文献 [22] 总结的遗传算法 得出的结果进行比较。表 4 给出了 MBGA 的平 均 PRD 与其他算法的平均 PRD 的数值，MBGA 的平均 PRD 数值最小为 0.21。相较于 GA、SA 和 HAS，MBGA 得出的最大完工时间最小。 第 2 期 裴小兵，等：改进区块遗传算法解决分布式车间调度问题 ·309·