批量流水调度问题的量子候鸟协同优化算法

陈林烽 齐学梅 陈俊文 黄琤 陈付龙

摘 要：为了求解批量流水调度问题（LFSP）的最小化最大完工时间，提出一种量子候鸟协同优化（QMBCO）算法。首先，采用Bloch量子球面编码方案扩大解空间;然后，运用FL算法优化初始解，以弥补传统随机初始解的不足，保证初始种群具有较高的质量;最后，使用候鸟优化（MBO）算法及变邻域搜索（VNS）算法进行迭代，增强算法的全局搜索能力。采用随机生成不同规模的实例仿真，将QMBCO算法与目前较优的离散粒子群优化（DPSO）算法、MBO算法和量子布谷鸟协同搜索（QCCS）算法相比较。结果表明，在两种不同运行时间下QMBCO与DPSO、MBO、QCCS相比产生的最优解平均百分比偏差（ARPD）分别平均下降65%、34%和24%，证明了QMBCO算法的有效性和高效性。

关键词：批量流水调度问题;最大完工时间;候鸟优化算法;Bloch量子球面编码;变邻域搜索算法;平均百分比偏差

中图分类号：TP301.6

文献标志码：A

Quantuminspired migrating birds cooptimization algorithm

for lotstreaming flow shop scheduling problem

CHEN Linfeng1，2，QI Xuemei1，2*，CHEN Junwen1，2，HUANG Cheng1，2，CHEN Fulong1，2

1.School of Computer and Information， Anhui Normal University， Wuhu Anhui 241002， China;

2.Anhui Provincial Key Laboratory of Network and Information Security（Anhui Normal University）， Wuhu Anhui 241002， China

Abstract：

A Quantuminspired Migrating Birds CoOptimization （QMBCO） algorithm was proposed for minimizing the makespan in Lotstreaming Flow shop Scheduling Problem （LFSP）. Firstly， the quantum coding based on Bloch coordinates was applied to expand the solution space. Secondly， an initial solution improvement scheme based on FraminanLeisten （FL） algorithm was used to makeup the shortage of traditional initial solution and construct the random initial population with high quality. Finally， Migrating Birds Optimization （MBO） and Variable Neighborhood Search （VNS） algorithm were applied for iteration to achieve the information exchange between the worse individuals and superior individuals in proposed algorithm to improve the global search ability. A set of instances with different scales were generated randomly， and QMBCO was compared with Discrete Particle Swarm Optimization （DPSO）， MBO and Quantuminspired Cuckoo CoSearch （QCCS） algorithms on them. Experimental results show that compared with DPSO， MBO and QCCS， QMBCO has the Average Relative Percentage Deviation （ARPD） averagely reduced by 65%， 34% and 24% respectively under two types of running time， verifying the effectiveness and efficiency of the proposed QMBCO algorithm.

Key words：

Lotstreaming Flow shop Scheduling Problem （LFSP）; makespan; Migrating Birds Optimization （MBO） algorithm; quantum coding based on Bloch coordinates; Variable Neighborhood Search （VNS） algorithm; Average Relative Percentage Deviation （ARPD）

0 引言

批量流水調度问题（Lotstreaming Flow shop Scheduling Problem， LFSP）是一类典型的调度问题，对其进行研究具有重要的理论意义和工程价值，广泛存在于炼钢、食品加工、化工和制药等工业领域[1]。其概念最早是由Reiter[2]在1966年提出，传统的优化方法如线性规划（Linear Programming， LP）、分支定界（Branch And Bound， BAB）不适合解决此类复杂的组合优化问题，智能优化算法成为求解此类调度问题的主要趋势。

