·463· 轩华，等：含忽略工序和不相关机的混合流水车间调度 第3期 自适应变异概率4由式(8)确定： r=2,则执行N2;若r=3,令max=1,执行N3;若 F(g) r=4,令Lmx=4,执行N1;若r=5,令mx=2,执行 F max -Favg F(g)≥Favg N3;若r=6,令Lax=6,执行N1。该过程往复o次产 中an,F(g)<Fwg 生领飞鸟的个邻域解，若其中的最佳解优于当前 (8) 领飞鸟，则更新领飞鸟，取其余(o-1)个邻域解中 2.4基于3种邻域搜索结构的候鸟优化 的最佳解加入共享邻域解集X和XR。 为提高算法的搜索能力，进一步改善遗传算 4)右侧跟飞鸟进化。对右侧队列中每个个体 法解的质量，设计引入基于工件、机器和工序位 的3种邻域搜索结构的候鸟优化算法。 g,执行与3)相同的邻域搜索过程产生(o-1)个邻 域解，构成集合DR,找到XxUDπ内的最佳解，若其 1)邻域搜索结构N 优于当前解，则更新跟飞鸟，清空XR,从XRUDR未 随机选择一个工序“，从在该工序处理的工件 用的解集中选择最好的邻域解加入X。 集中随机生成两个工件π，和π2，将它们在该工序 5)左侧跟飞鸟进化。对左侧队列中每个个体 处理的机器号进行交换，重复该过程直至达到最 大循环次数Lmxo g,仍采用与3)相同的邻域搜索过程产生(o-1)个 邻域解，构成集合DL,若XUD内最佳解优于当前 2)邻域搜索结构N2 解，则更新跟飞鸟，清空X,将XUD未用的解集 从机器集中寻找处理工件数超过两个的机 中最好的邻域解加入X。 器，分别计算每台机器上工件处理时间之和，从 中获取具有最大总处理时间的机器K,进而得到 6)G1=G1+1,若G<Gx,返回3)，否则， 它对应的工序“，从该机器处理的工件集中选取处 G=1,执行7)。 理时间最长的工件π，将min(PxkK(k=1,2,…,m)对 7)领飞鸟更新。若α=1，将左侧队列的第一 应的机器作为该工件分配的机器。 个跟飞鸟作为新领飞鸟，将原领飞鸟移至左侧队 3)邻域搜索结构N 列末端，令α=0：否则，将右侧队列的第一个跟飞 鸟作为新领飞鸟，把原领飞鸟移至右侧队列末 随机生成一个工序位x,确定它所对应的工件 π=「x/h(1-p门和工序u=x-πh(1-p),将该工 端，令a=1。 序位的机器号依次设置为1,2，…，m,分别计算相 8)而=而+1，若而>y,算法停止，输出最佳解； 应个体的适应度值，从中选取适应度值最大的机 否则，返回3)。 器号填入该工序位，重复该过程直至达到最大循 2.5遗传候鸟优化算法流程 环次数x。 首先，考虑本文研究的问题是含不相关机的 引入上述邻域搜索结构执行候鸟优化算法， HFSMO,其不仅与工件的处理序列有关，还与工 具体步骤如下： 件在每道工序的机器分配相关，因此本文设计基 1)参数初始化。设置Lmax、m以及候鸟优化 于机器号的编码方案，在解码时采用最短处理时 最大迭代数y,巡回数Gx,令而=1，G1=1,=1, 间和先进先出规则确定工件处理序列：采用考虑 候鸟种群规模为6。 机器处理时间的全局搜索产生一个个体，用随机 2)初始种群生成。设计初始种群由3部分构 程序生成剩余(e-1)个个体以生成种群规模为e的 成：①对每个工件的未忽略工序，从可利用的并 初始种群：计算适应度，根据轮盘赌法选择个体 行机中选择工件处理时间最短的机器作为该工件 生成新种群；对新种群根据自适应更新策略计算 分配的机器，从而产生一个个体；②应用前述全 交叉概率及变异概率山，以此执行交叉和变异操 局搜索方法产生50%(6-1)个个体；③从GA解中 作，得到遗传进化后的最佳解并记录历史最佳 选取最好的50%(6-1)个个体。从6个个体中选取 解。最后，当最佳解T次没变时，按照基于3种邻 最大完工时间最小的个体作为领飞鸟，其余均为 域搜索结构的候鸟优化产生新解，若新解优于历 跟飞鸟，若跟飞鸟与领飞鸟相同，则将领飞鸟通 史最佳解，则更新历史最佳解，否则保持原解不 过基于机器最短处理时间的多点变异或邻域搜索 变，重复上述过程直至满足算法的停止标准。 结构N(Lx=2)产生新跟飞鸟：若新跟飞鸟与其 综上所述，所研究的GMBOA执行如下： 余跟飞鸟相同，则对新跟飞鸟继续应用邻域搜索 1)设置种群规模e,最大迭代数B和累计数T, 结构N进行更新，直至产生与其余跟飞鸟不同的 令Z=F,A=1,t=1: 新跟飞鸟。 2)若λ>B或CPU达到最大运行时间，程序停 3)领飞鸟进化。随机产生[1,6]之间的一个 止，输出最佳解；否则，执行3)： 整数r,若r=1,令Lax=2,对领飞鸟执行N1;若 3)结合随机程序和全局搜索产生初始种群：自适应变异概率 ψ 由式 (8) 确定： ψ =    ψmax −(ψmax −ψmin) ( λ β + F(g) Fmax − Favg ) ,F(g) ⩾ Favg ψmin,F(g) < Favg (8) 2.4 基于 3 种邻域搜索结构的候鸟优化 为提高算法的搜索能力，进一步改善遗传算 法解的质量，设计引入基于工件、机器和工序位 的 3 种邻域搜索结构的候鸟优化算法。 1）邻域搜索结构 N1 u π1 π2 Lmax 随机选择一个工序 ，从在该工序处理的工件 集中随机生成两个工件 和 ，将它们在该工序 处理的机器号进行交换，重复该过程直至达到最 大循环次数 。 2）邻域搜索结构 N2 k ′ u π min{Pπku}(k = 1,2,··· ,mu) 从机器集中寻找处理工件数超过两个的机 器，分别计算每台机器上工件处理时间之和，从 中获取具有最大总处理时间的机器 ，进而得到 它对应的工序 ，从该机器处理的工件集中选取处 理时间最长的工件 ，将 对 应的机器作为该工件分配的机器。 3）邻域搜索结构 N3 x π = ⌈x/[h ·(1− p)]⌉ u = x−π · h ·(1− p) 1,2,··· ,mu ηmax 随机生成一个工序位 ，确定它所对应的工件 和工序 ，将该工 序位的机器号依次设置为 ，分别计算相 应个体的适应度值，从中选取适应度值最大的机 器号填入该工序位，重复该过程直至达到最大循 环次数 。 引入上述邻域搜索结构执行候鸟优化算法， 具体步骤如下： Lmax ηmax γ Gmax ω¯ = 1 G1 = 1 α = 1 δ 1）参数初始化。设置 、 以及候鸟优化 最大迭代数 ，巡回数 ，令 ， ， ， 候鸟种群规模为 。 50% (δ−1) 50% (δ−1) δ N1(Lmax = 2) N1 2）初始种群生成。设计初始种群由 3 部分构 成：①对每个工件的未忽略工序，从可利用的并 行机中选择工件处理时间最短的机器作为该工件 分配的机器，从而产生一个个体；②应用前述全 局搜索方法产生 个个体；③从 GA 解中 选取最好的 个个体。从 个个体中选取 最大完工时间最小的个体作为领飞鸟，其余均为 跟飞鸟，若跟飞鸟与领飞鸟相同，则将领飞鸟通 过基于机器最短处理时间的多点变异或邻域搜索 结构 产生新跟飞鸟；若新跟飞鸟与其 余跟飞鸟相同，则对新跟飞鸟继续应用邻域搜索 结构 进行更新，直至产生与其余跟飞鸟不同的 新跟飞鸟。 r r = 1 Lmax = 2 N1 3）领飞鸟进化。随机产生 [1, 6] 之间的一个 整 数 ， 若 ， 令 ，对领飞鸟执行 ； 若 r = 2 N2 r = 3 ηmax = 1 N3 r = 4 Lmax = 4 N1 r = 5 ηmax = 2 r = 6 Lmax = 6 N1 o o (o−1) XL XR ，则执行 ； 若 ， 令 ，执行 ； 若 ，令 ，执行 ；若 ，令 ，执行 N3；若 ，令 ，执行 。该过程往复 次产 生领飞鸟的 个邻域解，若其中的最佳解优于当前 领飞鸟，则更新领飞鸟，取其余 个邻域解中 的最佳解加入共享邻域解集 和 。 g (o−1) DR XR ∪ DR XR XR ∪ DR XR 4）右侧跟飞鸟进化。对右侧队列中每个个体 ，执行与 3）相同的邻域搜索过程产生 个邻 域解，构成集合 ，找到 内的最佳解，若其 优于当前解，则更新跟飞鸟，清空 ，从 未 用的解集中选择最好的邻域解加入 。 g (o−1) DL XL ∪ DL XL XL ∪ DL XL 5）左侧跟飞鸟进化。对左侧队列中每个个体 ，仍采用与 3）相同的邻域搜索过程产生 个 邻域解，构成集合 ，若 内最佳解优于当前 解，则更新跟飞鸟，清空 ，将 未用的解集 中最好的邻域解加入 。 6 ） G1 = G1 +1 ， 若 G1 < Gmax ， 返 回 3 ），否则， G1=1，执行 7)。 α = 1 α = 0 α = 1 7）领飞鸟更新。若 ，将左侧队列的第一 个跟飞鸟作为新领飞鸟，将原领飞鸟移至左侧队 列末端，令 ；否则，将右侧队列的第一个跟飞 鸟作为新领飞鸟，把原领飞鸟移至右侧队列末 端，令 。 8）ω¯ = ω¯ +1 ，若 ω > γ ¯ ，算法停止，输出最佳解； 否则，返回 3）。 2.5 遗传候鸟优化算法流程 (e−1) e ξ ψ T 首先，考虑本文研究的问题是含不相关机的 HFSMO，其不仅与工件的处理序列有关，还与工 件在每道工序的机器分配相关，因此本文设计基 于机器号的编码方案，在解码时采用最短处理时 间和先进先出规则确定工件处理序列；采用考虑 机器处理时间的全局搜索产生一个个体，用随机 程序生成剩余 个个体以生成种群规模为 的 初始种群；计算适应度，根据轮盘赌法选择个体 生成新种群；对新种群根据自适应更新策略计算 交叉概率 及变异概率 ，以此执行交叉和变异操 作，得到遗传进化后的最佳解并记录历史最佳 解。最后，当最佳解 次没变时，按照基于 3 种邻 域搜索结构的候鸟优化产生新解，若新解优于历 史最佳解，则更新历史最佳解，否则保持原解不 变，重复上述过程直至满足算法的停止标准。 综上所述，所研究的 GMBOA 执行如下： e β T Z ∗ = F λ = 1 t = 1 1）设置种群规模 ，最大迭代数 和累计数 ， 令 ， ， ； 2）若 λ > β 或 CPU 达到最大运行时间，程序停 止，输出最佳解；否则，执行 3）； 3）结合随机程序和全局搜索产生初始种群； ·463· 轩华，等：含忽略工序和不相关机的混合流水车间调度 第 3 期