求解混合流水车间调度问题的离散布谷鸟算法

罗函明，罗天洪，吴晓东，陈科百

1.重庆交通大学 机电与车辆工程学院，重庆400074

2.重庆文理学院 智能制造工程学院，重庆402160

1 引言

车间调度问题是指在有限的资源条件下，如何合理地安排车间生产任务，以满足或优化一个或多个性能指标。该问题的性能指标种类繁多，如常用的生产效率指标[1]和近年来提出的绿色化指标[2]。混合流水车间是一种常见的流水作业生产车间，具备一般流水车间和并行机车间的特点，生产过程柔性化，更符合生产实际情况。混合流水车间调度问题（Hybrid Flow-shop Scheduling Problem，HFSP），也称为柔性流水车间调度问题（Flexible Flow-shop Scheduling Problem，FFSP），在电子、物流及互联网服务等现代行业都有着十分广泛的应用，可追溯到机械、化工、纺织、制药等传统行业。HFSP是一种NP-hard 组合优化问题[3]，不可能在多项式时间内精确求得最优解，解决该问题的最佳方法是采用元启发式算法。因此，对HFSP 的研究具有重要的实际应用价值和理论研究价值。

与一般流水车间调度问题相比，HFSP 在各道工序中存在并行机，需要同时确定工件排序和机器分配。按并行机类型的不同，HFSP可分为三类[1]：均匀并行机，指工件每道工序在任意一台并行机上的加工时间与其加工速度成反比；相同并行机，指工件每道工序在任意一台并行机上的加工时间相同；不相关并行机，指工件每道工序在任意一台并行机上的加工时间互不相关，有所不同。不相关并行机上的加工时间取决于工件与机器的适配程度，更符合实际生产，同时，加工时间的互不相关性加大了求解难度，因此本文研究的是不相关并行机HFSP。

本文研究目的是针对HFSP的特性来设计一种有效的元启发式算法，以求解该类问题，并提高解的质量和稳定性。

2 混合流水车间调度问题

HFSP 的求解方法有精确计算、启发式规则和元启发式算法[4]。相对于精确计算求解时间过长，启发式规则难以获得全局最优解，元启发式算法运算速度快，所得解质量好，因而运用广泛，如遗传算法（Genetic Algorithm，GA）、模拟退火算法、禁忌搜索算法，新兴的粒子群优化算法（Particle Swarm Optimization，PSO）[5]、蚁群优化算法[6]、蝙蝠算法[7]和混合蛙跳算法[8]等。王凌等[1]针对不相关并行机HFSP 提出了人工蜂群算法，采用基于多操作的邻域搜索和随机搜索，通过实例验证了该算法求解HFSP 的有效性。王圣尧等[9]建立了HFSP 解空间的概率模型，进而提出了一种分布估计算法，对HFSP有着较快的求解速度。崔琪等[10]针对相同并行机HFSP提出一种变邻域改进遗传算法，采用NEH 启发式算法产生初始种群，设计两种交叉算子提高算法搜索效率。Bozorgirad等[11]提出将三种基于禁忌搜索及三种基于模拟退火的局部搜索算法与两种基于遗传算法的种群算法进行实验对比，结果表明基于种群的算法比局部搜索算法在求解HFSP 时得到的解质量更优。Santosa 等[12]针对有限等待区间HFSP，提出了一种多目标离散粒子群优化算法。Azami等[13]针对航空航天复合材料制造系统中的两阶段HFSP，提出一种新的启发式规则生成遗传算法的初始种群，并在算法中设计了一种新的交叉算子。虽然对于HFSP 的求解算法已有大量研究，但是大多算法都沿用了一般流水车间调度的求解方法，即基于工件排列的编码方法以及基于工件先到先加工和最先空闲机器规则的解码方法。这种解码方法易导致算法早熟，因此王芳等[14]设计了一种混合随机概率与规则解码方法（简称随机规则解码），扩大搜索空间，阻止算法早熟，但该方法并没有根据HFSP的特性来设计，还有待改进和提高解的质量。

