王柏琳等：安装时间和机器受限的订单接受与并行机调度 ·537· 表34种算法生成零成本问题解的算例数量 Table 3 Number of solutions with zero total cost produced by the four algorithms CCGA TGA GADR CCGA CCGAII TGA GADR 30 2 20 19 ◇ 150 0 0 0 31 呼 14 分 5 0 0 0 2 14 0 10 0 1 31 23 0 15 0 0 2 33 20 22 12 0 0 3 100 2 0 0 0 200 2 0 0 0 1 0 0 0 0 10 3 10 0 0 0 0 15 24 11 0 12 15 0 0 0 20 32 , 20 9 0 0 总计 255 126 18 113 此外，表2中CCGA的标准差最小，说明CCGA的求 是有效的.②CCGAⅡ的平均总成本是CCGA的3.4 解性能相对稳定.进一步，由表2可以计算出 倍，这说明对于订单接受与调度，列表拒绝方法比嵌 CCGAII、TGA和GADR相对于CCGA的平均总成本 入染色体进化的拒绝决策更为有效 偏离率，分别为2.43、10.95和20.75，由此可得：① 表4给出了4种算法在求解规模组20X5、 基于协同进化的CCGA和CCGAII明显优于TGA和 100X10、200X20以及所有1000个实例的平均CPU GADR.在实验中，CCGA和CCGAII的种群规模和 时间，计算效率由高至低分别为CCGAII、CCGA、 进化代数仅为TGA和GADR的一半，却能显著超越 TGA、GADR,其中CCGAII和CCGA的计算时间非 后两种算法，这说明协同进化对于求解并行机调度 常相近. 表44种算法的CPU时间 Table 4 CPU times of the four algorithms CCGA CCGAII TGA GADR n m CCGA CCGAII TGA GADR 0.31 0.30 0.59 0.84 200 20 33.91 32.41 66.45 241.31 100 10 7.72 7.37 15.46 32.98 平均值 14.24 13.23 23.28 72.28 现对表4结果分析如下： GADR.这说明了CCGA的编码方案有效且遗传算 (1)CCGA计算时间略多于CCGAII,这是因为 子的计算效率较优. CCGA需要对订单逐一判定是否拒绝.但两个算法 下面对算法收敛性进行比较.图3给出了规模 的计算时间平均差值仅1.01s,说明列表拒绝方法 100X10的实例在迭代600代时的算法收敛曲线. 对计算时间的影响基本可以忽略 可以看出，基于列表拒绝方法的CCGA和TGA (2)TGA和GADR的计算时间明显慢于CCGA 能够得到相对较优的初始解.为便于进一步观察， 和CCGAI,这是由两倍的种群规模和进化代数所导 图4给出了CCGA和TGA的收敛曲线.在这4种算 致的.其中GADR的计算时间最长，这是因为 法中，CCGA最先在第241代找到了最优的零成本 GADR采用了单点交叉算子来生成合法的置换序 解，CCGAⅡ则在550代达到零成本.经进一步运行 列，进而采用指派规则为订单确定机器.单点交叉 算法发现，GADR和TGA在2OO0代时仍未取得零 算子需要搜索一个父代在交叉点后的每个等位基因 成本，最终达到6和67.以上结果表明，CCGA具有 在另一父代中出现的顺序，复杂度为0(n2):指派规 良好的收敛性和求解质量 则为每个订单寻找具有最小临时加工时间的机器， 5结论 复杂度为0(m),共计n个订单，复杂度为0(mm). 因此每条染色体进化操作的复杂度为0(mm+n2), 本文针对不相关并行机环境下具有可加工机器 而CCGA、CCGAII和TGA则为O(n),明显低于 限制、顺序和机器依赖的安装时间的订单接受与调王柏琳等: 安装时间和机器受限的订单接受与并行机调度 表 3 4 种算法生成零成本问题解的算例数量 Table 3 Number of solutions with zero total cost produced by the four algorithms n m CCGA CCGAII TGA GADＲ n m CCGA CCGAII TGA GADＲ 20 2 20 19 3 17 150 2 0 0 0 0 5 31 28 14 21 5 2 0 0 0 50 2 14 7 0 1 10 8 0 0 1 5 31 23 0 13 15 9 0 0 2 10 33 20 1 22 20 12 0 0 3 100 2 0 0 0 0 200 2 0 0 0 0 5 7 0 0 1 5 0 0 0 0 10 22 7 0 5 10 0 0 0 0 15 24 11 0 12 15 1 0 0 0 20 32 11 0 15 20 9 0 0 0 总计 255 126 18 113 此外，表 2 中 CCGA 的标准差最小，说明 CCGA 的求 解 性 能 相 对 稳 定． 进 一 步，由 表 2 可 以 计 算 出 CCGAII、TGA 和 GADＲ 相对于 CCGA 的平均总成本 偏离率，分别为 2. 43、10. 95 和 20. 75，由此可得: ① 基于协同进化的 CCGA 和 CCGAII 明显优于 TGA 和 GADＲ． 在实验中，CCGA 和 CCGAII 的种群规模和 进化代数仅为 TGA 和 GADＲ 的一半，却能显著超越 后两种算法，这说明协同进化对于求解并行机调度 是有效的． ②CCGAII 的平均总成本是 CCGA 的 3. 4 倍，这说明对于订单接受与调度，列表拒绝方法比嵌 入染色体进化的拒绝决策更为有效． 表 4 给 出 了 4 种 算 法 在 求 解 规 模 组 20X5、 100X10、200X20 以及所有 1000 个实例的平均 CPU 时间，计算效率由高至低分别为 CCGAII、CCGA、 TGA、GADＲ，其中 CCGAII 和 CCGA 的计算时间非 常相近． 表 4 4 种算法的 CPU 时间 Table 4 CPU times of the four algorithms s n m CCGA CCGAII TGA GADＲ n m CCGA CCGAII TGA GADＲ 20 5 0. 31 0. 30 0. 59 0. 84 200 20 33. 91 32. 41 66. 45 241. 31 100 10 7. 72 7. 37 15. 46 32. 98 平均值 14. 24 13. 23 23. 28 72. 28 现对表 4 结果分析如下: ( 1) CCGA 计算时间略多于 CCGAII，这是因为 CCGA 需要对订单逐一判定是否拒绝． 但两个算法 的计算时间平均差值仅 1. 01 s，说明列表拒绝方法 对计算时间的影响基本可以忽略． ( 2) TGA 和 GADＲ 的计算时间明显慢于 CCGA 和 CCGAII，这是由两倍的种群规模和进化代数所导 致的． 其 中 GADＲ 的 计 算 时 间 最 长，这 是 因 为 GADＲ 采用了单点交叉算子来生成合法的置换序 列，进而采用指派规则为订单确定机器． 单点交叉 算子需要搜索一个父代在交叉点后的每个等位基因 在另一父代中出现的顺序，复杂度为 O( n2 ) ; 指派规 则为每个订单寻找具有最小临时加工时间的机器， 复杂度为 O( m) ，共计 n 个订单，复杂度为 O( mn) ． 因此每条染色体进化操作的复杂度为 O( mn + n2 ) ， 而 CCGA、CCGAII 和 TGA 则为 O ( n) ，明显 低 于 GADＲ． 这说明了 CCGA 的编码方案有效且遗传算 子的计算效率较优． 下面对算法收敛性进行比较． 图 3 给出了规模 100X10 的实例在迭代 600 代时的算法收敛曲线． 可以看出，基于列表拒绝方法的 CCGA 和 TGA 能够得到相对较优的初始解． 为便于进一步观察， 图 4 给出了 CCGA 和 TGA 的收敛曲线． 在这 4 种算 法中，CCGA 最先在第 241 代找到了最优的零成本 解，CCGAII 则在 550 代达到零成本． 经进一步运行 算法发现，GADＲ 和 TGA 在 2000 代时仍未取得零 成本，最终达到 6 和 67． 以上结果表明，CCGA 具有 良好的收敛性和求解质量． 5 结论 本文针对不相关并行机环境下具有可加工机器 限制、顺序和机器依赖的安装时间的订单接受与调 · 735 ·