。816 北京科技大学学报 第32卷 mYT,)将此工件安排到设备m上加工. 「34 3 Step4执行GI算法的Sep4到Step5 矩阵 T-= 3 2, 将和T分别上下翻转而后 3.2设计子种群B L35 子种群B采用逆序调度算法具体步骤如下 左右翻转得到： (1)首先，根据约束条件(1)和(2)对原问题的 9 83 相关数据进行变换即转换为逆向问题的数据，具体 地讲就是将加工时间矩阵和机器顺序矩阵分别进行 13113, 1073 上下翻转而后左右翻转进行转换，如表1所示的车 间作业调度问题的机器顺序矩阵为= 「153 123 「343 T=233, 21 对应的时间矩阵T=334,则其逆 L343 31 L351 则代入求解式(1)~(3得到： 「213「153 问题的数据即为k31王，T23 X=多-文+T= L321L343 「9 83「153 「51013 (2)然后，根据正序调度算法的步骤执行逆序 13- 13 113十233= 2 5 13, 调度算法.也就是说，正、逆序调度算法染色体编码 10 7 3L343 L61013 用的步骤是相同的，但是输入的数据不同. 等=多=13 3.3种群交叉 y=↓ 将两个子种群和B中的最优解取出，再在每 个种群中随机选取num个染色体将这nunm个染色 则逆序染色体即为所求 体经过相互转换后进行互换，进入对方种群. 同理，可以通过逆序调度方案的染色体x求得 假设正序染色体为￥逆序染色体为子则正逆 正序调度方案的染色体X 序染色体之间转换的具体过程如下. 4计算实验 对于染色体的第1部分来讲，首先将矩阵丫及 其对应的加工时间矩阵T上下翻转而后左右翻转 4.1测试数据与参数 得到X和T接着用调度方案的最大完工时间减 本文采用Mab编程语言，在CHU主频 去将会得到其对应逆问题的工序开工时间矩阵， 253GHz2GRAM的PC机上进行算法实现. 算例的所有数据均来自OR-lba的Job Shop 最后加上与逆问题所对应的加工时间矩阵则得到 排序的T和LA系列问题.算法选用的基本参数 其逆序染色体的第一部分，如下式所示： 为：子种群的规模均为PopS ize-40交叉概率P.= X=-X十T (3) 0.6子种群交叉的染色体个数num=5算法的终止 对于染色体的第2部分来讲，染色体对应的适 条件为：最大运行代数为10000最大运行时间为 应度值不论正序还是逆序保持不变，如下式所示： 1600,S适应度值达到当前最优值OP.t如果算法没 $=y (4) 有找到最优解，则将目前找到的“最好解”作为最终 对于染色体的第3部分来讲，如果=0则 调度解其对应的M akespan为m在本文的研究 =上反之亦然.如下式所示： 中，通过计算Cmax与当前最优值OP的相对误差来 1￥=0 0等=1 5) 判断算法的有效性，如下式所示： 由、和组成逆向染色体￥ Cs-OPt de OPt一X100% (6) 以上面图2所示的正逆序调度方案为例，进一 步说明正逆序染色体和之间的关系. 42实验结果与分析 通过正序调度甘特图可以知道正序染色体为 针对43个不同规模T和LA系列基准算例， 「3710 表2列出了算法FBGIGA各运行10次后的实验结 X=31113,￥=13等=0对应的加工时间 果以及蚁群算法MFBA的、混合遗传算法 L389 HGA、两层粒子群算法PT-SPPS)的实验结北 京 科 技 大 学 学 报 第 32卷 max(Tm＊t , rO＊ij )将此工件安排到设备 m ＊ t 上加工 . Step4 执行 GT算法的 Step4到 Step5. 3.2 设计子种群 B 子种群 B采用逆序调度算法, 具体步骤如下. ( 1) 首先, 根据约束条件 ( 1)和 ( 2)对原问题的 相关数据进行变换即转换为逆向问题的数据, 具体 地讲就是将加工时间矩阵和机器顺序矩阵分别进行 上下翻转而后左右翻转进行转换, 如表 1所示的车 间作 业 调 度 问 题 的 机 器 顺 序 矩 阵 为 JM = 1 2 3 2 1 3 3 1 2 , 对应的时间矩阵 T= 3 4 3 3 3 2 3 5 1 , 则其逆 问题的数据即为 J → M = 2 1 3 3 1 2 3 2 1 , T → = 1 5 3 2 3 3 3 4 3 . ( 2) 然后, 根据正序调度算法的步骤执行逆序 调度算法.也就是说, 正 、逆序调度算法染色体编码 用的步骤是相同的, 但是输入的数据不同 . 3.3 种群交叉 将两个子种群 A和 B中的最优解取出, 再在每 个种群中随机选取 num个染色体, 将这 num个染色 体经过相互转换后进行互换, 进入对方种群. 假设正序染色体为 x, 逆序染色体为 x → , 则正逆 序染色体之间转换的具体过程如下. 对于染色体的第 1部分来讲, 首先将矩阵 x1 及 其对应的加工时间矩阵 T上下翻转而后左右翻转 得到 x 1和 T → , 接着用调度方案的最大完工时间 x2 减 去 x → 1将会得到其对应逆问题的工序开工时间矩阵, 最后加上与逆问题所对应的加工时间矩阵 T → 则得到 其逆序染色体的第一部分 x → 1, 如下式所示: x → 1 =x2 -x 1 +T → ( 3) 对于染色体的第 2部分来讲, 染色体对应的适 应度值不论正序还是逆序保持不变, 如下式所示: x2 =x → 2 ( 4) 对于染色体的第 3 部分来讲, 如果 x3 =0, 则 x → 3 =1;反之亦然.如下式所示: x → 3 = 1, x3 =0 0, x3 =1 ( 5) 由 x → 1 、x → 2和 x → 3组成逆向染色体 x →. 以上面图 2所示的正逆序调度方案为例, 进一 步说明正逆序染色体 x和 x →之间的关系. 通过正序调度甘特图可以知道正序染色体 x为 x1 = 3 7 10 3 11 13 3 8 9 , x2 =13, x3 =0, 对应的加工时间 矩阵 T= 3 4 3 3 3 2 3 5 1 , 将 x1 和 T分别上下翻转而后 左右翻转得到 : x 1 = 9 8 3 13 11 3 10 7 3 , T → = 1 5 3 2 3 3 3 4 3 , 则代入求解式 ( 1) ～ ( 3)得到: x → 1 =x2 -x 1 +T → = 13 - 9 8 3 13 11 3 10 7 3 + 1 5 3 2 3 3 3 4 3 = 5 10 13 2 5 13 6 10 13 , x → 2 =x2 =13, x → 3 =1, 则逆序染色体 x → 即为所求 . 同理, 可以通过逆序调度方案的染色体 x → 求得 正序调度方案的染色体 x. 4 计算实验 4.1 测试数据与参数 本文 采 用 Matlab编 程 语言, 在 CPU主 频 2.53 GHz, 2GRAM的 PC机上进行算法实现 . 算例的所有数据均来自 OR-library的 JobShop 排序的 FT和 LA系列问题 .算法选用的基本参数 为:子种群的规模均为 PopSize=40;交叉概率 Pc = 0.6;子种群交叉的染色体个数 num=5;算法的终止 条件为:最大运行代数为 10 000, 最大运行时间为 1 600 s, 适应度值达到当前最优值 Opt.如果算法没 有找到最优解, 则将目前找到的 “最好解 ”作为最终 调度解, 其对应的 Μakespan为 C ＊ max.在本文的研究 中, 通过计算 C ＊ max与当前最优值 Opt的相对误差来 判断算法的有效性, 如下式所示: %dev= C ＊ max -Opt Opt ×100% ( 6) 4.2 实验结果与分析 针对 43个不同规模 FT和 LA系列基准算例, 表 2列出了算法 FBGTGA各运行 10 次后的实验结 果, 以 及 蚁 群 算 法 MFBAnt [ 6] 、 混 合 遗 传 算 法 HGA [ 11] 、两层粒子群算法 PT-JSP-PSO [ 12] 的实验结 · 816·