基于改进候鸟迁徙优化的多目标批量流混合流水车间调度

图1 A公司铝锅产线构型图

Fig.1 Configuration diagram of the aluminum pot production line of A Company

该混合流水线的每台拉伸机与内喷涂机同一时刻只能生产一种产品,拉伸机与内喷涂机需加工完当前工单后才能切换生产下一个工单.内喷涂机M₂₁一次只能生产一种产品,拉伸机M₁₁与拉伸机M₁₂生产的不同产品需要根据加工顺序依次进入内喷涂机M₂₁,尚未进行内喷涂的产品需在缓存区B₁中等待.内喷涂段生产速率大于包装段,缓存区B₂用以暂存未能及时包装的产品.

通过分析各机器生产速率可知,产线的生产瓶颈在于包装段,其最大生产速率总计为800个/h,而产线其他机器的产能有剩余.此外订单的产品数量差别较大,生产小批量订单加上换模时间将使产线的生产速率达不到包装线的速率引起产能损失;若一直生产大批量订单又可能导致在制品堆积问题.如何在最小化完工时间与在制品数量的两个目标下得到最优调度结果是本研究的主要内容.本研究的基本假设如下:

(1) 原材料不存在缺料情况;

(2) 每台机器的处理时间为固定值,机器不会出现故障;

(3) 数量较大的订单会拆分成若干个数量不等的工单;

(4) 拉伸机与内喷涂机的换模时间为固定值;

(5) 包装线的设置时间非常短,可认定为无换模时间;

(6) 任何两个订单的产品规格型号都不相同,无法共用一套模具;

(7) 缓存区为无限容量缓存区.

1.2 问题建模

本文研究一个有4台机器的三阶段不相等批量流混合流水车间调度问题,该三阶段不相等批量流混合流水车间调度问题具体描述如下:

(1) 本文的研究对象是一个2+1+1型三阶段混合流水车间,由第1阶段的两台并行(相同)机器和第2、3阶段各一台机器组成.在此混合流水车间中,机器换线生产不同订单的产品时需换模.第1阶段与第2阶段、第2阶段与第3阶段之间各设有一个缓存区.流水线形式及加工路线均满足1.1节所提出的背景要求.

(2) 在以4台机器组成的三阶段2+1+1型混合流水车间,根据加工顺序处理一个有n个订单的任务J.订单i(i=1, 2, …, n)有 $C_{i}^{J}$ 个同一规格的产品, $C_{i}^{J}$ 大于订单的最小批量Q_min;每个订单将被拆成 ${N^{S}}_{i}$ 个工单(子批),每个工单的产品数量不同,记S_ij为订单i的第j(j=1, 2, …, ${N^{S}}_{i}$ )个工单, ${C^{S}}_{ij}$ 为订单i的第j个工单的产品数量.在此, ${C^{S}}_{ij}$ 是必须优化的决策变量.

由问题背景可知,除包装段外其余机器换线时需要进行换模设置,产线的拉伸段生产速率与内喷涂段的生产速率相同且都大于包装段的生产速率.为使两者产能匹配,存在一个最佳批量Q,每个产品以这个批量进行加工能使拉伸机、内喷涂段加工时间加上换模时间与包装段的加工时间相匹配.

最佳批量Q只有等于瓶颈工序的最佳批量才能达到最大生产速率,记k为机器编号,k=1,2,3,4,分别为拉伸机M₁₁、拉伸机M₁₂、内喷涂机M₂₁、包装机M₃₁;t_k为机器k的节拍; $t_{c_{k}}$ 为机器k的换模时间.Q_k为机器k(包装机除外,k=1,2,3)生产速率要达到包装机生产速率的最小加工批量,内喷涂机M₂₁的最低批量:Q₃= $\frac{t_{c_{3}}}{t_{4} - t_{3}}$ ,拉伸机M₁₁与拉伸机M₁₂机器完全相同,其加工节拍完全相等,因此拉伸机M₁₁、M₁₂的最低批量:Q₁=Q₂= $\frac{t_{c_{1}}}{t_{4} - \frac{t_{1}}{2}}$ .整条产线的最佳加工批量Q=max{Q₃,Q₁}.

根据上述问题描述以及定义的数学符号,建立如下数学模型:

(1)

\begin{array}{l} t_{ij 3}^{SA} > t_{ij 1}^{SA} + {C^{S}}_{ij} (t_{1} - t_{3}), \\ 当工单在拉伸机 1 加工时 \\ t_{ij 3}^{SA} > t_{ij 2}^{SA} + {C^{S}}_{ij} (t_{2} - t_{3}), \\ 当工单在拉伸机 2 加工时 \end{array}\}

(2)

t_{ijk}^{SA}

≥0

(3)

{t^{F}}_{ijk}

t_{ijk}^{SA}

{C^{S}}_{ij}

t_k

(4)

t_{ij 1}^{SA}

≥

{t^{F}}_{i' j' 1}

t_{c_{1}}

(5)

t_{ij 2}^{SA}

≥

{t^{F}}_{i' j' 2}

t_{c_{2}}

(6)

t_{ij 3}^{SA}

≥

{t^{F}}_{i' j' 3}

t_{c_{3}}

(7)

t_{ij 4}^{SA}

≥

{t^{F}}_{i' j' 4}

(8)D_ijk+D_i″j″k≤1, k=1, 2, 3

(9)

{C^{S}}_{ij}

≥Q_min

目标函数:

(10)f₁=min(max

{t^{F}}_{ijk}

)

(11)$f_{2}=min N_{a}=min|\frac{\sum^{t=max t^{F}_{ijk}}_{t=1}}{max t \frac{F}{ijk}}|$

