鄒裕吉，宋豫川，王 毅，王馨坤

(重慶大學(xué) 機(jī)械傳動(dòng)國(guó)家重點(diǎn)實(shí)驗(yàn)室，重慶 400044)

隨著“中國(guó)制造2025”的提出，以及云計(jì)算、互聯(lián)網(wǎng)和大數(shù)據(jù)等信息技術(shù)的發(fā)展，大規(guī)模定制化和多品種小批量的生產(chǎn)模式逐漸成為主流。在這種以個(gè)性化為主的生產(chǎn)模式下，產(chǎn)品種類繁多，工藝流程復(fù)雜，合理的車間調(diào)度方案對(duì)于提高生產(chǎn)效率至關(guān)重要。在傳統(tǒng)的柔性作業(yè)車間調(diào)度問題研究中通常不考慮工件的轉(zhuǎn)移時(shí)間，導(dǎo)致這種調(diào)度結(jié)果并不是理論最優(yōu)調(diào)度結(jié)果，對(duì)于實(shí)際生產(chǎn)的指導(dǎo)存在不足。AGV(automated guided vehicles)是一種高柔性、高可靠性及高效率的先進(jìn)物流裝備，在數(shù)字化車間中負(fù)責(zé)實(shí)現(xiàn)工件的轉(zhuǎn)移[1]。在這種情況下，機(jī)器的調(diào)度和AGV的調(diào)度會(huì)相互影響，所以AGV和機(jī)器集成調(diào)度問題越來越受關(guān)注。

土耳其學(xué)者Ulusoy等[2-4]于1993年首先將AGV和機(jī)器集成調(diào)度作為研究對(duì)象，在不考慮AGV路徑?jīng)_突的前提下，應(yīng)用遺傳算法求解調(diào)度問題，并建立了標(biāo)準(zhǔn)算例庫。Abdelmaguid等[5]在Ulusoy的基礎(chǔ)上提出一種精英保留策略，研究了6種交叉操作和3種變異操作的最佳組合以及交叉和變異最優(yōu)概率范圍。Zheng等[6]針對(duì)該問題，建立了混合整數(shù)線性規(guī)劃模型，以最大完工時(shí)間為優(yōu)化目標(biāo)，提出禁忌搜索算法結(jié)合12種鄰域結(jié)構(gòu)求解該模型。Deroussi等[7]提出一種混合粒子群遺傳算法用以解決柔性制造系統(tǒng)中AGV和機(jī)器集成調(diào)度問題，包含了一種基于AGV的解決方案。劉二輝等[8]提出一種改進(jìn)花授粉算法求解AGV和機(jī)器集成調(diào)度問題，并研究了AGV數(shù)量對(duì)調(diào)度結(jié)果的影響。

以上研究為了將問題簡(jiǎn)化，都聚焦于AGV和機(jī)器的調(diào)度，著力于解決AGV和機(jī)器的任務(wù)指派、任務(wù)執(zhí)行時(shí)序問題，將AGV的行駛道路設(shè)定為單道單向，并且不考慮潛在的路徑?jīng)_突。當(dāng)AGV的行駛道路為單道雙向時(shí)，系統(tǒng)的運(yùn)行效率將會(huì)得到提高，但路徑?jīng)_突也會(huì)隨之增加。路徑?jīng)_突如果不解決，就會(huì)出現(xiàn)AGV碰撞以及路徑被死鎖等問題，打亂調(diào)度計(jì)劃甚至造成生產(chǎn)系統(tǒng)癱瘓。因此，在AGV和機(jī)器集成調(diào)度問題中，考慮AGV路徑?jīng)_突具有重要的現(xiàn)實(shí)意義。Said-imehrabad等[9]建立了一個(gè)由車間調(diào)度和無沖突路徑組成的數(shù)學(xué)模型，提出一種二階段蟻群算法，首先解決AGV的分配問題，然后再解決AGV的路徑?jīng)_突問題。Shi等[10]考慮AGV運(yùn)行時(shí)間、停車和轉(zhuǎn)彎的影響，提出一種兩階段調(diào)度策略，首先通過Dijkstra算法規(guī)劃路徑，然后考慮AGV之間的約束關(guān)系并通過遺傳算法對(duì)結(jié)果進(jìn)一步優(yōu)化。Lyu等[11]提出一種改進(jìn)遺傳算法求解柔性作業(yè)車間AGV和機(jī)器的集成調(diào)度問題，通過Dijkstra算法為AGV規(guī)劃無沖突的最短路徑，并把AGV數(shù)量當(dāng)做變量研究最大完工時(shí)間的變化，若在算法中采用主動(dòng)解碼，其結(jié)果將會(huì)更優(yōu)。

AGV和機(jī)器集成調(diào)度問題已經(jīng)被證明是NP難問題的疊加[7]，這類問題的解空間龐大且復(fù)雜，精確算法難以在可接受的時(shí)間內(nèi)求得最優(yōu)解，啟發(fā)式算法更適合求解此類問題。鯨魚優(yōu)化算法是Mirjalili等[12]于2016年模仿座頭鯨獨(dú)特捕食行為提出的仿生算法，和其他智能優(yōu)化算法相比，具有結(jié)構(gòu)簡(jiǎn)單、參數(shù)少、搜索能力強(qiáng)且易于實(shí)現(xiàn)等優(yōu)點(diǎn)，在航路規(guī)劃[13]、港口拖船調(diào)度[14]及選址問題[15]等離散優(yōu)化問題中的應(yīng)用越來越多。

