閆紅超，湯偉*，姚斌

（1.陜西科技大學(xué)電氣與控制工程學(xué)院，西安 710021；2.陜西科技大學(xué)電子信息與人工智能學(xué)院，西安 710021）

0 引言

生產(chǎn)調(diào)度是實(shí)現(xiàn)先進(jìn)制造的基礎(chǔ)和關(guān)鍵，高質(zhì)量的調(diào)度方案能夠降低生產(chǎn)成本、提高資源利用率和生產(chǎn)效率，從而增強(qiáng)企業(yè)的競(jìng)爭(zhēng)力。置換流水車(chē)間調(diào)度問(wèn)題（Permutation Flowshop Scheduling Problem，PFSP）主要研究n個(gè)工件在m臺(tái)機(jī)器上的加工過(guò)程，目的是找到一個(gè)工件排序使得調(diào)度目標(biāo)最優(yōu)?；赑FSP 的生產(chǎn)模式在制造業(yè)中存在廣泛的應(yīng)用場(chǎng)景；然而，3 臺(tái)機(jī)器以上的PFSP 屬于NP-hard 問(wèn)題［1］，求解困難，因此，研究和開(kāi)發(fā)高效的求解算法具有重要的理論價(jià)值和現(xiàn)實(shí)意義。

解決PFSP 的有效方法包括最優(yōu)求解法和近似求解法。最優(yōu)求解法是基于模型的方法，主要有分支定界、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃以及拉格朗日松弛法等。由于計(jì)算復(fù)雜度高，最優(yōu)求解法通常僅適用于求解小規(guī)模的PFSP［2］。近似求解法主要包括啟發(fā)式算法和元啟發(fā)式算法。啟發(fā)式算法主要有NEH（Nawaz-Enscore-Ham）算法［3］、Johnson 規(guī)則［4］等，這些算法雖然能在短時(shí)間內(nèi)構(gòu)造出解，但難以保證質(zhì)量。近年來(lái)元啟發(fā)式算法在車(chē)間調(diào)度中得到了廣泛的應(yīng)用，主要有基于變鄰域搜索的粒子群優(yōu)化（Particle Swarm Optimization based on Variable Neighborhood Search，PSOVNS）算法［5］、分布估計(jì)算法（Estimation of Distribution Algorithm，EDA）［6］、Liu 等［7］提出的混合差分進(jìn)化（Hybrid Differential Evolution algorithm proposed by Liu et al，L-HDE）算法、雙種群協(xié)同學(xué)習(xí)（Double Population Co-Learning，DPCL）算法［8］、混合共生生物搜索（Hybrid Symbiotic Organisms Search，HSOS）算法［9］等。

鳥(niǎo)群算法（Bird Swarm Algorithm，BSA）是由Meng 等［10］提出的一種基于鳥(niǎo)群行為的群智能優(yōu)化算法，主要思想來(lái)源于對(duì)鳥(niǎo)群覓食、警戒和飛行等群體行為的模擬以及對(duì)鳥(niǎo)群覓食過(guò)程中共享信息的研究。相比差分進(jìn)化算法、粒子群優(yōu)化算法等常見(jiàn)的傳統(tǒng)優(yōu)化算法，該算法獨(dú)有的多路徑搜索機(jī)制使其更好地平衡了高效性與準(zhǔn)確性［11］。BSA 已經(jīng)在動(dòng)態(tài)能耗管理［11］、微電網(wǎng)優(yōu)化配置［12］、離散智能車(chē)間調(diào)度［13］和柔性作業(yè)車(chē)間調(diào)度［14］等方面得到了應(yīng)用。

目前還查閱不到基于鳥(niǎo)群算法對(duì)置換流水車(chē)間調(diào)度問(wèn)題（PFSP）的研究。本文針對(duì)以最大完工時(shí)間最小化為目標(biāo)的PFSP，提出了一種混合鳥(niǎo)群算法（Hybrid Bird Swarm Algorithm，HBSA）進(jìn)行求解。首先，結(jié)合一種基于NEH 的啟發(fā)式算法和混沌映射提出了一種新的種群初始化方法，以改善初始種群的質(zhì)量和多樣性；其次，采用最大排序值（Largest Ranked Value，LRV）規(guī)則［7］將連續(xù)的位置值轉(zhuǎn)換為離散的工件排序，從而使算法能夠處理離散的調(diào)度問(wèn)題；最后，借鑒變鄰域搜索（Variable Neighborhood Search，VNS）和迭代貪婪（Iterated Greedy，IG）算法的思想針對(duì)個(gè)體最佳工件排序和種群最佳工件排序分別提出了局部搜索方法，以強(qiáng)化算法對(duì)解空間的探索能力。針對(duì)廣泛使用的Rec標(biāo)準(zhǔn)測(cè)試集［15］進(jìn)行仿真測(cè)試，并將結(jié)果與多種算法的結(jié)果進(jìn)行比較，以驗(yàn)證算法的性能。

