无等待流水车间调度(no-wait flowshop scheduling，NWFS)问题是一类重要的约束组合优化问题，广泛存在于炼钢、 化工制造、 食品加工和塑料塑造等工业领域^[1]. 该问题可描述为： n个作业在m台机器上按给定加工时间、 顺序进行加工且作业在加工过程中不能被中断. 优化目标有最小化最大完工时间、 总延迟和总完工时间等，其中，最小化总完工时间(total flow time，TFT)是实际应用中的重要指标，TFT最小化可促进资源稳定有效利用、 作业快速周转以及在制品库存最小化. 最小化总完工时间的NWFS问题记为F_m|nwt|∑C_i. 已经证明，在机器数m>2时，该问题为强NP难问题^[2].

目前，求解F_m|nwt|∑C_i主要采用启发式算法和智能算法. 启发式算法分为构造启发式和复合启发式. Rajendran等^[3]提出了基于任务插入的构造启发式算法，Bertolissi^[4]设计了基于比较的构造启发式算法，朱夏等^[5]构建了基于目标增量的快速迭代贪婪算法，李亚志等^[6]提出了基于插入—分段的复合启发式(insertion-segment based composite heuristic，ISCH)算法，Laha等^[7]设计了最新的改进启发式算法(improved heuristic algorithm，IHA)，实验结果显示其性能优于复合启发式算法^{[8, 9]}，IHA是现阶段较优的启发式算法. 启发式算法尽管求解速度较快，但求解质量一般不太理想. 智能优化算法对F_m|nwt|∑C_i优化表现出高度的有效性. Pan等^[10]提出了离散粒子群优化算法(discrete particle swarm optimization algorithm with the variable neighborhood descent local search，DPSO_VND)，Gao等^[11]开发了离散的和声搜索算法(discrete harmony search，DHS)，Jarboui等^[12]提出了基于变邻域搜索的混合遗传算法(genetic algorithm-variable neighborhood search，GA-VNS)，实验结果证明GA-VNS求解质量优于DPSO_VND.

萤火虫优化(glowworm swarm optimization，GSO)算法是一种新颖的智能算法，通过模拟萤火虫的社会行为实现优化，具有收敛速度快、 设置参数少、 易于实现及并行设计，广泛应用于工程优化问题^{[13, 14, 15, 16, 17]}. 然而因其寻优能力主要是靠萤火虫个体之间的相互作用和影响，个体自身缺乏变异机制，因而算法存在“早熟收敛”缺陷. 量子进化算法(quantum-inspired evolutionary algorithm，QEA)^[18]将量子计算与进化计算相融合，通过量子比特编码、 解码染色体，同时利用当前最优个体信息更新量子旋转门，能加速算法收敛.

为了弥补萤火虫优化算法的不足，将量子进化机制嵌入萤火虫算法中，并与设计的一种局部邻域搜索算法(local neighborhood search，LNS)相融合，提出了基于LNS的量子萤火虫优化(quantum-inspired GSO based on LNS，QGSO_LNS)算法，以实现优化性能互补. 将QGSO_LNS与几个较优的算法(IHA、 DGSO(discrete GSO)^[13]、 GA-VNS及DHS)进行仿真比较，实验结果表明所提算法能高效地求解F_m|nwt|∑C_i问题.

令n个作业在m台机器上加工时间为一个n×m矩阵P，其中P_i，k为作业J_i(i=1，2，…，n)在机器M_k(k=1，2，…，m)上的加工时间. 作业开工时间距离构成一个n×n矩阵D，其中元素D_i，j(i，j=1，2，…，n)为相邻两作业J_i和J_j的开工时间距离，规定同一作业间的距离为∞，D_i，j计算公式为

易知，式(1)时间复杂度为O(m). 设S=｛π₁，π₂，…，π_i-1，π_i，…，π_n｝表示一个调度，其中π_i∈｛J₁，J₂，…，J_n｝(i=1，2，…，n)表示S的第i个位置上的作业. 在NWFS中，任意2个作业间的距离都是固定的，与具体的调度序列无关. 因此，调度S的总完工时间可按式(2)计算：

由式(1)和式(2)可知，调度序列中任何2个相邻作业的TFT只与两者的加工时间有关，与其它作业无关. 此外，为了有效地提高算法运行效率，本文所有邻域搜索产生新序列的TFT值均采用目标增量法^[5]计算.

本文优化目标可描述为：

∃序列S^*∈调度集合Π，对于∀S∈Π，均有f(S^*)≤f(S)成立.

