批量流水調(diào)度問題的量子候鳥協(xié)同優(yōu)化算法

陳林烽 齊學梅 陳俊文 黃琤 陳付龍

摘 要：為了求解批量流水調(diào)度問題（LFSP）的最小化最大完工時間，提出一種量子候鳥協(xié)同優(yōu)化（QMBCO）算法。首先，采用Bloch量子球面編碼方案擴大解空間;然后，運用FL算法優(yōu)化初始解，以彌補傳統(tǒng)隨機初始解的不足，保證初始種群具有較高的質(zhì)量;最后，使用候鳥優(yōu)化（MBO）算法及變鄰域搜索（VNS）算法進行迭代，增強算法的全局搜索能力。采用隨機生成不同規(guī)模的實例仿真，將QMBCO算法與目前較優(yōu)的離散粒子群優(yōu)化（DPSO）算法、MBO算法和量子布谷鳥協(xié)同搜索（QCCS）算法相比較。結(jié)果表明，在兩種不同運行時間下QMBCO與DPSO、MBO、QCCS相比產(chǎn)生的最優(yōu)解平均百分比偏差（ARPD）分別平均下降65%、34%和24%，證明了QMBCO算法的有效性和高效性。

關鍵詞：批量流水調(diào)度問題;最大完工時間;候鳥優(yōu)化算法;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?引言

批量流水調(diào)度問題（Lotstreaming Flow shop Scheduling Problem， LFSP）是一類典型的調(diào)度問題，對其進行研究具有重要的理論意義和工程價值，廣泛存在于煉鋼、食品加工、化工和制藥等工業(yè)領域[1]。其概念最早是由Reiter[2]在1966年提出，傳統(tǒng)的優(yōu)化方法如線性規(guī)劃（Linear Programming， LP）、分支定界（Branch And Bound， BAB）不適合解決此類復雜的組合優(yōu)化問題，智能優(yōu)化算法成為求解此類調(diào)度問題的主要趨勢。

近年來，許多研究學者將智能優(yōu)化算法用于求解LFSP。例如，Pan等[3]提出解決批量流水調(diào)度問題分布式估計算法（Estimation of Distribution Algorithm， EDA），通過多種調(diào)度實例證明所提算法性能優(yōu)于混合遺傳算法（Hybird Genetic Algorithm， HGA）。Sang等[4]提出離散雜草入侵算法解決以序列相關最大完工時間的批量流水調(diào)度問題，通過與EDA，人工蜂群（Artificial Bee Colony， ABC）算法以及改進的羊群遺傳算法（Sheep Flock Heredity Algorithm， SFHA）比較證明其算法性能。近幾年，Meng等[5]相繼提出改進的候鳥優(yōu)化算法（Improved Migrating Birds Optimization， IMMBO）處理批量流水調(diào)度問題，通過多種調(diào)度實例證明其算法在處理各種批量問題的高效性。然而，這些算法大多沒有從算法整體的離散與收斂性考慮，隨著問題規(guī)模的擴大易陷入“局部最優(yōu)”。

候鳥優(yōu)化算法（Migrating Birds Optimization， MBO）[6]是由Duman等提出的一種新的元啟發(fā)式算法，算法通過模擬候鳥遷徙過程中的V字形編隊以減少能量損耗，因具有參數(shù)少、結(jié)構(gòu)簡單、易于理解、尋優(yōu)能力及局部搜索能力強等優(yōu)點而受到廣泛關注。該算法已經(jīng)成功應用于二次分配[6]、流水調(diào)度[7-8]、柔性制造系統(tǒng)[9]、經(jīng)典旅行商[10]等問題。但這些針對MBO算法的研究大多數(shù)只考慮單個算法的應用，并沒有結(jié)合其他算法進行優(yōu)劣互補，影響其整體的求解能力及效率。

量子遺傳算法（Quantum Genetic Algorithm， QGA）概念由Narayanan等[11]在1996年最先提出，Han等[12]基于此概念又提出量子進化算法（Quantuminspired Evolutionary Algorithm， QEA）并成功將其應用于背包問題。王錚等[13]采用量子進化算法及量子旋轉(zhuǎn)角優(yōu)化技術并將其成功應用至多輪廓路徑的優(yōu)化，驗證了其算法的可行性和有效性。雖然傳統(tǒng)量子進化算法在計算性能和優(yōu)化求解方面具有較好的能力，但單一使用也有收斂速度慢、易陷入局部最優(yōu)等缺點。

