基于改进候鸟算法的柔性作业车间分批调度问题

刘雪红，段 程，王 磊+

(1.武汉理工大学 机电工程学院，湖北 武汉 430070；2.数字制造湖北省重点实验室，湖北 武汉 430070)

0 引言

在现实生产中，大规模制造的柔性作业车间通常采用提高技术或通过组织安排的方式来提高资源利用能力，如事先预测、工序并行、分批调度生产等[1]，其中分批调度是解决柔性作业车间问题的主要手段。分批调度指在加工过程中由于物料和工序的性质，允许分批传输和生产，从而使后续工序提前加工，缩短完工时间。

本文主要研究柔性作业车间内的分批调度问题(Flexible Job-shop Scheduling Problem with Lot Streaming, FJSP-LS)。根据批量划分方式的不同分为一致子批(consistent sublots)和可变子批(variable sublots)[2]。目前大多数分批调度研究，将一致子批的划分策略应用到流水车间[3-7]、作业车间[8-11]和柔性作业车间[12-14]，可变子批因其复杂性而研究较少,主要研究是将可变子批策略应用于流水车间[15]和柔性作业[1]，通过将最小批量进行批次划分后确定最优调度方案，再优化批量，从而在不影响制造时间的前提下优化批次数目,但是为了不减少制造时间，往往需要更多的批次数目，导致传输次数增加、生产成本增大，因此必须考虑批次数目与制造时间之间的关系，才能提出更合理的生产方案。

在FJSP-LS求解方法上，现有研究主要采用元启发式算法，如遗传算法[12]、差分算法[16]、禁忌搜索[1,8]和粒子群算法[14]等,大多侧重于调度方案的优化，对批次划分方案的制定缺乏深入研究。候鸟优化(Migrating Birds Optimization, MBO)算法是DUMAN等[17]于2011年首先提出的自然启发的元启发式算法，具有参数少、易于理解、结构简单等优点，成功用于多种优化问题，尤其是求解二次分配问题时，该算法获得了比模拟退火算法、禁忌搜索算法和指导的进化模拟退火算法质量更高的解。同时，越来越多的学者尝试将MBO运用到生产线调度上，同样获得了高质量的解[7,18-19]。

因此，本文以最小制造时间和最小批次数目为优化目标，采用可变批次的划分策略开展多目标柔性作业车间分批调度研究。针对可变子批下的柔性作业车间分批调度问题(Flexible Job-shop Scheduling Problem with Variable Sublots, FJSP-VS)，本文设计了一种改进的候鸟优化(Improved Migrating Birds Optimization, IMBO)算法，并结合柔性作业车间分批调度析取图的特点，提出精英分批与可行邻域结构策略，以实现制造时间和批次数目协同优化。

1 问题描述及数学模型

1.1 问题描述及符号定义

FJSP-VS描述如下：在某车间内，n种零件在m台机器加工，每个零件有多道工序，每种零件的各道工序可以在多台机器上选择加工，零件工序的先后顺序不能发生改变。另外，还需要满足以下假设：

(1)每种零件的每道工序最终只能安排在一台机器上加工。

(2)机器在加工一类零件的各个子批任务时，不允许加工其他零件的子批。

(3)零件在每台机器上的加工时间不变。

(4)一道工序的加工过程一旦开始，便不可中断。

为便于描述模型，文中使用的符号定义如表1所示。

表1 模型参数符号及说明

1.2 数学模型

本文所研究的调度问题的优化目标是：最小化最大完工时间和最小化批次数量。在文献[12]一致子批数学模型的基础上，根据问题描述和参数设置，构建多目标FJSP-VS的数学模型：

f={minCmax,minS}；

(1)

Cmax=max(Cj,o,s,m);∀(j,o,s,m)。

(2)

(3)

s.t.

Cr,m≥Cj,o,s,m+Ω×Xr,m,j,o,s-Ω; ∀(r,j,o,s,m)；

(4)

bj,o,s∈R;∀(j,o)；