綜上所述，傳統(tǒng)的作業(yè)車間調(diào)度研究不考慮工件轉(zhuǎn)移時(shí)間，無法滿足當(dāng)前生產(chǎn)模式轉(zhuǎn)變所帶來的新需求。同時(shí)，目前對(duì)于AGV和機(jī)器集成調(diào)度問題的研究大多不考慮路徑?jīng)_突，與實(shí)際生產(chǎn)情況不符，而考慮路徑?jīng)_突的研究大多采用分階段的策略進(jìn)行求解，并非真正意義上的集成調(diào)度。鯨魚優(yōu)化算法作為一種啟發(fā)式算法在離散優(yōu)化領(lǐng)域取得了一定的成功，但在調(diào)度領(lǐng)域的應(yīng)用不多。為了實(shí)現(xiàn)無沖突路徑的AGV和機(jī)器集成調(diào)度，筆者首先以最大完工時(shí)間為優(yōu)化目標(biāo)，建立數(shù)學(xué)模型；然后，為了求解該模型，將鯨魚優(yōu)化算法應(yīng)用在集成調(diào)度領(lǐng)域，對(duì)于鯨魚優(yōu)化算法存在的不足，提出針對(duì)性的改進(jìn)方法，即基于時(shí)間窗和Dijkstra的離散型鯨魚優(yōu)化算法；鯨魚優(yōu)化算法作為算法迭代的整體框架，基于時(shí)間窗的Dijkstra算法用于算法解碼過程中AGV的路徑規(guī)劃；最后，通過標(biāo)準(zhǔn)算例對(duì)比實(shí)驗(yàn)和柔性算例實(shí)驗(yàn)驗(yàn)證了所提算法的性能。

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

假設(shè)有n個(gè)需要加工的工件，m臺(tái)用于加工的機(jī)器，k臺(tái)用于運(yùn)輸工件的AGV。每一個(gè)工件有ni道工序，每道工序至少可由一臺(tái)機(jī)器加工，選擇不同的機(jī)器加工時(shí)間一般不同。每臺(tái)AGV可以在任意兩臺(tái)機(jī)器以及倉庫之間運(yùn)輸工件，運(yùn)輸?shù)穆肪€一般是起點(diǎn)和終點(diǎn)之間可行的最短路徑，運(yùn)輸時(shí)間取決于運(yùn)輸路線的長(zhǎng)度以及路途中的沖突狀況。AGV完成一個(gè)運(yùn)輸任務(wù)分為空載和負(fù)載兩個(gè)階段，空載階段AGV需要從當(dāng)前位置行駛到工件當(dāng)前所在的位置；負(fù)載階段AGV將工件從當(dāng)前位置運(yùn)輸?shù)郊庸C(jī)器所在位置。

已知條件有：AGV數(shù)量、各機(jī)器的位置、所有工序可選擇進(jìn)行加工的機(jī)器及對(duì)應(yīng)的加工時(shí)間、任意兩節(jié)點(diǎn)之間的距離(當(dāng)不可通行時(shí)為無窮大)。要求在滿足一定的約束條件的情況下達(dá)到優(yōu)化目標(biāo)的目的，具體可分為以下幾個(gè)子問題：為每一道工序分配機(jī)器和AGV；為各機(jī)器安排加工任務(wù)序列和各加工任務(wù)開工時(shí)間；為各AGV安排運(yùn)輸任務(wù)序列和各運(yùn)輸任務(wù)開始時(shí)間。此外，為了簡(jiǎn)化問題，存在以下假設(shè)：

1)在開始時(shí)刻，所有AGV和工件都在倉庫，AGV隨機(jī)出發(fā)，有先后順序。

2)每臺(tái)AGV均可運(yùn)輸所有工件且一次只能運(yùn)輸一個(gè)工件。

3)AGV的行駛速度恒定不變。

4)每臺(tái)加工機(jī)器的工件緩沖區(qū)無限大。

5)AGV完成運(yùn)輸任務(wù)后可以?？吭跈C(jī)床旁邊，不需要返回倉庫。

6)每臺(tái)機(jī)器一次只能加工一個(gè)工件且一旦開始加工就不會(huì)中斷。

7)加工準(zhǔn)備時(shí)間以及裝卸工件的時(shí)間算在加工時(shí)間中。

8)所有路段同一時(shí)刻只允許一臺(tái)AGV通過，且任意路段可容納AGV的車身，不存在AGV占用兩個(gè)車道的情況。

9)同一個(gè)工件的工序有先后約束，不同工件之間的工序無約束。

10)不考慮AGV故障、電量等因素，也不考慮機(jī)器故障。

11)所有工件都增加一道虛擬工序，加工時(shí)間為0，加工機(jī)器的位置為倉庫位置，便于處理將工件運(yùn)送回倉庫。

1.2 數(shù)學(xué)模型

目標(biāo)函數(shù)如下：

f=min(max(C1,…,Ci，…,Cn))。

(1)

約束條件如下：

1)任意工序都只能由一臺(tái)機(jī)器完成加工。

(2)

2)任意一道工序最多只由一臺(tái)AGV負(fù)責(zé)運(yùn)輸。

(3)

3)AGV空載出發(fā)時(shí)間不早于AGV上一次運(yùn)輸任務(wù)結(jié)束時(shí)間和工件開工時(shí)間。

(4)

(5)

4)AGV空載結(jié)束時(shí)間為空載出發(fā)時(shí)間與空載運(yùn)行時(shí)間之和。

(6)

5)AGV負(fù)載出發(fā)時(shí)間不早于AGV空載結(jié)束時(shí)間和工件完工時(shí)間。

(7)

(8)

6)AGV負(fù)載結(jié)束時(shí)間為負(fù)載出發(fā)時(shí)間與負(fù)載運(yùn)行時(shí)間之和。

(9)

7)某工序的開工時(shí)間不早于負(fù)載結(jié)束時(shí)間和機(jī)器前序工序的完工時(shí)間。

(10)

(11)

8)工序的完工時(shí)間為開工時(shí)間和加工時(shí)間之和。

(12)

9)工件的完工時(shí)間為AGV將其運(yùn)送到倉庫的時(shí)間。

(13)

10)某個(gè)路段有AGV進(jìn)入之后，在該AGV駛出該路段之前，不允許其他AGV從該路段出口駛?cè)搿?/p>

(14)

11)同一時(shí)刻任意一個(gè)節(jié)點(diǎn)只能容下一臺(tái)AGV。

(15)

2 算法描述

2.1 基本鯨魚優(yōu)化算法

