李西興 楊道明 李 鑫 吳 銳

1. 湖北工業(yè)大學機械工程學院，武漢，430068 2. 湖北工業(yè)大學現(xiàn)代制造質量工程湖北省重點試驗室，武漢，430068

0 引言

隨著我國制造業(yè)的改革優(yōu)化和創(chuàng)新發(fā)展，傳統(tǒng)的大規(guī)模標準化生產模式逐步被大規(guī)模個性化定制模式取代。同時，借助于云計算、大數(shù)據(jù)、數(shù)字孿生等“互聯(lián)網+制造”技術落地生根，大規(guī)模也逐漸被小批量替代(尤其是在零部件制造企業(yè))。另外，為了快速應對市場變化，交貨期也進一步縮短。多品種、小批量、短周期、個性化的制造特點對企業(yè)業(yè)務流程(包括加工作業(yè)流程、緊急事件處理流程)的優(yōu)化提出了更高要求，優(yōu)化制造資源配置策略、提高制造資源利用率成為制造企業(yè)亟需解決的問題。傳統(tǒng)的制造任務與機器、人員間的優(yōu)化配置逐步擴展為多類型制造資源間的集成優(yōu)化，其中作業(yè)車間自動導引車(automated guided vehicle，AGV)參與的集成調度逐漸成為生產調度優(yōu)化領域的重點研究問題之一。

AGV是一種具有高柔性、高效率、高可靠性、智能化的物流運輸裝備，相關應用和研究主要分布在以下兩個領域。

(1)倉儲運輸領域[1-4]。主要包括：考慮堆場緩沖區(qū)大小的自動堆垛機與AGV集成優(yōu)化調度[5]；考慮岸橋、丁升式AGV和自動軌道吊協(xié)同調度的混合式自動化碼頭設備協(xié)同調度[6]；考慮充電過程的垂岸式集裝箱堆場布局和AGV作業(yè)集成調度[7]。梁承姬等[8]針對AGV數(shù)量偏多導致的自動化碼頭運輸區(qū)擁堵問題，采用多學科變量耦合優(yōu)化設計的方法建立了AGV協(xié)調調度與優(yōu)化配置耦合模型，并利用改進遺傳算法(genetic algorithm，GA)進行求解，但未考慮場橋對AGV的影響。

(2)作業(yè)車間領域[9-11]。XU等[12]針對智能制造車間的物流動態(tài)調度問題，提出了一種基于“需求-調度-反饋”模式的AGV智能物流調度模型和響應方法，同時應用物聯(lián)網技術以滿足動態(tài)和實時性的需求。CHEN等[13]提出了一種基于AGV的模塊化預制制造系統(tǒng)的設施布局規(guī)劃方法，以最小化生產時間和最大化工作站利用率為優(yōu)化目標。魏永來等[14]將整車間物料調度視為一個小型車間物料系統(tǒng)，提出了以AGV路徑-運輸時間-配送成本為目標的多AGV調度優(yōu)化模型，將禁忌搜索算法引入蝙蝠算法并求解，通過某實際車間進行了仿真驗證。FONTES等[15]將聯(lián)合生產運輸調度問題轉化為一種新的混合整數(shù)線性規(guī)劃模型，即集成機器調度問題和AGV調度問題，構建了兩組鏈式決策策略(一組用于機器，另一組用于AGV)，通過機器操作和運輸任務的完成時間約束相互連接。劉二輝等[16]綜合考慮AGV的利用率和工件最大完工時間兩個因素建立了面向共融AGV作業(yè)車間的多目標優(yōu)化數(shù)學模型，利用改進花授粉算法求解并搭建集成調度平臺進行驗證。賀長征等[17]為了實現(xiàn)AGV路徑規(guī)劃與機器調度的同步集成，搭建了AGV/機器的雙資源調度數(shù)學模型，同時針對路徑沖突問題制定了速度調節(jié)、幾何路徑調節(jié)和混合調節(jié)的解決策略，增強了模型的動態(tài)優(yōu)化能力，但忽略了小車充電和故障問題。在實際作業(yè)車間中，AGV的物理屬性(如規(guī)格型號、功率、運載能力、續(xù)航時間等)存在差異，不同行走路徑帶來的時間消耗不同，會對整個工件任務的加工時間、調度規(guī)劃、完工交貨造成影響。為了增強調度方案的可行性和合理性、保障生產任務的順利執(zhí)行，作業(yè)車間AGV融合調度研究具有重要意義。