近年來，许多研究学者将智能优化算法用于求解LFSP。例如，Pan等[3]提出解决批量流水调度问题分布式估计算法（Estimation of Distribution Algorithm， EDA），通过多种调度实例证明所提算法性能优于混合遗传算法（Hybird Genetic Algorithm， HGA）。Sang等[4]提出离散杂草入侵算法解决以序列相关最大完工时间的批量流水调度问题，通过与EDA，人工蜂群（Artificial Bee Colony， ABC）算法以及改进的羊群遗传算法（Sheep Flock Heredity Algorithm， SFHA）比较证明其算法性能。近几年，Meng等[5]相继提出改进的候鸟优化算法（Improved Migrating Birds Optimization， IMMBO）处理批量流水调度问题，通过多种调度实例证明其算法在处理各种批量问题的高效性。然而，这些算法大多没有从算法整体的离散与收敛性考虑，随着问题规模的扩大易陷入“局部最优”。

候鸟优化算法（Migrating Birds Optimization， MBO）[6]是由Duman等提出的一种新的元启发式算法，算法通过模拟候鸟迁徙过程中的V字形编队以减少能量损耗，因具有参数少、结构简单、易于理解、寻优能力及局部搜索能力强等优点而受到广泛关注。该算法已经成功应用于二次分配[6]、流水调度[7-8]、柔性制造系统[9]、经典旅行商[10]等问题。但这些针对MBO算法的研究大多数只考虑单个算法的应用，并没有结合其他算法进行优劣互补，影响其整体的求解能力及效率。

量子遗传算法（Quantum Genetic Algorithm， QGA）概念由Narayanan等[11]在1996年最先提出，Han等[12]基于此概念又提出量子进化算法（Quantuminspired Evolutionary Algorithm， QEA）并成功将其应用于背包问题。王铮等[13]采用量子进化算法及量子旋转角优化技术并将其成功应用至多轮廓路径的优化，验证了其算法的可行性和有效性。虽然传统量子进化算法在计算性能和优化求解方面具有较好的能力，但单一使用也有收敛速度慢、易陷入局部最优等缺点。

基于以上算法的缺陷，本文提出了一种量子候鸟协同优化（Quantuminspired Migrating Birds CoOptimization， QMBCO）算法，用于求解批量流水调度问题中最小化最大完工时间。算法首先采用Bloch球面量子编码方案[14]扩充全局最优解的数量，并使用FL（FraminanLeisten）算法[15]改进初始解，有效提高种群质量。采用MBO算法[16]与变邻域搜索算法 （Variable Neighborhood Search， VNS）算法[17]迭代，进一步提高算法的局部搜索能力。QMBCO算法采用Bloch球面量子编码方案并将启发式算法和智能优化算法相结合，优劣互补。FL算法具有较强的探索能力，而MBO算法及VNS算法具有较强的求精能力，通过结合这几种方案协同使整体具有较好的平衡能力。仿真实验结果表明所提算法的优越性。

1 问题描述

LFSP描述为：有m台机器和n个工件，每个工件可分成若干小批量，每个小批量在各机床上加工顺序相同，但加工时间可能不同。同时约定：1）同一机器上一个工件的所有小批量完成后另一个工件的小批量方可开始加工;2）所有机器上各工件小批量的加工次序完全相同;3）在任何时刻一台机器只能够加工一个小批量，一个小批量只能在一台机器上加工;4）批量运输时间包含在加工时间内;5）同一台机器上相邻批量之间机器可空闲。已知工件数和各批量在各台机器上所需的加工时间，求满足上述约束条件的可行调度，使工件的最大完成时间（Cmax）最短。

在n个工件m台机器的调度中，令工件j={1，2，…，n}，机器i={1，2，…，m}为工件πj批量数。设π={π1，π2，…，πn}处理的工件序列，πk为序列π的第k个工件，pj，i为工件j在机器i上的批量加工时间，Sj，i，q为工件j在机器i上第q个批量的最早开始加工时间，Cj，i，q为工件j在机器i上第q个批量的最早完工时间，Cmax（π）为序列π的最大完工时间。图1所描述的是3个工件和3台机器最大完工时间的甘特图。根据LFSP的特征，本文提出计算最大完工时间的计算方法如下：