鯨魚優(yōu)化算法是Mirjalili通過座頭鯨獨(dú)特的泡泡網(wǎng)狩獵方式抽象而來，種群中鯨魚的最優(yōu)位置就是算法所獲得的最優(yōu)解，迭代過程主要分為兩個(gè)階段：探索階段和開發(fā)階段，通過|A|和1的大小關(guān)系來區(qū)分[12]。

(16)

(17)

式中:r1是0到1之間的隨機(jī)數(shù)；f為當(dāng)前迭代次數(shù)；fmax為最大迭代次數(shù)。

當(dāng)|A|≤1時(shí)，算法側(cè)重于局部開發(fā)，鯨魚個(gè)體向當(dāng)前種群最優(yōu)鯨魚個(gè)體靠近，有收縮包圍和螺旋更新兩種靠近方式，為了實(shí)現(xiàn)這兩種方式的同步，引入概率p去判斷應(yīng)該執(zhí)行哪種更新方式。

(18)

D=|CXbest-Xt|，

(19)

C=2·r2。

(20)

式中：D為更新步長(zhǎng)；b為控制螺旋線形狀的常量系數(shù)；l為[0,1]范圍服從均勻分布的隨機(jī)數(shù)；r2為0到1之間的隨機(jī)數(shù)。

當(dāng)|A|>1時(shí)，算法側(cè)重于進(jìn)行全局搜索，鯨魚個(gè)體向當(dāng)前種群中一個(gè)隨機(jī)選擇的鯨魚個(gè)體靠近。

Xt+1=Xrand(t)-A·D，

(21)

D=|C·Xrand-Xt|。

(22)

鯨魚優(yōu)化算法作為新型群智能優(yōu)化算法，存在結(jié)構(gòu)簡(jiǎn)單、參數(shù)少、搜索能力強(qiáng)且易于實(shí)現(xiàn)等優(yōu)點(diǎn)，但也有群智能優(yōu)化算法的通病，如收斂速度慢、容易陷入局部最優(yōu)及收斂精度較低等。針對(duì)以上缺點(diǎn)，筆者結(jié)合車間調(diào)度問題的特點(diǎn)提出一種改進(jìn)型鯨魚優(yōu)化算法。

2.2 離散化改造

為了更加清晰地描述問題，此處引入一個(gè)實(shí)例加以說明，各工件的信息如表1所示。

表1 加工信息

2.2.1 問題編碼

作業(yè)車間機(jī)器和AGV共同調(diào)度問題中的調(diào)度子問題包含3個(gè)部分：工序排序、機(jī)器分配和AGV分配。筆者采用三段式編碼，由3條基因串組成：第1條為基于工序的基因串，第2條為基于機(jī)器的基因串，第3條為基于AGV的基因串?；虼忻總€(gè)位置值的取值范圍為[-δ,δ]。由于引入了Levy步長(zhǎng)更新鯨魚個(gè)體，如果δ取得過小，更新后的個(gè)體工序序列基因值相對(duì)大小變化較大，導(dǎo)致個(gè)體被破壞；如果δ取得過大，則會(huì)導(dǎo)致Levy步長(zhǎng)策略效果不明顯，一般設(shè)為2～5之間的數(shù)。圖1所示為一個(gè)合法的編碼。

圖1 個(gè)體連續(xù)編碼示意圖Fig. 1 Schematic diagram of individual continuous coding

2.2.2 編碼轉(zhuǎn)換

鯨魚優(yōu)化算法的解空間是連續(xù)空間，然而調(diào)度問題是離散組合優(yōu)化問題。為了使得鯨魚優(yōu)化算法適用于調(diào)度問題，需要將連續(xù)的解空間映射到離散的解空間。由于工序排序、機(jī)器選擇和AGV選擇的約束不同，需要采取不同的轉(zhuǎn)換機(jī)制。

采用LPV(largest position value)規(guī)則[16]對(duì)工序序列進(jìn)行解空間的轉(zhuǎn)換。具體的操作過程為，首先給所有基因從左至右安排一個(gè)從1開始的固定ID與之對(duì)應(yīng)，然后將他們按從大到小的順序排序，最后根據(jù)每個(gè)基因?qū)?yīng)的ID得到一個(gè)新的基因串，按照每個(gè)工件的工序數(shù)轉(zhuǎn)換為可以用以解碼的序列，過程見圖2。

圖2 LPV轉(zhuǎn)換示意圖Fig. 2 LPV conversion diagram

圖2中，離散編碼中的值表示的是工件號(hào)，從左至右出現(xiàn)的次數(shù)表示的是工序，第1個(gè)3表示的是工序O31，第2個(gè)3表示的是工序O32。

對(duì)于機(jī)器和AGV的解空間轉(zhuǎn)換，采用文獻(xiàn)[17]的方法。首先根據(jù)式(16)將連續(xù)的編碼轉(zhuǎn)換為離散編碼，然后根據(jù)工序可選機(jī)器和AGV序列，轉(zhuǎn)換為具體的機(jī)器和AGV編號(hào)。同時(shí)，通過逆運(yùn)算實(shí)現(xiàn)從離散空間映射到連續(xù)空間，具體見式(23)。在AGV和機(jī)器基因串中，從左至右依次為從第一個(gè)工件到最后一個(gè)工件每一道工序?qū)?yīng)的機(jī)器和AGV。具體見圖3和圖4。

(23)

式中:m(i)為連續(xù)編碼的基因值；z(i)為該工序可選的加工機(jī)器數(shù)或者AGV數(shù)；u(i)為得到的離散基因值。

圖3 機(jī)器編碼轉(zhuǎn)換示意圖Fig. 3 Schematic diagram of machine coding conversion

圖4 AGV編碼轉(zhuǎn)換示意圖Fig. 4 Schematic diagram of AGV encoding conversion