AGV參與的集成調度問題有多種求解方法[18]。CHEN等[19]針對制造空間受限且有AGV參與的家具制造車間，提出了基于規(guī)則的染色體評估方法對傳統(tǒng)GA進行改進，進而提高其求解性能。而DANG等[20]建立了面向AGV調度的整數(shù)規(guī)劃模型，將禁忌搜索算法與GA混合來求解最大完工時間最小化問題。LYU等[21]同時考慮了最佳AGV數(shù)量、最短運輸時間、路徑規(guī)劃問題和無沖突路由問題，提出了一種基于時間窗的GA與Dijkstra算法相結合的混合求解算法。岳笑含等[22]考慮AGV電量狀況,以最小完成時間與調度最少AGV數(shù)量作為優(yōu)化目標，提出了一種改進的混合GA-粒子群優(yōu)化(particle swarm optimization，PSO)算法對問題進行求解。范佳靜等[23]提出了改進分散搜索算法，將其應用于以AGV數(shù)量最少為目標的多目標規(guī)劃模型，即通過GA獲得新解，利用模式搜索法改進新解，從而提高算法收斂速度。LI等[24]提出了一種改進的和聲搜索算法對以AGV緩沖區(qū)等待時間和總行駛距離為目標的優(yōu)化數(shù)學模型進行求解。

綜上所述，目前對AGV參與的集成調度問題，尤其是將其與FJSP相結合的研究較少；同時，在探索優(yōu)化求解算法方面大多還是以GA、PSO等傳統(tǒng)元啟發(fā)法式算法為主，因此，本文針對柔性作業(yè)車間AGV融合調度問題，提出使用混合遺傳鯨魚優(yōu)化算法(hybrid genetic whale optimization algorithm，HGWOA)進行求解。該方法綜合考慮AGV與FJSP問題的集成優(yōu)化，引入遺傳算法中的交叉/變異算子來保證WOA可行解的多樣性，通過3種鄰域結構和精英池策略來提高算法的局部尋優(yōu)能力。最后通過實例驗證了該方法的有效性和可行性。

1 問題描述

柔性作業(yè)車間調度問題可描述為：n個工件在m臺機器上加工，每個工件均有多道具有順序約束的工序，每道工序均具有一臺或者多臺可選加工機器，通過合理安排工序加工順序和加工機器以使給定指標最優(yōu)化。

本文在柔性作業(yè)車間調度問題基礎上加入AGV資源約束，考慮AGV在裝載站/卸載站、機器輸入輸出緩沖區(qū)之間運輸工件，各段距離及AGV運行速度已知，相鄰設備間距不等。工件從裝載站開始，依次被運輸?shù)桨才诺脑O備輸入區(qū)，工序加工完成后放入輸出區(qū)，由AGV將其運輸至下一臺設備，加工完成的工件送至卸載站。設備單次充電后的運輸距離一定，每次運輸后距離累計，剩余運輸距離不足則AGV不分配運輸任務，達到閾值后充電，充電時間一定，充電期間AGV不可用。

1.1 變量定義

表1所示為所有索引及集合變量的定義，表2所示為所有參數(shù)變量的定義，表3所示為所有決策變量的定義。

表1 索引及集合含義Tab.1 Index and collection meaning

表2 參數(shù)及含義Tab.2 Parameters and meaning

表3 決策變量及含義Tab.3 Decision variables and meaning

1.2 問題假設

(1)不考慮AGV差異性，即運輸速度、單次充電運輸距離、充電時間等相同。

(2)裝載站、卸載站、機器緩沖區(qū)容量無限。

(3)不考慮工序開始加工前的準備時間和完成后的釋放時間。

(4)工序開始加工和運輸后不可中斷。

(5)0時刻所有的工件均可被加工，所有機器和AGV均處于可用狀態(tài)。

1.3 模型建立

優(yōu)化目標選擇車間調度問題中最常使用的是最小化最大完工時間，本文中最大完工時間即所有工件被運輸至卸載站所需時間的最大值：

(1)

(2)

i=1,2,…,n