1 置換流水車(chē)間調(diào)度問(wèn)題

置換流水車(chē)間調(diào)度問(wèn)題的描述為：已知各個(gè)工件在各臺(tái)機(jī)器上的加工時(shí)間，要求找到各工件在機(jī)器上的加工順序使得某個(gè)調(diào)度目標(biāo)最優(yōu)。相關(guān)的約束條件有：一臺(tái)機(jī)器在同一時(shí)刻只能加工一個(gè)工件；一個(gè)工件在同一時(shí)刻只能被一臺(tái)機(jī)器加工；每臺(tái)機(jī)器上的工件加工順序相同；工件一旦在機(jī)器上開(kāi)始加工就不能中斷；不考慮所有工件的準(zhǔn)備時(shí)間；開(kāi)始時(shí)間為零。

生產(chǎn)調(diào)度的最終目的是在滿(mǎn)足約束條件的前提下，合理安排現(xiàn)有資源、提高生產(chǎn)效率，使成本最小化或效益最大化，因此最小化最大完工時(shí)間是主要的調(diào)度目標(biāo)。

假 設(shè)J={J1，J2，…，Jn} 為n個(gè)工件的集合；M={M1，M2，…，Mm} 為m臺(tái)機(jī)器的集合 ；π=[π(1)，π(2)，…，π(n)]為所有工件的一個(gè)排序，表示加工順序?yàn)閺摩?1)到π(n)；P(i，j)為工件π(i)在機(jī)器Mj上的加工時(shí)長(zhǎng)；C(i，j)為工件π(i)在機(jī)器Mj上的完工時(shí)間。各個(gè)工件在各臺(tái)機(jī)器上的完工時(shí)間可按照如下方法進(jìn)行計(jì)算：

工件排序π對(duì)應(yīng)的最大完工時(shí)間Cmax為最后一個(gè)工件在最后一臺(tái)機(jī)器上的完工時(shí)間，即

求解以最大完工時(shí)間最小化為調(diào)度目標(biāo)的PFSP，目的是找到一個(gè)工件排序π*，使得：

式中Π為所有工件排序的集合。

PFSP 是一種典型的組合優(yōu)化問(wèn)題，且有研究表明3 臺(tái)機(jī)器以上的PFSP 屬于NP-hard 問(wèn)題，具有指數(shù)爆炸、工序相關(guān)等復(fù)雜性，求解非常困難。針對(duì)該問(wèn)題，本文提出一種混合鳥(niǎo)群算法（HBSA），用于更加有效地最小化最大完工時(shí)間。

2 混合鳥(niǎo)群算法

2.1 基本鳥(niǎo)群算法（BSA）

如果rand(0，1) ＜P，則鳥(niǎo)兒進(jìn)行覓食；否則進(jìn)行警戒。rand(0，1)為(0，1)區(qū)間均勻分布的隨機(jī)數(shù)，P為(0，1)區(qū)間的一個(gè)固定值。

覓食行為的位置更新策略為：

式中：C為認(rèn)知加速系數(shù)；S為社會(huì)加速系數(shù)；pi表示第i只鳥(niǎo)的歷史最優(yōu)位置；g代表整個(gè)種群的歷史最優(yōu)位置；t=1 時(shí)，每只鳥(niǎo)的歷史最優(yōu)位置為其初始位置，種群的歷史最優(yōu)位置為初始種群的最優(yōu)位置。

警戒行為的位置更新策略為：

假設(shè)每隔FQ間隔，鳥(niǎo)群會(huì)飛到另一個(gè)地方，F(xiàn)Q是一個(gè)正整數(shù)。

生產(chǎn)者的位置更新策略為：

式中：randn(0，1)表示均值為0、標(biāo)準(zhǔn)差為1 服從高斯分布的隨機(jī)數(shù)。

