王柏琳等：安装时间和机器受限的订单接受与并行机调度 ·533· 限定在可加工机器范围内，令y,对应订单j而不是 输出决策对RS,{π：IHi}） 订单x,且y的值域为0,1M门而不是可加工机器 此编码和解码方案具有以下优点：首先，保证了 集合M,即y,表示订单j被指派到可加工机器集合 个体X和Y的独立性：此外，将算法的搜索空间限 M的第y台机器上 定在可行解范围内，这样可以简化遗传算子的设计， 下面举例说明此编码方案.考虑5个工件、3台 从3.3节可以看出，在此编码下，采用最基本的遗传 机器的实例，其中M1={1,2},M2={1,3},M3= 算子即可保证子代个体的合法性. {1,2,3},M4={2,3},M={2}.给定染色体编码 3.2协同进化策略 X,Y],其中X=B4215],Y=21321].根据个体 协同进化策略能够有效解决多决策的联合优化 X,首先调度订单3(x1=3),将其指派到机器3(M3 问题.如果一个问题能够拆分成关联性不强的多个 (y3)=3);此后，订单4(x2=4)指派到机器3(M4 子问题，则可以采用基于协同进化的群智能算法，独 (y)=3),紧随订单3加工；订单2和订单1依次被 立地对每个子问题进行进化操作，然后综合各个子 指派到机器1和机器2；订单5指派到机器2且紧随 问题的解来进行评价和选择.在本文的CCGA编码 订单1加工.因此，初始调度为Ⅱ。={，π，π}= 方案中，个体X和Y是彼此独立的，分别对应着订 {J2},{J1,J},{J3,J}}. 单排序决策和订单指派决策，且任意的X和Y均可 在CCGA中，订单拒绝决策是基于初始调度制 组合成一个可行的调度方案.这一特征符合协同进 定的，解码过程的伪代码如下，其中循环语句的单次 化的应用场景.此外，个体X和Y具有不同的进化 耗时0(1)，共循环n次，复杂度为0(n). 要求：个体X是一个订单序列，要求每个基因的取 Decoding() 值都不同：个体Y允许基因间取值重复，但每个基 Iput:染色体K,Y]: 因的值域不同.因此，对个体X和Y分别设计遗传 π：=☑，Hi;Rs=0: 算子并令其独自进化，这种方式比执行统一的遗传 For u=1 to n do 进化操作更为有效. j=x:i=M(y) 因此，本文将协同进化引入算法，基本思路如 f(π：=O)Then C=Pg' 下：依次进化由个体X和Y组成的两个种群（分别 Else C=C()+Sim(I+Pii 记为popx和pop:在每次迭代中，首先进化popx, T;=max (C:-d,0} 将其中个体与po即y中的最优个体进行组合，通过评 If (rej,<T)Then RS=RSU), 价和选择得到新种群popx;进而采用相同的方法进 Elseπ：=π：U{U};/Rule2 化popy令off,和of,表示popx和popy的子代种 End For 群，ps表示种群规模，则CCGA的求解框架如图1 生成初始种群pOP pop,,确定最好个体X,Y门 进化集合X 进化集合Y 调用集合X的遗传算子， 调用集合的遗传算子 进化popr,得到of, 进化pop,得到o, 构造2s个染色体X,门 构造2ps个染色体X",了 VXE pop,U offy VYepop,Uoffy 中 对2ps个染色体解码并评价 对2ps个染色体解码并评价 选择Ts个集合X,构成新的 选择ps个集合Y,构成新的 种群popx,更新X 种群popy,更新Y” 否 满足终止准则 是 输出染色体X,Y门 图1CCGA的协同进化求解框架 Fig.1 Cooperative coevolution in CCGA王柏琳等: 安装时间和机器受限的订单接受与并行机调度 限定在可加工机器范围内，令 yj 对应订单 j 而不是 订单 xj ，且 yj 的值域为［1，| Mj |］而不是可加工机器 集合 Mj ，即 yj 表示订单 j 被指派到可加工机器集合 Mj 的第 yj 台机器上． 下面举例说明此编码方案． 考虑 5 个工件、3 台 机器的实例，其中 M1 = { 1，2} ，M2 = { 1，3} ，M3 = { 1，2，3} ，M4 = { 2，3} ，M5 = { 2} ． 给定染色体编码 ［X，Y］，其中 X =［34215］，Y =［21321］． 根据个体 X，首先调度订单 3( x1 = 3) ，将其指派到机器 3( M3 ( y3 ) = 3) ; 此后，订单 4( x2 = 4) 指派到机器 3 ( M4 ( y4 ) = 3) ，紧随订单 3 加工; 订单 2 和订单 1 依次被 指派到机器1 和机器2; 订单5 指派到机器2 且紧随 订单1 加工． 因此，初始调度为 Π0 = { π0 1，π0 2，π0 3 } = { { J2 } ，{ J1，J5 } ，{ J3，J4 } } ． 在 CCGA 中，订单拒绝决策是基于初始调度制 定的，解码过程的伪代码如下，其中循环语句的单次 耗时 O( 1) ，共循环 n 次，复杂度为 O( n) ． 图 1 CCGA 的协同进化求解框架 Fig． 1 Cooperative coevolution in CCGA Decoding( ) Input: 染色体［X，Y］; πi = ，i; ＲS = ; For u = 1 to n do j = xu ; i = Mj ( yj ) ; If ( πi = ) Then Cj = pij， Else Cj = Cπi ( | πi| ) + siπi ( | πi| ) j + pij; Tj = max { Cj － dj ，0} ; If ( rejj≤Tj ) Then ＲS = ＲS∪{ j} ， Else πi = πi∪{ j} ; / /Ｒule 2 End For 输出决策对〈ＲS，{ πi |i} 〉 此编码和解码方案具有以下优点: 首先，保证了 个体 X 和 Y 的独立性; 此外，将算法的搜索空间限 定在可行解范围内，这样可以简化遗传算子的设计， 从 3. 3 节可以看出，在此编码下，采用最基本的遗传 算子即可保证子代个体的合法性． 3. 2 协同进化策略 协同进化策略能够有效解决多决策的联合优化 问题． 如果一个问题能够拆分成关联性不强的多个 子问题，则可以采用基于协同进化的群智能算法，独 立地对每个子问题进行进化操作，然后综合各个子 问题的解来进行评价和选择． 在本文的 CCGA 编码 方案中，个体 X 和 Y 是彼此独立的，分别对应着订 单排序决策和订单指派决策，且任意的 X 和 Y 均可 组合成一个可行的调度方案． 这一特征符合协同进 化的应用场景． 此外，个体 X 和 Y 具有不同的进化 要求: 个体 X 是一个订单序列，要求每个基因的取 值都不同; 个体 Y 允许基因间取值重复，但每个基 因的值域不同． 因此，对个体 X 和 Y 分别设计遗传 算子并令其独自进化，这种方式比执行统一的遗传 进化操作更为有效． 因此，本文将协同进化引入算法，基本思路如 下: 依次进化由个体 X 和 Y 组成的两个种群( 分别 记为 popX 和 popY ． 在每次迭代中，首先进化 popX， 将其中个体与 popY 中的最优个体进行组合，通过评 价和选择得到新种群 popX ; 进而采用相同的方法进 化 popY ． 令 offX 和 offY 表示 popX 和 popY 的子代种 群，ps 表示种群规模，则 CCGA 的求解框架如图 1 · 335 ·