·461· 轩华，等：含忽略工序和不相关机的混合流水车间调度 第3期 minz=Cmax (1) 种群以提高初始解的质量，设计自适应更新策略 s.t.Cmx≥Ch,j (2) 以计算交叉概率及变异概率山，以此执行交叉和 式中：Ch表示工件j(j=1,2,…,n)在工序h的完工 变异操作。最后，引入结合邻域搜索的候鸟优化 时间。式(2)通过检查工件在最终工序h的完工时 算法以扩大遗传算法解的邻域搜索范围，从而获 间，确定最大完工时间。 得较好的近优解。 Cis=(1-Wis)Cis-1+Wis (3) 2.1 编码、解码和适应度选择 k=1 含不相关并行机的HFSMO需确定工件在每 式中：m,为工序s(s=1,2,,h)可利用的机器数； 道工序的机器分配，因此设计基于机器号的整数 F为一个足够大的数；P为工件在工序s的机器 编码方案以表述机器分配序列σ。考虑到HFS的 k(k=1,2,,m)上的处理时间；W为二元参数， 多工序处理需求，令每个工件所忽略的工序数不 若工件在工序s上处理，其值为1，否则为0：B:表 超过h-2,根据忽略工序比例p,随机产生每个工 示工件j在工序s的开工时间；X为二元变量，若 件的未忽略工序信息序列r,如图1(n=5,h=5和 工件j在工序s的机器k上处理，其值为1，否则为 p=0.6),其中U:表示工件j在阶段s的工序；然后 0。式(3)定义了工件在每道工序的完工时间，若 基于τ生成相应工件的机器号M,为平衡并行机 工件未在工序s处理，则它在该工序的完工时间 器的负荷，令其值满足[1，m,]的均匀分布，从而形 为它在紧前未忽略工序的完工时间。 成长度为nh(1-p)的一个染色体，其中每个元素 ∑X=1,以s (即工序位上的数值)为对应工件所在工序分配 的机器号。 该约束确保每个工件在任一工序只能分派到 UU UU UUU:UUU 台机器进行处理。 Cja≤B+1,s∈l,2,…,h-1,j 图1未忽略工序信息序列 该约束说明了每个工件只完完成前一工序的 Fig.1 Information sequence of unmissing operations 处理任务后方可开始下一道工序的处理。 初始化种群时，由于每道工序所含的机器为 B1≥RYj 不相关并行机，考虑不同的机器处理同一工件的 式中R为工件的释放时间。该约束描述了工件 时间不同，而最大完工时间与工件的处理时间相关。 只有到达生产系统才可开始处理。 因此，基于张国辉等2的研究提出考虑处理时间 B≥(Cs-Z批s2).WxW,j,i,k,s,j≠i(4) 的全局搜索以产生一个个体，而其他个体则由随 B≥(Cs-(1-Zt)2)WW,Vjii,k,s,j≠i(5) 机程序生成。令数组0={P11,P21,…,PmP12,…, 式中：Z为二元变量，若工件和j在工序s的机器 Pm,P1h,P2h,…,Pmh}为记录从工序1到工序h的 k上处理且工件j早于工件i,其值为1，否则为0。 每台机器的累计处理时间的一维数组，其初始值 这两个约束表示：同一道工序分派在同一台机器 均设为0，全局搜索从任一工件开始，对它的第 处理的两个工件之间的优先级关系，若Zk=0且 一道未忽略工序“，将可利用并行机的工件处理时 W=W=1,约束式(4)描述了工件j在工序s的机 间分别与数组内该机器位置的数值相加，即对 器k上的开工时间必须在工件的完工时间之后， k=1,2,,m,计算{P+pk,从中选择累计处理 若Z=1且W:=W=1,约束式（⑤）描述了工件i在 时间最短的机器K作为工件j在工序所分配的机 工序s的机器k上的开工时间必须在工件的完工 器，将该机器号填入个体内工序位(h(1-P)-1)+1), 时间之后。 令Pa=min(P+ps,更新数组0；然后，对工件j Ba≥0，Ca≥0Hi,s (6) 的第2,3，…，h(1-p)道工序重复上述过程，从而完 Xk∈{0,1，Zk∈{0,1，方s (7) 成该工件所有工序的机器分配。接着，再从剩余 约束式(6)、(7)定义了变量取值范围。 工件集内随机选择一个工件执行上述过程，直至 2遗传候鸟优化算法 完成所有工件未忽略工序的机器分配。结合随机 程序产生的(e-1)个个体共同构成了如图2所示 遗传算法广泛用于求解HFSMO问题，为 的种群规模为e的初始种群。 使遗传算法有效求解含不相关并行机的HF- 为计算最大完工时间，需为分配至同一台机 SMO问题，设计基于机器号的编码方案，采用考 器的工件进行排序，为此，设计了基于最短处理 虑机器处理时间的全局搜索和随机程序生成初始 时间的解码方案，即对于机器分配序列σ，当minz = Cmax (1) s.t. Cmax ⩾ Cjh,∀ j (2) Cjh j j = 1,2,··· ,n h h 式中： 表示工件 （ ）在工序 的完工 时间。式 (2) 通过检查工件在最终工序 的完工时 间，确定最大完工时间。 Cjs = (1−Wjs)·Cj,s−1 +Wjs ·   Bjs + ∑ms k=1 Xjks·Pjks   ,∀ j,s (3) ms s s = 1,2,· · ·,h F Pjks j s k k = 1,2,· · ·,ms Wjs j s Bjs j s Xjks j s k j s 式中： 为工序 （ ）可利用的机器数； 为一个足够大的数； 为工件 在工序 的机器 （ ）上的处理时间； 为二元参数， 若工件 在工序 上处理，其值为 1，否则为 0； 表 示工件 在工序 的开工时间； 为二元变量，若 工件 在工序 的机器 上处理，其值为 1，否则为 0。式 (3) 定义了工件在每道工序的完工时间，若 工件 未在工序 处理，则它在该工序的完工时间 为它在紧前未忽略工序的完工时间。 ∑ms k=1 Xjks = 1,∀ j,s 该约束确保每个工件在任一工序只能分派到 一台机器进行处理。 Cjs ⩽ Bj,s+1,s ∈ {1,2,··· ,h−1},∀ j 该约束说明了每个工件只完完成前一工序的 处理任务后方可开始下一道工序的处理。 Bj1 ⩾ Rj ,∀ j Rj 式中 为工件 j 的释放时间。该约束描述了工件 只有到达生产系统才可开始处理。 Bjs ⩾ (Cis −Zjiks ·Ω)· WjsWis,∀ j,i, k,s, j , i (4) Bis ⩾ (Cjs −(1−Zjiks)·Ω)· WjsWis,∀ j,i, k,s, j , i (5) Zjiks i j s k j i Zjiks = 0 Wjs = Wis = 1 j s k i Zjiks = 1 Wjs = Wis = 1 i s k j 式中： 为二元变量，若工件 和 在工序 的机器 上处理且工件 早于工件 ，其值为 1，否则为 0。 这两个约束表示：同一道工序分派在同一台机器 处理的两个工件之间的优先级关系，若 且 ，约束式 (4) 描述了工件 在工序 的机 器 上的开工时间必须在工件 的完工时间之后， 若 且 ，约束式 (5) 描述了工件 在 工序 的机器 上的开工时间必须在工件 的完工 时间之后。 Bjs ⩾ 0,Cjs ⩾ 0,∀ j,s (6) Xjks ∈ {0,1},Zjiks ∈ {0,1},∀ j,s (7) 约束式 (6)、(7) 定义了变量取值范围。 2 遗传候鸟优化算法 遗传算法已广泛用于求解 HFSMO 问题，为 使遗传算法有效求解含不相关并行机 的 HF￾SMO 问题，设计基于机器号的编码方案，采用考 虑机器处理时间的全局搜索和随机程序生成初始 ξ ψ 种群以提高初始解的质量，设计自适应更新策略 以计算交叉概率 及变异概率 ，以此执行交叉和 变异操作。最后，引入结合邻域搜索的候鸟优化 算法以扩大遗传算法解的邻域搜索范围，从而获 得较好的近优解。 2.1 编码、解码和适应度选择 σ p τ n = 5,h = 5 p = 0.6 U s j j s τ Ms j [1,ms] n · h ·(1− p) 含不相关并行机的 HFSMO 需确定工件在每 道工序的机器分配，因此设计基于机器号的整数 编码方案以表述机器分配序列 。考虑到 HFS 的 多工序处理需求，令每个工件所忽略的工序数不 超过 h−2，根据忽略工序比例 ，随机产生每个工 件的未忽略工序信息序列 ，如图 1（ 和 ），其中 表示工件 在阶段 的工序；然后 基于 生成相应工件的机器号 ，为平衡并行机 器的负荷，令其值满足 的均匀分布，从而形 成长度为 的一个染色体，其中每个元素 （即工序位上的数值）为对应工件所在工序分配 的机器号。 U1 3 U1 4 U2 2 U2 3 U3 4 U3 5 U4 4 U4 5 U5 2 U5 5 图 1 未忽略工序信息序列 Fig. 1 Information sequence of unmissing operations θ = {ps11, ps21,··· , psm11 , ps12,··· , psm21 , ps1h, ps2h,··· , psmh h} h j u θ k = 1,2,· · ·,mu {Pjku + psku} k ′ j u (h(1− p)(j−1)+1) psuk′ = min{Pjku + psku} θ 2,3,··· ,h(1− p) (e−1) e 初始化种群时，由于每道工序所含的机器为 不相关并行机，考虑不同的机器处理同一工件的 时间不同，而最大完工时间与工件的处理时间相关。 因此，基于张国辉等[28] 的研究提出考虑处理时间 的全局搜索以产生一个个体，而其他个体则由随 机程序生成。令数组 为记录从工序 1 到工序 的 每台机器的累计处理时间的一维数组，其初始值 均设为 0，全局搜索从任一工件 开始，对它的第 一道未忽略工序 ，将可利用并行机的工件处理时 间分别与数组 内该机器位置的数值相加，即对 ，计算 ，从中选择累计处理 时间最短的机器 作为工件 在工序 所分配的机 器，将该机器号填入个体内工序位 ， 令 ，更新数组 ；然后，对工件 j 的第 道工序重复上述过程，从而完 成该工件所有工序的机器分配。接着，再从剩余 工件集内随机选择一个工件执行上述过程，直至 完成所有工件未忽略工序的机器分配。结合随机 程序产生的 个个体共同构成了如图 2 所示 的种群规模为 的初始种群。 σ 为计算最大完工时间，需为分配至同一台机 器的工件进行排序，为此，设计了基于最短处理 时间的解码方案，即对于机器分配序列 ， 当 ·461· 轩华，等：含忽略工序和不相关机的混合流水车间调度 第 3 期