式(2)表示工件運輸完成時間等于最后一道工序的開始運輸時間加上其運輸?shù)叫遁d站所需時間。

開始運輸時間必須晚于其工序加工完成時間，即

Hi,j≥Ei,ji=1,2,…,nj=1,2,…,bi

(3)

工序的加工完成時間等于其起始加工時間加上實際加工所需時間，即

(4)

i=1,2,…,nj=1,2,…,bi

工序約束，即工序的起始加工時間必須晚于其前置工序完成后運輸至當前機器的時間，即

(5)

i=1,2,…,nj=1,2,…,bi-1

設備約束如下：

(6)

i,i′=1,2,…,nj=1,2,…,bij′=1,2,…,bi′

式(6)確保一臺設備在任一時刻只能加工至多一道工序。

AGV時間約束如下：

(7)

i,i′=1,2,…,nj=1,2,…,bi-1j′=1,2,…,bi′

式(7)表明工序Oi′,j′的起始運輸時間必須晚于與其使用同一AGV進行運輸?shù)木o前工序完成運輸后空載運行至Oi′,j′機器的時間，確保任一臺AGV在任一時刻都只執(zhí)行一個運輸任務。

限定一道工序只能選擇一臺而且必須選擇一臺可行機器進行加工，即

(8)

限定工序完成加工后必須選擇一臺且只能選擇一臺AGV執(zhí)行運輸任務，即

(9)

限定AGV在單次充滿電后的運輸時間不超出可用的最大運輸時間，即

(10)

r=1,2,…,wθ=0,1,2,…,fr

限定AGV在充電之前的最后一道運輸任務完成時間加上充滿電的時間早于充電后第一道運輸任務的起始運輸時間，即

(11)

r=1,2,…,wθ=0,1,2,…,fr-1

2 改進鯨魚優(yōu)化算法

2.1 鯨魚優(yōu)化算法簡介

根據(jù)座頭鯨群體狩獵行為特點——Bubble-net覓食(即泡泡網覓食或氣幕覓食)，WOA算法抽象出包圍獵物、 Bubble-net攻擊和隨機搜索3個計算階段。

2.1.1包圍獵物

每只鯨魚代表一個個體,每個個體在搜索空間的位置代表一個解。鯨魚能夠通過回聲定位識別獵物位置并包圍獵物,鯨魚位置更新公式如下：

(12)

A=2a×rand1-a

(13)

C=2rand2

(14)

其中，rand1、rand2為[0，1]范圍內均勻分布產生的隨機數(shù)；a中元素a為收斂因子，隨迭代次數(shù)t從2線性減小到0，即

a=2-2t/tmax

(15)

式中，tmax為最大迭代次數(shù)。

2.1.2Bubble-net攻擊

鯨魚在覓食過程中是以向上螺旋式運動并不斷收縮包圍圈來攻擊獵物的，為了從數(shù)學上描述Bubble-net覓食行為，設計收縮包圍機制和螺旋更新位置兩種方法。

收縮包圍機制通過式(2)隨著收斂因子a的減小實現(xiàn)，同時系數(shù)向量A的波動范圍也隨著收斂因子a減小，即當收斂因子a在迭代過程中從2減小到0時，系數(shù)向量A的波動范圍為[-a，a]。當系數(shù)向量A為[-1，1]內的隨機值時，鯨魚t+ 1時刻的位置可以是t時刻的位置與t時刻全局最優(yōu)位置之間的任意位置，即表示鯨魚始終在收縮包圍圈內游動。

在螺旋更新位置方法中，鯨魚以螺旋運動向獵物游動，其數(shù)學模型為

(16)

鯨魚在獵物收縮包圍圈內同步沿著螺旋形路徑游動，為了模擬這種同步行為，在優(yōu)化過程中假設選擇收縮包圍機制和螺旋更新位置概率均為0.5，同步行為的數(shù)學模型為

(17)

其中，pr為[0，1]范圍內均勻分布產生的隨機數(shù)。

2.1.3隨機搜索

當系數(shù)向量|A|> 1時,表示鯨魚在收縮包圍圈外游動,此時鯨魚個體根據(jù)彼此位置進行隨機搜索,其數(shù)學模型為

(18)