式中: ${t^{S}}_{ijk}$ 为工单S_ij在机器k上的开始加工时间; ${t^{F}}_{ijk}$ 为工单S_ij在机器k上的完工时间;记S_i'j'为根据排程结果在相同机器上工单S_ij前一个工单; ${t^{S}}_{i' j' k}$ 为工单S_i'j'在机器k上的开始加工时间; ${t^{F}}_{i' j' k}$ 为工单S_i'j'在机器k上的结束加工时间; $N_{W}^{t}$ 为产线在t时刻产线中在制品数量;N_a为从产线开始加工到结束加工期间内的平均在制品数量;D_ijk为二进制变量,当工单S_ij分配到机器k上时为1,否则为0;D_i″j″k为二进制变量,当与工单S_ij不属同一订单的任一子批S_i″j″分配到机器k上时为1,否则为0.

式(1)表示同一工单在内喷涂机上的开始加工时间与该工单在拉伸机上开始加工时间的约束;式(2)表示每个工单的开始加工时间必须大于等于0;式(3)为机器k上的工单S_ij的开始加工时间与完工时间之间的关系;式(4)~(7)分别表示在拉伸机1、拉伸机2、内喷涂机、包装线上,下一个工单的开始时间与上一个工单完工时间的约束;式(8)表示不同订单子批次(工单)在拉伸机1、拉伸机2和内喷涂机上是不可混流生产的;式(9)表示拆分后的每个工单的最小产品数;式(10)表示完成所有订单生产的最小化完工时间;式(11)表示产线的平均在制品数量最小化.

2 自适应候鸟迁徙优化算法

基本的MBO算法是针对二次分配这种连续函数优化问题提出的,不能直接用于处理HFSP这类离散的组合优化问题,需要转换成离散形式.本文基于候鸟迁徙优化算法,结合ILS-HFSP问题,提出一种AMBO算法,包括批量拆分规则、编码与解码机制、邻域搜索策略、种群初始化、领导解优化、跟随解优化、领导解替换与算子权重自适应调整等,可有效求解ILS-HFSP问题.

2.1 算法具体定义

2.1.1 批量拆分规则对于批量流问题,需要明确订单的拆分规则.常见的订单拆分方式为给定一个随机数,对需要拆分的订单随机拆分成该数量个子订单^[5],随机数的选取范围需根据订单大小与问题特征具体问题具体分析.本研究的批量大小不完全相同,拆分批量的上下限应根据每个订单的大小进行调整.

产品数量大的订单是引起在制品堆积的原因,由于本文订单存在一个最小批量Q_min,规定只有当订单产品数量>2Q_min时才能被拆分,所以大订单至少需要拆分成个工单,最多能拆分成个工单.

因此,订单的拆分规则为: ① 订单数量 $C_{i}^{J}$ <2Q_min的订单不进行拆分,其工单数为 ${N^{S}}_{i}$ =1;② 订单数量 $C_{i}^{J}$ >2Q_min的订单从 $[\frac{C_{i}^{J}}{2 Q_{\min}}, \frac{C_{i}^{J}}{Q_{\min}}]$ 中随机选取一个整数作为订单的工单数 ${N^{S}}_{i}$ ,并将其随机拆分成 ${N^{S}}_{i}$ 个产品数量不相等工单.

2.1.2 编码与解码机制 ILS-HFSP问题需同时优化订单拆分问题和作业调度问题,因此编码应同时考虑这两个方面,本文采用两阶段编码方案.用自然数序列代表所有可能的工单排列,编码分为两段:第1段表示加工顺序;第2段表示待分配的工单编码,每个工单编码对应一个加工顺序编号.每个工单编码由一个工单编号与其对应工单的数量组成,工单编号数为4位整数,工单数量为5位整数.例如,工单编号为101,数量为 3000 的工单的工单编码为010103000.编码示例如图2所示.

图2

图2 编码示例

Fig.2 Code sample

每个编码都代表订单拆分后的工单在内喷涂机上的排程结果,为了进一步得到每个工单在各机器上的加工时间序列,计算每个解的适应度值,需对编码进行解码.由于拉伸机1与拉伸机2并行工作,每个工单只能在其中一台机器上加工,解码时需要考虑两个问题:① 所有工单在机器上的开始加工时间与完工时间;② 系统平均在制品数量.其具体过程如下.

假设有b个工单,其在内喷涂机上的加工序列为∂=(∂₁, ∂₂, …, ∂_b),即依次将工单∂_q从∂中取出并执行如下步骤.

步骤1 选取具有最先空闲时间的拉伸机,将工单∂_q分配到该机器上,确定其在该拉伸机上的开始加工时间与完工时间;

步骤2 重复步骤1,直到完成所有工单的拉伸机分配;

步骤3 根据加工序列与各工单在拉伸机上完工时间依次计算每个工单在内喷涂机上的开始加工时间与完工时间;

步骤4 根据每个工单在内喷涂机上的完工时间,计算每个工单在包装线的开始加工时间与完工时间,得到加工完所有工单的最终完工时间;

步骤5 根据解码所得到的各工单在其对应加工机器上的开始加工时间、结束加工时间、各机器的节拍与换模时间,计算流水车间开始加工到结束加工的平均在制品数量.

2.1.3 适应度函数值在得到解在各机器上的加工时间后,需要评估解的适应度值来完成领导解、跟随解的排序选择.本文采用权重和法处理多目标优化问题,由于研究的两个目标具有不同量纲,需先进行目标归一化处理,具体过程如下所示:

(12)

{\tilde{f}}_{y}

\frac{f_{y} - \min f_{y}}{\max f_{y} - \min f_{y}}

