陳林烽 齊學(xué)梅 陳俊文 黃琤 陳付龍

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

關(guān)鍵詞：批量流水調(diào)度問(wèn)題;最大完工時(shí)間;候鳥(niǎo)優(yōu)化算法;Bloch量子球面編碼;變鄰域搜索算法;平均百分比偏差

中圖分類(lèi)號(hào)：TP301.6

文獻(xiàn)標(biāo)志碼：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)度問(wèn)題（Lotstreaming Flow shop Scheduling Problem， LFSP）是一類(lèi)典型的調(diào)度問(wèn)題，對(duì)其進(jìn)行研究具有重要的理論意義和工程價(jià)值，廣泛存在于煉鋼、食品加工、化工和制藥等工業(yè)領(lǐng)域[1]。其概念最早是由Reiter[2]在1966年提出，傳統(tǒng)的優(yōu)化方法如線性規(guī)劃（Linear Programming， LP）、分支定界（Branch And Bound， BAB）不適合解決此類(lèi)復(fù)雜的組合優(yōu)化問(wèn)題，智能優(yōu)化算法成為求解此類(lèi)調(diào)度問(wèn)題的主要趨勢(shì)。

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

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

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

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

1?問(wèn)題描述

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

在n個(gè)工件m臺(tái)機(jī)器的調(diào)度中，令工件j={1，2，…，n}，機(jī)器i={1，2，…，m}為工件πj批量數(shù)。設(shè)π={π1，π2，…，πn}處理的工件序列，πk為序列π的第k個(gè)工件，pj，i為工件j在機(jī)器i上的批量加工時(shí)間，Sj，i，q為工件j在機(jī)器i上第q個(gè)批量的最早開(kāi)始加工時(shí)間，Cj，i，q為工件j在機(jī)器i上第q個(gè)批量的最早完工時(shí)間，Cmax（π）為序列π的最大完工時(shí)間。圖1所描述的是3個(gè)工件和3臺(tái)機(jī)器最大完工時(shí)間的甘特圖。根據(jù)LFSP的特征，本文提出計(jì)算最大完工時(shí)間的計(jì)算方法如下：

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)化算法，類(lèi)似于遺傳算法對(duì)生物進(jìn)化的模擬、粒子群優(yōu)化算法對(duì)鳥(niǎo)群捕食過(guò)程的模擬等，MBO算法是對(duì)候鳥(niǎo)在遷徙過(guò)程中隊(duì)列個(gè)體排列次序的模擬。算法共5個(gè)步驟，群體中的候鳥(niǎo)稱為一個(gè)解，其基本流程如下：

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

步驟2?領(lǐng)飛鳥(niǎo)進(jìn)化。在領(lǐng)飛鳥(niǎo)周?chē)S機(jī)生成a個(gè)鄰域，搜索這些鄰域，若找到比領(lǐng)飛鳥(niǎo)更優(yōu)的最優(yōu)解則替換領(lǐng)飛鳥(niǎo)，若沒(méi)有則不替換。然后將未被使用的鄰域按照目標(biāo)值從優(yōu)到劣的順序排序，把最好的2b個(gè)鄰域平均分配給其后左右兩只跟飛鳥(niǎo)作為其鄰域的一部分。

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

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

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

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

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

3.1?基于Bloch球面坐標(biāo)量子編碼

在量子計(jì)算中，量子比特是最小的信息單位。有兩種狀態(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）是一對(duì)復(fù)數(shù)，cos（θ/2）2和eiφsin（θ/2）2分別表示量子位處于|0〉和|1〉的概率，且滿足：

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

因此，量子比特可以用三維Bloch球面上的一點(diǎn)P（cosφsinθ，sinφsinθ，cosθ）描述，如圖2所示。在QMBCO算法中，采用量子比特的Bloch坐標(biāo)編碼種群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)隨機(jī)生成。

在QMBCO算法中，每個(gè)種群量子比特都可分解在Bloch球面上的x、y、z三個(gè)位置上，即可表示為種群的三個(gè)位置，分別為：

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）

對(duì)于LFSP，量子位數(shù)n表示工件個(gè)數(shù)，工件的加工序列對(duì)應(yīng)量子種群根據(jù)LOV（Largest Order Value）規(guī)則生成的加工序列π={π1，π2，…，πn}。

3.2?種群初始化

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

3.3?領(lǐng)飛鳥(niǎo)優(yōu)化

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

1）首先參考相關(guān)實(shí)驗(yàn)數(shù)據(jù)，根據(jù)分析結(jié)果設(shè)定一個(gè)合適的參數(shù)值d（1

2）對(duì)當(dāng)前的領(lǐng)飛鳥(niǎo)序列Xled={π1，π2，…，πn}，隨機(jī)刪減序列Xled中的d個(gè)工件，并將被刪減的這d個(gè)工件依次存入序列πd中， Xled刪減d個(gè)工件之后的序列記為Xled′={π1，π2，…，πn-d}，令i=1。

3）將πd中的第i個(gè)工件插入Xled′中的所有空位，分別評(píng)估計(jì)算插入工件后序列的最大完工時(shí)間，保留最大完工時(shí)間最短的序列作為新的Xled′。

