基于差分量子粒子群优化算法的作业车间调度

黄宇， 顾智勇， 张中印， 王东风

(华北电力大学自动化系， 保定 071003)

以提高工作效率为目标的工业流水线问题研究一直是工业界普遍关注的领域，而群体智能算法具有很强的优化搜索能力，是求解流水线问题的有效手段，受到人们的广泛研究[1-2]。然而作业车间调度问题(job-shop scheduling problem，JSP)的求解复杂程度高，并随着调度规模的增加影响求解的精度和速度，导致流水线上的工作效率降低，因此提出有效、合理的智能优化算法并应用于求解JSP具有重要的理论与现实意义[3-4]。

文献[5]提出一种新的混合整数规划模型用于求解JSP，虽然这种模型的调度方法表达清晰、易于理解，但是存在搜索效率低、难以求解较大规模JSP的缺点。文献[6]研究了基于异构并行遗传算法并应用于JSP，但是其不足之处在于对种群初始化依赖程度较大。文献[7]设计出一种有效种群初始化于方法用于提高遗传算法求解JSP的性能，但是其不足之处在于局部搜索能力较弱，并且容易出现早熟收敛。文献[8]介绍了混合遗传算法和带有变量邻域搜索的帝国主义竞争算法来求解JSP，提高了求解速度，但仍存在局部收敛问题。文献[9]采用染色体思想进行局部搜索并结合遗传算法进行求解JSP，此方法将最优随机个体添加到初始种群中，虽然这种方法可以获得高质量的初始个体，但它增加了计算时间并降低了种群多样性。文献[10]提出了一种可变邻域搜索方法，然而，大多数邻域结构都是随机生成的，这使得搜索变得盲目。因此，随着JSP问题规模的增加，搜索效率降低。文献[11]研究了基于混合蚁群算法的柔性JSP，并将遗传算子与寻优蚁群有机结合，提高了获得JSP最优解的概率。文献[12-13]分别将离散粒子群算法、遗传算法应用于求解JSP并得到了不错的搜索效果。文献[14]利用自适应学习策略改进了细菌觅食算法，采用在多邻域结构下按贡献选择搜索方式，改善了原始算法在求解JSP出现的早熟问题。

现有求解JSP算法大部分是单一群体智能算法，存在着收敛时间慢、求解精度差等不足之处，导致难以有效地解决工业流水线上的调度问题。为此，现提出一种基于差分特性的量子粒子群优化算法。量子粒子群算法运用量子叠加原理克服了粒子群算法的粒子聚集性低且粒子搜索范围有限的问题，具有更好的全局收敛性，但在搜索后期存在粒子早熟问题。而差分进化算法可通过变异交叉策略提高种群粒子多样性，提升局部搜索性能，但在收敛后期速度变慢。所提算法结合二者的优势，应用差分进化思想改善量子粒子群算法迭代过程粒子多样性不足问题，具有很好的全局收敛性和优化性能。最后通过FT和LA两类JSP经典算例对所提方法的求解效果进行验证。

1 JSP数学模型

每个工件包含多道加工工序，每道工序所需时间固定且由对应的机器完成。每个制造的工件都是在预定的机器上按照预定的操作顺序生产的。要求各工件选择满足工艺约束条件的机器，确定最佳操作顺序以达到加工性能最优[15]。

设机器j加工工件k的时间为tki,j，机器j加工工件k的第i个操作的完成时间为T(ki,j)，q=(k1,k2,…,kn)是所有工件的排序，Q为所有排序集合。机器j完成操作ki的两个条件：一是机器j完成操作ki-1，二是上一个机器j-1的操作已经完成。数学描述为

T(ki,j)=max{T(ki-1,j),T(ki,j-1)}+tki,j，

i=1,2,…,n，j=2,3,…，m

(1)

则完成所有工件操作的最大加工时间为

Tmax(q)=T(kn,m)

(2)

寻求最大完成时间的最小值的调度方案为

minf=min[Tmax(q)] ∀q∈Q

(3)