乞食者的位置更新策略為：

式中：FL∈[0，2]表示乞食者跟隨生產(chǎn)者去尋找食物。

2.2 求解PFSP的混合鳥(niǎo)群算法

基本鳥(niǎo)群算法僅適用于求解連續(xù)性問(wèn)題，對(duì)于離散的PFSP 不能直接使用；與其他群智能優(yōu)化算法相似，基本鳥(niǎo)群算法在處理復(fù)雜問(wèn)題時(shí)，存在易陷入局部最優(yōu)、易過(guò)早收斂、收斂精度差等缺點(diǎn)。

為了彌補(bǔ)上述不足，采用LRV 規(guī)則將連續(xù)的位置值轉(zhuǎn)換為離散的工件排序，使得算法可用于求解PFSP；結(jié)合一種基于NEH 的啟發(fā)式算法和混沌映射來(lái)初始化種群，以改善初始種群的質(zhì)量和多樣性、提升算法迭代的效率；借鑒變鄰域搜索和迭代貪婪算法的思想對(duì)個(gè)體最佳工件排序和種群最佳工件排序進(jìn)行局部搜索，以強(qiáng)化算法對(duì)解空間的探索能力，從而提出了一種混合鳥(niǎo)群算法（HBSA）。HBSA 的流程如圖1 所示，其中，種群（個(gè)體）最佳工件排序是指種群（個(gè)體）歷史最優(yōu)解對(duì)應(yīng)的工件排序。

圖1 HBSA流程Fig.1 Flow chart of HBSA

2.2.1 編碼方式與LRV轉(zhuǎn)換