由于VNS算法每次迭代要完整地搜索当前解邻域，这在大规模流水调度中会造成算法运行时间大幅增加、 优化性能下降； 另外，当解逼近全局最优时，解中大部分“块”结构^[19]均已稳定，重复移动块内作业易破坏“优质”邻域结构，降低求解质量. 鉴于此，本文改进邻域搜索方式，提出了局部邻域搜索算法LNS.

LNS算法只对局部最优解执行一次随机扰动，产生前后邻域结构的变化，并且仅对变化的位置进行搜索，不重复执行完整搜索. LNS算法的基本框架如图 1所示.

图 1 LNS算法框架 Fig. 1 LNS algorithm framework

图选项

为方便描述，令当前作业调度S=｛π₁，π₂，…，π_n｝，并引入虚作业π₀为初始作业，π_n+1为终止作业，它们在所有机器上的加工时间均为0且不参与调度，此时S=｛π₀，π₁，π₂，…，π_n，π_n+1｝. 同时，给出如下定义：

定义1  序对交换(pair-exchange)： 将S中任意两个作业π_i(i=1，2，…，n)和π_j(j=1，2，…，n)调换到对方位置，记为Swap(S，i，j).

定义2  序对移位(shift)： 将S中的作业π_i(i=1，2，…，n)从所在位置删除，再插入到作业π_j(j=1，2，…，n)的位置，记为Shift(S，i，j).

定义3  插入点(cut point)： 位于S中相邻作业对(π_x，π_x+1)(x=0，1，…，n)中间的位置.

定义4  邻居作业(neighborhood job)： 位于S中某作业π_x(x=1，2，…，n)相邻位置的作业.

当前对S执行一次交换或移位后，对应有2种不同局部邻域结构，如图 2和图 3所示.

图 2 局部邻域序对交换结构图 Fig. 2 Structure of local neighborhood for pair-exchange

图选项

图 3 局部邻域移位结构图 Fig. 3 Structure of local neighborhood for shift

图选项

在图 2中，作业π_i与π_j(i，j=1，2，…，n)交换后，调度作业A=｛π_i，π_j｝，A的邻居作业V=｛π_i-1，π_i+1，π_j-1，π_j+1｝，对应插入点CP=｛(π_i-1，π_j)，(π_j，π_i+1)，(π_j-1，π_i)，(π_i，π_j+1)｝； 在图 3中，作业π_i移位到位置j后，A=｛π_i｝，V=｛π_i-1，π_i+1，π_j，π_j+1｝，CP=｛(π_i-1，π_i+1)，(π_j，π_i)，(π_i，π_j+1)｝. 剩余作业U=S-A-V.

上述A、 V(剔除虚作业π₀和π_n+1)中任一作业均可与非自身作业构成序对进行交换或移位，U中任一作业也可移位至CP中任一插入点处； 然后评估所述全部操作作用于S后产生的目标增量值，选取最小值对应的序对更新S，计算新的A、 V、 CP和U； 重复上述过程直至S不再变化. 该过程称为局部邻域搜索. 其步骤描述如下：

步骤1  对扰动后的解S执行外循环，即先计算S的邻域结构变化后产生的A、 V、 CP和U，循环计数t←0.

步骤2  判断V、 CP和A是否不全为空： 若是，则执行步骤3； 否则，转步骤4.

步骤3  对S执行内循环，即先从｛A，V｝中随机取一作业π_from，任取另一作业π_to←S-π_from或从CP中随机取出π_to，任取π_from←U. 然后，选取所有可能的序对(from，to)，并评估相应作业对交换操作Swap(S，from，to)、 移位操作Shift(S，from，to)对应的局部最小目标增量值Δ_top¹和Δ_to²，选取较小值Δ_t←min｛Δ_top¹，Δ_top²｝. t←t+1，转步骤2.

步骤4 取最小增量Δ_min←min｛Δ₁，Δ₂，…，Δ_t｝. 若Δ_min<0，则S接受Δ_min对应的序对操作，转步骤1； 否则，邻域最优解S_b←S，算法停止并返回S_b.

LNS算法由两层循环构成，内循环表示对S执行局部交换、 移位对应的增量评估过程，循环时间复杂度为O(n)； 外循环表示S得到改进次数设为c，实际上，算法每次运行时，c值是变化的，故LNS算法复杂度为O(cn).

在基本萤火虫算法中，算法的优化机制主要由以下4个参数确定.

1) 亮度： 表示萤火虫的相对荧光亮度，用I(r)表示：

2) 吸引度： 表示萤火虫之间的吸引度，可用β表示，定义为

3) 移动： 萤火虫i受到一个更亮的萤火虫j吸引后，按式(7)来确定位置移动方式.