基于機(jī)器的基因串前3個(gè)基因值為工件1對(duì)應(yīng)的3道工序?qū)?yīng)的機(jī)器，圖3和4表達(dá)的意思為：工件1的3道工序分別選擇1，4，3號(hào)機(jī)器進(jìn)行加工；基于AGV的基因串與基于機(jī)器的基因串類似。AGV的基因串前3個(gè)數(shù)字的意思為：工件1 3道工序分別選擇1，3，2號(hào)AGV進(jìn)行運(yùn)輸。針對(duì)機(jī)器和AGV共同調(diào)度問題，上述編碼及其轉(zhuǎn)換方式不會(huì)產(chǎn)生非法解。

2.2.3 規(guī)則調(diào)整

算法迭代過程中，可能會(huì)導(dǎo)致鯨魚個(gè)體的某些維度越界。在原始鯨魚優(yōu)化算法中，每一輪迭代完成以后才會(huì)對(duì)越界個(gè)體進(jìn)行調(diào)整。然而這種處理方式會(huì)導(dǎo)致一些問題，如在鯨魚個(gè)體迭代過程中可能會(huì)選中越界的個(gè)體作為位置更新的基準(zhǔn)，進(jìn)而造成更多個(gè)體越界，不僅會(huì)增加算法的運(yùn)行時(shí)間而且還會(huì)導(dǎo)致一些非越界個(gè)體被破壞。因此，選擇在個(gè)體位置更新以后就進(jìn)行個(gè)體越界的調(diào)整。原始鯨魚優(yōu)化算法中，將越界的維度設(shè)置為最大值或者最小值，當(dāng)越界情況較多時(shí)，導(dǎo)致個(gè)體之間相似度越來越大。因此，可以將越界的維度設(shè)置為接近邊界的一個(gè)值。具體調(diào)整規(guī)則見式(24)。

(24)

式中X(i)表示個(gè)體X的第i個(gè)維度。

2.3 種群初始化

初始化種群對(duì)于進(jìn)化算法來說十分重要[18]，初始解的質(zhì)量和多樣性對(duì)于算法的求解精度和收斂速度有非常大的影響。這里提出一種擴(kuò)展GLR選擇方法結(jié)合混沌映射和對(duì)立學(xué)習(xí)的種群初始化方法。

如果在生成初始解的時(shí)候，考慮各機(jī)器和AGV的工作時(shí)間與負(fù)載均衡可以大大提高種群的質(zhì)量。在FJSP(flexible job-shop scheduling problem)問題上GLR(global, local, random)機(jī)器選擇方法[19]被證明是一個(gè)比較有效的方法，該方法在隨機(jī)生成50%個(gè)體的基礎(chǔ)上，考慮工作時(shí)間與負(fù)載均衡，使用全局選擇方法生成20%的個(gè)體。在該方法中，首先隨機(jī)選擇一道工序，將所有可加工機(jī)器已工作時(shí)間加上該工序的加工時(shí)間，然后選擇目前加工時(shí)間最小的那個(gè)機(jī)器作為本道工序的加工機(jī)器并更新其加工時(shí)間。局部選擇方法生成30%的個(gè)體，在該方法中，首先隨機(jī)選擇一個(gè)工件，為該工件的所有工序選擇機(jī)器，按照全局選擇的方法進(jìn)行選擇機(jī)器，不同的是，當(dāng)一個(gè)工件所有工序都選擇了對(duì)應(yīng)的機(jī)器后，將所有的機(jī)器運(yùn)行時(shí)間置零。該方法也應(yīng)用在AGV的選擇上，在AGV序列初始化時(shí)，為了減少計(jì)算量，在計(jì)算AGV的運(yùn)行時(shí)間時(shí)不考慮沖突。

由于對(duì)于優(yōu)化問題的全局最優(yōu)解沒有任何先驗(yàn)知識(shí)，初始種群應(yīng)該盡可能地均勻分布在解空間中。所以增強(qiáng)初始種群的多樣性以奠定算法全局搜索的基礎(chǔ)一直是算法優(yōu)化的一個(gè)方向。目前，大多數(shù)研究主要采用混沌映射策略和對(duì)立學(xué)習(xí)策略來增強(qiáng)智能優(yōu)化算法初始種群的多樣性。Ewees等[20]提出一種基于混沌映射的多元宇宙優(yōu)化算法用以提高算法的全局搜索性能；Shen等[21]提出一種基于PSO和混沌映射的多種群優(yōu)化算法；Alamri等[22]提出一種對(duì)立學(xué)習(xí)策略對(duì)鯨魚優(yōu)化算法進(jìn)行改進(jìn)。混沌映射和對(duì)立學(xué)習(xí)在改進(jìn)算法上取得了許多成功，但是由于有很多混沌映射和對(duì)立學(xué)習(xí)方法可供選擇，所以選擇什么方法可以最大程度上提高算法性能是一個(gè)值得研究的問題；Elaziz等[23]使用基于差分進(jìn)化算法的超啟發(fā)式算法選擇混沌映射方法和對(duì)立學(xué)習(xí)方法及其比例以得出最優(yōu)組合，通過對(duì)35組標(biāo)準(zhǔn)函數(shù)的測(cè)試證明了其結(jié)論的可靠性。在經(jīng)過GLR方法生成個(gè)體的基礎(chǔ)上使用高斯映射和標(biāo)準(zhǔn)對(duì)立學(xué)習(xí)且比例為25%的策略生成初始化種群。高斯映射和標(biāo)準(zhǔn)對(duì)立學(xué)習(xí)表達(dá)式見式(25)(26)。

(25)

(26)

2.4 Levy飛行策略和閾值