采用LRV 規(guī)則將表示位置的一組連續(xù)值映射成工件排序，使鳥(niǎo)群算法能用于解決離散的PFSP。具體方法是每次從代表位置的一組連續(xù)值中選擇最大值所屬的維度作為下個(gè)要加工的工件，直至遍歷所有的位置值。空間維度D取值為工件的數(shù)量n。如圖2 所示，根據(jù)LRV 將一個(gè)6 維空間中個(gè) 體i的位置xi=[1.25，-0.79，4.01，-0.52，-1.30，1.15］，轉(zhuǎn)換為一個(gè)工件排序πi=[2，5，1，4，6，3]。

圖2 LRV規(guī)則表示方法Fig.2 Representation of LRV rule

將工件排序πi對(duì)應(yīng)的最大完工時(shí)間Cmax(πi)作為第i只鳥(niǎo)的適應(yīng)度值f(i)，即

顯然，最大完工時(shí)間最小的個(gè)體為種群最優(yōu)個(gè)體，種群最優(yōu)個(gè)體對(duì)應(yīng)的最大完工時(shí)間為種群最優(yōu)解。

2.2.2 種群初始化

好的初始種群有助于提升算法迭代的效率、提高算法的性能。啟發(fā)式算法能夠在較短時(shí)間內(nèi)獲得質(zhì)量較高的解，保證初始種群中有質(zhì)量較高的個(gè)體；混沌是非線(xiàn)性系統(tǒng)普遍存在的現(xiàn)象，具有有界性、隨機(jī)性、遍歷性等特點(diǎn)［16］，采用混沌映射初始化種群，可使個(gè)體離散地分布在解空間內(nèi)，從而有效地提高種群的多樣性，因此，結(jié)合啟發(fā)式算法和混沌映射進(jìn)行種群初始化以提高初始種群的質(zhì)量和多樣性。

1）NEHLJP1 啟發(fā)式算法。

NEHLJP1 是Liu 等［17］提出的一種基于NEH 的改進(jìn)算法，該算法較NEH 具有更強(qiáng)的尋優(yōu)能力，且計(jì)算復(fù)雜度和NEH相同。NEHLJP1 算法的步驟如下：

步驟1 計(jì)算工件i(i=1，2，…，n)在所有機(jī)器上加工時(shí)長(zhǎng)的平均值A(chǔ)VGi、標(biāo)準(zhǔn)偏差STDi和偏度SKEi，并根據(jù)AVGi+DEVi+abs(SKEi)的結(jié)果按照非增的順序排序，得到優(yōu)先序列γ，其中abs()表示取絕對(duì)值。

步驟2 令工件排序π=[γ(1)]，j=2。

步驟3 將工件γ(j)插入到π中使最大完工時(shí)間最小的位置。如果存在多個(gè)位置，則根據(jù)Liu 等［17］提出的擇優(yōu)（Tie Breaking，TBLJP1）機(jī)制決定最終的插入位置。

步驟4 令j=j+1，若j≤n，則繼續(xù)執(zhí)行步驟3；否則，π即為最終的工件排序，算法結(jié)束。

2）Logistic 映射。

Logistic 映射是一種典型的混沌映射系統(tǒng)，對(duì)應(yīng)的系統(tǒng)方程［18］為：

式中：Xk為混沌變量，μ是控制變量。通常取μ=4，此時(shí)系統(tǒng)處于完全混沌狀態(tài)，X遍歷整個(gè)［0，1］區(qū)間。

3）種群初始化。

按照下述方法產(chǎn)生規(guī)模為N的初始種群：首先使用NEHLJP1 產(chǎn)生的解初始化種群中約10%的個(gè)體，然后用Logistic 映射產(chǎn)生其余的個(gè)體。具體方法為：

步驟1 基于NEHLJP1 產(chǎn)生一個(gè)工件排序π。令I(lǐng)nitNum=

步驟2 使用π生成InitNum個(gè)個(gè)體：

式 中 ：i∈{1，2，…，InitNum}，j∈{1，2，…，n}，xmax=5，xmin=-5。

步驟3 采用Logistic 映射生成剩余的個(gè)體：

式中：i∈{}InitNum+1，InitNum+2，…，N。特別地，xInitNum為隨機(jī)生成的n維混沌變量。

2.2.3 局部搜索與改進(jìn)技術(shù)

變鄰域搜索（VNS）和迭代貪婪（IG）算法是簡(jiǎn)單、有效的局部搜索技術(shù)。

VNS 通過(guò)多種鄰域操作強(qiáng)化算法對(duì)解空間的探索能力［5，7］，其中，插入和交換是最常用的操作。對(duì)于工件排序π中隨機(jī)的兩個(gè)位置j，k∈{1，2，…，n}∧j≠k，插入是將位置j上的工件取出并插入到位置k從而得到新的工件排序π'，如圖3 所示；交換則是將這兩個(gè)位置上的工件互換從而得到新的工件排序π'，如圖4 所示。

圖3 插入操作實(shí)例Fig.3 Example of insert operation

圖4 交換操作實(shí)例Fig.4 Example of swap operation

IG 基于插入鄰域通過(guò)不斷地解構(gòu)（Destruction）、構(gòu)造（Construction）和局部搜索（Local Search）以提升解的 質(zhì)量［19-20］。解構(gòu)即從工件排序π中隨機(jī)抽取d個(gè)工件（每次抽取1 個(gè)，抽取d次），其他工件的順序保持不變，從而得到d個(gè)被刪除工件的排列πR和剩余n-d個(gè)工件的排列πD；構(gòu)造則是將πR中的工件按照被抽取的順序依次插入到πD中使最大完工時(shí)間最小的位置，從而得到完整的工件排序π'；局部搜索基于插入鄰域?qū)Ζ?進(jìn)行局部搜索以提升π'的質(zhì)量。

為了彌補(bǔ)基本鳥(niǎo)群算法易陷入局部最優(yōu)、易過(guò)早收斂、收斂精度差等不足，借鑒VNS 和IG 算法的思想提升個(gè)體歷史最優(yōu)解和種群歷史最優(yōu)解的質(zhì)量，主要思想為：

1）采用VNS 產(chǎn)生新解?；诓迦豚徲虍a(chǎn)生新解并對(duì)其進(jìn)行優(yōu)劣評(píng)估，以充分利用其簡(jiǎn)單、高效的優(yōu)點(diǎn)；基于交換鄰域產(chǎn)生擾動(dòng)，以進(jìn)一步強(qiáng)化算法跳出局部最優(yōu)的能力。

2）引入TBLJP1機(jī)制。工件插入過(guò)程中易產(chǎn)生大量具有最小最大完工時(shí)間而順序不同的工件排序，如何選擇對(duì)算法最終的優(yōu)化結(jié)果有著顯著的影響，因此引入TBLJP1機(jī)制進(jìn)一步擇優(yōu)。

3）由于工件的插入會(huì)對(duì)離插入位置近的工件產(chǎn)生較大的影響［21］，因此在構(gòu)造過(guò)程中，將插入位置前面及后面的工件去除并重新插入。為了節(jié)約計(jì)算開(kāi)銷(xiāo)，此操作僅針對(duì)種群最佳工件排序?qū)嵤?/p>