Sπ1，1，1=0

Cπ1，1，1=pπ1，1

Sπ1，k，1=Cπ1，k-1，1

Cπ1，k，1=Sπ1，k，1+pπ1，k; k=2，3，…，m （1）

Sπ1，1，e=Cπ1，1，e-1

Cπ1，1，e=Sπ1，1，e+pπ1，1

Sπ1，k，e=max{Cπ1，k-1，e，Cπ1，k，e-1}

Cπ1，k，1=Sπ1，k，e+pπ1，k;e=2，3，…，lπ1， k=2，3，…，m （2）

Sπi，1，1=Cπi-1，1，lπi-1Cπi，1，1=Sπi，1，1+pπi，1

Sπi，k，1=max{Cπi，k-1，1，Cπi-1，k，lπi-1}

Cπi，k，1=Sπi，k，1+pπi，k; i=2，3，…，n， k=2，3，…，m（3）

Sπi，1，e=Cπi，1，e-1

Cπi，1，e=Sπi，1，e+pπi，1

Sπi，k，e=max{Cπi，k-1，e，Cπi，k，e-1}

Cπi，k，e=Sπi，k，e+pπi，k; i=2，3，…，n， e=2，3，…，lπi， k=2，3，…，m（4）

Cmax（π）=Cπn，m，lπn（5）

2 传统MBO算法

MBO算法是一种新颖的智能优化算法，类似于遗传算法对生物进化的模拟、粒子群优化算法对鸟群捕食过程的模拟等，MBO算法是对候鸟在迁徙过程中队列个体排列次序的模拟。算法共5个步骤，群体中的候鸟称为一个解，其基本流程如下：

步骤1 初始化。设置4个参数分别为种群大小，每个解的邻域数量a、传递给下一个解的邻域数量b、种群所有个体的巡回次数、优化次数c等。

步骤2 领飞鸟进化。在领飞鸟周围随机生成a个邻域，搜索这些邻域，若找到比领飞鸟更优的最优解则替换领飞鸟，若没有则不替换。然后将未被使用的邻域按照目标值从优到劣的顺序排序，把最好的2b个邻域平均分配给其后左右两只跟飞鸟作为其邻域的一部分。

步骤3 优化跟飞鸟。跟飞鸟的邻域由上一只鸟传递给它的b个个体和在它周围随机产生的a-b个个体组成，搜索这a个个体中最优个体，若优于跟飞鸟则替换，否则跟飞鸟不变。同样将邻域中未被使用的b个最好的邻域传递给下一个跟飞鸟作为其邻域的一部分。跟飞鸟的优化是从队首向队尾逐个进行，左右两边分别进行，直到所有的跟飞鸟都进行一次邻域搜索后，一次跟飞鸟优化完成。

步骤4 在种群中产生新的领飞鸟。循环步骤2、3至c次，在领飞鸟左右两只鸟中选择较好的一只作为新的领飞鸟，被替换的领飞鸟回到队尾。

步骤5 直到达到设定迭代次数后停止该算法，否则重复步骤2～步骤5。

3 量子候鸟协同优化（QMBCO）算法

由于传统MBO算法是针对二次分配这种连续函数优化问题而提出，不能直接用于处理LFSP这类离散的组合优化问题，需要转换成离散形式。本文基于传统候鸟优化算法，结合LFSP求解，提出一种新的QMBCO算法，包括基于Bloch球面量子编码、种群初始化、领飞鸟优化、跟飞鸟优化、领飞鸟的替换、变邻域搜索策略等，可有效应用于求解批量流水调度问题。

3.1 基于Bloch球面坐标量子编码

在量子计算中，量子比特是最小的信息单位。有两种状态“0”和“1”，即量子线性叠加态，可由式（6）表示：

|φ〉=cos（θ/2）|0〉+eiφsin（θ/2）|1〉（6）