Levy飛行是一種服從Levy分布的隨機(jī)搜索路徑，Levy分布是法國(guó)數(shù)學(xué)家Levy提出的一種概率分布。由于Levy分布是一種重尾分布，所以Levy飛行是一種短距離和偶爾長(zhǎng)距離相間的搜索方式。隨著Levy飛行在連續(xù)優(yōu)化領(lǐng)域取得大量成功，近年來逐漸有學(xué)者將其應(yīng)用到組合優(yōu)化問題的研究中。王學(xué)武等[24]提出一種結(jié)合Levy飛行的粒子群算法以解決點(diǎn)焊機(jī)器人的路徑優(yōu)化問題；徐坤等[25]提出一種Levy飛行模式與蟻群算法的信息素更新方式相結(jié)合的算法用來解決TSP問題；Liu等[26]將levy飛行結(jié)合差分進(jìn)化算法用來解決JSP問題。以上表明Levy策略在解決組合優(yōu)化問題上也有較優(yōu)異的表現(xiàn)。鯨魚優(yōu)化算法在迭代后期a逐漸減小，算法容易陷入局部最優(yōu)。因此，將Levy飛行策略引入到算法迭代后期，增強(qiáng)其跳出局部最優(yōu)的能力。同時(shí)，在算法的探索階段引入Levy飛行策略可以增強(qiáng)算法的全局搜索能力。

X(t+1)=X(t+1)+[r-1/2]⊕L。

(27)

式中：X(t)表示的是經(jīng)過鯨魚優(yōu)化算法迭代以后的個(gè)體；[r-1/2]有3種取值，r是服從范圍在[0,1]的均勻分布函數(shù)，當(dāng)r<1/2時(shí)，[r-1/2]取-1；當(dāng)r=1/2時(shí)，[r-1/2]取0；當(dāng)r>1/2時(shí)，[r-1/2]取1；⊕表示的是Levy飛行操作。所采用的工序編碼轉(zhuǎn)換方式，本質(zhì)上取決于各個(gè)維度的相對(duì)值大小，所以對(duì)于工序向量要對(duì)每個(gè)維度單獨(dú)進(jìn)行Levy飛行操作。Levy飛行具體的數(shù)學(xué)表達(dá)式見式(28)～(31)。

L(s)～|s|-1-β,0<β≤2，

(28)

(29)

(30)

(31)

式中：Γ是標(biāo)準(zhǔn)伽馬函數(shù)；β一般取1.5。

閾值操作也是防止算法陷入局部最優(yōu)常見做法之一。具體的做法為：在算法開始時(shí)設(shè)置一個(gè)全局最優(yōu)保持代數(shù)g并令其等于零，然后在算法迭代過程中記錄當(dāng)前最優(yōu)值保持代數(shù)，當(dāng)g達(dá)到設(shè)置的閾值l時(shí)，用隨機(jī)生成的個(gè)體代替50%較劣個(gè)體。閾值的設(shè)置對(duì)算法有較大的影響，當(dāng)閾值設(shè)置過小時(shí)，算法不易收斂且導(dǎo)致算法復(fù)雜度增加；當(dāng)閾值設(shè)置過大時(shí)，會(huì)造成算法收斂速度變慢。一般設(shè)為最大迭代次數(shù)的10%～15%。

2.5 局部搜索

在開發(fā)階段，種群個(gè)體以當(dāng)前最優(yōu)個(gè)體為基準(zhǔn)來更新自己的位置，對(duì)較優(yōu)個(gè)體進(jìn)行局部搜索可以較大提升算法求解精度和收斂速度。由于AGV設(shè)備比較昂貴，在車間中AGV數(shù)量往往較少。對(duì)于機(jī)器和AGV共同調(diào)度的問題，經(jīng)常出現(xiàn)工件等待AGV運(yùn)輸?shù)默F(xiàn)象，合理地分配AGV對(duì)于減小最大完工時(shí)間至關(guān)重要。提出的局部搜索分為兩部分：基于工序和機(jī)器的變鄰域搜索和基于約束AGV的鄰域搜索，把最遲完成搬運(yùn)任務(wù)的AGV定義為約束AGV。

1)鄰域結(jié)構(gòu)N1：在其工序的基因串中，隨機(jī)選擇兩個(gè)位置，保證這兩個(gè)位置必須對(duì)應(yīng)不同工件的工序，互換它們的位置。

2)鄰域結(jié)構(gòu)N2：在其工序的基因串中，隨機(jī)選擇兩個(gè)位置，將后一個(gè)基因插入到前一個(gè)基因的前一個(gè)位置。

3)鄰域結(jié)構(gòu)N3：在其機(jī)器的基因串中，隨機(jī)選擇一個(gè)位置，保證該位置對(duì)應(yīng)工序的可加工機(jī)器不唯一，從該工序的可加工機(jī)器中隨機(jī)選擇一個(gè)替換該位置的機(jī)器。

在以上3種鄰域結(jié)構(gòu)的基礎(chǔ)上，基于工序和機(jī)器的變鄰域搜索算法步驟如下。

步驟1 設(shè)置初始參數(shù)，將要進(jìn)行變鄰域搜索的個(gè)體設(shè)為初始個(gè)體X；當(dāng)前迭代次數(shù)n設(shè)為1，最大迭代次數(shù)nmax設(shè)為5，p設(shè)為1，pmax設(shè)為3。

步驟2 判斷是否達(dá)到循環(huán)終止條件n≥nmax，如滿足，輸出當(dāng)前個(gè)體X；否則，轉(zhuǎn)步驟3。

步驟3 在個(gè)體X的基礎(chǔ)上隨機(jī)選擇一個(gè)鄰域結(jié)構(gòu)，得到一個(gè)擾動(dòng)個(gè)體。

步驟4 在擾動(dòng)個(gè)體X′的基礎(chǔ)上進(jìn)行變鄰域搜索，其具體步驟為：

1)判斷是否達(dá)到終止條件p≥pmax，如滿足，輸出當(dāng)前解X′。

步驟5 令X←X′，n←n+1，轉(zhuǎn)步驟2。

基于約束AGV的鄰域搜索以基于工序和機(jī)器的變鄰域搜索輸出的個(gè)體為初始解，步驟如下。

步驟① 初始化參數(shù)，將初始個(gè)體設(shè)為X；當(dāng)前操作的AGV任務(wù)編號(hào)n←1，nmax為總?cè)蝿?wù)數(shù)。

步驟② 判斷是否滿足終止條件n≥nmax，如滿足，輸出個(gè)體X；否則，轉(zhuǎn)步驟③。

步驟③ 將當(dāng)前任務(wù)分配給當(dāng)前運(yùn)行時(shí)間最小的AGV得到新個(gè)體X′；如果f(X′)