4) 搜索半径： 萤火虫i的搜索半径r_d决定了其可感知其它个体的亮度范围，并选择亮度更大的个体组成其邻域集N_i，通过一定的选择算法选取要移动到的个体. 移动完毕，按式(8)更新搜索半径的值：

在QGSO_LNS中，量子个体q的每个量子位的状态|φ〉的概率幅度用量子角形式表示，即|φ〉=[α，β]^T=[cos θ，sin θ]^T. 在NWFS问题中，q的每个量子位可代表一个作业，则包含n个作业的q可编码为

本文采用单链编码方式，即q=(cos θ₁，cos θ₂，…，cos θ_n)，群体初始化时，量子角θ_j(j=1，2，…，n)在[0，2π]内随机生成. 量子解码采用变异的LOV(largest-order-value)规则^[20]对q的值进行升序排列，并对排序后的值依次搜索其在排序前序列中的位置，得到的位置序列｛x₁，x₂，…，x_n｝可生成一组作业｛J_x1，J_x2，…，J_xn｝，即解码结果.

QGSO_LNS算法融合了萤火虫算法、 量子进化机制和局部邻域搜索策略，其基本思想是： 先用量子编码方案随机产生一定规模的萤火虫种群，每只萤火虫的位置表示一种调度作业序列； 然后，任取一个体S进行解码，采用ISCH算法^[6]进行优化，并对优化结果执行个体重排，以保持生成的新量子编码序列解码结果正确； 个体重排完毕后，根据式(3)～式(5)计算每个个体i的相对荧光亮度，构造相应的邻域集，并采用赌轮法从中选取一个体j，按式(6)和式(7)对i的量子旋转门进行更新； 接着，按式(8)更新其搜索半径值，并对新种群个体进行量子解码及适应度评估，取出群体最优解后执行LNS算法优化，对优化结果再次进行重排，重复上述过程，直至满足停止条件； 最后输出全局最优解. 算法框架如图 4所示.

图 4 QGSOLNS算法框架 Fig. 4 QGSOLNS algorithm framework

图选项

图 5描述了个体重排过程. 在图 5中，S的量子编码q=(0.564，0.281，0.37，0.009，0.963，0.55)，经解码后得到一个作业序列S^old=｛J₄，J₂，J₃，J₆，J₁，J₅｝，采用ISCH优化得到一个改进序列S^new=｛J₃，J₆，J₄，J₁，J₂，J₅｝，然后对S进行重排. 重排过程是通过移位S的编码序列实现，它由多次移位过程构成，移位次序由量子编码值递增顺序进行，移位次数由序列长度确定，每次移位项的位置和要插入位置分别由S^old和S^new的作业下标决定. 图 5中虚线箭头指示的就是第一次移位过程，可用Shift(q，4，3)表示，其中，4和3分别为S₁^old和S₁^new的作业下标. 上述初始序列经过6次移位后，结果为(0.55，0.564，0.009，0.37，0.963，0.28)，即S的新编码序列S′.

图 5 个体重排过程示例 Fig. 5 The example of individual rearrangement process

图选项

QGSO_LNS算法步骤描述如下：

步骤1  初始化种群各参数，包括种群大小n_ps、 最大进化代数g等. 令加工时间矩阵为P_n×m，根据P计算作业开工距离矩阵D_n×n，迭代次数t←0.

步骤2  对种群执行量子编码｛S¹，S²，…，S^n_ps｝←Encoding()，任取一个体并执行ISCH算法以生成较优的初始解S. 最优调度序列S^*←S.

步骤3  对S执行量子重排过程S′←Re-Permu(S)，S←S′.

步骤4  对每个萤火虫个体Sⁱ，搜索其搜索半径r_dⁱ内的个体S^j(i，j=1，2，…，n_ps)，然后，按式(4)计算两者的距离r_ij. 若距离Sⁱ的r_ij处亮度I_i(r)≥I₀，则将S^j加入Sⁱ的邻域集N_i←｛S^j｝.

步骤5  对N_i执行赌轮法选择个体S^j←Routte(N_i). 按式(6)和式(7)执行量子旋转门更新Rotate(i，j)，按式(8)更新萤火虫Sⁱ的搜索半径r_dⁱ，然后对Sⁱ执行量子解码得(Sⁱ)′←Decoding(Sⁱ)，并计算(Sⁱ)′目标函数值f((Sⁱ)′)，根据f((Sⁱ)′)取群体最优解S←min｛(S¹)′，(S²)′，…，(S^n_ps)′｝.

步骤6  执行S_b←LNS(S). 若f(S_b)<f(S^*)，则(S，S^*)←S_b； 否则不更新S和S^*.

步骤7  t←t+1. 若t<g，转步骤3； 否则，算法停止并返回S^*.