式中：n为总工件数；m为机器总数。

JSP调度解的编码具有多样且复杂的特点，其数量也会随着调度规模剧烈增长，形成一个巨大的解空间，其空间解的极小值分布并无特殊规律，且调度指标计算耗时较长。为此，提出一种基于差分进化的量子粒子群优化算法并应用于求解JSP中。

2 差分量子粒子群算法

2.1 量子粒子群优化算法

量子粒子群优化(quantum particle swarm optimization, QPSO)算法引入了量子模型的概念，是粒子群算法(particle swarm optimization,PSO)的发展。QPSO中粒子的状态由概率函数而不是速度、位置来描述，该理论认为粒子在由可行解构成的势场中运动，其运动轨迹符合特定的概率分布，可通过概率密度函数学习粒子出现在位置x的概率。QPSO的进化方程为

(4)

P=αPbest(i)+(1-α)Gbest

(5)

(6)

式中：F[x(t+1)]为粒子的分布函数；L(t)为分布的标准偏差；σ(t)为势场中心；P为局部中心点；Pbest(i)为第i个粒子当前达到的最佳值；Gbest为当前所有粒子的最佳值；β为收缩扩张系数，一般情况下β的值从1至0.5线性递减；u和a为均匀分布在0～1的随机数；mbest为平均最佳值，定义为总体所有最佳位置的平均值，其计算公式为

(7)

式(7)中：M为粒子维度数。

QPSO运用量子叠加基本原理及其量子分布特征,解决了PSO算法中粒子聚集特性较低且粒子搜索范围有限的问题。不过,在量子粒子集群计算过程中收敛后期仍会存在大量粒子早熟的现象,从而导致整个种群的复杂性大大下降,并因此面临着局部问题优化求解。难以有效地解决解空间巨大，且具有组合优化特性的车间作业调度问题。为此，将差分进化引入量子粒子群，采取面向JSP的编码和操作算子，将其运用于离散空间；利用差分进化(differential evolution，DE)中的变异操作方式，提高了群体突变的可能性，从而避免个体陷入局部最优；并且使用DE中的交叉方法提升对个体极值信息的使用水平。从而可以实现较短时间求取JSP问题的最优解，提高算法的搜索精度和计算速度。

2.2 差分进化算法

差分进化是一种高效的并行搜索算法，交叉、变异和选择是DE算法的3个核心操作。

(1)变异操作目的是在种群迭代过程中构建变异个体Vi。对于每个目标个体，选择3个随机且不同的个体对其进行差分求和操作即产生变异个体。变异操作的计算公式为

Vi(t+1)=Xr1(t)+F[Xr2(t)-Xr3(t)]

(8)

式(8)中：r1、r2、r3分别为从区间[1，MP]中选取的不同随机整数，MP为最大种群数；Vi(t+1)为当前迭代过程的变异个体；Xi(t)为选取的基向量与差分向量；F为缩放因子，一般情况下F∈[0.5,1]。

(2)在变异操作后引入交叉操作以保持种群多样性。该过程根据交叉概率从变异个体或目标个体中选择元素来构建测试种群，交叉操作方程为

Ui,j(t+1)=

(9)

式(9)中：CR为交叉概率，一般取CR∈[0.8,1]；jrand为随机数。

(3)选择操作中，根据适应度函数选取当前种群和测试种群中表现更好的个体，进而生成新的种群。选择操作表达式为

Xi(t+1)=

(10)

针对QPSO存在的粒子更新方式造成的搜索精度不足问题[16-18]，将DE算法引入QPSO，采用差分量子粒子群算法(differential evolution quantum particle swarm optimization， DEQPSO)以解决JSP。

2.3 DEQPSO粒子搜索策略

DEQPSO算法粒子更新策略是QPSO和DE两种算法粒子更新策略的结合，QPSO引入量子机制克服了PSO算法在全局收敛性上的不足，DE算法的变异操作可提升群体突变可能性，防止个体收敛到局部极值，并使用交叉、选择方法融合入QPSO中进行粒子更新，增强粒子全局和局部搜索能力，直至得到全局最优解。改进的公式为