2.6 多AGV路徑規(guī)劃

在算法對(duì)個(gè)體進(jìn)行解碼的過程中，工序確定加工機(jī)器以后，還需要根據(jù)工件的最早可開工時(shí)間以及機(jī)器的加工時(shí)間確定工序的實(shí)際開完工時(shí)間。在傳統(tǒng)的車間調(diào)度方案中，工序的最早可開工時(shí)間為上道工序的完工時(shí)間，而AGV和機(jī)器集成調(diào)度問題要考慮工件的轉(zhuǎn)移時(shí)間以及路途中可能遇到的路徑?jīng)_突，因此要想確定工序的最早可開工時(shí)間，需要先給AGV規(guī)劃無沖突路徑，筆者采用一種基于時(shí)間窗的Dijkstra算法為AGV規(guī)劃無沖突路徑。

2.6.1 Dijkstra算法

在最短路徑規(guī)劃中Dijkstra算法能夠從全局出發(fā)，具有較強(qiáng)的穩(wěn)定性且算法簡(jiǎn)單[28]。Dijkstra算法要訪問所有節(jié)點(diǎn)及其連通的節(jié)點(diǎn)，肯定可以求出最短路徑，但是在節(jié)點(diǎn)和路段較多的地圖中，求解時(shí)間會(huì)急劇增大。工廠環(huán)境中，AGV沿著固定的軌道行走，AGV也只需往返于各機(jī)器之間。因此，工廠環(huán)境下的地圖節(jié)點(diǎn)和路段都比較少，Dijstra算法可以較好地發(fā)揮性能。另外，優(yōu)化目標(biāo)是最小化最大完工時(shí)間，AGV只有盡早完成任務(wù)工件才能盡早開工，基于貪心策略選擇最短路徑是全局最優(yōu)解。因此，應(yīng)用Dijkstra算法對(duì)AGV進(jìn)行路徑規(guī)劃是一個(gè)較好的選擇。

2.6.2 基于時(shí)間窗的Dijkstra算法

在多AGV參與的制造系統(tǒng)中，路徑?jīng)_突是路徑規(guī)劃中常見的問題。只有解決了路徑?jīng)_突才能實(shí)現(xiàn)真正意義上的集成調(diào)度。在工廠環(huán)境下的AGV沖突主要有：相向沖突、節(jié)點(diǎn)占用沖突和路口沖突。如圖5所示。

圖5 AGV沖突示意圖Fig. 5 AGV conflict diagram

AGV路徑?jīng)_突本質(zhì)上為AGV在時(shí)間或者空間上出現(xiàn)了重疊，時(shí)間窗方法是一種沖突預(yù)測(cè)方法，將地圖以路段為單位記錄鎖定的時(shí)間。時(shí)間窗被證明是一個(gè)可以有效避免AGV沖突的方法。對(duì)于時(shí)間窗的表示方式為：[tin,tout,nin,nout]，nin為進(jìn)入該路段的節(jié)點(diǎn)，nout為離開該路段的節(jié)點(diǎn)，tin和tout分別為進(jìn)入和離開的時(shí)間。這種表示方式可以包含兩部分信息，節(jié)點(diǎn)的時(shí)間窗和路段的時(shí)間窗。由于AGV車身通過節(jié)點(diǎn)需要時(shí)間且要保持安全距離，因此會(huì)在一段時(shí)間內(nèi)占用該節(jié)點(diǎn)。當(dāng)兩個(gè)節(jié)點(diǎn)時(shí)間窗有重疊時(shí)，說明這兩個(gè)AGV有節(jié)點(diǎn)沖突。當(dāng)兩個(gè)路段時(shí)間窗有重疊并且兩個(gè)AGV進(jìn)入該路段的節(jié)點(diǎn)不同時(shí)，說明這兩個(gè)AGV有相向沖突。

解決AGV沖突主要有兩種方法：等待法和二次規(guī)劃法。對(duì)于相向沖突，只有二次規(guī)劃才能解決沖突。對(duì)于節(jié)點(diǎn)占用沖突和路口沖突，等待法肯定可以解決沖突，在時(shí)間窗上表現(xiàn)為將要等待的AGV的時(shí)間窗往后平移至沒有重疊，二次規(guī)劃也可以解決，但是可能會(huì)導(dǎo)致新的沖突甚至死鎖。假設(shè)等待法多花費(fèi)的時(shí)間為Δt，二次規(guī)劃的行駛時(shí)間為T2。如果滿足式(32)，則采用二次規(guī)劃法。

T1+Δt1>Tn+Δtn。

(32)

將時(shí)間窗嵌入到Dijkstra算法中，在對(duì)AGV進(jìn)行路徑規(guī)劃的同時(shí)考慮避碰。為了減少計(jì)算量，對(duì)已經(jīng)規(guī)劃好路徑的AGV不再更改路徑。算法流程圖圖6。

圖6 基于時(shí)間窗的Dijkstra算法流程圖Fig. 6 Dijkstra algorithm flow chart based on time window

2.7 解 碼

以最大完工時(shí)間最小為優(yōu)化目標(biāo)時(shí)，最優(yōu)解必然在主動(dòng)調(diào)度集中[29]。故采用主動(dòng)解碼，在不推遲已經(jīng)被安排的工序開工時(shí)間的前提下，根據(jù)工件的最早可開工時(shí)間查找機(jī)器能夠完成本道工序的空閑時(shí)間段進(jìn)行插入式解碼。傳統(tǒng)的作業(yè)車間調(diào)度中，工件的最早可開工時(shí)間為前序工序的完工時(shí)間，而AGV和機(jī)器集成問題需要考慮工件的轉(zhuǎn)移時(shí)間，所以工件的最早可開工時(shí)間為AGV負(fù)載結(jié)束時(shí)間。

2.8 時(shí)間復(fù)雜度分析

T=2O(n)+O(N)+O(N·(n+f(n)))=O(N·(n+f(n)))。

(33)