QGSO_LNS算法的时间开销主要集中在步骤1、 步骤2和步骤6，由于n_ps、 g等循环控制参数仿真时设为一个常量，可得时间复杂度分别为O(mn²)、 O(n³)和O(cn)，整个算法的复杂度为max｛O(mn²)，O(n³)｝.

为了验证所提算法的性能，对F_m|nwt|∑C_i问题，采用Taillard^[21]110个基准实例测试. 按问题规模将20×5到200×20分为11组，每组10个实例，如： 20×5组包括Ta001-Ta010. 算法仿真采用VC++实现，并在CPU 2.83 GHz、 RAM 2 GB的PC机上运行.

参数设置的标准是测试各参数数据以判断算法优化能力是否达到最佳. 经多次实验比较，QGSO_LNS算法的各参数值设置如表 1所示.

表 2给出了LNS算法与2种较优的VNS算法VNS_J^[12](记文^[12]提出的VNS算法为VNS_J)、 VNS_4^[22]进行时间性能比较(单位： s). 为公平起见，3种算法均在同一机器上运行，邻域解的变化采用目标增量法且算法的最大迭代次数相同，依次取50(短期，记为K)、 100(中期，记为M)和500(长期，记为L).

由表 2可知，算法时间性能从好到坏依次为LNS、 VNS_J和VNS_4. 对于均值，VNS_J算法的K、 M和L值分别为3.41 s、 6.65 s和32.15 s； VNS_4算法相应分别为7.8 s、 14.58 s和73.37 s； 而LNS只有0.38 s、 0.77 s和3.78 s，远小于VNS_4和VNS_J算法的耗时值. 这说明LNS具有更高的运行效率.

为验证所提算法的性能，将QGSO_LNS与目前较优的启发式算法IHA、 群智能算法DGSO、 GA-VNS和DHS进行比较，性能指标采用ARPD(average relative percentage deviation)，计算公式如下：

由表 3可知，QGSO_LNS算法对中小规模作业(n=20，50)优化效果较GA-VNS算法、 DHS算法并不明显，但在大规模作业(n=100，200)下，QGSO_LNS算法明显优于其他算法. 这是因为在QGSO_LNS算法中，一方面采用了目标增量法及局部邻域优化方法，极大地加快了算法迭代速度； 另一方面，引入了量子机制的QGSO_LNS算法是一种全局搜索性质的算法，当n值较大时有利于扩大算法的搜索空间并降低种群“早熟”概率. 平均而言，5种算法中，IHA、 DGSO、 GA-VNS和DHS的ARPD值分别为10.831％、 0.445％、 0.066％和0.161％，而QGSO_LNS最小，只有0.038％，较前4种算法分别改善了99.65％、 91.46％、 42.42％和76.4％，说明了所提算法的高效性.

为了能够更直观地进行算法性能对比，将所提算法与上述较优的算法DGSO、 GA-VNS和DHS进行ARPD性能对比，如图 6所示.

图 6 DGSO、 GA-VNS、 DHS和QGSOLNS的ARPD比较图 Fig. 6 Diagram of ARPD comparison among DGSO，GA-VNS，DHS and QGSOLNS algorithms

图选项

由图 6可知，当n≤50时，所提算法的ARPD值优势并不明显； 而当n>50时，其值明显低于DGSO、 GA-VNS和DHS. 这说明QGSO_LNS算法更适合大规模无等待调度.

图 7描述了4种算法在Ta071、 Ta101实例下的进化收敛曲线. 由图 7(a)可知，4种算法的收敛速度在开始时大致相同，然而进化到了350代左右，DGSO、 GA-VNS和DHS基本陷于“停滞”，而QGSO_LNS由于具有较优的初始解，并利用量子萤火虫混合算法及快速高效的局部邻域搜索策略，最终获得了全局最优解，可以看出QGSO_LNS具有更好的全局搜索能力； 图 7(b)的收敛情况则更为明显，说明所提算法在大规模调度下具有更强的优化性能.

图 7 DGSO、 GA-VNS、 DHS和QGSOLNS算法的进化收敛曲线对比 Fig. 7 Comparison of convergence curves among DGSO，GA-VNS，DHS and QGSOLNS algorithms

图选项

本文提出了一种高效的量子萤火虫优化算法，解决了无等待流水调度最小化总完工时间问题. 通过采用量子优化编码和旋转机制、 快速的目标增量计算及高效的局部邻域搜索方法，极大地加快了算法迭代速度，拓展了算法全局搜索能力. 与目前较优的几种算法在标准测试用例上进行仿真实验比较，结果表明所提算法性能高效，能有效地求解F_m|nwt|∑C_i问题.