由上述分析可知,WOA算法主要參數(shù)為系數(shù)向量A和C，其中參數(shù)A對協(xié)調WOA算法全局探索和局部開發(fā)能力至關重要。當|A|> 1時，鯨魚種群將擴大搜索范圍,以找到更好的候選解，即為WOA算法的全局探索能力；當|A|≤ 1時，鯨魚種群將縮小搜索范圍,在局部區(qū)域進行精細搜索，即為WOA算法的局部開發(fā)能力。而參數(shù)A的值在很大程度上依賴于收斂因子a的變化：較大的收斂因子a具有較好的全局搜索能力，避免算法陷入局部最優(yōu)；較小的收斂因子a具有較強的局部搜索能力，以加快算法的收斂速度。

2.2 編碼/解碼

根據(jù)該問題的特性，采取雙層編碼方式，即編碼后的個體向量由兩部分組成：工序排序向量(operation sequence vector，OV)和機器選擇向量(machine select vector，MV)。在OV中，各元素表示的是工件的索引號，該索引號第幾次出現(xiàn)表明是該工件的第幾道工序。MV由各對應工序所選擇的機器索引號構成，對應的工序按工件號及工序號由小到大排序。圖1中給出了一個3工件5設備問題案例可行解的編碼方案。

圖1 編碼方案Fig.1 Coding scheme

上述編碼只表述了柔性作業(yè)車間調度問題對應的工序排序和設備選擇兩個子問題，并未包含AGV的選擇子問題，因此在解碼過程設計中，必須考慮AGV的選擇問題。本文基于最先開始服務AGV優(yōu)先選擇的規(guī)則設計了以下新的解碼算法。

(1)初始化機器可用時間向量αj，工件加工時間向量βi，AGV位置記錄向量λr，AGV時間記錄向量θr，目標函數(shù)值f=0，t=1。

(2)在OV中從左至右取出第t個元素，獲得其工件號i和工序號j，并且在MV中取出對應工序的機器序號k，取得對應的加工時間p。

(3)比較βi與αj，將其中的較大值設置為當前工序Oi,j最早開始加工時間Si,j。若j=1，即當前工序為該工件內的第一道工序，則轉步驟(4)，否則轉步驟(5)。

(4)從AGV中選擇最早能從當前位置空載運行至裝載站的Ar，為Ar添加兩個運輸任務。一個是從當前位置λr空載至裝載站的任務，起始時間為θr，運輸時間可通過當前位置至裝載站的距離確定，之后計算得到任務終止時間，更新θr為任務終止時間。之后為Ar添加從裝載站運輸至機器k的運輸任務，過程類似。在添加運輸任務之后累計Ar的累計運輸時長，若剩余時長小于安全值，則為Ar增加充電任務，更新θr為θr、T以及運行至充電站所需時間之和。

(5)獲取工序Oi,j的前置工序所在機器k′，然后從AGV中選擇最早能從當前位置空載運行至裝載站的Ar，若Ar已經在機器k′處，則轉步驟(7)，否則轉步驟(6)。

(6)為Ar添加一個從AGV當前所在設備位置空載至前置工序所在機器k′的任務，起始時間為θr或前置工序的加工完成時間中的較大值，計算得到任務完成時間，更新θr為任務完成時間。

(7)為Ar添加從機器k′運輸工件至機器k的運輸任務，起始時間為θr，計算得到任務完成時間，更新θr為任務完成時間。同樣更新和判斷Ar累計運輸時長，若剩余時長低于安全值則添加充電任務。

(8)更新工序Oi,j的起始加工時間Si,j，設置其為步驟(3)中Si,j與步驟(4)或步驟(7)中運輸任務完成時間中的較大值，工序Oi,j完成時間則為Si,j+P。若Si,j+P大于f，則設置f為Si,j+P。

(9)若t小于編碼長度，t←t+1，則轉步驟(2)，否則終止。

2.3 種群初始化

初始解質量的好壞會直接影響算法的求解性能，完全隨機生成雖然使初始種群具有良好的多樣性，但是具有一定的盲目性。為了提高算法初始解的質量并保持良好的多樣性，本文采用了混合初始化策略來生成初始解，混合初始化策略包含隨機初始化方法和策略選擇初始化方法。根據(jù)文獻[35-36]，本文種群中30%的個體采用隨機初始化方法生成，即工件隨機排序，工序對應的機器在合法范圍內隨機選擇；剩余70%的個體采用策略選擇的方法生成，將工件隨機排序，在選擇合法機器時考慮加工時間的因素，選擇最可能加工時間小的機器對工件加工。