4）基于Taillard 加速算法［22］計(jì)算最大完工時(shí)間，以節(jié)約計(jì)算開(kāi)銷(xiāo)、提高算法的運(yùn)行效率。

針對(duì)個(gè)體最佳工件排序（i=1，2，…，n）的局部搜索方法為：如果個(gè)體歷史最優(yōu)解pi連續(xù)M次迭代沒(méi)有得到改善，則執(zhí)行交換操作以產(chǎn)生擾動(dòng)；然后進(jìn)行解構(gòu)、構(gòu)造和局部搜索操作，如果新的工件排序更優(yōu)，則更新?；贛atlab 的偽代碼如下：

輸入表示個(gè)體歷史最優(yōu)解pi對(duì)應(yīng)的工件排序；d表示在解構(gòu)階段去除工件的個(gè)數(shù)；

輸出。

其中，第2）行計(jì)算個(gè)體最優(yōu)解pi未得到改善的連續(xù)迭代次數(shù)；第3）～5）行為交換操作；第7）行為解構(gòu)；第8）行為帶TBLJP1機(jī)制的構(gòu)造；第9）～12）行為帶TBLJP1機(jī)制的局部搜索；第13）～15）行為新解的接受。

針對(duì)種群最佳工件排序π*的局部搜索方法為：如果種群歷史最優(yōu)解g連續(xù)M次迭代沒(méi)有得到改善，則基于交換鄰域產(chǎn)生擾動(dòng)，然后執(zhí)行一輪（n次）d=1 的解構(gòu)、構(gòu)建操作，如果新的工件排序更優(yōu)，則更新π*，并執(zhí)行下一輪的解構(gòu)、構(gòu)建，綜合考慮優(yōu)化效果及計(jì)算開(kāi)銷(xiāo)，解構(gòu)和構(gòu)建操作最多執(zhí)行K輪。具體步驟如下：

輸入π*表示種群歷史最優(yōu)解g對(duì)應(yīng)的工件排序；K表示解構(gòu)和構(gòu)建操作最多執(zhí)行K輪；

輸出π*。

其中，第2）行計(jì)算種群最優(yōu)解g未得到改善的連續(xù)迭代次數(shù)；第3）～5）行為交換操作；第8）～15）行為一輪解構(gòu)、構(gòu)建操作（帶TBLJP1機(jī)制），第17）行為新解的接受。

2.2.4 計(jì)算復(fù)雜度分析

算法主要的計(jì)算開(kāi)銷(xiāo)是對(duì)個(gè)體適應(yīng)度值的計(jì)算，主要集中在算法迭代階段，因此忽略種群初始化階段的計(jì)算開(kāi)銷(xiāo)。算法每迭代一次，在更新鳥(niǎo)群的位置之后需要重新評(píng)估所有個(gè)體，計(jì)算復(fù)雜度為O(N×mn)；對(duì)個(gè)體的最佳工件排序進(jìn)行局部搜索，計(jì)算復(fù)雜度為O(N×d×mn+N×mn2)；對(duì)種群最佳工件排序進(jìn)行局部搜索，計(jì)算復(fù)雜度為O(3K×mn2)。因此，算法G次迭代的計(jì)算復(fù)雜度為：O(G× (N× (1 +D) ×mn+(3K+N) ×mn2))?？梢?jiàn)，整個(gè)算法的計(jì)算復(fù)雜度并不算高。這主要得益于以下兩點(diǎn)：1）局部搜索基于Taillard 加速算法求解完工時(shí)間，能夠有效降低算法的計(jì)算復(fù)雜度；2）在對(duì)個(gè)體最佳工件排序的局部搜索中，僅基于交換鄰域產(chǎn)生擾動(dòng)，并不對(duì)新產(chǎn)生的個(gè)體進(jìn)行評(píng)估，可節(jié)省的計(jì)算復(fù)雜度為，即通過(guò)合理的算法設(shè)計(jì)降低了計(jì)算復(fù)雜度。此外，也可以看出，在問(wèn)題規(guī)模確定的情況下，算法的計(jì)算復(fù)雜度主要取決于參數(shù)G、K、N。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