其中：|φ〉量子比特状态，量子角θ∈[0，π]，φ∈[0，2π]。cos（θ/2）和eiφsin（θ/2）是一对复数，cos（θ/2）2和eiφsin（θ/2）2分别表示量子位处于|0〉和|1〉的概率，且满足：

cos（θ/2）2+eiφsin（θ/2）2=1（7）

因此，量子比特可以用三维Bloch球面上的一点P（cosφsinθ，sinφsinθ，cosθ）描述，如图2所示。在QMBCO算法中，采用量子比特的Bloch坐标编码种群q为：

q=

cosφ1sinθ1

sinφ1sinθ1

cosθ1

cosφ2sinθ2

sinφ2sinθ2

cosθ2

…

…

…

cosφnsinθn

sinφnsinθn

cosθn（8）

其中：n是量子位数，φi（1≤i≤n），θi（1≤i≤n）分别在（0， 2π）和（0， π）内随机生成。

在QMBCO算法中，每个种群量子比特都可分解在Bloch球面上的x、y、z三个位置上，即可表示为种群的三个位置，分别为：

qx=（cosφ1sinθ1，cosφ2sinθ2，…，cosφnsinθn）（9）

qy=（sinφ1sinθ1，sinφ2sinθ2，…，sinφnsinθn）（10）

qz=（cosθ1，cosθ2，…，cosθn）（11）

对于LFSP，量子位数n表示工件个数，工件的加工序列对应量子种群根据LOV（Largest Order Value）规则生成的加工序列π={π1，π2，…，πn}。

3.2 种群初始化

初始化种群是QMBCO算法优化的起点，好的初始种群能有效提高算法的性能[5]。候鸟种群的初始化，设种群个体数为ps，根据相关数据实验设置其他参数值，种群中的每只候鸟对应一个解。FL算法基于NEH（Nawaz， Enscore， and Ham）算法的改进，是求解流水调度中启发式算法性能较好的一种[15]，其原理是采用交换邻域、插入邻域两种搜索模式，以改善部分序列，本文采用FL算法产生初始解，保证初始候鸟具有较高的质量。为了使初始种群具有全局性，本文采用Bloch球面坐标解码与FL算法结合的方法产生初始种群的所有个体，计算各自的最大完成时间，将最大完成时间最短的鸟作为初始鸟群的领飞鸟，并将种群中剩下的鸟均分到V形的左右两边。分别使用两个数组Lp和Rp存储，形成初始V形队形，用数组Sn_L和Sn_R表示V形队列左右两边个体分享给下一个个体的邻域解集合。

3.3 领飞鸟优化

领飞鸟的优化采用迭代贪婪（Iterated Greedy，IG）算法[18]进行循环迭代。本文利用IG算法中删减和插入的思想生成领飞鸟的Cnum个邻域解，并进行评估比较。具体的实现方法如下：

1）首先参考相关实验数据，根据分析结果设定一个合适的参數值d（1

2）对当前的领飞鸟序列Xled={π1，π2，…，πn}，随机删减序列Xled中的d个工件，并将被删减的这d个工件依次存入序列πd中， Xled删减d个工件之后的序列记为Xled′={π1，π2，…，πn-d}，令i=1。

3）将πd中的第i个工件插入Xled′中的所有空位，分别评估计算插入工件后序列的最大完工时间，保留最大完工时间最短的序列作为新的Xled′。

4）如果i

5）若生成的邻域解数量小于Cnum，重复2）～4）操作;否则操作停止。

6）完成上述操作后将领飞鸟的邻域解存入数组LBc中，计算邻域解集合中最大完工时间最短的序列，比较该序列与当前领飞鸟序列的最大完工时间，若该序列更优则替换当前领飞鸟，否则领飞鸟不变。

3.4 跟飞鸟优化

为了保证算法的搜索性能，对跟飞鸟与领飞鸟采用不同的优化策略。跟飞鸟邻域解采用随机选择交换和插入的方法。随机选择跟飞鸟序列中的位置，执行交换（SWAP）和插入（INSERT）操作，实现跟飞鸟邻域解集合的构建。