, y=1,2

式中:y=1,2分别表示目标函数(10)与目标函数(11); ${\tilde{f}}_{y}$ 为目标f_y归一化值;max f_y和min f_y分别为目标f_y的上界和下界.通过这种方式,每种目标都可以归化为区间[0, 1]之间的值.目标的上界和下界是随着算法的运行实时更新,即每次产生新解,利用其目标值来更新上界和下界.归一化后的适应度函数为

(13)F_min=λ₁

{\tilde{f}}_{1}

+λ₂

{\tilde{f}}_{2}

式中:λ₁、λ₂为2个目标函数的权重.

最小化总加时间与最小化平均在制品数量是本研究的两个目标,产线优化的首要目标是最大化生产速率使得企业效益最大化,而最小化平均在制品数量是为减少成本,属于次要目标,取权重λ₁=0.6,λ₂=0.4.

2.2 改进策略

2.2.1 邻域搜索算子 MBO算法是一种基于邻域搜索的元启发式算法,因此有必要为其确定高效的邻域搜索算子.基于本文所采用的两阶段编码机制,从文献[21]中引入4种常见的邻域算子,分别为插入算子、贪婪插入算子、交换算子、贪婪交换算子.交换算子计算量小但局部搜索能力有限;贪婪算子虽然能提高局部搜索的结果,但会极大增加计算量.为平衡计算量与局部搜索结果,基于最佳批量原则本文提出一种时间窗算子,使其以较短的时间得到较优的解.以上算子都是针对调度子问题,针对批量拆分子问题,本文采用批量调整算子,使各订单的工单数与工单的产品数随算法迭代调整.

(1) 时间窗算子.

由于工单产品数量各不相同,首先定义一个推进时间窗W=[t^es, t^lf],t^es为在内喷涂机处任务的开始时间,t^lf为在内喷涂机处任务的结束时间,其是预测时域内包含一定数量工单的时间窗口,而其平均宽度取2Qt₃.时间窗为2Q的匹配度较小,因此增加一个宽放系数γ,使时间窗的宽度取为

(14) (2-2γ)Qt₃≤t^lf-t^es≤(2+2γ)Qt₃

式中:γ为时间窗的宽放系数,常见的宽放系数为0.05、0.1、0.2等,为尽可能匹配较多的订单,取宽放系数为0.2.

每次搜索的目标是从当前解中随机寻找拉伸机编号不相同的两个未被匹配时间窗的工单,对其进行时间窗匹配,形成一个新的邻域解,且满足如下订单关系式:

(15) (2-2γ)Qt₃≤

C_{\bar{ij}}^{S}

t₃+