布谷鸟搜索（Cuckoo Search，CS）算法是由Yang等[15]于2009 年提出的一种新型元启发式算法，有着算法结构简单、控制参数少、寻优能力强和易于结合其他算法进行改进等优点，已被成功应用于多种工程优化领域[16-18]。然而，CS算法应用于求解HFSP的研究较少。Burnwal等[19]基于CS算法求解以最小化延期惩罚成本和最大化机器利用率为目标的HFSP，经仿真验证了CS算法性能优于GA、PSO 算法；Marichelvam 等[20]通过NEH 启发式规则生成HFSP的初始解，提高了CS算法的收敛速度；Han等[21]针对HFSP设计了自适应CS算法，并加强了算法跳出极值的能力。文献调研表明，CS 算法在求解调度类问题时，大多数文献都是基于某种排序映射规则将CS 算法产生的连续解转换为离散解。该方法不能将连续解空间中全局搜索和局部搜索之间的关系有效地转换到离散解空间，削弱了CS 算法优越的寻优能力。针对该方法的缺陷，陈飞跃等[22]为求解带阻塞有差速的HFSP，提出了一种基于交叉策略的离散莱维飞行，但这种交叉策略容易产生不可行调度解，寻优能力还有待加强。

为更好地求解不相关并行机HFSP，基于上述研究，本文所做的研究改进有：（1）设计了一种改进的随机规则解码方法，即基于工件数与并行机数，按概率随机分配机器，提高了解的质量；（2）根据标准布谷鸟算法中莱维飞行和巢寄生行为两种位置更新策略的核心思想，提出了基于位置交叉和个体距离的离散莱维飞行，设计了基于最优插入和最优交换的巢寄生策略；（3）结合以上两点，在标准布谷鸟算法结构的基础上，构建了一种求解HFSP 的离散布谷鸟（Discrete Cuckoo Search，DCS）算法，并通过实例测试和算法比较，验证了该算法在求解质量和稳定性方面的优越性。

3 问题描述及模型构建

不相关并行机HFSP 一般可描述为：n 个工件都需要按照相同的h 道工序顺序进行加工，每道工序有mj台并行机(mj≥1;j=1,2,…,h)，每个工件的任意一道工序均可在该工序的任意一台并行机上加工，且每道工序只能加工一次，已知各工件的各工序在各并行机上的加工时间，加工时间有所不同，要求确定每道工序的工件加工排序和对应的机器分配情况，使得最大完工时间最小。

因HFSP的数学模型已有丰富而完善的研究，且本文研究的是该问题的一种新的求解方法，本节参考王芳等[14]提出的0-1混合整数规划模型，建立不相关并行机HFSP数学模型，符号定义如下：

N 为工件集合，N={1 ,2,…,n} ；

H 为工序集合，H={1 ,2,…,h} ；

M 为机器集合，M={1 ,2,…,m} ；

Mj为第j 道工序的可用机器集合：

mj为第j 道工序的可用机器数量；

i ∈N,k ∈M,t ∈N ；

Pi,j,k为工件i 的第j 道工序在机器k 上的加工时间；

Kk,t为机器k 第t 次开始加工的时刻；

Jk,t为机器k 第t 次结束加工的时刻；

Fi,j为工件i 的第j 道工序开始加工时间；

Ci,j为工件i 的第j 道工序结束加工时间；

U 为充分大的正数。

定义如下机器分配和工件排序两个0-1决策变量：

基于以上两决策变量构建不相关并行机HFSP数学模型如下：

目标函数（1）表示工件的最大完工时间最小化；约束（2）确保任一工件的任一道工序只能在该道工序中的某一台机器上加工一次；约束（3）确定工件在某台机器上加工顺序；约束（4）确保一个工件只能在一台机器上加工一次；约束（5）确保机器只能按顺序加工工件；约束（6）确保机器加工任一工件的开始时刻等于该工件开始加工时刻；约束（7）和（8）确保任一工件结束加工时刻等于开始加工时刻与加工时间之和；约束（9）确保机器前一次加工结束时刻不大于后一次的加工开始时刻；约束（10）确保工件前一道工序加工结束时刻不大于后一道工序的开始加工时刻。

4 求解HFSP的DCS算法

4.1 概述

