求解柔性车间调度问题的双层编码离散布谷鸟算法∗

罗浩嘉潘大志，2

（1.西华师范大学数学与信息学院 南充637009）（2.西华师范大学计算方法与应用研究所 南充637009）

1 引言

车间调度是现代企业制造的基础，优化调度方案是先进企业亟待解决的关键问题，作业车间调度问题是典型的NP-hard问题，也是组合优化问题领域的研究热点问题，有很强的工程应用背景。Johnson［1］于1954年首次讨论了作业车间调度问题（Job-shop Scheduling Problem，JSP），而随着制造业领域的进步和发展，柔性作业车间调度问题（Flexi⁃ble Job-shop Scheduling Problem，FJSP）应运而生，它是对传统调度问题的进一步拓展和延伸。FJSP的求解主要包括精确算法［2］、启发式算法［3］和智能优化算法。近年来，针对求解FJSP的智能优化算法越来越多，如遗传算法［4］、蚁群算法［5］、粒子群算法［6］、禁忌搜索算法［7］、模拟退火算法［8］等。牛琳等［9］结合柔性作业车间调度的特点，采用模拟退火算法融合遗传算法对调度领域进行了研究。王芳［10］等设计了一种混合随机概率与规则解码方法，扩大了搜索空间，阻止算法早熟。Xiong等［11］采用了新的生成机制来产生初始种群，从而加快了算法的收敛速度，从而减少了算法的运行时间。

布谷鸟搜索算法（Cuckoo Search，CS）是由Yang等［12］提出的一种新型元启发式算法，由于其结构简单容易实现、控制参数少、能有效平衡全局最优和局部最优并且等优点，已被成功应用于多个领域。Ouaar等［13］基于标准布谷鸟算法的思想，将布谷鸟算法离散化，用于求解车间调度问题。Han等［14］针对混合流水车间调度问题设计了自适应布谷鸟算法，并加强了算法跳出极值的能力。罗函明等［15］采用基于改进解码方法的离散布谷鸟算法求解混合流水车间调度问题，提高了解的质量。由于集成编码的个体只能简单表示问题的解，在后续更新操作上会过于复杂和繁琐，本文采用多层编码把个体编码分为两层，每一层所代表的含义不同，复杂问题的解也可以用一个完整的个体编码表示，很大程度上提升了算法的可读性。

2 柔性作业车间调度问题

柔性车间调度可描述为有n个工件在m台机器上加工，每个工件有一道或者多道加工工序，每道工序可以有多种可选择的加工机器，其中每道工序只能由一个机器加工一次且必须等上一道工序加工完成才能进行下一次加工。调度的目标是为每道工序分配最合适的机器以及确定每台机器上每道工序的加工次序，以满足特定的优化目标。已知各工件的各工序在机器上的加工时间，要求确定工件加工顺序和对应的机器分配情况，使得最大完工时间最小［16］。

符号定义：

n表示工件数量；

m表示工序数量；

Mj表示第j道工序的可使用机器集合；

Pijk表示工件i的工序j在机器k上的加工时间；

Sijk表示工件i的工序j在机器k上的开始加工时刻；

Cijk表示工件i的工序j在机器k上的结束加工时刻；

Njk表示工序j在机器k上加工的工件数量；

Pjk表示在工序j的机器k上进行加工的第R个工件。

本文优化的目标是最小化最大完工时间，其数学模型如下：

其中，i=1，2，…，n;j=1，2，…，m;k∈Mj，式（2）表示每个工件在每道工序只能被一台机器加工；式（3）表示对每道工序，分配给工序内所有机器的工件数之和为n；式（4）表示对同一工件的加工，下一道工序必须在上一道工序结束后才能开始；式（5）表示对任何工件，其完成时间取决于其在某个机器上的加工时间和开始时间；式（6）表示每个机器在同一时间只能加工一个工序；式（7）为变量取值范围。

3 多层编码的离散布谷鸟算法

3.1 标准布谷鸟算法

2009年剑桥大学的Xin-SheYan和S.Deb通过模拟布谷鸟寄生育雏行为提出了布谷鸟算法（Cuckoo Search，CS），布谷鸟在繁殖期间并不自己筑巢，而是通过寄生的方式将自己的幼卵产在其他鸟类的鸟巢中让其他鸟类孵化幼卵，为了提高繁殖率，布谷鸟在选择宿主鸟窝时会选择和自己卵形相似、卵的颜色、孵化周期一样的鸟窝。即便如此仍然存在着被宿主发现寄生卵的可能性，幼卵一旦被宿主发现，宿主便会抛弃鸟巢重新筑巢。本文根据基本布谷鸟算法的核心思想，提出了改进的离散布谷鸟算法。

3.2 个体编码

本文采用双层整数编码，第一层是基于工序的整数编码，第二层是基于机器的整数编码。在第一层编码中，每个工件用一个整数表示，从左到右整数出现的顺序就代表工件加工的先后顺序；在第二层编码中，整数代表每道工序对应选择的机器序号。即个体的前半部分表示所有工件的加工顺序，后半部分表示每道工序加工时选择的机器序号。每一个完整的编码序列就代表一个鸟巢信息，即待优化问题的一个可行解。具体编码方式如图1。

如图1所示，该个体有四个工件，每个工件有两道加工工序，可以在两种机器上进行加工。其中，J21表示个体中工件2的第1道工序，T212表示工件2第1道工序在机器2上生产；J41表示工件4的第1道工序，T411表示工件4第1道工序在机器1上生产，以此类推。

图1 离散布谷鸟算法多层编码

3.3 离散levy飞行更新策略