(11)

式(11)中：r为生成的随机序列，其取值代表种群数量；c为生成的随机系数。

对于迭代过程中产生的最优个体，通常它们包含最有价值的信息，因此采用多邻域搜索局部搜索方法对这些最优值个体进行局部搜索，以提高算法的寻优速度，改善搜索质量。

自适应学习的多邻域搜索局部搜索步骤如下。

步骤 2邻域选择操作。若某邻域选择概率大于给定值，选定其作为移动邻域，否则改变搜索区域。筛选opt′的所有邻域，获得最优个体点bs；若f(opt′)>f(bs)，则opt′=bs；若f(opt′)≤f(bs) ，则重新进行邻域选择。

步骤3邻域奖励值更新操作。若f(opt)

图1 DEQPSO算法粒子搜索步骤

DEQPSO伪代码如表1所示。

表1 DEQPSO伪代码

2.4 DEQPSO计算复杂度分析

算法计算复杂度是影响算法执行效率的关键因素，可用于评判算法性能。将所提算法从空间复杂度和时间复杂度两方面进行分析。

空间复杂度是指算法运行所需的计算机存储空间大小。相比于QPSO，DEQPSO增加了差分进化和多邻域搜索操作，故空间复杂度有所增加，但对于求解JSP，增加程度是线性阶的，对存储空间影响较小。

算法的时间复杂度是指运行算法所需的时间长短，主要反映于算法执行次数。对于某个JSP问题，假设问题规模为D=n×m(n为工件数，m为机器数)，种群规模数为M。对于标准QPSO算法，时间复杂度为ο(D×M)。DEQPSO增加了差分进化算法的变异、交叉、选择操作以及多邻域搜索策略，而标准QPSO算法中也存在选择操作，所以变异、交叉操作的时间复杂度为ο(D×M)；对于多邻域局部搜索策略寻求最优值的时间复杂度为ο(D)。因此应用DEQPSO进行求解JSP的时间复杂度仍为ο(D×M)，整体时间复杂度不变。

2.5 DEQPSO实验性能测试

选取6种已被广泛应用于测试优化算法性能的标准测试函数[12]对所提出DEQPSO算法性能进行验证。表2展示了所采用的测试函数方程、变量的搜索范围以及最优解。

表2所列的6种测试函数中，前4种是维度为n的高维测试函数，f5、f6为低维测试函数，f1、f2和f3为单极值点标准测试函数，f4、f5和f6为多极值点标准测试函数。对于相同的给定条件，使用不同算法对测试函数进行寻优得到的最优解与理论值差别越小，说明算法寻优性能越好，求解精度越高。

表2 基准测试函数

将DEQPSO与引力搜索算法(gravitational search algorithm, GSA)、PSO、QPSO、差分进化算法(differential evolution algorithm，DE)以及正弦余弦算法(sine cosine algorithm，SCA)进行性能比较。将测试函数f1、f2、f3以及f4的维数n设置为32，各算法的种群规模均设置为80，最大迭代次数设置为1 200。其余参数设置信息如下。

DEQPSO参数：缩放因子为0.56，交叉概率为0.8；GSA参数：引力初值为100，学习因子为0.75；PSO和QPSO参数：加速常数c1、c2分别为3、2，惯性因子为0.6；DE参数：缩放因子为0.5，交叉概率为0.9；SCA参数：比例因子a为2，转化概率r∈[0,1]。

表3展示了30次独立重复实验下各算法对各测试函数的求解情况，统计数据中的最优结果已重点标出，其中PSO与GSA的计算结果参见文献[19]。