1） 执行SWAP方法。在序列长度的范围内随机生成两个不相等的随机数x、y，将跟飞鸟序列πfellow={π1，π2，…，πn}中x和y位上的πx和πy进行交换，从而产生新的序列。例如，序列{2，4，6，3，1，5}中第3位和第5位上的6和1执行交换操作产生新的序列{2，4，1，3，6，5}，交换过程如图3所示。

2） 执行INSERT方法。在序列长度的范围内随机生成两个不相等的随机数x、y，将跟飞鸟序列πfellow={π1，π2，…，πn}中x位上的πx插入到y位上，从而产生新的序列。例如，序列{2，4，6，3，1，5}中第3位上的6插入到第5位，产生新的序列{2，4，3，1，6，5}，插入过程如图4所示。

3.5 领飞鸟替换

当巡回次数达到后，则进行领飞鸟的替换。V形编队有左右两个队列，轮流用左边队列和右边队列的第一只鸟对领飞鸟进行替换，并将原来领飞鸟移至相应左右两翼队末。

3.6 VNS算法

VNS算法是已被证明了的具有增强种群收敛且适合求解流水调度问题[18]的启发式算法， 其基本思想是在搜索过程中系统地改变邻域结构集来拓展搜索范围，获得局部最优解，再基于此局部最优解来拓展搜索范围找到另一个局部最优解的过程。本文采用一种改进的VNS算法，该算法结合成对交换搜索（PairExchange Search， PES）算法、插入搜索（Insertion Search， IS）、剪切修复插入搜索（Insertion Search with CutandRepair， ISCR），从而有利于算法跳出局部最优，增加获得全局最优解的概率。本文对MBO算法处理后的解执VNS算法，循环直至收敛。在此结构中，MBO及VNS算法具有较强的局部搜索能力，可丰富当前解的邻域结构，增强算法全局搜索能力。

3.7 全局收敛性

因MBO算法具有全局收敛性[6]，而VNS算法有较强的局部收敛性[19]。QMBCO算法通过MBO及VNS算法迭代至最优解，故具有全局收敛性。

3.8 算法描述

根据3.1～3.6节的内容，QMBCO的具体描述如下：

算法1 QMBCO算法。

输入 ps， Cnum， Snum， K， imax;

输出 最优解Xled。

程序前

1）

定義参数ps， Cnum， Snum， K， imax， Lp，Rp， Sn_L， Sn_R， LBc， FBc， Nbest， Xled;

2）

初始化种群，随机生成ps个个体{X1，X2，…，Xps};

3）

执行Bloch球面坐标量子编码种群X={X1，X2，…，Xps}←Encoding，生成ps个调度序列π，输出调度序列中最小目标值作为初始解π′其进行FL算法优化;

4）

Xled=Min{X1，X2，…，Xps}，找出种群中目标值最小的个体作为领飞鸟Xled，并将剩下的鸟均分到V形两边，填入数组Lp，Rp中;

5）

for i←1 to imax

6）

for j←1 to K

7）

用IG算法生成领飞鸟的Cnum个邻域解LBc，其中LBc[]={N1，N2，…，NCnum}，Nbest[]=Min{N1，N2，…，NCnum};

8）

if f（Nbest）

/*f（x）为序列x的目标值*/

9）

将LBc中未被使用的Cmax最佳的2Snum个邻域解随机填入数组Sn_L和Sn_R，使得两数组都包含Snum个解;//Cmax为批量流水调度的目标值

10）

for m1←1 to （ps-1）/2//左边跟飞鸟优化

11）

随机使用SWAP和INSERT的方法生成 Lp[m1]的Cnum-Snum个邻域解，然后和Sn_L合并构成Lp[m1]的邻域解集合FBc[m1];

12）

Nbest=Min（f（FBc[]））;