T=5O(N·n)+O(N)+O(N·(n+f(n)))+O(f(n))=O(N·(n+f(n)))。

(34)

綜上所述，所提算法和原始鯨魚優(yōu)化算法的時(shí)間復(fù)雜度是一樣的，在同樣的運(yùn)行環(huán)境下的運(yùn)行時(shí)間在同一數(shù)量級(jí)。

2.9 算法流程

算法流程見圖7，具體流程如下。

步驟1 讀入初始信息，包括工件的加工信息和工廠的地圖信息。設(shè)置算法參數(shù)：種群規(guī)模NIND、最大迭代次數(shù)iitmax。

步驟2 根據(jù)種群規(guī)模和編碼方式初始化種群。

步驟3 判斷是否達(dá)到最大種群最大迭代次數(shù)，若達(dá)到，輸出最優(yōu)解；否則，計(jì)算所有個(gè)體最大完工時(shí)間并按照基于時(shí)間窗的Dijkstra算法進(jìn)行路徑規(guī)劃，記錄當(dāng)前全局最優(yōu)解，轉(zhuǎn)步驟4。

步驟4 判斷當(dāng)前全局最優(yōu)解保持代數(shù)是否達(dá)到閾值，如達(dá)到，轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟6。

步驟5 隨機(jī)生成種群規(guī)模50%的個(gè)體以替代種群中50%較劣的個(gè)體，轉(zhuǎn)步驟6。

步驟6 更新鯨魚種群。

步驟7 對(duì)當(dāng)前種群較優(yōu)個(gè)體進(jìn)行局部搜索。

步驟8 保持種群規(guī)模，選擇較優(yōu)個(gè)體進(jìn)入下一次迭代，轉(zhuǎn)步驟3。

圖7 算法流程圖Fig. 7 Algorithm flowchart

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

為了確定和檢驗(yàn)離散型鯨魚優(yōu)化算法在求解AGV和機(jī)器集成調(diào)度時(shí)的性能，筆者在MATLAB 2019a的編程環(huán)境，Inter(R) Core(TM) i5-8500 CPU，3.0 GHz主頻，8.0 Gb內(nèi)存的運(yùn)行環(huán)境下開展以下實(shí)驗(yàn)：

1)標(biāo)準(zhǔn)算例對(duì)比實(shí)驗(yàn)。對(duì)Ulusoy提出的標(biāo)準(zhǔn)算例庫進(jìn)行實(shí)驗(yàn)，并與其他學(xué)者已有的研究成果進(jìn)行對(duì)比。

2)柔性算例實(shí)驗(yàn)。對(duì)文獻(xiàn)[11]提出的柔性作業(yè)車間AGV和機(jī)器集成調(diào)度算例進(jìn)行實(shí)驗(yàn)。

3.1 標(biāo)準(zhǔn)算例實(shí)驗(yàn)

表2中，LB by Ulusoy是由Ulusoy等[2]提出的下限法得到的理論最優(yōu)值；LB by Zheng是由Zheng等[6]提出的改進(jìn)下限估算法得到的理論最優(yōu)值；STW是Bilge等[4]提出的滑動(dòng)時(shí)間窗算法；AGA是Abdelmaguid等[5]提出的混合啟發(fā)式遺傳算法；MTS是Montane等[30]提出的禁忌搜索算法；PGA是Lyu等[11]提出的改進(jìn)遺傳算法；WOA為原始鯨魚優(yōu)化算法；IWOA是筆者提出的離散型鯨魚優(yōu)化算法。其中STW，AGA，MTS，RGA以及PGA均來自于文獻(xiàn)中的原始數(shù)據(jù)。WOA和IWOA部分公共參數(shù)設(shè)置如下：種群規(guī)模80，最大迭代次數(shù)100。WOA的個(gè)體邊界設(shè)為1，IWOA的個(gè)體邊界設(shè)為3，最優(yōu)個(gè)體保持代數(shù)閾值設(shè)為20。WOA和IWOA對(duì)每一個(gè)算例獨(dú)立運(yùn)行5次取最優(yōu)解，和其他文獻(xiàn)結(jié)果對(duì)比如表2和表3所示。

表2 t/p>0.25的算法結(jié)果比較

續(xù)表2

表3 t/p<0.25的算法結(jié)果比較

續(xù)表3

表2和表3中加粗的數(shù)據(jù)為各算法中最優(yōu)結(jié)果。從表2和表3中的82個(gè)標(biāo)準(zhǔn)算例的對(duì)比中可以發(fā)現(xiàn)原始鯨魚優(yōu)化算法在這種解空間較大的情形下，算法很難收斂到全局最優(yōu)解，性能表現(xiàn)較差。對(duì)其進(jìn)行改進(jìn)后，所有算例結(jié)果均不劣于原始鯨魚優(yōu)化算法，并有41個(gè)算例結(jié)果更優(yōu)；相較于原始鯨魚優(yōu)化算法的結(jié)果，IWOA有19個(gè)算例結(jié)果提升了5%以上，其中有7個(gè)算例結(jié)果提升了10%以上。在表2的40個(gè)標(biāo)準(zhǔn)算例中，IWOA所有算例結(jié)果均不劣于其他學(xué)者采用的方法；其中算例EX101、EX103、EX44、EX94、EX104結(jié)果優(yōu)于其他算法結(jié)果；特別的，算例EX22達(dá)到了理論最優(yōu)解。在表3中的42個(gè)標(biāo)準(zhǔn)算例中，IWOA有15個(gè)算例達(dá)到了理論最優(yōu)值；除算例EX840外，IWOA剩下所有算例的結(jié)果均不劣于其他學(xué)者提出的方法，其中算例EX441的結(jié)果優(yōu)于其他算法結(jié)果。由此可以看出，在解決AGV和機(jī)器集成調(diào)度的問題時(shí)，IWOA和其他算法相比具有一定的優(yōu)越性。

3.2 柔性算例實(shí)驗(yàn)

