王柏琳等：安装时间和机器受限的订单接受与并行机调度 ·535· 输出染色体☒，Y]的拒绝订单集合和调度 散均匀分布；安装时间s海∈DU几0,20]；订单拒绝 方案 成本rej∈DU1,10];单位拖期成本e:∈U0.5, 1.5],交货期d,∈DU50,50n/(m+1)]. 4数据实验 算法参数设置如下：GADR采用Joo和Kimo 4.1实验环境设置 的实验参数，即交叉和变异概率分别为0.8和0.2， 为了检验模型的正确性以及算法的有效性，本 种群规模ps=2n,最大代数mxGen=1000.对于 节首先针对较小问题规模的算例进行实验，通过 CCGA、CCGAⅡ和TGA,考虑到插入邻域和交换邻 IBM公司的CPLEX数学规划软件对数学模型求解， 域是调度算法中被广泛应用且十分有效的两种邻域 并将CCGA取得的解与最优解进行比较；进而，为了 结构，且二者优化效果相近8-9，因此在进化个体 检验CCGA算法及其协同进化策略和列表拒绝方法 X时移位和换位概率设置为相等且相对较高的值， 的有效性，针对问题规模较大的算例进行实验，并设 均为0.4，而基于逆序邻域的倒位概率则设为相对 置了如下三个对比算法： 较低的值，为0.2：进化个体Y时，参考GADR的参 (1)由Joo和Kima提出的基于指派规则的遗 数设置，交叉和变异概率分别为0.8和0.2.考虑到 传算法GADR_PO(这里简称为GADR),用来解 TGA和GADR均未采用协同进化，因此TGA种群规 决引言部分提到的本文特例问题，即考虑安装时间 模ps和最大代数mxGen与GADR相同，采用协同 和可加工机器限制的不相关并行机调度.此处将第 进化的CCGA和CCGAII的ps和mxGen减半：ps= 三个对比算法所采用的订单拒绝方法（详见(3）)引 n,mxGen =500. 入GADR 4.2小规模算例的实验检验 (2)未采用协同进化策略的传统遗传算法(tra- 本节将检验本文提出的数学模型的可行性，并 ditional GA,TGA).TGA将X和Y作为一条染色体 观察CCGA算法相对于最优值的偏差情况.考虑到 同时进化，其编码方案、遗传算子和选择算子均与 精确算法适用于问题规模较小的算例，因此本节的 CCGA相同.TGA用来检验CCGA协同进化策略的 实验对象为小规模算例，具体设置如下：机器数m= 有效性. 2,3,4,订单数n=m,其中倍数t=2,3,4.根据 (3)一种协同进化遗传算法，与CCGA的区别 问题规模分为9组实验，每组随机生成10个算例， 在于，此算法用染色体编码来表示订单拒绝决策，而 共计90个算例.数学模型采用CPLEX数学规划软 没有采用列表拒绝方法，将其记为CCGAI.为提高 件，在.NET环境下用C#语言编写；CCGA算法采用 计算效率，CCGAⅡ不另设染色体子集来表示订单拒 C#语言编写.运行环境为ntel Core5-6300U/ 绝变量，而是参考Shabtay等回提出的方法，将个体 CPU2.40GHz and RAM 8.0G. Y的基因y（j)值域由1，IMI]扩展为O, 实验结果见表I,其中Avg.表示该组实验的成 IM,I],若y=0则说明订单j被拒绝。CCGAII用来 本均值，Time表示平均计算时间，Opt.表示CCGA 检验CCGA列表拒绝方法的有效性. 算法取得最优值的比例（即取得最优值的算例数/ 在以上两组实验中，算例参数均设置为：订单j 该组实验算例总数) 的加工时间上下限为p∈DU2,99]和p∈DU 由表1看出，CCGA共有80%的算例取得了最 几，Lp,2],在机器i上的加工时间为P∈DU 优值，即最小的总成本，其中有两组实验取得最优值 p,,P],其中DUa,b]表示位于[a,b]区间的离 的算例的比例高达1O0%;此外，CCGA的总成本均 表1 CPLEX与CCGA的实验结果 Table 1 Experimental results for CPLEX and CCGA CPLEX CCGA CPLEX CCGA t(n) t(n) Avg. Time/s Avg. 0pt./% Time/s Avg. Time/s Avg. 0pt./% Time/s 22(4) 0 0.072 0.9 70 0.022 34(12) 0.8 0.106 1.6 80 0.077 3(6) 0.7 0.069 2.1 60 0.036 4 2(8) 2.1 0.086 2.1 100 0.055 4(8) 0.8 0.084 2.8 70 0.048 3(12) 1.6 0.106 1.6 100 0.081 32(6) 0 0.069 0.5 80 0.036 4(16) 0.8 0.220 3.2 70 0.109 3(9) 0.1 0.077 0.8 90 0.056 平均值 0.77 0.099 1.73 80 0.058王柏琳等: 安装时间和机器受限的订单接受与并行机调度 输出染色体［X* ，Y* ］的拒绝订单集合和调度 方案 4 数据实验 4. 1 实验环境设置 为了检验模型的正确性以及算法的有效性，本 节首先针对较小问题规模的算例进行实验，通过 IBM 公司的 CPLEX 数学规划软件对数学模型求解， 并将 CCGA 取得的解与最优解进行比较; 进而，为了 检验 CCGA 算法及其协同进化策略和列表拒绝方法 的有效性，针对问题规模较大的算例进行实验，并设 置了如下三个对比算法: ( 1) 由 Joo 和 Kim［10］提出的基于指派规则的遗 传算法 GA_DＲ_P［10］( 这里简称为 GADＲ) ，用来解 决引言部分提到的本文特例问题，即考虑安装时间 和可加工机器限制的不相关并行机调度． 此处将第 三个对比算法所采用的订单拒绝方法( 详见( 3) ) 引 入 GADＲ． ( 2) 未采用协同进化策略的传统遗传算法( tra￾ditional GA，TGA) ． TGA 将 X 和 Y 作为一条染色体 同时进化，其编码方案、遗传算子和选择算子均与 CCGA 相同． TGA 用来检验 CCGA 协同进化策略的 有效性． ( 3) 一种协同进化遗传算法，与 CCGA 的区别 在于，此算法用染色体编码来表示订单拒绝决策，而 没有采用列表拒绝方法，将其记为 CCGAII． 为提高 计算效率，CCGAII 不另设染色体子集来表示订单拒 绝变量，而是参考 Shabtay 等［2］提出的方法，将个体 Y 的 基 因 yj ( j) 值 域 由［1，| Mj |］扩 展 为［0， | Mj |］，若 yj = 0 则说明订单 j 被拒绝． CCGAII 用来 检验 CCGA 列表拒绝方法的有效性． 在以上两组实验中，算例参数均设置为: 订单 j 的加工时间上下限为 p + j ∈DU［2，99］和 p － j ∈DU ［1，? p + j /2」］，在机器 i 上的加工时 间 为 pij ∈DU ［p － j ，p + j ］，其中 DU［a，b］表示位于［a，b］区间的离 散均匀分布; 安装时间 sikj∈DU［10，20］; 订单拒绝 成本 rejj∈DU［1，10］; 单位拖期成本 wj ∈U［0. 5， 1. 5］，交货期 dj∈DU［50，50n /( m + 1) ］． 算法参数设置如下: GADＲ 采用 Joo 和 Kim［10］ 的实验参数，即交叉和变异概率分别为 0. 8 和 0. 2， 种群规模 ps = 2n，最大代数 mxGen = 1000． 对于 CCGA、CCGAII 和 TGA，考虑到插入邻域和交换邻 域是调度算法中被广泛应用且十分有效的两种邻域 结构，且二者优化效果相近［18--19］，因此在进化个体 X 时移位和换位概率设置为相等且相对较高的值， 均为 0. 4，而基于逆序邻域的倒位概率则设为相对 较低的值，为 0. 2; 进化个体 Y 时，参考 GADＲ 的参 数设置，交叉和变异概率分别为 0. 8 和 0. 2． 考虑到 TGA 和 GADＲ 均未采用协同进化，因此 TGA 种群规 模 ps 和最大代数 mxGen 与 GADＲ 相同，采用协同 进化的 CCGA 和 CCGAII 的 ps 和 mxGen 减半: ps = n，mxGen = 500． 4. 2 小规模算例的实验检验 本节将检验本文提出的数学模型的可行性，并 观察 CCGA 算法相对于最优值的偏差情况． 考虑到 精确算法适用于问题规模较小的算例，因此本节的 实验对象为小规模算例，具体设置如下: 机器数 m = 2，3，4，订单数 n = tm，其中倍数 t = 2，3，4． 根据 问题规模分为 9 组实验，每组随机生成 10 个算例， 共计 90 个算例． 数学模型采用 CPLEX 数学规划软 件，在 . NET 环境下用 C#语言编写; CCGA 算法采用 C# 语 言 编 写． 运 行 环 境 为 Intel Core i5--6300U / CPU2. 40GHz and ＲAM 8. 0G． 实验结果见表 1，其中 Avg． 表示该组实验的成 本均值，Time 表示平均计算时间，Opt． 表示 CCGA 算法取得最优值的比例( 即取得最优值的算例数/ 该组实验算例总数) ． 由表 1 看出，CCGA 共有 80% 的算例取得了最 优值，即最小的总成本，其中有两组实验取得最优值 的算例的比例高达 100% ; 此外，CCGA 的总成本均 表 1 CPLEX 与 CCGA 的实验结果 Table 1 Experimental results for CPLEX and CCGA m t( n) CPLEX CCGA Avg． Time / s Avg． Opt． /% Time / s m t( n) CPLEX CCGA Avg． Time / s Avg． Opt． /% Time / s 2 2 ( 4) 0 0. 072 0. 9 70 0. 022 3 4 ( 12) 0. 8 0. 106 1. 6 80 0. 077 3 ( 6) 0. 7 0. 069 2. 1 60 0. 036 4 2 ( 8) 2. 1 0. 086 2. 1 100 0. 055 4 ( 8) 0. 8 0. 084 2. 8 70 0. 048 3 ( 12) 1. 6 0. 106 1. 6 100 0. 081 3 2 ( 6) 0 0. 069 0. 5 80 0. 036 4 ( 16) 0. 8 0. 220 3. 2 70 0. 109 3 ( 9) 0. 1 0. 077 0. 8 90 0. 056 平均值 0. 77 0. 099 1. 73 80 0. 058 · 535 ·