从表3的寻优结果可以看出，在6种基准函数测试条件下，除DE算法所得f4函数的最好值精度略优于所提算法外，本文算法求解所得结果的平均值、中值、标准差、最优值精度均远高于PSO、GSA、QPSO、DE以及SCA。其中，在绝对误差小于1×10-2范围内，本文算法得到了6种测试函数的理论最优解，而其余5种算法在误差范围内得到理论最优解函数的个数分别为3、4、5、5、1，且误差均大于所提算法，结果表明DEQPSO具有更好的收敛性能。对于函数f5，所提算法与DE算法得到了理论最优值0，而其余4种算法均存在一定的误差；对于函数低维函数f6，6种算法取得了相近的结果，且寻优结果误差均小于1×10-2。综合以上分析可得，相比于PSO、GSA、QPSO、DE以及SCA算法，DEQPSO具有更好的寻优性能以及适用性。

表3 6种算法的实验结果比较

3 仿真与实验

为了验证本文算法求解作业车间调度问题的性能，使用两类经典的JSP算例进行测试。第一种是FISHER与THOMPSON提出的FT类，由FT06、FT10和FT20组成；第二种是LA类，选取不同规模的8种典型问题，并与典型离散粒子群算法[12]、遗传算法[13]和细菌觅食优化算法[14]进行对比。以MATLAB为开发环境，利用CPU主频为3.4 GHz和内存为4.0 GB的计算机进行仿真。算法运行相关参数设置如下每个JSP问题实例的初始种群规模M=500，迭代次数T=200，交叉概率CR=0.75；终止条件：最大迭代数200。选择完成所有工件操作的最大加工时间作为评价指标。各算例均进行10次独立运算，记录10次实验的运行时间以及求解结果平均值，对照情况如表4所示。

从表4可以看出，对于FT、LA两类JSP算例，相比于其他3种算法，本文算法都能以较快的收敛速度得到其最优解；采用本文算法在求解较为困难的FT20、LA21算例时仍取得了较好的寻优结果，其中，FT20算例在10次独立实验中有6次得到了1 165的最优解。DEQPSO在求解难度较大的LA36问题时误差较大，但相较于其他参考算法，DEQPSO仍表现出较强的搜索能力。

表4 DEQPSO与典型离散粒子群算法、遗传算法以及细菌觅食算法的性能比较

为测试算法的收敛性能，并与其他3这种参考算法进行比较，仅给出FT10和LA36算例分别如图2、图3所示，其中对于FT10、DEQPSO在迭代到48代时，搜索到的工作时长已经接近最优值930，典型离散而粒子群算法为953，遗传算法为965，细菌觅食算法为973，由此可见DEQPSO算法的收敛性能优于其他3种算法；对于LA36，本文算法迭代到100次时，其搜索解为1 268，而其他3种算法均在1 400以上，其他算例情况相似，可知本文算法对于空间搜索更加充分，更容易获得空间最优解。图4为求得的LA16算例调度甘特图，方框中数字代表工件序号，从左到右依次表示该工件的加工次序。如图4中灰色方框代表了工件J1的各道工序。

图2 FT10收敛性能比较

图3 LA36收敛性能比较

图4 LA16算例的调度甘特图(加工周期为945 h)

4 结论

以作业车间调度问题为研究对象，通过对原始QPSO优化机理分析，引入差分进化思想，提出一种差分量子粒子群优化算法。对所提DEQPSO算法求解性能进行验证，得出以下结论。

(1)对6种标准测试函数进行最优值求解，DEPQSO算法求解结果的平均值、中值、标准差、以及最好值精度均优于PSO、GSA、QPSO、DE、SCA等算法，其中DEQPSO在绝对误差小于1×10-2范围内得到了6种函数的理论最优解，而其他算法未能全部收敛于理论值，所提算法具有更好的收敛性能以及适用性。

(2)对FT、LA两类JSP算例进行求解，将所提算法与离散粒子群算法、遗传算法以及细菌觅食算法进行对比。其中，LA36算例的理论最优解1 268，4种算法所得结果分别为1 294.6、1 457.4、1 374.3以及1 398，且所提算法收敛时间最短。仿真结果表明，相比于其他算法，DEPQSO算法寻优速度和精度都有了明显提升。

(3) 所提出的差分量子粒子群算法可以较好地改善车间调度问题加工周期，为实际工业流水线作业问题提供了理论依据。