在标准的CS算法中，levy飞行更新鸟巢位置是一种连续性的位置更新，因此本文需要设计一种适用于调度问题的离散levy飞行。由于levy飞行在搜索过程中伴随着频繁的短距离搜索以及少数长距离全局探索，短距离搜索用于在当前最优解周围仔细搜寻提高局部搜索能力，而少数长距离跳跃式探索有利于扩大搜索范围，使之更容易跳出局部最优。因此，本文通过2-opt操作代替levy飞行中的短距离搜索，用double-bridge（双桥）操作代替levy飞行中长距离跳跃式搜索，通过2-opt与dou⁃ble-bridge结合代替levy飞行进行鸟巢位置更新操作。

1）2-opt move：又称为“反序算子”，随机选择两个不相邻的点ci和cj，断开ci和ci+1以及cj和cj-1之间的弧，并引入两个新的弧，得到的新序列。如图2，图（a）为原始序列，图（b）为2-opt操作后产生的新序列。若得到的新序列（b）优于原始序列（a），则更新序列；否则，继续循环，直到得到更优的序列或者达到最大循环次数为止。

图2 2-opt move

2）double-bridge move：随机选择四个不相邻的点c0、ci、cj和ck，断开c0和c1、ci和ci+1、cj和cj+1以及ck和ck+1之间的弧，并引入四个新的弧，得到新的序列。如图3，图（a）为原始序列，图（b）为double-bridge操作后产生的新序列。若得到的新序列（b）优于原始序列（a），则更新序列；否则，保持原始序列。

图3 double-bridge move

3.4 随机游走策略

本文采用基于择优交换和择优插入的巢寄生方式将标准CS算法中的随机游走策略离散化。首先生成一个服从均匀分布的随机数r，将其与被发现概率Pa进行比较，如果r>Pa则通过择优交换或者择优插入操作更新位置信息，否则，不对其进行位置更新操作。择优插入操作和择优交换操作的概率均为0.5。

1）择优插入操作：随机从工件加工序列中提取出一个工件号，将取出的工件号按照从左到右的顺序，依次插入到剩下的序列中组成新序列，并将新序列与原序列进行比较，当新序列优于原序列时，退出择优插入操作，否则，继续进行择优插入操作，直到无法进行插入操作为止，如图4所示。

图4 择优插入操作

2）择优交换操作：随机从工件加工序列中选择一个工件号，将所选工件号按照从左到右的顺序，依次与剩下序列中的工件进行交换组成新序列，并将交换后的新序列与原序列进行比较，当新序列优于原序列时，退出择优交换操作，否则，继续交换操作，直到无法进行交换操作为止，如图5所示。

图5 择优交换操作

3.5 算法描述

综合以上步骤和结论，算法主要的流程如下。

Step 1初始化种群数量NIND，迭代次数MAX⁃GEN，鸟巢被发现概率Pa；

Step 2随机产生初始序列，并计算每个序列对应的调度时间，找出当前最短调度时间并记为初始全局最短调度时间；

Step 3用2-opt操作与double-bridge操作结合使用代替levy飞行操作更新鸟巢位置。计算更新之后的调度时间，若比当前最短调度时间小，则更新全局最短调度时间；

Step 4生成一个服从均匀分布的随机数r，将其与被发现概率Pa进行比较，若r>Pa则采用择优交换或者择优插入操作代替全局随机游走策略对鸟巢位置进行更新。计算更新之后的调度时间，若比当前最短调度时间小，则更新全局最短调度时间；

Step 5检查算法是否达到最大迭代次数，若达到最大迭代次数，停止算法迭代，输出全局最短调度时间，若未达到则重复Step3、Step4。

4 仿真测试及分析

4.1 算例与参数设置

为了验证算法的可行性，本文用Matlab对柔性车间调度进行实例分析，选取同一个算例将离散布谷鸟算法（DCS）与改进遗传算法（GA）和改进混合粒子群算法（PSO）进行对比。6个工件在10台机器上加工，每个工件都要经过6道工序，每个工件的每个工序可选择机器和对应机器所需加工时间已确定，如表1所示。

表1 加工机器选择和对应加工时间

4.2 算法结果分析和对比

本文采用Matlab R2018a编程，运行环境为In⁃tel（R）Xeon（R）CPU E5-@3.30GHz，RAM 8GB。为了方便DCS、GA和PSO算法对比，三种算法设置相同的主要参数，个体数目为40，最大迭代次数为50。同时三个算法的其他参数都调到最优。为了避免结果的随机性，每组算法独立运行30次，分别记录其最优值Cbest、平均值Cavr、标准差Cstd和方差Cvar测评算法的性能，最后运行结果如表2所示。经过30次独立运算和比较，DCS算法最稳定，不容易陷入局部最优；而PSO算法和GA算法，虽然也能得到最优，但是产生的解并不稳定，随机性比较高。

表2 算法对比实验结果

图6 为迭代曲线图，如图7为DCS算法求解得出的工件加工甘特图。图6直观地对比了迭代过程中DCS、GA和PSO算法关于柔性车间问题的最短调度时间，曲线的起点为各个算法随机产生的初始种群中的最优值，由于初始种群是随机产生的，导致各个算法的初始最优解相差较大，随着迭代次数的增加，种群个体逐渐趋向于最优。可以看出，DCS算法不仅得到的解更优，收敛速度也更快并且不容易陷入局部最优。

图6 进化曲线图

图7 工件加工甘特图

5 结语

本文研究了以最小化最大完工时间为目标的柔性车间调度问题，建立了基于各个工序最早完工的调度模型，提出了离散布谷鸟算法求解该问题，并且采用双层整数编码方法对个体进行编码，将后续步骤简单化。最后通过对比试验，验证了本文采用的离散布谷鸟算法的可行性和稳定性。在此基础上，以完工时间、流水时间和延迟时间等多目标的改进FJSP求解将是进一步的研究目标。