基于以上算法的缺陷，本文提出了一種量子候鳥協(xié)同優(yōu)化（Quantuminspired Migrating Birds CoOptimization， QMBCO）算法，用于求解批量流水調(diào)度問題中最小化最大完工時間。算法首先采用Bloch球面量子編碼方案[14]擴充全局最優(yōu)解的數(shù)量，并使用FL（FraminanLeisten）算法[15]改進初始解，有效提高種群質(zhì)量。采用MBO算法[16]與變鄰域搜索算法 （Variable Neighborhood Search， VNS）算法[17]迭代，進一步提高算法的局部搜索能力。QMBCO算法采用Bloch球面量子編碼方案并將啟發(fā)式算法和智能優(yōu)化算法相結(jié)合，優(yōu)劣互補。FL算法具有較強的探索能力，而MBO算法及VNS算法具有較強的求精能力，通過結(jié)合這幾種方案協(xié)同使整體具有較好的平衡能力。仿真實驗結(jié)果表明所提算法的優(yōu)越性。

1?問題描述

LFSP描述為：有m臺機器和n個工件，每個工件可分成若干小批量，每個小批量在各機床上加工順序相同，但加工時間可能不同。同時約定：1）同一機器上一個工件的所有小批量完成后另一個工件的小批量方可開始加工;2）所有機器上各工件小批量的加工次序完全相同;3）在任何時刻一臺機器只能夠加工一個小批量，一個小批量只能在一臺機器上加工;4）批量運輸時間包含在加工時間內(nèi);5）同一臺機器上相鄰批量之間機器可空閑。已知工件數(shù)和各批量在各臺機器上所需的加工時間，求滿足上述約束條件的可行調(diào)度，使工件的最大完成時間（Cmax）最短。