實(shí)驗(yàn)仿真環(huán)境為：Windows 10 操作系統(tǒng)、主頻3.6 GHz的CPU、8.0 GB 的內(nèi)存，編程語(yǔ)言及版本為Matlab R2019b。參數(shù)設(shè)置為：N=100，G=1 000，C=S=1.5，a1=a2=1，P∈[0.8，1]，F(xiàn)L∈[0.5，0.9]，F(xiàn)Q=3，T0=100，Tf=1，β=0.9，M=5，K=n/5，d=3。

為了測(cè)試算法的有效性，基于廣泛使用的Rec 標(biāo)準(zhǔn)測(cè)試集進(jìn)行驗(yàn)證，表1 給出了Rec 標(biāo)準(zhǔn)測(cè)試集中各算例的已知最優(yōu)解，具體的測(cè)試算例可通過(guò)OR-LIBRARY 獲取，每個(gè)算例均獨(dú)立運(yùn)行20 次。以最佳相對(duì)誤差（Best Relative Error，BRE）和平均相對(duì)誤差（Average Relative Error，ARE）為指標(biāo)進(jìn)行比較，計(jì)算公式如下：

表1 Rec標(biāo)準(zhǔn)測(cè)試集的最優(yōu)解Tab.1 The optimal results of Rec benchmark

3.2 算法比較

用HBSA1 表示BSA 和種群初始化方法的組合；用HBSA2 表示BSA、種群初始化方法及對(duì)個(gè)體最佳工件排序進(jìn)行局部搜索的組合；HBSA3 表示BSA、種群初始化方法及對(duì)種群最佳工件排序進(jìn)行局部搜索的組合。為了驗(yàn)證改進(jìn)工作的有效性，針對(duì)Rec 標(biāo)準(zhǔn)測(cè)試集，將HBSA 與BSA、HBSA1、HBSA2 和HBSA3 進(jìn)行比較。表2 給出了比較結(jié)果。

表2 HBSA與BSA、HBSA1～HBSA3計(jì)算結(jié)果的比較Tab.2 Comparison of computational results among HBSA，BSA and HBSA1～HBSA3

圖5 給出了HBSA 和BSA 對(duì)Rec07、Rec17、Rec27 和Rec37 的收斂曲線(xiàn)。從圖5 可以看出，對(duì)于上述所有的算例，HBSA 的初始值、收斂的速度和精度都明顯優(yōu)于BSA。這是因?yàn)樵诜N群初始化階段，HBSA 結(jié)合NEHLJP1 啟發(fā)式算法產(chǎn)生10%的個(gè)體、使用混沌映射生成剩余的個(gè)體，使得初始種群擁有更好的初始值和較好的多樣性，算法迭代的效率更高；對(duì)個(gè)體最佳工件排序和種群最佳工件排序進(jìn)行局部搜索則增強(qiáng)了算法對(duì)解空間的探索能力，并能在一定程度避免陷入局部最優(yōu)，從而使算法具有更高的收斂速度和收斂精度。綜上所述，比較結(jié)果表明：提出的改進(jìn)措施大幅度地提高了算法收斂的速度和精度，有效提高了算法的性能。

圖5 HBSA和BSA對(duì)Rec07、Rec17、Rec27及Rec37的收斂曲線(xiàn)Fig.5 Convergence curves of HBSA and BSA for Rec07，Rec17，Rec27 and Rec37

為了進(jìn)一步驗(yàn)證HBSA 的性能，將計(jì)算結(jié)果與以下4 種優(yōu)化算法相比較：1）混合差分進(jìn)化算法（L-HDE）［7］；2）混合共生生物搜索算法（HSOS）［9］；3）離散狼群算法（Discrete Wolf Pack Algorithm，DWPA）［23］；4）多班級(jí)教學(xué)優(yōu)化（Multi-Class Teaching-Learning-Based Optimization，MCTLBO）算法［24］。

表3 給出了計(jì)算結(jié)果的比較。

表3 HBSA與四種優(yōu)化算法計(jì)算結(jié)果的比較Tab.3 Comparison of computational results among HBSA and four optimization algorithms

圖6 給出了HBSA 與L-HDE、HSOS、MCTLBO 及DWPA取得的BRE的比較。

圖6 BRE的比較Fig.6 Comparison of BRE