(5)

C1,m-bj,o,1×Tj,o,m-Sj,o,m-Ω×X1,m,j,o,1+Ω≥0;

∀(m,j,o)；

(6)

Cr,m-bj,o,1×Tj,o,m-So,j,m,o′,j′-

Ω×(Xr,m,j,o,1+Xr-1,m,j′,o′,Sj′,o′)+2Ω≥Cr-1,m;

∀(r,m,j,o,j′,o′)|(r>1);

(7)

∀(j,o,m,r,s,m′,r′)|(o>1)；

(8)

Cr,m-bj,o,s×Tj,o,m-Tm,m′-

Ω×(Xr,m,j,o,s+Xr′,m′,j,o-1,bfj,o,s)+2Ω≥Cr′,m′;

∀(r,r′,m,m′,j,o,s)|(o>1);

(9)

Xr,m,j,o,s≤Pj,o,m;∀(r,m,j,o,s)；

(10)

(11)

Xr,m,j,o,s=Xr-1,m,j,o,s-1=Xr+1,m,j,o,s+1;

∀(r,j,m,s)|{(r>1)∧s∈(1,Sj)}；

(12)

Xr′,m,j,o,s′≤1-Xr,m,j,o,s;

∀(r,r′,m,o,o′,s,s′,j)|{(o′>o)∧(r′

(13)

(14)

Zr+1,m≤Zr,m;∀(r,m)。

(15)

其中：式(1)为目标函数，表示最小化最大完工时间和最小化划分批次数量；式(2)表示最大完成时间是最后完成批次的完成时间；式(3)表示划分批次的数目为批量不为0的批次数总和；式(4)表示机器m上第r个任务的完成时间大于等于被分配批次的完成时间；式(5)为批次划分约束，批次大小在上下界内；式(6)和式(7)为加工机器约束，安装准备操作在子批任务到达之前就能进行；式(8)和式(9)为工艺顺序约束，只有在待加工子批所包含的批量在上一道工序加工结束并运送到加工机器上，才可以开始加工；式(10)和式(11)确保每一个工序的批次分配到唯一一台具有加工能力的机器上；式(12)表示不允许混流加工；式(13)表示如果批次Oj,o,s是机器m执行的第r个任务，则工序Oj,o的后续工序不能在机器m上第r个任务之前加工；式(14)和式(15)确保机器m上第r个任务只能分配一个批次，且将任务r分配后才可以分配任务r+1。

1.3 析取图模型

析取图模型已经成为研究车间调度问题的标准模型，在此采用析取图模型G=(V,A,E)可以更好地理解FJSP-VS的结构。本文构建的析取图组成如下：

(16)

(17)

Pj,o,m=Pj′,o′,m=1;

(18)

(19)

Oj,o,s=πm,r,Oj′,o′,s′=πm,r+1。

(20)

其中：式(16)表示节点V由集合V1和V2组成，V1是起始节点0和终止节点*两个虚拟节点的集合，V2是所有批次的工序节点集合，二者权重为批次的加工时间；式(17)表示有向实线弧集合A包括集合A1和A2，A1是批次的首道工序与起始节点或末道工序与终止节点的连接弧，A2表示所有批次加工工序的约束关系，其中弧的权重表示传输时间；式(18)表示虚线弧集合E包括集合E1，E2，E3，E1表示机器的首个任务与起始节点之间的虚线弧，E2表示机器上可加工工序之间的虚线弧，E3表示同工序不同批次之间的虚线弧，其中弧的权重为机器之间任务的准备时间；式(19)表示每一个批次各道工序的机器指派已经确定，此时将多余的虚线弧去掉后，一个调度方案就可以通过析取图展现出来；式(20)为一个解形式的虚线弧集合。表2所示为一个FJSP-VS例子，图1a和图1b分别为该问题的析取图模型和一个可行解形式，此时解形式的析取图是无循环的，说明调度方案满足加工约束，它是一个可行解。

表2 析取图演示案例

关键路径指两个虚拟节点之间的最长路线，路线的权重之和即为该方案的完工时间。从起始节点到关键路径上的某个关键操作o的权重用Ho表示，该关键操作到终止节点的权重用To表示：

(Vj,o-1,bfj,o,s,Vj,o,s)∈A；

(Vj′,o′,s′,Vj,o,s)∈F；

(21)

(Vj,o,s,Vj,o+1,s′)∈A；

(Vj,o,s,Vj′,o′,s′)∈F；

(22)

Cmax=max{Hj,o,s+Bj,o,s×Tj,o,m+Tj,o,s};

∀Vj,o,s∈V∧Xr,m,j,o,s=1。

(23)

2 算法设计

2.1 编码方案和种群初始化

2.1.1 编码方案

针对FJSP-VS的特性，本文根据文献[12]的编码方式设计了一种两阶段编码方法，每一个可行解编码形式如图2所示，图中左侧表示批次划分方案，右侧表示调度方案。在批次划分编码中，由于每个批次有批量下限，根据式(24)可得每种零件每个工序的最大批次划分数L，从而确定批次划分编码长度。用L个范围为[0,1]、精度为0.1的随机数aj,o,s，通过式(25)得到每个批次的批量数，如果aj,o,s=0，则批量为0。在调度编码中，(j,o,m)表示第j个零件的第o道工序在第m台机器上加工，从而根据调度编码确定每一台机器的序列任务。生产时，每道工序的批次按顺序依次加工。为满足约束式(12)，基因(j,o,m)的位置需要始终在基因(j,o′,m)前,其中o′>o。

(24)

(25)

2.1.2 种群初始化

初始解的质量对算法的求解速度和求解质量有很大影响，为了提高初始解的质量并兼顾搜索能力，本文基于FJSP-LS的特点提出3种策略用于初始化种群。对于批次划分编码，采用生成随机数的策略确定随机划分方案；对于调度编码，50%的个体采用随机生成策略，20%的个体采用先到先加工的机器选择策略，30%的个体按照选择最先结束加工机器的原则。对非支配解进行拥挤度距离排序，选择拥挤度距离最大的非支配解作为种群的领飞鸟。

2.2 精英分批策略

证明当工序满足上述两个条件时，该工序的加工受到机器约束，即使采用最小批量加工，也不会提前加工，而后续工序因为也受到相同约束，加工任务的批次划分不会导致后续工序提前加工，所以其分批操作将不会减少最大完工时间。只满足条件①时(如图3a)，工序Oj,o的分批可使后续工序Oj,o+1提前开工；只满足条件②时(如图3b)，工序Oj,o-1与其后续工序Oj,o可以通过分批使Oj,o提前开工，从而达到缩短完工时间的目的；当同时满足条件①和②时，工序Oj,o的分批操作不会影响最终完工时间。不满足上述条件的工序称为精英工序，其分批操作可以影响最终完工时间。

结合上述证明，本文提出一种精英分批策略：在生成邻域结构前，先取消领飞鸟或跟飞鸟不必要的批次划分，从而在不影响最终完成时间的前提下减少批次数目；选取精英工序生成邻域结构，从而通过改变批次划分方案来减少最终完工时间。

2.3 邻域结构设计

邻域结构设计是为了让种群向所期望的方向进化。在MBO算法中，除领飞鸟外，其他所有个体的邻域解集均由其自身产生的邻域解和前面个体未使用的邻域解两部分组成。针对本文编码结构的特殊性，分别对批次划分和调度编码设置相应的邻域结构。

2.3.1 批次划分编码的邻域结构

本文针对精英工序的批次划分编码设计3种操作，对应3种邻域结构：

(1)批量突变 将精英工序对应的批次编码基因突变为不同的随机数，从而改变批量大小，影响最大完工时间。此时允许其突变为0，以减少批次数量。

(2)批次合并 将精英工序对应的批次编码与同操作的其他批次编码求和，将同操作的其他批次编码设置为0，以减少批次数量。

(3)批次置换 将精英工序对应的批次编码与同操作的其他批次编码互换，从而改变批次的加工顺序。

2.3.2 调度编码的邻域结构

在批次划分编码的邻域结构中会导致同工序不同批次之间互换，因为本文不考虑混流和并行的情况，所以调度编码只针对工序生成邻域结构。考虑到柔性车间中调度编码生成邻域结构的操作可能会导致不可行解，本文提出基于关键路径的可行邻域结构。

(1)可行邻域

柔性作业车间析取图中，如果存在弧线循环，则表示该调度方案不可行，因此所生成邻域解的析取图中，弧线不应出现循环。在柔性作业车间可行域研究的基础上[20-21]，针对FJSP-LS，同时考虑安装时间和运输时间，提出以下定理：

定理2当满足条件①和条件②后，工序Oj，o可以移动到工序Ov，v′和Ow，w′之间进行组织生产，该调度方案一定是可行方案。

①max{Hx,x′,Sx,Hv,v′-1,Sv}

②min{Hy,y′,Sy+by,y′,Sy×Ty,y′,m′,Hw,w+1,Sw+bw,w+1,Sw×Tw,w+1,m}>Hu,u′-1,Su;(Vu,u′-1,Su,Vu,u′,Su),(Vw,w,Sw,Vw,w+1,Sw)∈A;(Vw,w,Sw,Vy,y′,1)∈E。

证明如图4所示，当工序Oj，o插入工序Ov，v′和Ow，w′之后，原先相关的虚线弧就会取消(如虚线1)，而生成新的虚线弧，如虚线2和虚线3所示。当不满足条件①时，工序Oj，o的后续工序Oj，o+1可能和Ov，v′的前任工序Ov，v′-1或机器前任务Ou，u′之间存在虚线弧(如虚线弧4和虚线弧5)，即工序Oj，o+1在Ov，v′-1或Ou，u′之前加工，从而使析取图中出现循环(Oj，o，Oj，o+1，Ov，v′-1，Ov，v′，Oj，o)或(Oj，o，Oj，o+1，Ou，u′，Ov，v′，Oj，o)。因此，当满足条件①时，能够保证工序Ov，v′-1和Ou，u′执行后，Oj，o+1才会执行，防止出现虚线弧4和虚线弧5；当满足条件②时，能够保证工序Oj，o-1不会在Ow，w′+1和Oy，y′执行后开始执行，防止出现虚线弧6和虚线弧7。由此可以避免循环的出现。

(2)邻域结构

在满足定理2的基础上，本文基于关键工序并考虑可行邻域，随机选取一道关键工序，采用同机器的一次插入操作，或者选取在其他可行机器上执行一次插入操作，分别计算新解的最大完工时间，从而在批次数不变的基础上获取完工时间最小的解，进而优化调度方案。

2.4 局部搜索和跳跃机制

2.4.1 局部搜索策略

由于每个个体每次生成的邻域解数受算法参数的限制，为进一步地挖掘更好解，本文对一部分跟飞鸟进行局部搜索优化，参考上述可行邻域的思想，对一部分关键工序执行同机器和异机器的插入操作，从而寻找更优调度方案。

2.4.2 跳跃机制

为了避免算法陷入早熟收敛状态，设计一种跳跃机制。如果种群中的个体超过设定的limit代没有得到改善，则在其邻域解中选择拥挤度距离最大的邻域解作为新的个体，从而提高算法搜索的多样性。

2.5 改进候鸟优化算法流程

为了方便描述算法，引入以下符号：Psize为初始鸟群的个体数；k为每个个体产生的自身邻域解数；x为每个个体传给下一个体的邻域解数量；G为巡回次数；limit为跳跃代数；a为采用批次邻域搜索的概率(1-a表示采用调度邻域搜索的概率)；b为局部搜索的个体占跟飞鸟数的百分比。结合上文对算法的论述，IMBO算法流程如图5所示。

3 仿真实验

3.1 测试算例

本文采用随机生成的12组算例，如表3所示，其中LB和UB分别表示取值的下限与上限，D表示任务种类个数，M表示机器个数，同时设定加工时间To,j,m∈U(1,8)、准备时间So,j,m(So,j,m，o′,j′)∈U(10,15)、传输时间Tm,m′∈U(5,10)、可选机器数U(1,5)。算法的运行环境为2.20 GHz PC，12 GB RAM，Windows 7，64位操作系统，编程语言为MATLAB。

表3 测试算例数据

3.2 性能指标与参数设置

为了评价算法获得解集的收敛性和多样性，采用反转世代距离[22]IGD和错误率[23]ER作为多目标进化算法性能的评估标准：

(26)

(27)

式中：N*为真实Pareto前沿点集的规模；di为第i个真实前沿点到真实Pareto前沿的最近欧氏距离；N为最优解集；若最优解集中第i个解在真实Pareto前沿点集上则ei=0，否则ei=1。

算法参数的设置通常对元启发式算法的有效性具有重要作用。影响IMBO算法性能的主要参数包括种群大小Psize、巡回次数G、领飞鸟产生的邻域解的数量k、每个个体传给下一代的邻域解的数量x、跳跃代数limit、最大迭代次数Gmax、生成批次邻域的概率a和局部搜索的百分比b。为了找到较优秀参数的组合，本文采用正交实验法对参数进行优化配置。因为k与x之间存在相互约束，不适合采用正交实验[23]，所以本文参考文献[7,18-19]并结合大量测试，设置k=5，x=1。其他参数的因素水平表如表4所示。

表4 因素水平表

表5 正交实验表

续表5

3.3 分批方式对比

为了对比可变子批和一致子批两种划分策略，对算例5和算例6的测试数据分别采用两种不同的分批策略，独立运行10次，每次运行时间为M×D×10 s，两种策略得到的Pareto前沿如图6所示。

由图中结果发现，当批次数相同时，可变批次与一致子批相比可以更好地发挥分批作用。由于可变子批策略是对各道工序进行批量划分，划分方案灵活多变，可以通过较少的批次数目缩短制造时间，而且可以更好地展现批次划分与制造时间的关系，从而指导决策者做出合理的批次划分和调度方案。

3.4 算法对比

为了验证本文IMBO算法的性能，分别选择改进的遗传算法(Improved Genetic Algorithm, IGA)[24]、模拟退火混合的离散粒子群优化算法(Hybrid Discrete Particle Swarm Optimization integrated with Simulated Annealing algorithm, HDPSO-SA)[25]和改进的差分进化模拟退火算法(Improved Differential Evolution Simulated Annealing Algorithm，IDESAA)[26]3种解决柔性作业车间多目标问题的算法，开展对比试验，以错误率ER和反世代距离IGD作为评价指标，ER和IGD越小，算法综合性能越好。

将4种算法在每组测试数据下独立运行10次，每次运行时间为M×D×10 s，取各指标平均值作为最终测试结果，如表6所示。根据算法对比结果，IMBO算法的评价指标IGD和ER在绝大数算例中优于其他算法，说明相同测试条件下，在解决柔性作业车间的可变批次问题方面，IMBO算法得到的近似Pareto前沿比其他算法更接近真实的Pareto前沿，从而验证了IMBO算法改进机制的合理性与有效性。

表6 算法对比测试结果

4 结束语

本文研究了可变批次划分下的柔性作业车间分批调度问题，以最小化最大完工时间和最小化批次数目为优化目标建立了相应的数学模型和析取图模型。其次，针对该问题的特点并结合析取图模型，提出一种IMBO算法，从可行邻域和精英分批等方面提高了算法的寻优能力。最后，通过算例比较了可变子批和一致子批两种划分方式的不同，证明可变批次的划分方式可以更好地发挥分批策略的作用，并与其他求解分批问题的元启发式算法进行对比，有效验证了本文所提IMBO算法求解复杂分批调度问题的有效性。