為了驗(yàn)證IWOA在柔性生產(chǎn)系統(tǒng)中的性能，對(duì)文獻(xiàn)[11]中的算例進(jìn)行實(shí)驗(yàn)，該算例中包含4個(gè)工件、6臺(tái)機(jī)器，AGV數(shù)量從1增加到6。文獻(xiàn)[11]中PGA運(yùn)行參數(shù)為：種群規(guī)模設(shè)為80，最大迭代次數(shù)設(shè)為80，交叉率設(shè)為0.9，變異率設(shè)為0.1，算法獨(dú)立運(yùn)行10次取最好結(jié)果。為了更好地對(duì)比，IWOA和WOA的種群規(guī)模、最大迭代次數(shù)、獨(dú)立運(yùn)行次數(shù)和文獻(xiàn)[11]設(shè)為相同的值。WOA的個(gè)體邊界設(shè)為1，IWOA的個(gè)體邊界設(shè)為3，最優(yōu)個(gè)體保持代數(shù)閾值設(shè)為10。表4中v表示AGV數(shù)量，Cmax表示最大完工時(shí)間，單位為min，tcpu表示運(yùn)行時(shí)間，單位為s，MT為平均最大完工時(shí)間，單位為min。

表4 柔性算例結(jié)果

從表4中可以看出，除了算例1中AGV數(shù)量為1時(shí)，IWOA的最大完工時(shí)間大于PGA，在其他算例中，IWOA的最大完工時(shí)間均不劣于其他兩種算法；并且在各算例中可以看出，最大完工時(shí)間隨著AGV數(shù)量的增加而減少，但增加到一定數(shù)量后不再變化，這是由于在AGV數(shù)量較少時(shí)，AGV數(shù)量為制約最大完工時(shí)間的主要因素，較多工件加工完成后需要等待AGV的運(yùn)輸，當(dāng)AGV增加到一定數(shù)量后，加工設(shè)備成為主要制約因素，較多工件運(yùn)輸完成后需要等待加工機(jī)器。從表4中看出在加工機(jī)器數(shù)量相同的情況下，在算例1和算例2中，隨著AGV數(shù)量的增加，IWOA的最大完工時(shí)間小于PGA，這是由于IWOA使用了貪婪解碼，可以在較大程度上利用加工機(jī)器的空閑時(shí)間。在運(yùn)行時(shí)間方面，WOA機(jī)制簡(jiǎn)單，運(yùn)行時(shí)間最短，IWOA的運(yùn)行時(shí)間最長(zhǎng)。從最大完工時(shí)間可以看出，在IWOA中平均值和最小值相差較大，這是因?yàn)镮WOA中加入了Levy飛行的策略，可能導(dǎo)致出現(xiàn)一些較差解，但同時(shí)也可以使算法擁有跳出局部最優(yōu)的能力。

圖8為算例1中AGV數(shù)量為3時(shí)的甘特圖，ET表示AGV的空載行程?？梢钥闯觯泄ば蜷_工時(shí)間在AGV負(fù)載結(jié)束時(shí)間、工件前序工序完工時(shí)間及機(jī)器前序工序完工時(shí)間之后，滿足約束條件。

圖8 最優(yōu)調(diào)度結(jié)果甘特圖Fig. 8 Optimal scheduling result Gantt chart

圖9為算例1中AGV數(shù)量為3時(shí)各路段的時(shí)間窗圖，用不同顏色區(qū)分AGV，可以看出，在任意時(shí)刻的縱坐標(biāo)上不會(huì)出現(xiàn)同一輛AGV，說明AGV分配方案是可行的；在任意路段，不會(huì)出現(xiàn)不同AGV時(shí)間窗的重疊，說明AGV之間不會(huì)發(fā)生碰撞，IWOA可以為AGV規(guī)劃無沖突的路徑。

圖9 各路段時(shí)間窗Fig. 9 Time window of each road section

圖10是算例1中WOA和IWOA在AGV數(shù)量為3時(shí)的收斂曲線。WOA在迭代中后期目標(biāo)值出現(xiàn)最大完工時(shí)間較大幅度減少，體現(xiàn)了WOA在后期具有較強(qiáng)局部開發(fā)能力的特點(diǎn)；但在這之后，最大完工時(shí)間不再改變，說明WOA陷入了局部最優(yōu)。相對(duì)WOA來說，IWOA的初始種群的質(zhì)量較高，驗(yàn)證了IWOA的種群初始化方法的有效性；IWOA在第25代就開始收斂到了89 min，說明算法有較好的收斂速度和收斂精度。

圖10 算法收斂曲線Fig. 10 Algorithm convergence curve

4 結(jié) 論

針對(duì)柔性作業(yè)車間AGV和機(jī)器集成調(diào)度的問題，以最小化最大完工時(shí)間為優(yōu)化目標(biāo)建立了相應(yīng)的數(shù)學(xué)模型，并提出一種離散型鯨魚優(yōu)化算法進(jìn)行求解。在離散型鯨魚優(yōu)化算法中，提出一種結(jié)合GLR選擇方法和混沌映射及對(duì)立學(xué)習(xí)的初始化策略，可以提高初始種群的多樣性；對(duì)原始鯨魚優(yōu)化算法中的調(diào)整規(guī)則進(jìn)行了改進(jìn)，節(jié)省算法運(yùn)行時(shí)間的同時(shí)不僅可以避免個(gè)體被破壞，還可以在出現(xiàn)較多越界情況時(shí)防止個(gè)體相似度增大；引入levy飛行策略和閾值重啟操作，增強(qiáng)算法的全局搜索能力的同時(shí)增強(qiáng)算法跳出局部最優(yōu)的能力；設(shè)計(jì)了一種局部搜索策略，增強(qiáng)算法的收斂精度。通過和82個(gè)標(biāo)準(zhǔn)算例以及柔性算法的仿真對(duì)比實(shí)驗(yàn)，證明了所提出算法的可行性和優(yōu)越性。下一步將研究考慮完工時(shí)間、AGV行駛時(shí)間、AGV等待時(shí)間等AGV和機(jī)器集成調(diào)度多目標(biāo)優(yōu)化問題。