13）

if f（Nbest）

14）

将FBc[]中未被使用的Cmax最佳的Snum个邻域解填入Sn_L;

15）

endfor

16）

for m2←1 to （ps-1）/2//右边跟飞鸟优化

17）

随机使用SWAP和INSERT方法生成Rp[m2]的Cnum-Snum个邻域解，然后和Sn_R合并构成 Rp[m2]的邻域解集合 FBc[m2];

18）

Nbest=Min（f（FBc[]））;

19）

if f（Nbest）

20）

将 FBc[]中未被使用的Cmax最佳的Snum个邻域解填入Sn_R;

21）

endfor

22）

endfor

23）

if f（Rp[1]） < f（Lp[1]）

24）

领飞鸟回到右边队尾;

25）

Xled=Rp[1];

26）

else

27）

领飞鸟回到左边队尾;

28）

Xled=Lp[1];

29）

对当前解执行VNS优化，若更优则赋值给领飞鸟的解;

30）

判断是否达到迭代次数，若未达到则转至步骤4），否则输出领飞鸟的解（最优解）

31）

endfor

程序后

3.9 QMBCO流程

QMBCO的流程如图5所示。

4 仿真实验与算法性能评价

4.1 参数设置

为了检验算法性能，仿真实验以Visual Studio为开发环境，在CPU 2.83GHz、RAM 4GB的PC上运行。设置n（n∈{20，40，60，80，100}）为工件数，m（m∈{5，10，20}）为机器数，m和n共有15种不同的组合，每个组合产生10个调度实例。相关生产数据服从以下均匀分布：工件j在机器i上的批量加工时间pj，i∈U（1，50），工件πj的子批量数lπj∈U（1，5）。设定算法最大运行时间为 ρ×m×n，分享邻域大小Snum为1。对每个实例执行10次独立运算，其他参数各数值采用正交实验设计方法，表1是每个参数因素及其对应的水平值，表中imax、ps、Cnum、K和d分别表示表示最大迭代次数、种群大小、邻域大小、巡回次数和IG算法中序列的删减个数。

从表1的5因素3水平表可知，正交表可安排18组实验，即L18（37），将最后两列设置为空置列，如表2所示。

以n=60，m=10实例为实验数据，采用Taguchi实验方法[20]。Taguchi强调使用信噪比（S/N_ratio）来确定在噪声因素下对质量的影响。信噪比可以归类为中间值最好，越小越好和越大越好。在分析实验结果时， 信噪比值的计算能够很好地保护目标函数值。在大多数情况下，每个水平对应的目标值非常接近，因此信噪比的影响至关重要。本文信噪比计算公式如下：

S/N_ratio=-10lgf（s）2（12）

其中，f（s）是目标函数值，即最大完工时间。图6为各因素水平下平均信噪比关系图。

在QMBCO算法中，信噪比取较大值较好。通过计算每组实验的信噪比并绘制出各因素下平均信噪比值圖形，如图6所示。由图6可得，imax、ps、Cnum、K 和d的值分别在水平3、1、3、3、3时较大，故取参数imax=40，ps=71，Cnum=3，K=8，d=8。

4.2 性能比较

为验证所提算法的性能，将QMBCO算法与目前较优的离散粒子群优化算法（Discrete Particle Swarm Optimization， DPSO）[21]、量子布谷鸟协同搜索 （Quantuminspired Cuckoo CoSearch， QCCS）算法[22]和MBO[6]算法进行比较。以平均百分比偏差（Average Relative Percentage Deviation， ARPD）[19]作为评价标准，其计算公式如下：

ARPD=1N∑Ni=1（fi（H）-GiGi）×100%（13）