2.4 改進搜索策略

在改進搜索操作中，引入遺傳算法中的交叉/變異算子來保證可行解的多樣性；提出3種鄰域結構和精英池策略來提高算法的局部尋優(yōu)能力。

2.4.1交叉變異算子

針對OV、MV向量各自的特點分別設計了高效的交叉和變異操作，以實現(xiàn)搜索操作，即在鯨魚優(yōu)化算法的包圍獵物、 Bubble-net攻擊搜索中使用交叉算子，隨機搜索操作中使用變異算子。

(1)OV的交叉操作采用廣泛使用的POX交叉方法[37]，操作過程如下：①將工件序號隨機分配到兩個非空且互補的集合Q1和Q2中；②從父代X1選出包含在集合Q1中的工件序號，保持各工件序號的位置不變復制到子代X′中；③從父代X2中選出包含在集合Q2中的工件序號，將其按順序依次插入子代X′的空缺處；④按照步驟②和③的操作，從父代X1中選出包含在集合Q2中的工件序號，保持位置不變復制到子代X″中，從父代X2中選出包含在集合Q1中的工件序號，按順序插入子代X″的空缺處；⑤從子代X′和X″中選出較優(yōu)的個體作為交叉后的子代。

(2)MV的交叉操作采用RPX(radom probability crossover)交叉操作，即遍歷MV中的元素，以50%的概率交換兩個體MV中元素。

(3)OV的變異操作采用常用的兩點交叉操作。

(4)MV的變異采用替換變異，即隨機選擇MV中的一個元素將其替換為可用機器集合內的另外一臺機器。

2.4.2 3種鄰域結構和精英池策略

本文提出3種鄰域結構：①交換鄰域結構，將個體的OV向量任意指定的兩個位置進行交換得到新的個體；②插入鄰域結構，指定個體的OV向量的某一元素插入到該OV向量的任意指定位置；③變異鄰域結構，以一定的概率對MV中的元素進行合法替換變異?；谏鲜?種鄰域結構，引入一種基于精英池的迭代局部搜索進行局部搜索操作。具體操作流程如下：

(1)將全局最優(yōu)個體作為迭代搜索的初始解π，設置tcn=0。初始化精英池中只有初始解π。

(2)利用交換鄰域結構對π進行搜索操作，得到新解π′。若π′優(yōu)于π，則設置π=π′，tcn=0，將π′插入精英池中，轉至步驟(5)；否則設置tcn←tcn+1，轉至步驟(3)。

(3)利用插入鄰域結構對π進行搜索操作，得到新解π′。若π′優(yōu)于π，則設置π=π′，tcn=0，將π′插入精英池中，轉至步驟(5)；否則設置tcn←tcn+1，轉至步驟(4)。

(4)利用輪盤賭方法從精英池中選擇最優(yōu)個體，并對其使用變異鄰域結構進行搜索得到新解π′，若π′優(yōu)于π，則設置π=π′，tcn=0，將π′插入精英池中，轉至步驟(5)；否則設置tcn←tcn+1，轉至步驟(5)。

(5)若tcn<5，則跳轉至步驟(2)，否則終止。

2.5 HGWOA算法基本流程

綜上所述，HGWOA算法步驟總流程如圖2所示，具體描述如下：

圖2 HGWOA算法流程圖Fig.2 HGWOA algorithm flow chart

(1)初始化算法參數(shù)。

(2)根據(jù)初始化策略初始化鯨魚種群，對種群進行評價，找出全局最優(yōu)個體。

(3)迭代開始，依次遍歷種群中的個體。生成一個[0，1]之間的隨機數(shù)pr，若pr<0.5，則轉步驟(4)，否則轉步驟(5)。

(4)若|A|<1，則隨機選擇一個不同于當前個體的新個體，基于當前個體與新個體進行交叉操作，獲得一個新個體替換當前個體。若|A|≥1，則選擇全局最優(yōu)個體與當前個體進行交叉操作。