标准CS算法是一种求解连续型优化问题的元启发式算法，其核心思想是基于莱维飞行行为和巢寄生行为的两种位置更新策略。莱维飞行行为是模仿自然界一些鸟类的飞行行为，可描述为一个运动体运动方向随机，运动步长以小步移动为主，并偶尔伴有大步位移；巢寄生行为是指某些种类的布谷鸟有着具有侵略性的繁殖策略，它们趁其他鸟类（宿主鸟）外出时，偷偷在宿主鸟巢中产蛋，让其代为孵化和育雏，而宿主鸟一旦发现了外来鸟蛋，会直接扔掉或者新建一个鸟巢。

因HFSP属于组合优化问题，标准CS算法的位置更新策略中具体公式已不再适用，需要重新根据HFSP 的特性设计具体位置更新策略，以保留标准CS 算法优势。因此，本文基于标准CS算法的核心思想，提出求解HFSP的DCS算法。

4.2 解码方法的改进

在进行详细的算法设计之前，需进行编码和解码规则的设计。因为直接利用HFSP 的数学模型求解，属于精确计算，而HFSP是一种NP难题，在合理的时间范围内精确计算只能求解很小规模且简单的问题。因此，在求解HFSP 这类调度问题时，大量文献都是根据问题描述及模型约束等，设计相应的编码和解码规则。这种方式既方便算法的进化操作，也方便快速获得目标函数值以及详细的调度方案。

本节在已有研究的基础上，在编码方面直接采用基于排列的编码方法，在解码方面基于王芳等[14]提出的一种随机规则解码方法，根据HFSP的特性，提出改进的随机规则解码方法，使得解码方法更加合理有效，能进一步提高解的质量。

基于排列的编码方法，其编码序列为：

其中，n 为待加工工件数，xi∈{1,2,…,n} ，工件号xi在编码序列中的位置代表工件第一道工序的加工顺序。

解码可分为工件排序和机器分配两部分。原始解码方法是按照工件先到先加工规则和最先机器空闲规则，确定工件排序时，第一道工序由编码序列确定工件先后加工顺序，后续工序的工件排序采用先到先加工规则，按照工件前一工序的完成时间排列顺序，先完成的先加工，若有工件在前一工序的完成时间相同，则随机确定这些工件的加工顺序；分配机器时，将工件分配到加工当前工件所需的完工时间最早的机器上。随机规则解码方法是于2017 年提出的，工件排序按先到先加工规则确定，而在分配机器时，当生成的随机概率u 大于给定的机器选择概率Pm 时，则随机分配机器，反之，按完工时间来分配机器。随机概率u 服从[0，1]均匀分布，机器选择概率Pm 选取王芳等[14]确定的0.85 概率值。由于随机概率的存在，同一编码序列对应的目标函数值很有可能不同，因此为获得更优解，设定最大循环解码次数C，当循环过程中出现比上一代更优的目标函数值时，则退出循环，并记为该序列的目标函数值。

表1为一个6工件、2工序的不相关并行机HFSP的加工时间表，编码序列[2,4,3,6,1,5] 经上述两种解码方法所得的甘特图如图1、图2 所示。甘特图中方框内数字代表工件号，工件号自下至上出现的顺序代表工序。例如，图1 中工件2 的第1 道工序在机器M1 上加工，开工时刻为0，完工时刻为3，第2 道工序在机器M6上加工，开工时刻为3，完工时刻为7。对比图1、图2可知，在第2道工序给4号工件分配机器时，满足u ＞Pm，于是将4号工件随机分配给已加工了3号工件的5号机器。虽然最后两者解码得到的最大完工时间都为9，但是后者重复地将工件分配给同一台机器，使6号机器仅在短时间内加工了一个工件，同时加大了5 号机器负荷，还有可能增大最后完工时间。

表1 加工时间表

图1 原始规则解码

图2 随机规则解码