其中：N表示具有相同规模的实例个数，H表示参与比较的某一算法， fi（H）表示采用算法H求解实例i得到的目标值，Gi表示第i个实例在参与比较的几个算法中所得最小目标值。由式（13）可知，ARPD越小，算法优化效率越高。上述算法的ARPD比较如表3所示。此外，通过tTest将QMBCO与其他算法进行比较如表4所示，其值为1或-1表明前一算法在95%置信度上优于或劣于后一算法，值为0表明两种算法所得最大完工时间没有显著差别。

从表3和表4可以看出，当ρ=50时，QMBCO算法在所有实例中都优于DPSO和MBO算法。对于QCCS算法的比较，QMBCO算法在所有实例中除了20×10与100×5均更优。从表3和表4可以看出，当ρ=100时，QMBCO算法优于所有比较的算法。在两种不同运行时间下QMBCO与DPSO、MBO、QCCS相比ARPD平均下降65%、34%和24%。

为了更加直观地体现算法的寻优能力，本文采用方差分析法（ANalysis Of VAriance， ANOVA）[5]，用于所提算法与其他算法样本均数差别的显著性检验。图7中（a）和（b）分别表示在ρ=50，100时，四种算法在均值的95%置信区间下最小显著性差异（Least Significant Difference， LSD）的区间图。从图7（a）可以看出在ρ=50时，QMBCO较优于MBO与QCCS，明显优于DPSO。从图7（b）中从可以看出所提QMBCO明显优于所比较的三种算法。

5 結语

针对LFSP，本文提出了一种新的QMBCO算法。该算法是量子进化算法与候鸟优化算法的首次结合解决批量调度问题，通过模拟跟飞鸟替换领飞鸟过程，智能达到一种高效的寻优模式。算法采用Bloch量子球面编码方案扩大可行解空间，运用MBO及VNS算法增强收敛性。设定相同的算法终止时间并采用各个规模随机产生的实例进行仿真实验，与其他较优算法相比较证明所提算法的寻优能力。然而，本文采用数据集中工件数的大小仅适用于100以内，超过此范围则优化效率低，因此数据集规模大小是进一步研究的重点。

参考文献 （References）

[1]潘玉霞，谢光，肖衡. 离散和声求解带启动时间批量流水线调度问题[J]. 计算机应用， 2014， 34（2）：528-532. （PAN Y X， XIE G， XIAO H. Discrete harmony search algorithm for lotstreaming flow shop scheduling problem with setup time[J]. Journal of Computer Applications， 2014， 34（2）： 528-532.）

[2]REITER S. A system for managing jobshop production[J]. The Journal of Business， 1966， 39（3）：371-393.

[3]PAN Q， RUIZ R. An estimation of distribution algorithm for lotstreaming flow shop problems with setup times[J]. Omega， 2012， 40（2）： 166-180.

[4]SANG H， PAN Q， DUAN P， et al. An effective discrete invasive weed optimization algorithm for lotstreaming flowshop scheduling problems[J]. Journal of Intelligent Manufacturing， 2018， 29（6）： 1337-1349.

[5]MENG T， PAN Q， LI J， et al. An improved migrating birds optimization for an integrated lotstreaming flow shop scheduling problem[J]. Swarm and Evolutionary Computation， 2018， 38： 64-78.

[6]DUMAN E， UYSAL M， ALKAYA A F. Migrating birds optimization： a new metaheuristic approach and its performance on quadratic assignment problem[J]. Information Sciences， 2012， 217： 65-77.

[7]ZHANG B， PAN Q， GAO L， et al. An effective modified migrating birds optimization for hybrid flowshop scheduling problem with lot streaming[J]. Applied Soft Computing， 2017， 52： 14-27.

[8]SIOUD A， GAGN C. Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times[J]. European Journal of Operational Research， 2018， 264（1）： 66-73.

[9]NIROOMAND S， HADIVENCHEH A， SAHIN R， et al. Modified migrating birds optimization algorithm for closed loop layout with exact distances in flexible manufacturing systems[J]. Expert Systems with Applications， 2015， 42（19）： 6586-6597.