C_{\overset{'}{i}}^{S}

t₃+2

t_{c_{3}}

≤ (2+2γ)Qt₃

式中: $C_{\bar{ij}}^{S}$ 、 $C_{\overset{'}{i}}^{S}$ 分别为工单 $S_{\bar{ij}}$ 与 $S_{\overset{'}{i}}$ 的产品数量.时间窗算子的流程图如图3所示,其具体实施过程如下.

图3

图3 时间窗算子

Fig.3 Time window operation

步骤1 将当前鸟中的所有工单输入到一个搜索集中;

步骤2 判断搜索集是否为空,若为空则采用随机交换操作形成邻域解并结束邻域搜索;

步骤3 寻找搜索集中产品数量最大的工单;

步骤4 判断该工单与其后一工单是否能满足时间窗约束,若满足时间窗约束则将找到的订单2加工序号与订单1后的加工序号交换,若不能则跳到步骤5;

步骤5 寻找个体中能与其满足时间窗约束的工单,若无法找到,则将该工单从搜索集中剔除并重复步骤1~5,若找到则将找到的工单与其后一工单位置进行交换形成新的解.

(2) 批量调整算子.

在工单编码段任选一个具有两个以上工单的订单,选择其中两个相邻的工单对其重新分配:随机选取其中一工单中随机数量的产品分配到另一工单中.若重新分配后的工单数量低于最小批量Q_min,则以50%概率将该工单全部分配到另一工单中,并将该工单所属订单的工单数减1;以50%的概率使该工单产品数量等于最小批量Q_min,并将其余数量的产品分配给另一工单.例如,一个 1300 与 4400 的工单组合,随机调整成 1600 与 4100 的组合.批量调整算子示意图如图4所示.

图4

图4 批量调整算子示意图

Fig.4 Diagram of batch adjustment operation

上述邻域搜索算子分别针对不同的子问题,如果只采用其中一种很难找到全局最优解.为了有效地联合两个子问题,提出了以下混合结构.

(1) 混合结构1:首先执行插入算子,然后执行批量调整算子.

(2) 混合结构2:首先执行贪婪插入算子,然后执行批量调整算子.

(3) 混合结构3:首先执行交换算子,然后执行批量调整算子.

(4) 混合结构4:首先执行贪婪交换算子,然后执行批量调整算子.

(5) 混合结构5:首先执行时间窗算子,然后执行批量调整算子.

2.2.2 邻域算子权重自适应调整本文采用了4种常见的邻域算子、时间窗算子、批量调整算子以及5种混合结构共计11种算子.为有效利用所采用的11种不同邻域算子,采用变邻域搜索策略使各算子的邻域得到充分探索.本文采用轮盘赌的方法,给每个算子以一个权重,在每次进行邻域搜索操作时根据每个算子权重随机选择邻域搜索算子得到邻域解.

邻域搜索的每个算子在算法的不同阶段对解的改进效果各不相同,例如在算法求解的初始阶段应优先选择全局搜索能力强的算子,在后期调整阶段应优先选择局部搜索能力强的算子.因此本文引入自适应调整策略^[22],使每个邻域算子权重随算法迭代自动调整,其具体计算如下.

给每个算子赋值一个权重w_O,其范围为[0,1]选择算子使用轮盘赌,每个算子被选择的概率P= $\frac{w_{O}}{\overset{11}{\sum_{O=1}} w_{O}}$ ,在每经过一个权重调整周期m次后更新权重:

(16)w_O=(1-r)w_O+

\frac{r π_{O}}{θ_{O}}

式中:π_O为算子O经过m次迭代后的得分累计情况,其初始值为0,若表现比最优解好,则取π_O=π_O+1,对其余算子取原值;θ_O为算子O经过一个权重调整周期时算子O使用的次数;r为反应因子,控制权重调整规则对启发式方法的效率变化作出反应的速度与权重调整幅度.如果r为0,那么将完全不使用分数,而是保持初始权重.如果r设置为1,则在最后一代中获得的分数决定权重.本文取r为0.5,在反应速度与调整幅度之间保持平衡.设每个算子的初始权重为1,当算法完成一个迭代周期m后更新每个算子被选择的概率P,并重新将算子的权重设为1.

2.2.3 扰动机制 MBO算法的邻域搜索机制过度关注了算法的局部搜索能力,为平衡算法的全局搜索和局部搜索能力,将扰动机制引入到MBO算法中.记g为扰动机制触发周期,如果领导解连续g次迭代没有更新,则扰动机制触发.在基本的扰动机制中,防止解陷入局部搜索的方法是用随机产生的新解将其替换.完全随机的方法会影响到算法的执行效率,为提高算法的执行效率,在连续第g次领导解没有更新时,以领导解为种子,引入Glover操作产生两个解分别替换领导解的左右跟随解.Glover操作将解序列拆分成z个子解序列,每个子序列以z为步长依次从原解序列中挑选组成,然后将z个子序列重新组合成扰动后的解序列.Glover操作的优势在于可以从种子解进行发散产生新解,并且新解继承旧解的序列信息,有利于提高算法的执行效率,已被文献^[5,23-24]等用于防止算法陷入局部最优解中,取得了良好的效果,并根据文献[5]采用z=3作为Glover操作的参数.

2.3 AMBO算法实现

AMBO算法包含以下几个步骤:种群初始化、领导解改进、跟随解改进、领导解替换与算子权重更新、循环迭代与扰动机制.具体流程如图5所示.

图5

图5 AMBO算法流程图

Fig.5 Flowchart of AMBO algorithm

步骤1 初始化种群.首先,设置AMBO算法的6个控制参数,包括鸟(解)群中个体的数量(α),要考虑的邻域解数(β),跟随解共享的邻域解数(χ),领导解更换后鸟群的迭代次数(ω),算子权重自适应调整周期(m)、扰动机制触发周期(g).然后根据批量拆分规则对所需排程的订单任务拆分后对每个工单赋以随机加工顺序生成一个可行解,重复此过程生成α个解,选取适应度最优的解作为领导解,并将其余解随机安置在V形种群结构上形成初始种群.

步骤2 领导解改进.根据各算子的初始权重得到相应被选择概率,采用轮盘赌方法围绕领导解生成β个邻域解.首先,对所得到的邻域解根据解码结果评估其适应度值,如果邻域解中最优解的适应度值优于领导解,那么领导解将被替换;否则,领导解保持不变.然后,将未使用的邻域根据其适应度值选取最优的2χ个解,分别形成包含χ个邻域解的左、右共享邻域集.

步骤3 跟随解改进.改进过程是沿着尾巴进行的.对于左(右)队列中的跟随解(例如X),根据各邻域算子权重以轮盘赌方式产生β个邻域解.所产生的β个邻域解和左(右)共享邻域集中的解被视为X的邻域集,对所得的邻域集根据解码结果评估其适应度值.如果最佳邻域解比X具有更好的适应性,则替换X;否则将保持跟随解不变.随后,在未使用的邻域中选择最优的χ个解,用来重建左(右)共享邻域集.重复上述过程,直到遍历完左队列和右队列中的所有跟随解为止.

步骤4 领导解替换与算子权重更新.在执行第3步ω次后,若追随解中的最优解比领导解适应值更优,则将最优追随解与当前最优解相互交换以更新领导解,否则解将保持不变.根据不同算子对解的改进情况更新其算子权重,并判断是否达到邻域搜索算子权重更新周期,若达到邻域搜索算子权重更新周期,依据邻域算子权重自适应调整式(16)分别更新每个算子的权重,并依据权重更新每个算子被选择的概率.

步骤5 循环迭代与扰动机制.为了防止算法陷入局部最优,采用Glover 操作对g次迭代后未更新的领导解进行扰动,取两个新解分别替换领导解后的左、右跟随解.算法在若干次迭代后如果达到最大迭代次数,则算法终止;否则,重复步骤2~5直到满足算法终止条件.

3 仿真实验研究

3.1 算例产生规则

A企业的订单统计分析后具有以下特征,产品数量在3×10³以下、3×10³~1×10⁴与1×10⁴~2×10⁴的订单分别占据其所有订单数的80%、15%与5%,产品总数量分别占所有订单的产品数总和的50%、30%与20%.出于A企业接单能力、成本、效率等因素的考虑,最大订单数量不超过2×10⁴,最小订单数量不小于10³,即Q_min=10³.设定所有订单的产品数量都能被10整除,订单的数量特征如表1所示.

表1 订单产品的数量特征

Tab.1 Quantity characteristics of product orders

产品数量范围	订单数比例/%	产品总数比例/%
1×10³~3×10³	80	50
3×10³~1×10⁴	15	30
1×10⁴~2×10⁴	5	20

文献[5]指出,目前关于批量流水车间调度问题没有基准算例,为此本文根据表1的订单产品数量特征,随机产生不同规模的订单任务作为算例来评估算法性能.各机器的生产速率以及问题背景保持一致:拉伸机1与拉伸机2的生产速率为4.5×10²个/h,内喷涂机的生产速率为9×10²个/h,包装段的生产速率为8×10²个/h.拉伸机1、拉伸机2与内喷涂机的换模时间都为30 min,可以得到最佳加工批量 Q=3.6×10³.

3.2 参数设置

参数设置通常在元启发式算法的有效性中起到重要作用.为了得到AMBO算法的最优参数,采用实验设计(DOE)方法设计了田口实验.AMBO算法中有6个控制因素,包括了α、β、χ、ω、m、g.由于β≥2χ+1,所以参数β、χ不满足实验设计要求.本文采用文献[17]建议的参数β=3、χ=1,将α、ω、m、g这4个参数作为实验因子,以一组订单数量为20的30个随机案例的平均值来测试在算法运行100 s时的平均最优结果值,通过Minitab17设计并运行分析最佳参数配置.

参考文献[5-6]中的因子水平,设计了4因子3水平的L9型正交田口实验,其各因子的3个水平取值分别为α{α1=25,α2=51,α3=81}、ω{ω1=5,ω2=10,ω3=15}、m{m1=5,m2=10,m3=15}、g{g1=10,g2=20,g3=30},表2为所设计的L9正交实验及相应的实验平均值.在Minitab17中分析后得到均值的主效应图如图6所示,其中:μ为每种参数的平均响应值.均值响应表如表3所示,其中:Δ为每个因子最大平均值减去最小平均值.从图6中可以得到,α=51、ω=10、m=10、g=10的参数组合下,AMBO算法将具有更好的性能.因此,将α=51、β=3、χ=1、ω=10、m=10、g=10作为AMBO算法的初始化参数.

表2 正交矩阵及响应值

Tab.2 Orthogonal matrices and response values

次序	α	ω	m	g	平均值
1	25	5	5	10	0.0801
2	25	10	10	20	0.0803
3	25	15	15	30	0.0881
4	51	5	10	30	0.0821
5	51	10	15	10	0.0767
6	51	15	5	20	0.0861
7	81	5	15	20	0.0896
8	81	10	5	30	0.0869
9	81	15	10	10	0.0886

图6

图6 均值主效应图

Fig.6 Mean main effects plot

表3 均值响应表

Tab.3 Mean response table

水平	α	ω	m	g
1	0.08283	0.08393	0.08437	0.0818
2	0.08163	0.0813	0.08367	0.08533
3	0.08837	0.0876	0.0848	0.0857
Δ	0.00673	0.0063	0.00113	0.0039
排序	1	2	4	3

3.3 算法测试

为验证AMBO算法求解问题的有效性,将其与基本MBO、遗传(GA)算法对比.因为问题的NP难特性,不能保证得到问题的最优解.因此,以多次重复实验所得到的最优解的平均值作为衡量算法求解精度,采用最优解的标准偏差评价算法的稳定性.因为订单随机性的影响,为了能够得到更多可靠的数据,算法在不同订单规模下随机生成30个订单任务,再对每个订单任务重复运行30次,得到每个任务的最优解平均值与标准偏差,分别对所得到的30个订单任务的最优解平均值与标准偏差取平均值,即得到所评价算法在该规模下的最优解平均值与标准偏差.

3种算法编码规则完全一致,其中遗传算法参数为种群规模为500,交叉概率P_c=0.8,交叉算子选用顺序交叉,变异概率P_m=0.1,变异算子选用插入算子与批量调整算子;AMBO算法参数为鸟群中个体的数量α=51,要考虑的邻域解数β=3,跟随鸟共享的邻域解数χ=1,领导鸟更换后鸟群的迭代次数ω=10,算子权重自适应调整周期m=10,扰动机制触发周期g=10;基本MBO算法的参数引自文献^[17]:鸟群中个体的数量α=51,要考虑的邻域解(β=3,跟随鸟共享的邻域解数χ=1,领导鸟更换后鸟群的迭代次数ω=10,邻域算子采用插入算子、交换算子与批量调整算子.将算法终止条件统一设置为连续迭代100次最优值不变;采用MATLAB 2014b编程,测试环境为Windows 10系统,CPU为i7-7700k、内存为16 GB.随机生成30个订单总数为20的任务,每个任务进行30次重复实验,得到的平均值与其标准偏差(SD)结果如表4所示.

3种算法实验所得的最优解均值、解的标准偏差、平均收敛迭代次数及算法平均运行时间的结果如表5所示,并根据算法迭代过程绘制了3种算法的平均收敛过程图如图7所示.其中:ξ为迭代次数;κ为每次迭代中30次重复的多目标最优值.

图7

图7 3种算法收敛效果图

Fig.7 Convergence effect diagram of three algorithms

由表4、表5和图7可知,GA算法收敛较快,但易陷入局部最优,求解精度差;而基本MBO算法虽然有一定的局部搜索能力,但其搜索能力有限,收敛速度慢且容易陷入局部最优,无法使候鸟集中在最优值附近;而本文提出的AMBO算法,采用了自适应算子权重与变邻域搜索,加快收敛速度且增强了局部搜索能力,较其他两种算法其求解精度更高,稳定性更好,求解时间与MBO算法较为接近,说明了AMBO算法的有效性.

表4 算法结果对比

Tab.4 Comparison of algorithm results

序号	AMBO		MBO		GA
序号	最优解均值	标准偏差	最优解均值	标准偏差	最优解均值	标准偏差
1	0.0649	0.00384	0.0653	0.00404	0.0664	0.00684
2	0.0625	0.00335	0.0626	0.00334	0.0642	0.00759
3	0.0683	0.00354	0.0726	0.00369	0.0764	0.00795
4	0.0686	0.00284	0.0784	0.00365	0.0814	0.00718
5	0.0748	0.00321	0.0765	0.00364	0.0787	0.00768
6	0.0646	0.00322	0.0795	0.00342	0.0834	0.00747
7	0.0706	0.00317	0.0796	0.00391	0.0777	0.00734
8	0.0715	0.00336	0.0771	0.00387	0.0804	0.00847
9	0.0673	0.00341	0.0715	0.00405	0.0761	0.00757
10	0.0711	0.00371	0.0826	0.00367	0.0817	0.00754
11	0.0621	0.00315	0.0645	0.00378	0.0794	0.00781
12	0.0733	0.00344	0.0799	0.00363	0.0844	0.00759
13	0.0875	0.00334	0.0884	0.00413	0.0919	0.00763
15	0.0865	0.00325	0.0886	0.00357	0.0884	0.00804
14	0.0686	0.00311	0.0726	0.00398	0.0757	0.00725
16	0.0639	0.00324	0.0709	0.00338	0.0704	0.00737
17	0.0716	0.00315	0.0719	0.00401	0.0717	0.00794
18	0.0639	0.00341	0.0656	0.00387	0.0732	0.00781
19	0.0723	0.00331	0.0695	0.00348	0.0774	0.00765
20	0.0633	0.00345	0.0644	0.00367	0.0706	0.00742
21	0.0643	0.00344	0.0684	0.00379	0.0704	0.00806
22	0.0659	0.00339	0.0724	0.00344	0.0722	0.00774
23	0.0665	0.00338	0.0726	0.00404	0.0719	0.00735
24	0.0649	0.00326	0.0686	0.00367	0.0704	0.00784
25	0.0685	0.00328	0.0699	0.00421	0.0717	0.00785
26	0.0696	0.00285	0.0699	0.00368	0.0707	0.00752
27	0.0724	0.00324	0.0726	0.00354	0.0731	0.00728
28	0.0624	0.00337	0.0679	0.00364	0.0695	0.00838
29	0.0688	0.00315	0.0695	0.00392	0.0714	0.00763
30	0.0691	0.00308	0.0719	0.00390	0.0737	0.00734
均值	0.0690	0.00330	0.0731	0.00375	0.0758	0.00764

表5 3种算法的实验结果

Tab.5 Experimental results of three algorithms

算法	最优解均值	解的标准偏差	平均收敛迭代次数	算法平均运行时间/s
GA	0.0758	0.00764	88	263.13
MBO	0.0731	0.00375	76	335.24
AMBO	0.0690	0.00330	56	358.12

进一步验证算法的有效性与稳定性,用3种算法对不同任务量求解.表6分别为订单总数为30、40、50的3种不同任务规模随机重复平均实验结果.

由表6可以看出,在小规模算例中,随着任务规模的增大,最优解均值会增加,算法运行时间将明显增加,算法平均收敛次数增加也十分明显.GA算法在收敛速度上有一定的优势,但其缺点在于容易陷入局部最优.MBO算法在运行时间上比GA慢,但其全局搜索结果比GA更好.AMBO算法的求解时间相比于GA算法较长,与MBO算法较接近,但其求解精度与解的标准偏差均优于MBO算法与GA算法.

表6 3种算法在不同规模下的实验结果

Tab.6 Experimental results of three algorithms at different scales

任务规模	算法	最优解均值	解的标准偏差	平均收敛迭代次数/次	算法平均收敛时间/s
30	GA	0.0771	0.00798	128	362.24
	MBO	0.0748	0.00384	112	466.25
	AMBO	0.0706	0.00376	87	493.46
40	GA	0.0778	0.00784	167	560.32
	MBO	0.0752	0.00391	154	650.21
	AMBO	0.0714	0.00364	125	708.72
50	GA	0.0806	0.00814	205	780.32
	MBO	0.0766	0.00414	179	920.31
	AMBO	0.0721	0.00385	162	994.63

上述测试算例规模较小,为进一步测试算例规模对算法的影响,选取任务规模为60、80、100的大规模案例,以最大CPU运行时间为终止条件,每个任务规模随机重复30次,以相对百分比增加率^[6](RPI)值与其标准差测试各算法寻优能力.最大CPU运行时间正比于量规模,因此设定CPU运行时间为n×ρ, n为订单总数,即排产任务规模,ρ为设置的常数,随着算法规模的增加,算法的测试时间也将增加,为了综合比较算法的性能,设置三种不同的ρ分别为10、20、30 s,在ρ=30时所对比算法大部分已达到收敛状态.RPI值计算公式如下:

(17)RPI(R_v)=

\frac{R_{v} - R_{\min}}{R_{\min}}

式中:R_v为所给算法的第v次实验所得目标值;R_min为该算例下参与比较的几个算法中所得最小目标值,RPI值越小,算法性能越优.表7为n=60,80,100这3个大规模算例30个随机重复实验的RPI平均值 $\bar{x}$ 与其标准差s.此外,通过T检验将AMBO算法与其他算法进行比较如表8所示,其值为1或 -1 表示AMBO算法在95%的置信度上优于或劣于该算法,值为0表明两种算法所求得的值没有显著差别.

由表7和8可知,当ρ=10,任务规模为60的测试实例中,AMBO算法均优于MBO算法与GA算法;任务规模为80的测试实例中,AMBO算法GA算法无显著差异,但优于MBO算法;任务规模为100的测试实例中,AMBO算法劣于GA算法但优于MBO算法.当ρ=20,30时,AMBO算法能在所有测试实例中优于MBO算法与GA算法.AMBO算法为了保证精度而牺牲了求解速度,在大规模算例中,尽管AMBO算法在分配较少的时间(ρ=10)时劣于GA,但在分配更多CPU时间(ρ=20,30)后,AMBO仍优于GA算法.因此,在大规模算例下,AMBO算法总体上优于MBO算法与GA算法.

表7 当ρ=10,20,30时,GA、MBO与AMBO算法RPI值比较

Tab.7 Comparison of RPI among GA, MBO, and AMBO algorithms at ρ=10,20, and 30

任务规模	算法	ρ=10		ρ=20		ρ=30
任务规模	算法	$\bar{x}$ /%	s	$\bar{x}$ /%	s	$\bar{x}$ /%	s
60	GA	5.78	4.78	8.15	4.32	13.01	3.81
	MBO	12.21	3.79	11.06	3.64	8.70	3.43
	AMBO	3.37	2.78	2.84	2.57	2.61	2.44
80	GA	3.73	5.24	7.27	4.71	11.42	4.29
	MBO	11.93	4.13	10.38	3.81	7.94	3.72
	AMBO	3.54	3.11	3.13	2.79	2.89	2.58
100	GA	2.41	5.67	5.61	5.12	7.56	4.52
	MBO	12.71	4.85	10.47	4.45	7.46	4.23
	AMBO	5.74	3.43	3.74	3.12	3.31	2.88

表8 当ρ=10,20,30时,AMBO与对比算法的T检验结果比较

Tab.8 T-test results for AMBO and other algorithms at ρ=10,20, and 30

任务规模	ρ=10		ρ=20		ρ=30
任务规模	GA	MBO	GA	MBO	GA	MBO
60	1	1	1	1	1	1
80	0	1	1	1	1	1
100	-1	1	1	1	1	1

从上述测试结果可以看出,AMBO算法在任务规模为50以下的小规模算例中,其求解精度与稳定性均优于MBO算法与GA算法;在大规模算例中,AMBO算法的寻优能力优于MBO算法,虽然在较少CPU时间内会劣于GA算法,但总体优于GA算法,故能说明AMBO算法的有效性.

4 结语

针对2+1+1型三阶段混合流水车间的ILS-HFSP,提出了基于变邻域搜索的AMBO算法,解决了最小化完工时间与最小化系统平均在制品数量的多目标优化问题.所设计的算法借鉴了自适应大邻域搜索算法,在邻域算子处设计了时间窗算子与算子权重随算法的迭代自适应调整策略,提高了算法的全局搜索能力与求解精度.通过对不同规模任务的30次随机重复实验,表明所建立的调度数学模型及改进的候鸟迁徙优化算法是可行有效的,AMBO算法相比于MBO算法与GA算法,具有求解质量更高、最优解标准偏差更小的优点.本研究可以降低混合流水车间的平均在制品数量,填补了ILS-HFSP问题关于最小化完工时间与最小化在制品数量多目标优化研究的空白,也更符合工厂实际生产.未来将结合缓存区配置优化与动态排程等方面进行进一步研究.

(本文编辑:石易文)

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

周炳海, 刘文龙.

考虑能耗和准时的混合流水线多目标调度

[J]. 上海交通大学学报, 2019, 53(7):773-779.

ZHOU

Binghai

, LIU

Wenlong

Multi-objective hybrid flow-shop scheduling problem considering energy consumption and on-time delivery

[J]. Journal of Shanghai Jiao Tong University, 2019, 53(7):773-779.

DOI:10.1016/j.ress.2019.106753 URL [本文引用: 1]

[2]

ZHOU X

, YU M

Semi-dynamic maintenance scheduling for multi-station series systems in multi-specification and small-batch production

[J]. Reliability Engineering & System Safety, 2020, 195:106753.

[3]

陶辛阳, 夏唐斌, 奚立峰.

基于健康指数的预防性维护与多目标生产调度联合优化建模

[J]. 上海交通大学学报, 2014, 48(8):1170-1174.

TAO

Xinyang

, XIA

Tangbin

, XI

Lifeng

Health-index-based joint optimization of preventive maintenance and multi-attribute production scheduling

[J]. Journal of Shanghai Jiao Tong University, 2014, 48(8):1170-1174.

[4]

李颖俐, 李新宇, 高亮.

混合流水车间调度问题研究综述

[J]. 中国机械工程, 2020, 31(23):2798-2813.

Yingli

, LI

Xinyu

, GAO

Liang

Review on hybrid flow shop scheduling problems

[J]. China Mechanical Engineering, 2020, 31(23):2798-2813.

DOI:10.1016/j.asoc.2016.12.021 URL [本文引用: 6]

[5]

ZHANG

, PAN Q

, GAO

, et al.

An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming

[J]. Applied Soft Computing, 2017, 52:14-27.

[6]

MENG

, PAN Q

, LI J

, et al.

An improved migrating birds optimization for an integrated lot-streaming flow shop scheduling problem

[J]. Swarm and Evolutionary Computation, 2018, 38:64-78.

DOI:10.1016/j.swevo.2017.06.003 URL [本文引用: 4]

[7]

ZHANG

, TAN Y

, ZHU J

, et al.

A competitive and cooperative migrating birds optimization algorithm for vary-sized batch splitting scheduling problem of flexible job-shop with setup time

[J]. Simulation Modelling Practice and Theory, 2020, 100:102065.

DOI:10.1016/j.simpat.2019.102065 URL [本文引用: 3]

[8]

NADERI

, YAZDANI

A model and imperialist competitive algorithm for hybrid flow shops with sublots and setup times

[J]. Journal of Manufacturing Systems, 2014, 33(4):647-653.

DOI:10.1016/j.jmsy.2014.06.002 URL [本文引用: 2]

[9]

LALITHA J

, MOHAN N

, PILLAI V

Lot streaming in [N-1](1)+N(m) hybrid flow shop

[J]. Journal of Manufacturing Systems, 2017, 44:12-21.

DOI:10.1016/j.jmsy.2017.04.018 URL [本文引用: 2]

[10]

李航, 章旸, 叶鸿庆, 等.

考虑批量流与换模时间的柔性生产线调度方法研究

[J]. 工业工程与管理, 2020, 25(3):179-187.

[本文引用: 2]

Hang

, ZHANG

Yang

, YE

Hongqing

, et al.

Research on flexible production line scheduling with lot streaming and setup times

[J]. Industrial Engineering and Management, 2020, 25(3):179-187.

[本文引用: 2]

[11]

ZHANG

, PAN Q

, GAO

, et al.

A multi-objective migrating birds optimization algorithm for the hybrid flowshop rescheduling problem

[J]. Soft Computing, 2019, 23(17):8101-8129.

DOI:10.1007/s00500-018-3447-8 URL [本文引用: 1]

[12]

LI J

, TAO X

, JIA B

, et al.

Efficient multi-objective algorithm for the lot-streaming hybrid flowshop with variable sub-lots

[J]. Swarm and Evolutionary Computation, 2020, 52:100600.

DOI:10.1016/j.swevo.2019.100600 URL [本文引用: 1]

[13]

GONG D

, HAN Y

, SUN J

A novel hybrid multi-objective artificial bee colony algorithm for blocking lot-streaming flow shop scheduling problems

[J]. Knowledge-Based Systems, 2018, 148:115-130.

DOI:10.1016/j.knosys.2018.02.029 URL [本文引用: 1]

[14]

沈倩, 管在林, 张正敏, 等.

面向卷烟生产调度的集成产能过滤算法与仿真技术的优化框架

[DB/OL].(2020 -10-26)[2021-02-07]. https://kns.cnki.net/kcms/detail/11.5946.TP.20201026.1016.012.html.

URL [本文引用: 1]

SHEN

Qian

, GUAN

Zailin

, ZHANG

Zhengmin

,, et al.

An optimization framework based on simulation integrated capacity filtering algorithm for cigarette production scheduling

[DB/OL].(2020 -10-26)[2021-02-07]. https://kns.cnki.net/kcms/detail/11.5946.TP.20201026.1016.012.html.

URL [本文引用: 1]

[15]

吕洁, 郭婷芳, 韩文民.

虚拟制造单元瓶颈缓冲区容量优化

[J]. 组合机床与自动化加工技术, 2016(12):121-124.

Jie

, GUO

Tingfang

, HAN

Wenmin

Bottleneck buffer allocation optimization of the virtual manufacturing

[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2016(12):121-124.

[16]

ENGEHAUSEN

, LÖDDING

Managing sequence-dependent setup times—The target conflict between output rate, WIP and fluctuating throughput times for setup cycles

[J]. Production Planning & Control, 2020: 1-17.

DOI:10.1016/j.ins.2012.06.032 URL [本文引用: 3]

[17]

DUMAN

, UYSAL

, ALKAYA A

Migrating birds optimization: A new metaheuristic approach and its performance on quadratic assignment problem

[J]. Information Sciences, 2012, 217:65-77.

[18]

DINDAR O

An improvement on the migrating birds optimization with a problem-specific neighboring function for the multi-objective task allocation problem

[J]. Expert Systems With Applications, 2017, 67:304-311.

DOI:10.1016/j.eswa.2016.09.035 URL [本文引用: 1]

[19]

EXPOSITO IZQUIERDO

, DE ARMAS

, LALLA RUIZ

Multi-leader migrating birds optimization: A novel nature-inspired metaheuristic for combinatorial problems

[J]. International Journal of Bio-Inspired Computation, 2017, 10(4):1.

[20]

ALMONACID

, SOTO

, CRAWFORD

Comparing three simple ways of generating neighboring solutions when solving the cell formation problem using two versions of migrating birds optimization [C]//2017 17th International Conference on Computational Science and Its Applications (ICCSA)

. Piscataway, NJ, USA: IEEE, 2017: 1-9.

[21]

TONGUR

, ÜLKER

The analysis of migrating birds optimization algorithm with neighborhood operator on traveling salesman problem[C]//The 19th Asia Pacific Symposium

Bangkok, Thailand: Springer, 2015: 1-11.

DOI:10.1287/trsc.1050.0135 URL [本文引用: 1]

[22]

ROPKE

, PISINGER

An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows

[J]. Transportation Science, 2006, 40(4):455-472.

[23]

姚妮

混合候鸟迁徙优化算法求解柔性作业车间调度问题

[J]. 华中师范大学学报(自然科学版), 2016, 50(1):38-42.

YAO

Hybrid migrating brids optimization algorithm for the flexible job shop scheduling problem

[J]. Journal of Central China Normal University (Natural Sciences), 2016, 50(1):38-42.

[24]

唐立力

求解低碳调度问题的改进型候鸟优化算法

[J]. 计算机工程与应用, 2016, 52(17):166-171.

TANG

Lili

Improved migrating birds optimization algorithm to solve low-carbon scheduling problem

[J]. Computer Engineering and Applications, 2016, 52(17):166-171.