因此，本文根据HFSP 需要同时确定工件和机器的特性，基于工件数和并行机数，对随机规则解码方法进行改进，提出改进随机规则解码方法，以提高解的质量。具体实施方法如下：工序j 中有mj台并行机，加工任意一道工序时，每mj个工件进行一次判断，当u ＞Pm时，任选其中一个工件对其随机分配机器，剩余工件则以先到先加工规则确定的排序并按完工时间来分配机器，反之，这mj个工件都按完工时间来分配机器，若最后不足mj个工件但多于一个，依然按上述规则分配机器，若仅剩一个工件，则按最先机器空闲规则分配机器。对上述编码序列用改进解码方法求得的甘特图如图3所示，获得最大完工时间为8，提高了解的质量。

图3 改进规则解码

4.3 离散莱维飞行的改进

在标准CS 算法中，莱维飞行是一种连续性的位置更新，而HFSP是一种典型的组合优化问题，因而需要设计适用于HFSP的离散莱维飞行。

一般的离散莱维飞行是基于某种排列映射规则，例如最小位置（Smallest Position Value，SPV）规则[23]和最大顺序值（Largest Order Value，LOV）规则[24]。SPV 规则指将实数向量中的各分量进行升序排列得到新向量，新向量中各分量所对应原来向量中的位置序列即为整数编码序列；LOV规则与SPV规则相反，是指对各分量进行降序排列。这种方法简单易于实现，既能保证调度解的可行性，又无须修改CS算法的进化操作，因而得到了广泛的运用。但是，这种方法不能有效地将连续空间中局部搜索与全局搜索之间的关系转换到离散空间，削弱了算法性能，容易陷入局部极值，难以搜索到最优解。因此，本文提出一种基于位置交叉和个体距离的离散莱维飞行机制，种群中每个鸟巢与最优鸟巢之间的个体距离视为概率，以这个概率进行基于位置的交叉操作。

基于位置的交叉是遗传算法中的一种交叉策略，使用这种交叉策略可以避免在交叉操作过程中产生不可行解；个体距离是刘长平等[25]在使用离散萤火虫算法时提出的，表示两个体在离散空间中距离远近程度，本文将其引入作为离散莱维飞行中的交叉概率。由于编码序列中xi仅代表工件号，工件号之差并不能代表它们在离散空间中的距离远近，因此本文对其稍做改进，使其更符合编码序列之间的远近程度，改进后个体距离求解过程如下：

首先，编码序列的个体零点位置定义为：

然后，编码序列的个体位置定义为：将编码序列X的工件号按从小到大排列，并记录每个工件号对应所在位置，即为个体位置S。

最后，编码序列之间的个体距离定义为：

式中，si,k、sj,k为个体i、j 第k 维的位置数；N 为分子项取值上限，按下式计算：

由定义可知di,j∈[0 ,1] ，反映了鸟巢之间的远近程度，值越大，则距离越远。

改进的离散莱维飞行具体实施步骤如下：

（1）计算当前鸟巢与最优鸟巢的个体位置及两者间的个体距离，并将后者定义为交叉概率。

（2）生成1×n 的随机概率矩阵，将概率矩阵中每个位置的概率与交叉概率相比较，若大于交叉概率，则当前鸟巢在该位置上对应的工件号保留，反之，删除对应该位置的工件号。

（3）将最优鸟巢的编码序列上与当前鸟巢的编码序列保留的工件号相同的工件号删除。

（4）将最优鸟巢剩余的工件号依次填入当前鸟巢被删除的工件号的位置。

例如，当前鸟巢编码序列为[2 ,1,5,3,4,6] ，最优鸟巢编码序列为[3 ,5,2,4,6,1] 。首先执行步骤（1），得到两个鸟巢的个体位置分别为[2 ,1,4,5,3,6] 和[6,3,1,4,2,5] ，它们之间的个体距离为2/3，即交叉概率为2/3；然后执行步骤（2），生成的随机概率矩阵为[0.81,0.91,0.13,0.74,0.63,0.09] ，与交叉概率相比较，则当前鸟巢编码序列变为[2 ,1,x,3,x,x] ；接着执行步骤（3），删除最优鸟巢编码序列上与之保留的相同的工件号，则最优鸟巢编码序列变为[ x,5,x,4,6,x] 。最后执行步骤（4），将其依次填入当前鸟巢编码序列中，即可得到新鸟巢的编码序列[2 ,1,5,3,4,6] 。

4.4 巢寄生策略的设计