[10]TONGUR V， LKER E. The analysis of migrating birds optimization algorithm with neighborhood operator on traveling salesman problem[C]// Proceedings ofthe 19th Asia Pacific Symposium on Intelligent and Evolutionary Systems. Berlin： Springer， 2016： 227-237.

[11]NARAYANAN A， MOORE M. Quantuminspired genetic algorithms[C]// Proceedings of the 1996 IEEE International Conference on Evolutionary Computation. Piscataway： IEEE， 1996： 61-66.

[12]HAN K H， KIM J H. Quantuminspired evolutionary algorithm for a class of combinatorial optimization[J]. IEEE Transactions on Evolutionary Computation， 2002， 6（6）： 580-593.

[13]王錚，杨卫波，王万良，等. 基于量子进化算法的多轮廓路径优化[J]. 计算机集成制造系统， 2017， 23（10）： 2128-2135.（WANG Z， YANG W B， WANG W L， et al. Path optimization for multicontour based on quantum evolutionary algorithm[J]. Computer Integrated Manufacturing Systems， 2017， 23（10）： 2128-2135.）

[14]李士勇，李盼池. 量子计算与量子优化算法[M]. 哈尔滨： 哈尔滨工业大学出版社， 2009： 86-100. （LI S Y， LI P C. Quantum Computation and Quantum Optimization Algorithms[M]. Harbin： Harbin Institute of Technology Press， 2009： 86-100.）

[15]FRAMINAN J M， LEISTEN R. An efficient constructive heuristic for flowtime minimisation in permutation flow shops[J]. Omega， 2003， 31（4）： 311-317.

[16]谢展鹏. 基于候鸟优化算法的有限缓冲区流水车间调度优化研究[D].武汉：华中科技大学， 2015： 11-21. （XIE Z P. Migrating birds optimization algorithm for flow shop scheduling problem with limited buffers[D]. Wuhan： Huazhong University of Science and Technology， 2015：11-21.）

[17]齐学梅，王宏涛，陈付龙，等. 求解多目标PFSP的改进遗传算法[J]. 计算机工程与应用， 2015， 51（11）：242-247. （QI X M， WANG H T， CHEN F L， et al. Improved genetic algorithm for multiobjective of PFSP[J]. Computer Engineering and Applications， 2015， 51（11）： 242-247.）

[18]RUIZ R， PAN Q， NADERI B. Iterated greedy methods for the distributed permutation flowshop scheduling problem[J]. Omega， 2019， 83： 213-222.

[19]QI X， WANG H， ZHU H， et al. Fast local neighborhood search algorithm for the nowait flow shop scheduling with total flow time minimization[J]. International Journal of Production Research， 2016， 54（16）： 4957-4972.

[20]CHENG B， CHANG C. A study on flowshop scheduling problem combining Taguchi experimental design and genetic algorithm[J]. Expert Systems with Applications， 2007， 32（2）： 415-421.

[21]NOUIRI M， BEKRAR A， JEMAI A， et al. An effective and distributed particle swarm optimization algorithm for flexible jobshop scheduling problem[J]. Journal of Intelligent Manufacturing， 2018， 29（3）： 603-615.

[22]ZHU H， QI X， CHEN F， et al. Quantuminspired cuckoo cosearch algorithm for nowait flow shop scheduling[J]. Applied Intelligence， 2019， 49（2）： 791-803.

This work is partially supported by the National Natural Science Foundation of China （61572036）.

CHEN Linfeng， born in 1992， M. S. candidate. His research interests include quantum computing， intelligent scheduling.

QI Xuemei， born in 1963， M. S.， professor. Her research interests include quantum computing， intelligent scheduling.

CHEN Junwen， born in 1996， M. S. candidate. Her research interests include quantum computing， data mining.

HUANG Cheng， born in 1995， M. S. candidate. His research interests include cyberphysical system， security of the Internet of things.

CHEN Fulong， born in 1978， Ph. D.， professor. His research interests include embedded and pervasive computing， cyberphysical system.