在n個工件m臺機器的調(diào)度中，令工件j={1，2，…，n}，機器i={1，2，…，m}為工件πj批量數(shù)。設π={π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臺機器最大完工時間的甘特圖。根據(jù)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?傳統(tǒng)MBO算法

MBO算法是一種新穎的智能優(yōu)化算法，類似于遺傳算法對生物進化的模擬、粒子群優(yōu)化算法對鳥群捕食過程的模擬等，MBO算法是對候鳥在遷徙過程中隊列個體排列次序的模擬。算法共5個步驟，群體中的候鳥稱為一個解，其基本流程如下：

步驟1?初始化。設置4個參數(shù)分別為種群大小，每個解的鄰域數(shù)量a、傳遞給下一個解的鄰域數(shù)量b、種群所有個體的巡回次數(shù)、優(yōu)化次數(shù)c等。

步驟2?領飛鳥進化。在領飛鳥周圍隨機生成a個鄰域，搜索這些鄰域，若找到比領飛鳥更優(yōu)的最優(yōu)解則替換領飛鳥，若沒有則不替換。然后將未被使用的鄰域按照目標值從優(yōu)到劣的順序排序，把最好的2b個鄰域平均分配給其后左右兩只跟飛鳥作為其鄰域的一部分。

步驟3?優(yōu)化跟飛鳥。跟飛鳥的鄰域由上一只鳥傳遞給它的b個個體和在它周圍隨機產(chǎn)生的a-b個個體組成，搜索這a個個體中最優(yōu)個體，若優(yōu)于跟飛鳥則替換，否則跟飛鳥不變。同樣將鄰域中未被使用的b個最好的鄰域傳遞給下一個跟飛鳥作為其鄰域的一部分。跟飛鳥的優(yōu)化是從隊首向隊尾逐個進行，左右兩邊分別進行，直到所有的跟飛鳥都進行一次鄰域搜索后，一次跟飛鳥優(yōu)化完成。

步驟4?在種群中產(chǎn)生新的領飛鳥。循環(huán)步驟2、3至c次，在領飛鳥左右兩只鳥中選擇較好的一只作為新的領飛鳥，被替換的領飛鳥回到隊尾。

步驟5?直到達到設定迭代次數(shù)后停止該算法，否則重復步驟2～步驟5。

3?量子候鳥協(xié)同優(yōu)化（QMBCO）算法

由于傳統(tǒng)MBO算法是針對二次分配這種連續(xù)函數(shù)優(yōu)化問題而提出，不能直接用于處理LFSP這類離散的組合優(yōu)化問題，需要轉(zhuǎn)換成離散形式。本文基于傳統(tǒng)候鳥優(yōu)化算法，結(jié)合LFSP求解，提出一種新的QMBCO算法，包括基于Bloch球面量子編碼、種群初始化、領飛鳥優(yōu)化、跟飛鳥優(yōu)化、領飛鳥的替換、變鄰域搜索策略等，可有效應用于求解批量流水調(diào)度問題。

3.1?基于Bloch球面坐標量子編碼

在量子計算中，量子比特是最小的信息單位。有兩種狀態(tài)“0”和“1”，即量子線性疊加態(tài)，可由式（6）表示：

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

其中：|φ〉量子比特狀態(tài)，量子角θ∈[0，π]，φ∈[0，2π]。cos（θ/2）和eiφsin（θ/2）是一對復數(shù)，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是量子位數(shù)，φi（1≤i≤n），θi（1≤i≤n）分別在（0， 2π）和（0， π）內(nèi)隨機生成。

在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，量子位數(shù)n表示工件個數(shù)，工件的加工序列對應量子種群根據(jù)LOV（Largest Order Value）規(guī)則生成的加工序列π={π1，π2，…，πn}。

3.2?種群初始化

初始化種群是QMBCO算法優(yōu)化的起點，好的初始種群能有效提高算法的性能[5]。候鳥種群的初始化，設種群個體數(shù)為ps，根據(jù)相關數(shù)據(jù)實驗設置其他參數(shù)值，種群中的每只候鳥對應一個解。FL算法基于NEH（Nawaz， Enscore， and Ham）算法的改進，是求解流水調(diào)度中啟發(fā)式算法性能較好的一種[15]，其原理是采用交換鄰域、插入鄰域兩種搜索模式，以改善部分序列，本文采用FL算法產(chǎn)生初始解，保證初始候鳥具有較高的質(zhì)量。為了使初始種群具有全局性，本文采用Bloch球面坐標解碼與FL算法結(jié)合的方法產(chǎn)生初始種群的所有個體，計算各自的最大完成時間，將最大完成時間最短的鳥作為初始鳥群的領飛鳥，并將種群中剩下的鳥均分到V形的左右兩邊。分別使用兩個數(shù)組Lp和Rp存儲，形成初始V形隊形，用數(shù)組Sn_L和Sn_R表示V形隊列左右兩邊個體分享給下一個個體的鄰域解集合。

3.3?領飛鳥優(yōu)化

領飛鳥的優(yōu)化采用迭代貪婪（Iterated Greedy，IG）算法[18]進行循環(huán)迭代。本文利用IG算法中刪減和插入的思想生成領飛鳥的Cnum個鄰域解，并進行評估比較。具體的實現(xiàn)方法如下：

1）首先參考相關實驗數(shù)據(jù)，根據(jù)分析結(jié)果設定一個合適的參數(shù)值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）若生成的鄰域解數(shù)量小于Cnum，重復2）～4）操作;否則操作停止。

6）完成上述操作后將領飛鳥的鄰域解存入數(shù)組LBc中，計算鄰域解集合中最大完工時間最短的序列，比較該序列與當前領飛鳥序列的最大完工時間，若該序列更優(yōu)則替換當前領飛鳥，否則領飛鳥不變。

3.4?跟飛鳥優(yōu)化

為了保證算法的搜索性能，對跟飛鳥與領飛鳥采用不同的優(yōu)化策略。跟飛鳥鄰域解采用隨機選擇交換和插入的方法。隨機選擇跟飛鳥序列中的位置，執(zhí)行交換（SWAP）和插入（INSERT）操作，實現(xiàn)跟飛鳥鄰域解集合的構(gòu)建。

1） 執(zhí)行SWAP方法。在序列長度的范圍內(nèi)隨機生成兩個不相等的隨機數(shù)x、y，將跟飛鳥序列πfellow={π1，π2，…，πn}中x和y位上的πx和πy進行交換，從而產(chǎn)生新的序列。例如，序列{2，4，6，3，1，5}中第3位和第5位上的6和1執(zhí)行交換操作產(chǎn)生新的序列{2，4，1，3，6，5}，交換過程如圖3所示。

2） 執(zhí)行INSERT方法。在序列長度的范圍內(nèi)隨機生成兩個不相等的隨機數(shù)x、y，將跟飛鳥序列πfellow={π1，π2，…，πn}中x位上的πx插入到y(tǒng)位上，從而產(chǎn)生新的序列。例如，序列{2，4，6，3，1，5}中第3位上的6插入到第5位，產(chǎn)生新的序列{2，4，3，1，6，5}，插入過程如圖4所示。

3.5?領飛鳥替換

當巡回次數(shù)達到后，則進行領飛鳥的替換。V形編隊有左右兩個隊列，輪流用左邊隊列和右邊隊列的第一只鳥對領飛鳥進行替換，并將原來領飛鳥移至相應左右兩翼隊末。

3.6?VNS算法

VNS算法是已被證明了的具有增強種群收斂且適合求解流水調(diào)度問題[18]的啟發(fā)式算法， 其基本思想是在搜索過程中系統(tǒng)地改變鄰域結(jié)構(gòu)集來拓展搜索范圍，獲得局部最優(yōu)解，再基于此局部最優(yōu)解來拓展搜索范圍找到另一個局部最優(yōu)解的過程。本文采用一種改進的VNS算法，該算法結(jié)合成對交換搜索（PairExchange Search， PES）算法、插入搜索（Insertion Search， IS）、剪切修復插入搜索（Insertion Search with CutandRepair， ISCR），從而有利于算法跳出局部最優(yōu)，增加獲得全局最優(yōu)解的概率。本文對MBO算法處理后的解執(zhí)VNS算法，循環(huán)直至收斂。在此結(jié)構(gòu)中，MBO及VNS算法具有較強的局部搜索能力，可豐富當前解的鄰域結(jié)構(gòu)，增強算法全局搜索能力。

3.7?全局收斂性

因MBO算法具有全局收斂性[6]，而VNS算法有較強的局部收斂性[19]。QMBCO算法通過MBO及VNS算法迭代至最優(yōu)解，故具有全局收斂性。

3.8?算法描述

根據(jù)3.1～3.6節(jié)的內(nèi)容，QMBCO的具體描述如下：

算法1?QMBCO算法。

輸入?ps， Cnum， Snum， K， imax;

輸出?最優(yōu)解Xled。

程序前

1）

定義參數(shù)ps， Cnum， Snum， K， imax， Lp，Rp， Sn_L， Sn_R， LBc， FBc， Nbest， Xled;

2）

初始化種群，隨機生成ps個個體{X1，X2，…，Xps};

3）

執(zhí)行Bloch球面坐標量子編碼種群X={X1，X2，…，Xps}←Encoding，生成ps個調(diào)度序列π，輸出調(diào)度序列中最小目標值作為初始解π′其進行FL算法優(yōu)化;

4）

Xled=Min{X1，X2，…，Xps}，找出種群中目標值最小的個體作為領飛鳥Xled，并將剩下的鳥均分到V形兩邊，填入數(shù)組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個鄰域解隨機填入數(shù)組Sn_L和Sn_R，使得兩數(shù)組都包含Snum個解;//Cmax為批量流水調(diào)度的目標值

10）

for m1←1 to （ps-1）/2//左邊跟飛鳥優(yōu)化

11）

隨機使用SWAP和INSERT的方法生成 Lp[m1]的Cnum-Snum個鄰域解，然后和Sn_L合并構(gòu)成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//右邊跟飛鳥優(yōu)化

17）

隨機使用SWAP和INSERT方法生成Rp[m2]的Cnum-Snum個鄰域解，然后和Sn_R合并構(gòu)成 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）

對當前解執(zhí)行VNS優(yōu)化，若更優(yōu)則賦值給領飛鳥的解;

30）

判斷是否達到迭代次數(shù)，若未達到則轉(zhuǎn)至步驟4），否則輸出領飛鳥的解（最優(yōu)解）

31）

endfor

程序后

3.9?QMBCO流程

QMBCO的流程如圖5所示。

4?仿真實驗與算法性能評價

4.1?參數(shù)設置

為了檢驗算法性能，仿真實驗以Visual Studio為開發(fā)環(huán)境，在CPU 2.83GHz、RAM 4GB的PC上運行。設置n（n∈{20，40，60，80，100}）為工件數(shù)，m（m∈{5，10，20}）為機器數(shù)，m和n共有15種不同的組合，每個組合產(chǎn)生10個調(diào)度實例。相關生產(chǎn)數(shù)據(jù)服從以下均勻分布：工件j在機器i上的批量加工時間pj，i∈U（1，50），工件πj的子批量數(shù)lπj∈U（1，5）。設定算法最大運行時間為 ρ×m×n，分享鄰域大小Snum為1。對每個實例執(zhí)行10次獨立運算，其他參數(shù)各數(shù)值采用正交實驗設計方法，表1是每個參數(shù)因素及其對應的水平值，表中imax、ps、Cnum、K和d分別表示表示最大迭代次數(shù)、種群大小、鄰域大小、巡回次數(shù)和IG算法中序列的刪減個數(shù)。

從表1的5因素3水平表可知，正交表可安排18組實驗，即L18（37），將最后兩列設置為空置列，如表2所示。

以n=60，m=10實例為實驗數(shù)據(jù)，采用Taguchi實驗方法[20]。Taguchi強調(diào)使用信噪比（S/N_ratio）來確定在噪聲因素下對質(zhì)量的影響。信噪比可以歸類為中間值最好，越小越好和越大越好。在分析實驗結(jié)果時， 信噪比值的計算能夠很好地保護目標函數(shù)值。在大多數(shù)情況下，每個水平對應的目標值非常接近，因此信噪比的影響至關重要。本文信噪比計算公式如下：

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

其中，f（s）是目標函數(shù)值，即最大完工時間。圖6為各因素水平下平均信噪比關系圖。

在QMBCO算法中，信噪比取較大值較好。通過計算每組實驗的信噪比并繪制出各因素下平均信噪比值圖形，如圖6所示。由圖6可得，imax、ps、Cnum、K 和d的值分別在水平3、1、3、3、3時較大，故取參數(shù)imax=40，ps=71，Cnum=3，K=8，d=8。

4.2?性能比較

為驗證所提算法的性能，將QMBCO算法與目前較優(yōu)的離散粒子群優(yōu)化算法（Discrete Particle Swarm Optimization， DPSO）[21]、量子布谷鳥協(xié)同搜索 （Quantuminspired Cuckoo CoSearch， QCCS）算法[22]和MBO[6]算法進行比較。以平均百分比偏差（Average Relative Percentage Deviation， ARPD）[19]作為評價標準，其計算公式如下：

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

其中：N表示具有相同規(guī)模的實例個數(shù)，H表示參與比較的某一算法， fi（H）表示采用算法H求解實例i得到的目標值，Gi表示第i個實例在參與比較的幾個算法中所得最小目標值。由式（13）可知，ARPD越小，算法優(yōu)化效率越高。上述算法的ARPD比較如表3所示。此外，通過tTest將QMBCO與其他算法進行比較如表4所示，其值為1或-1表明前一算法在95%置信度上優(yōu)于或劣于后一算法，值為0表明兩種算法所得最大完工時間沒有顯著差別。

從表3和表4可以看出，當ρ=50時，QMBCO算法在所有實例中都優(yōu)于DPSO和MBO算法。對于QCCS算法的比較，QMBCO算法在所有實例中除了20×10與100×5均更優(yōu)。從表3和表4可以看出，當ρ=100時，QMBCO算法優(yōu)于所有比較的算法。在兩種不同運行時間下QMBCO與DPSO、MBO、QCCS相比ARPD平均下降65%、34%和24%。

為了更加直觀地體現(xiàn)算法的尋優(yōu)能力，本文采用方差分析法（ANalysis Of VAriance， ANOVA）[5]，用于所提算法與其他算法樣本均數(shù)差別的顯著性檢驗。圖7中（a）和（b）分別表示在ρ=50，100時，四種算法在均值的95%置信區(qū)間下最小顯著性差異（Least Significant Difference， LSD）的區(qū)間圖。從圖7（a）可以看出在ρ=50時，QMBCO較優(yōu)于MBO與QCCS，明顯優(yōu)于DPSO。從圖7（b）中從可以看出所提QMBCO明顯優(yōu)于所比較的三種算法。

5?結(jié)語

針對LFSP，本文提出了一種新的QMBCO算法。該算法是量子進化算法與候鳥優(yōu)化算法的首次結(jié)合解決批量調(diào)度問題，通過模擬跟飛鳥替換領飛鳥過程，智能達到一種高效的尋優(yōu)模式。算法采用Bloch量子球面編碼方案擴大可行解空間，運用MBO及VNS算法增強收斂性。設定相同的算法終止時間并采用各個規(guī)模隨機產(chǎn)生的實例進行仿真實驗，與其他較優(yōu)算法相比較證明所提算法的尋優(yōu)能力。然而，本文采用數(shù)據(jù)集中工件數(shù)的大小僅適用于100以內(nèi)，超過此范圍則優(yōu)化效率低，因此數(shù)據(jù)集規(guī)模大小是進一步研究的重點。

參考文獻 （References）

[1]潘玉霞，謝光，肖衡. 離散和聲求解帶啟動時間批量流水線調(diào)度問題[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]王錚，楊衛(wèi)波，王萬良，等. 基于量子進化算法的多輪廓路徑優(yōu)化[J]. 計算機集成制造系統(tǒng)， 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]李士勇，李盼池. 量子計算與量子優(yōu)化算法[M]. 哈爾濱： 哈爾濱工業(yè)大學出版社， 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]謝展鵬. 基于候鳥優(yōu)化算法的有限緩沖區(qū)流水車間調(diào)度優(yōu)化研究[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.