從圖6 中可以看出，HBSA 取得了所有（共21 個(gè)）測(cè)試用例的BRE的最優(yōu)值、排名第一；其次是MCTLBO，取得了12個(gè)最優(yōu)值；然后是HSOS，取得了11 個(gè)最優(yōu)值，最后是L-HDE和DWPA，均取得了10 個(gè)最優(yōu)值，從而證明了HBSA 的尋優(yōu)能力優(yōu)于上述四種算法。

圖7 給出了HBSA 與L-HDE、HSOS、MCTLBO 及DWPA取得的ARE的比較，同樣地，HBSA 取得了所有測(cè)試用例ARE的最優(yōu)值、排名第一；其次是HSOS，取得了7 個(gè)最優(yōu)值；然后是L-HDE 和DWPA，均取得了5 個(gè)最優(yōu)值；最后是MCTLBO，取得了2 個(gè)最優(yōu)值，從而證明了HBSA 的穩(wěn)定性強(qiáng)于上述四種算法。

圖7 ARE的比較Fig.7 Comparison of ARE

針對(duì)不同規(guī)模測(cè)試算例求得的BRE和ARE的平均值，HBSA 取得的結(jié)果分別為0.098 和0.173，相比L-HDE 的0.502 和0.757、HSOS 的0.583 和1.050、MCTLBO 的0.367 和0.747、DWPA 的0.427 和0.759，和至少下降了73.3%和76.8%，可見(jiàn)，HBSA 優(yōu)化結(jié)果較其他算法提升很明顯。各算法針對(duì)不同規(guī)模測(cè)試算例求得的BRE和ARE的平均值的比較如圖8 所示。

圖8 和的比較

值得說(shuō)明的是，針對(duì)Rec25 和Rec27，僅HBSA 的計(jì)算結(jié)果達(dá)到了目前已知最優(yōu)解，從而進(jìn)一步證明了HBSA 的優(yōu)越性。HBSA 求得Rec27 的最佳工件排序?yàn)椋害?=［17，11，28，10，4，30，16，29，19，9，25，3，23，21，18，20，24，6，1，12，2，22，27，8，5，26，14，13，7，15］；求得Rec25 的最佳工件排序并不唯一，其中一個(gè)工件排序?yàn)椋害?=［21，29，2，18，4，24，5，16，26，22，28，30，11，20，19，1，9，10，7，14，27，6，23，15，13，12，3，25，17，8］。

4 結(jié)語(yǔ)

本文針對(duì)以最大完工時(shí)間最小化為目標(biāo)的置換流水車(chē)間調(diào)度問(wèn)題（PFSP），提出了一種混合鳥(niǎo)群算法（HBSA）進(jìn)行求解。結(jié)合NEHLJP1 啟發(fā)式算法和混沌映射提出了一種新的種群初始化方法，以改善初始種群的質(zhì)量和多樣性；采用LRV 規(guī)則將連續(xù)的位置值轉(zhuǎn)換為離散的工件排序，從而使算法能夠處理離散的調(diào)度問(wèn)題；借鑒VNS 和IG 算法的思想針對(duì)個(gè)體最佳工件排序和種群最佳工件排序分別提出了局部搜索方法，以強(qiáng)化算法對(duì)解空間的探索能力。針對(duì)Rec 標(biāo)準(zhǔn)測(cè)試集進(jìn)行了仿真測(cè)試，根據(jù)最佳相對(duì)誤差和平均相對(duì)誤差進(jìn)行比較，結(jié)果顯示提出的改進(jìn)措施大幅度地提高了BSA 收斂的速度和精度，有效地提升了BSA 的性能；此外，HBSA 的表現(xiàn)也明顯優(yōu)于L-HDE、HSOS、MCTLBO 及DWPA 等算法，具有更強(qiáng)的全局尋優(yōu)能力和更好的穩(wěn)定性，尤其是針對(duì)Rec25 和Rec27 測(cè)試算例，僅HBSA 的計(jì)算結(jié)果達(dá)到了目前已知最優(yōu)解，進(jìn)一步證明了HBSA 的優(yōu)越性，從而為解決置換流水車(chē)間調(diào)度問(wèn)題提供了一種更加有效的方法。未來(lái)將在大規(guī)模地置換流水車(chē)間調(diào)度問(wèn)題、其他調(diào)度目標(biāo)的優(yōu)化及多個(gè)調(diào)度目標(biāo)的協(xié)同優(yōu)化等方面做進(jìn)一步的研究。