在标准CS 算法中，巢寄生策略的具体位置更新操作采用随机游动方式，是一种连续的位置更新，并不适合求解HFSP这类组合优化问题。本文根据HFSP的编码形式特点，设计基于最优交换和最优插入的巢寄生策略。这两种操作叙述如下：

（1）最优插入操作：从编码序列X 中随机删除一个工件号，得到n-1 个工件的序列X′，可知该序列有n个可插入位置，从左到右依次插入后计算新序列的目标函数值，当新序列的目标函数值优于原序列的目标函数值时，则退出最优插入操作，并更新编码序列，反之，则继续插入操作，直到达到可插入次数为止。

（2）最优交换操作：在工件序列X 中随机选取一个工件号，并与序列X 中其他位置上的工件一一交换，可知有n-1 次交换操作，从左到右依次交换后计算新序列的目标函数值，新序列的目标函数值优于原序列的目标函数值时，则退出最优交换操作，并更新编码序列，反之，则继续交换操作，直到达到可交换次数为止。

基于最优交换和最优插入的巢寄生策略可叙述为：对鸟巢i 生成一个服从均匀分布的随机数r ∈[0,1] ，并与给定的被发现概率Pa 相比，如果r ＞Pa，则执行位置更新操作，其中最优插入和最优交换操作各有0.5 的概率执行，产生新的鸟巢Xnew；若新鸟巢Xnew的适应度优于鸟巢

4.5 DCS算法流程及其复杂度

根据上述的求解HFSP 的算法设计思路，算法中各操作时间复杂度如表2 所示，算法总的时间复杂度为O(Gmax×PsizeChn logn)，log 的底数为大于1 的正整数，其中适应度计算和巢寄生策略都考虑最差情况。

表2 算法各操作复杂度

DCS算法流程伪代码如下所示：

1. 初始化参数：加工机器矩阵J 、加工时间矩阵T 、鸟巢种群数量Psize、被发现概率Pa、机器选择概率Pm、解码最大循环次数C、最大迭代次数Gmax；

2. 随机初始化鸟巢，计算并记录对应适应度值，记录当前全局最优鸟巢Xm、适应度值Fmin及具体最优调度方案；

3. repeat 4. 采用4.3节提出的离散莱维飞行产生新的鸟巢；

5. 计算新鸟巢的适应度，若有更优的鸟巢则鸟蛋被孵化，取代较差的鸟巢；

6. 采用4.4 节设计的巢寄生策略进行局部搜索，并记录当前最优鸟巢Xn、适应度值Fnew及其最优调度方案；

7.if Fnew＜Fmin

8. Xm=Xn；

9. Fmin=Fnew；

10. 替换最优调度方案；

11. end if

12. until满足算法终止条件；//达到最大迭代次数Gmax

13. return最优调度方案

5 仿真测试及分析

5.1 算法参数确定

求解HFSP 的DCS 算法主要相关参数有种群大小Psize、被发现概率Pa，解码方法中相关参数有机器选择概率Pm 和解码最大循环次数C。种群大小Psize对算法影响较大，若种群数量过小，则初始化个体在解空间分布密度小，对解空间的搜索不够彻底，并且影响种群多样性，也易导致算法陷入局部极值；若种群数量过大，则会大大增加算法运行时间，可能会出现重复搜索某区域的现象。被发现概率Pa 主要影响算法运行时间和收敛速度，较小时，算法运行时间较长，收敛速度较快，而过小可能导致算法陷入局部极值，对于大多数优化问题，通常取Pa=0.25，就能满足需求。机器选择概率Pm 直接影响算法搜索空间大小，进而影响算法收敛速度，Pm 较小，解码过程偏向于随机解码，此时搜索空间较大，Pm 较大，解码过程偏向于规则解码，此时搜索空间较小。解码最大循环次数C 对算法性能影响较大，C过小，难以对编码序列进行有效的解码，C 过大，则会过多增加算法运行时间。根据上述分析并经过大量的测试，为兼顾算法运行时间、收敛速度和优化质量，本文中，DCS算法参数设置如表3所示。

表3 算法参数设置

5.2 改进解码方法有效性验证