4）如果i

5）若生成的鄰域解數(shù)量小于Cnum，重復(fù)2）～4）操作;否則操作停止。

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

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

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

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

2） 執(zhí)行INSERT方法。在序列長(zhǎng)度的范圍內(nèi)隨機(jī)生成兩個(gè)不相等的隨機(jī)數(shù)x、y，將跟飛鳥(niǎo)序列π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}，插入過(guò)程如圖4所示。

3.5?領(lǐng)飛鳥(niǎo)替換

當(dāng)巡回次數(shù)達(dá)到后，則進(jìn)行領(lǐng)飛鳥(niǎo)的替換。V形編隊(duì)有左右兩個(gè)隊(duì)列，輪流用左邊隊(duì)列和右邊隊(duì)列的第一只鳥(niǎo)對(duì)領(lǐng)飛鳥(niǎo)進(jìn)行替換，并將原來(lái)領(lǐng)飛鳥(niǎo)移至相應(yīng)左右兩翼隊(duì)末。

3.6?VNS算法

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

3.7?全局收斂性

因MBO算法具有全局收斂性[6]，而VNS算法有較強(qiáng)的局部收斂性[19]。QMBCO算法通過(guò)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）

初始化種群，隨機(jī)生成ps個(gè)個(gè)體{X1，X2，…，Xps};

3）

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

4）

Xled=Min{X1，X2，…，Xps}，找出種群中目標(biāo)值最小的個(gè)體作為領(lǐng)飛鳥(niǎo)Xled，并將剩下的鳥(niǎo)均分到V形兩邊，填入數(shù)組Lp，Rp中;

5）

for i←1 to imax

6）

for j←1 to K

7）

用IG算法生成領(lǐng)飛鳥(niǎo)的Cnum個(gè)鄰域解LBc，其中LBc[]={N1，N2，…，NCnum}，Nbest[]=Min{N1，N2，…，NCnum};

8）

if f（Nbest）

/*f（x）為序列x的目標(biāo)值*/

9）

將LBc中未被使用的Cmax最佳的2Snum個(gè)鄰域解隨機(jī)填入數(shù)組Sn_L和Sn_R，使得兩數(shù)組都包含Snum個(gè)解;//Cmax為批量流水調(diào)度的目標(biāo)值

10）

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

11）

隨機(jī)使用SWAP和INSERT的方法生成 Lp[m1]的Cnum-Snum個(gè)鄰域解，然后和Sn_L合并構(gòu)成Lp[m1]的鄰域解集合FBc[m1];

12）

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

13）

if f（Nbest）

14）

將FBc[]中未被使用的Cmax最佳的Snum個(gè)鄰域解填入Sn_L;

15）

endfor

16）

for m2←1 to （ps-1）/2//右邊跟飛鳥(niǎo)優(yōu)化

17）

隨機(jī)使用SWAP和INSERT方法生成Rp[m2]的Cnum-Snum個(gè)鄰域解，然后和Sn_R合并構(gòu)成 Rp[m2]的鄰域解集合 FBc[m2];

18）

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

19）

if f（Nbest）

20）

將 FBc[]中未被使用的Cmax最佳的Snum個(gè)鄰域解填入Sn_R;

21）

endfor

22）

endfor

23）

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

24）

領(lǐng)飛鳥(niǎo)回到右邊隊(duì)尾;

25）

Xled=Rp[1];

26）

else

27）

領(lǐng)飛鳥(niǎo)回到左邊隊(duì)尾;

28）

Xled=Lp[1];

29）

對(duì)當(dāng)前解執(zhí)行VNS優(yōu)化，若更優(yōu)則賦值給領(lǐng)飛鳥(niǎo)的解;

30）

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

31）

endfor

程序后

3.9?QMBCO流程

QMBCO的流程如圖5所示。

4?仿真實(shí)驗(yàn)與算法性能評(píng)價(jià)

4.1?參數(shù)設(shè)置

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

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

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

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

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

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

4.2?性能比較

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

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

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

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

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

5?結(jié)語(yǔ)

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

參考文獻(xiàn) （References）

[1]潘玉霞，謝光，肖衡. 離散和聲求解帶啟動(dòng)時(shí)間批量流水線調(diào)度問(wèn)題[J]. 計(jì)算機(jī)應(yīng)用， 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)波，王萬(wàn)良，等. 基于量子進(jìn)化算法的多輪廓路徑優(yōu)化[J]. 計(jì)算機(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]李士勇，李盼池. 量子計(jì)算與量子優(yōu)化算法[M]. 哈爾濱： 哈爾濱工業(yè)大學(xué)出版社， 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]謝展鵬. 基于候鳥(niǎo)優(yōu)化算法的有限緩沖區(qū)流水車(chē)間調(diào)度優(yōu)化研究[D].武漢：華中科技大學(xué)， 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]齊學(xué)梅，王宏濤，陳付龍，等. 求解多目標(biāo)PFSP的改進(jìn)遺傳算法[J]. 計(jì)算機(jī)工程與應(yīng)用， 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.