(5)基于當前個體進行變異操作，利用變異后的個體替換當前個體。

(6)對種群進行評價，找出全局最優(yōu)個體，基于全局最優(yōu)個體進行迭代局部搜索操作，評價搜索得到的個體，若優(yōu)于全局最優(yōu)個體則替換。

(7)重復上述步驟直到算法達到終止條件，輸出結果。

3 仿真對比試驗

為驗證HGWOA求解所提問題的性能，進行如下操作：首先通過擴展FJSP的經典測試算例得到適用于驗證此問題的算例；然后采用正交試驗法對HGWOA中的參數(shù)進行優(yōu)化配置；最后，將FJSP中常用的經典算法GA[37]、PSO[38]及差分進化算法(differential evolution, DE)[39]作為對比算法來驗證HGWOA的求解性能。選取的3種對比算法經過對應文獻中的離散化改進后已適用于求解FJSP，但要適用于求解本文所提出的問題仍需作一定調整，在保證對比算法整體流程不變的基礎上，所作調整主要包括改為使用本文提出的編碼/解碼方案以及對搜索操作進行適應性改進。

3.1 測試算例生成

圖3 車間機器布局Fig.3 Workshop machine layout

本文將柔性作業(yè)車間調度問題中的經典Brandimarte測試算例[40]進行拓展，附加AGV等相關數(shù)據(jù),用于測試本文提出的算法。每個測試算例分別考慮AGV數(shù)量與機器數(shù)量的比例為1∶1、1∶2、1∶3，以MK01為例，AGV數(shù)量與機器數(shù)量比例為1∶1時，命名為MK01_1，比例為1∶2和1∶3時分別命名為MK01_2和MK01_3，其余的測試算例類似。假定機器布局如圖3所示，X、Y為建立坐標系的X軸、Y軸。裝卸載站、充電站以及各機器之間的運輸時間可通過圖中所示各坐標之間的距離計算得到。此外，AGV滿電運行時間DA=30，充滿電時間T=20，安全剩余可用時間Ds為各設備至充電站運輸時間中的最大值。

3.2 參數(shù)配置

相比于其他群智能優(yōu)化算法，WOA算法具有參數(shù)少、使用便捷的特點，需要設置的參數(shù)僅有種群規(guī)模P。本文采用正交試驗法對參數(shù)進行優(yōu)化配置，設置P參數(shù)水平分別為20、40、60、80、100共5個水平?；谥械纫?guī)模的算例MK09進行試驗，算法運行30次，取均值作為最終結果值。最終算法運行試驗結果分別為640.37、632.37、628.6、640.43、634.63，從中可以得出P=60時HGWOA具有最優(yōu)的性能。其余對比算法的參數(shù)設置與文獻中一致。

3.3 算法對比分析

算法采用C#語言進行編寫，運行環(huán)境為 Intel Core I7-5700HQ CPU 2.70 GHz，RAM 8 GB， Windows 10， 64 位操作系統(tǒng)。為公平對比各算法，所有算法運行時的終止條件設置為固定的最大運行時間，其值等于各算例的工件數(shù)目。為避免試驗結果的隨機性，針對每個算例將算法重復運行30次，得到30個結果值，最終結果取其平均值。試驗結果如表4 所示，其中均值指30次運行得到的均值，最優(yōu)值指30次運行中的最優(yōu)值，tcpu表示程序運行時間。

從表4中各算例結果的最優(yōu)值和平均值可以看出, HGWOA在大部分算例上都表現(xiàn)得最為優(yōu)異，GA次之，HGWOA取得最優(yōu)的比例遠遠大于其他對比算法，由此表明HGWOA在求解本文提出的問題時具有更優(yōu)良的性能。

為了驗證算法性能是否確實存在統(tǒng)計意義上的差異,利用試驗結果中的數(shù)據(jù)進行Wilcoxon測試(置信水平為0.05),試驗結果如表5所示。表5中p值均小于0.05，說明HGWOA在最優(yōu)值和均值兩指標上均顯著好于其他對比算法。

圖4為各算法在算例MK01_1、MK05_1、MK09_1、MK15_1進行的30次求解中所獲得結果的箱型圖。從圖中可看出，HGMOA在4個算例中均取得了最小的均值，但是其上限值和下限值并非在4個算例上均取得最優(yōu)，同時在部分算例上的散布大小并非最小，說明所提出的HGWOA雖然在尋求最優(yōu)上相比其他算法具有一定優(yōu)勢，但是在算法穩(wěn)定性上優(yōu)勢并不突出。