本节分别采用原始规则、随机规则和改进随机规则解码的DCS 算法（分别记为DCS_P、DCS_R、DCS_I）对5个随机生成的算例进行求解，以验证改进随机规则的有效性。采用10 工件、5 工序，并行机数[3,3,2,3,3] ，加工时间[30,60] 的5 个随机整数算例，为更好地符合实际生产，并行机处理同一个工件的同一道工序的最大时间差不得超过5。每种算法均独立运行10次，以运行结果的最优下界Cmax、平均值AVG、标准差STD作为评价指标，结果如表4所示。

表4 三种解码方法的运行结果对比

从表4可以看出，对于算例1，DCS_R和DCS_I算法求解得到的Cmax分别为356和355，小于DCS_P算法求解得到的358，再对比算例2～算例5，发现DCS_R 和DCS_I 算法所得到的Cmax数值都小于DCS_P 算法，验证了混合概率与规则的解码方法更可能得到更优解。然后，对算例1，DCS_I 算法求解10 次得到的平均值AVG 为355.9，小于DCS_R 算法得到的356.1，进一步看出，除算例3两种算法10次求解的平均值AVG相同外，对算例2、算例4、算例5，DCS_I算法求解所得AVG都小于DCS_R 算法，说明改进方法提高了算法解的质量。最后，对于算例1～算例5，采用三种解码方法求得的解的标准差STD 都小于1，说明DCS 算法的解的稳定性好。因此，对比结果验证了改进随机规则的有效性。

图4为算例1采用不同解码方法的收敛曲线图。可以看出，在算法前期时，DCS_P算法的收敛速度最快，但导致了算法早熟，从而陷入了局部极值；DCS_I 算法的收敛速度快于DCS_R 算法，说明改进方法能对解空间进行更为有效的搜索，从而加快算法收敛速度，进一步验证了改进随机规则的有效性。

图4 不同解码方法求解算例1的收敛曲线

5.3 实例验证及算法比较

本文利用王圣尧等[9]采用的两个不相关并行机HFSP实例进行测试，并与其他文献提出的求解算法做对比，其中SACS[21]算法为一种求解HFSP 的自适应布谷鸟算法，GA算法为常用算法，FOA[26]、EDA[9]、EDA_H[14]、IPSO[27]均为近年来求解以最小化完工时间为目标的不相关并行机HFSP 的典型代表算法。算法在Intel Core i5-7300HQ 2.50 GHz CPU、8 GB RAM、Windows 10操作系统和Matlab编程环境下编译测试。

DCS_I 算法求解实例中两种位置更新步骤的详细代码如下。

离散莱维飞行位置更新步骤的代码：

巢寄生策略位置更新步骤的代码：

表5、表6 为各种算法求解两个实例独立运行10 次的结果。

从表5、表6的运行结果可以看出，DCS_I算法对第一个实例的10次运行结果中有6次求出了最优解23，对第二个实例10 次运行结果都求出了最优解297。对比其他算法结果可以看出DCS_I 算法在解的质量方面优于SACS、GA、FOA、EDA等算法，说明了本文所提算法求解该类问题的优越性。DCS_I 算法求解结果对应的调度甘特图如图5、图6所示。

表5 实例1的运行结果

表6 实例2的运行结果

图5 实例1调度甘特图

图6 实例2调度甘特图

6 结束语

本文在不相关并行机混合流水车间调度问题的现有研究基础上，提出了一种求解HFSP 的离散布谷鸟算法。本文主要工作如下：

（1）提出了改进随机规则解码方法，通过算例对比分析，验证了改进解码方法的有效性，能合理地加快算法收敛速度，同时增加搜索到更优解的可能性，提高解的质量。

（2）根据标准布谷鸟算法的两种位置更新策略思想，提出了基于位置交叉和个体距离的离散莱维飞行，设计了基于最优插入和最优交换操作的巢寄生策略。

（3）通过实例测试和算法比较，验证了本文算法在求解质量和稳定性方面优于自适应布谷鸟算法、遗传算法和分布估计算法等。

通过研究，发现本文算法在求解大规模问题时，用时较长，因此如何减少算法求解时间而不牺牲算法原有性能是一个未来研究方向，或者结合工程实际需要，拓展本文算法的应用领域。