圖5為HGWOA和對比算法在測試算例MK01_1、MK05_1、MK09_1、MK15_1進行的30次求解中取得最優(yōu)值的一次運行的收斂曲線圖。

表4 試驗結果Tab.4 Experimental result

表5 Wilcoxon測試結果Tab.5 Wilcoxon test results

(a) MK01_1

(b) MK05_1

(c) MK09_1

(d) MK15_1圖4 30次求解結果箱型圖Fig.4 Box plot of 30-time solution results

(a) MK01_1

(b) MK05_1

(c) MK09_1

(d) MK15_1圖5 收斂曲線示例Fig.5 Convergence curve example

由圖5a可知，此次運行HGWOA的初始起點最差，但在算法剛開始運行的一段時間內HGWOA的收斂速度最快，其次是PSO。雖然在一開始PSO的初始條件優(yōu)于HGWOA，而且收斂速度較快，在算法運行初始階段一度領先于HGWOA，但 PSO在運行約 0.4 s后就陷入局部最優(yōu)無法跳出，說明該算法克服陷入局部最優(yōu)的能力有所欠缺。相比之下，HGWOA不僅在搜索的初期具有較快的收斂速度，而且在后續(xù)搜索中具有較好的跳出局部最優(yōu)的能力。就收斂結果來看，HGWOA獲得了最好的結果，GA 次之，PSO最差。

針對上述收斂曲線的融合調度方案甘特圖見圖6～圖8所示(限于篇幅，MK15_1融合調度優(yōu)化方案甘特圖掃OSID二維碼可見)。以圖6為例具體說明。圖6a為HGWOA所獲得的 MK01_1 算例最優(yōu)解Cmax=47時的機器加工任務調度甘特圖，圖中每一個方塊代表一道工序，方塊內上方數(shù)字表示工件號，下方數(shù)字表示工序號，由圖可知各工序加工順序安排以及機器的選擇。圖6b是圖6a對應的AGV運輸任務調度甘特圖，圖中“C”、“Z”、“X”分別代表充電站、裝載站和卸載站，每一個方塊代表一個AGV運輸任務，方塊內上方數(shù)字代表起點機器序號，下方數(shù)字則為終點機器序號。

(a) 機器加工任務調度甘特圖

(b) AGV運輸任務調度甘特圖圖6 MK01_1融合調度優(yōu)化方案甘特圖Fig.6 MK01_1 fusion scheduling optimization plan Gantt chart

4 結束語

本文研究了考慮AGV運輸工件的柔性作業(yè)車間AGV融合調度問題，以最小化最大完工時間為優(yōu)化目標建立了相應的數(shù)學模型并提出改進鯨魚優(yōu)化算法進行了求解。在所提鯨魚優(yōu)化算法中所做的改進包括設計編碼和解碼方案、引入混合初始化策略、交叉和變異方法、嵌入局部搜索等操作，提升了算法的尋優(yōu)能力。最后，將傳統(tǒng)的15個標準算例擴展成為30個案例，將HGWOA與常用算法進行了對比試驗，對比結果驗證了改進算法的合理性和有效性。

文中所建立的作業(yè)車間AGV融合調度模型未考慮AGV差異性，即運輸速度、單次充電運輸距離、充電時間等因素，與實際的生產制造系統(tǒng)存在差異，后續(xù)的融合調度優(yōu)化研究將重點考慮這些實際生產因素，并不斷改進和完善多目標的求解算法，以進一步豐富現(xiàn)在作業(yè)車間AGV融合調度優(yōu)化方案。

(a) 機器加工任務調度甘特圖

(b) AGV運輸任務調度甘特圖圖7 MK05_1融合調度優(yōu)化方案甘特圖Fig.7 MK05_1 fusion scheduling optimization plan Gantt chart

(a) 機器加工任務調度甘特圖

(b) AGV運輸任務調度甘特圖圖8 MK09_1融合調度優(yōu)化方案甘特圖Fig.8 MK09_1 fusion scheduling optimization plan Gantt chart