徐逸凡，張利平，唐秋華，黃雨晨

(武漢科技大學(xué) 1.冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室；2.機(jī)械傳動(dòng)與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430081)

柔性作業(yè)車間調(diào)度問題(flexible job-shop scheduling problem，F(xiàn)JSP)是傳統(tǒng)作業(yè)車間調(diào)度問題(jobshop scheduling problem, JSP)的拓展。傳統(tǒng)作業(yè)車間調(diào)度問題中，每個(gè)工件的加工工序是預(yù)先確定的，意味著每道工序的加工機(jī)器和加工時(shí)間是預(yù)先確定的。而在柔性作業(yè)車間調(diào)度問題中，每道工序的加工機(jī)器不用預(yù)先確定，可以在多種加工機(jī)器上選擇一種進(jìn)行加工，通常不同的加工機(jī)器伴隨著不同的加工時(shí)間。FJSP具有生產(chǎn)靈活性，更貼近實(shí)際，是企業(yè)迫切需要解決的問題。

車間實(shí)際生產(chǎn)中，有效的調(diào)度方式可以提高生產(chǎn)效率，降低生產(chǎn)成本。在相關(guān)的柔性作業(yè)車間調(diào)度研究中，陳瑾標(biāo)等[1]針對(duì)具有自動(dòng)裝卸搬運(yùn)機(jī)器人的制造單元，著重考慮其雙重資源約束的特點(diǎn)，提出了該系統(tǒng)的有限緩沖排隊(duì)網(wǎng)的建模方法。張超勇等[2]用改進(jìn)的兩級(jí)遺傳算法有效提高了FJSP的求解效率。為了更貼近實(shí)際生產(chǎn)，很多學(xué)者將工件的移動(dòng)時(shí)間作為一道重要工序融進(jìn)柔性作業(yè)車間調(diào)度問題中。張國(guó)輝等[3]設(shè)計(jì)出有效求解考慮工件移動(dòng)時(shí)間的柔性作業(yè)車間調(diào)度問題的改進(jìn)遺傳算法。有關(guān)研究表明，考慮運(yùn)輸時(shí)間的柔性作業(yè)車間調(diào)度可進(jìn)一步提升車間系統(tǒng)生產(chǎn)效率。

同時(shí)，隨著自動(dòng)化技術(shù)和車間智能化技術(shù)的不斷發(fā)展，自動(dòng)導(dǎo)引小車(automated guided vehicle，AGV)作為一種靈活高效的輸送設(shè)備在制造系統(tǒng)中得到廣泛應(yīng)用。據(jù)相關(guān)資料統(tǒng)計(jì)，制造業(yè)中不足5%的時(shí)間用于加工裝配，而超過95%的時(shí)間用于物料配送，因此物料的及時(shí)準(zhǔn)確供應(yīng)直接關(guān)系到生產(chǎn)線的流暢性。已有研究表明，合理的AGV分配與路徑規(guī)劃可有效提高物料配送效率和準(zhǔn)確率。國(guó)內(nèi)外對(duì)帶AGV柔性作業(yè)車間調(diào)度問題的研究主要集中在生產(chǎn)調(diào)度、機(jī)器分配、AGV調(diào)度分配、AGV路徑選擇4個(gè)方面，通常文獻(xiàn)選擇1個(gè)或2個(gè)方面進(jìn)行求解。徐云琴等[4]研究AGV最優(yōu)調(diào)度方案和最佳AGV數(shù)量，建立使用AGV搬運(yùn)的柔性作業(yè)車間調(diào)度模型。楊鋒英等[5]認(rèn)為AGV作業(yè)調(diào)度主要是對(duì)已有任務(wù)加工序列進(jìn)行AGV的分配和路徑優(yōu)化。何之洲等[6]提出了一種并行禁忌搜索算法，但是僅針對(duì)一臺(tái)搬運(yùn)機(jī)器人的job-shop調(diào)度問題。Babu等[7]使用差分進(jìn)化算法解決了在柔性制造系統(tǒng)中同時(shí)調(diào)度機(jī)器和2個(gè)相同的AGV的問題，但是沒有將工件加工完成后搬運(yùn)至卸載站的時(shí)間考慮在內(nèi)。Lacomme[8]引入了一個(gè)基于析取圖的框架來對(duì)有AGV的聯(lián)合調(diào)度問題進(jìn)行建模，并使用模因算法求得了新的下界值。綜上所述，含AGV的柔性作業(yè)車間調(diào)度研究較少，研究者往往集中在把運(yùn)輸時(shí)間這個(gè)因素作為一道工序放進(jìn)生產(chǎn)調(diào)度中，而忽略了物料設(shè)備選擇以及路徑的規(guī)劃，集成AGV調(diào)度與生產(chǎn)調(diào)度的柔性作業(yè)車間問題還有待進(jìn)一步研究。

灰狼算法(grey wolf optimization，GWO)自提出以來，就因具有良好的性能而引起了眾多學(xué)者的廣泛關(guān)注。GWO參數(shù)較少，易于實(shí)現(xiàn)，具備良好的收斂性，這些優(yōu)點(diǎn)使得GWO被大量應(yīng)用于各種實(shí)際問題的求解。GWO廣泛應(yīng)用于聚類分析、特征子集選擇、經(jīng)濟(jì)調(diào)度指派、直流電機(jī)最優(yōu)控制等諸多領(lǐng)域[9]。然而，灰狼算法多用于解決連續(xù)函數(shù)問題的研究，在車間調(diào)度這類非常復(fù)雜的離散組合優(yōu)化問題中的應(yīng)用還較少。姜天華[10]使用混合灰狼算法解決柔性作業(yè)車間調(diào)度問題，證明了算法的有效性。姚遠(yuǎn)遠(yuǎn)等[11]在重入混合流水車間調(diào)度問題中利用灰狼算法進(jìn)行雙目標(biāo)優(yōu)化求解，驗(yàn)證了算法的有效性。因此，本文將灰狼優(yōu)化算法擴(kuò)展應(yīng)用于帶AGV柔性作業(yè)車間調(diào)度問題，設(shè)計(jì)和改進(jìn)編碼方式、參數(shù)設(shè)定方式、鄰域搜索策略等來改進(jìn)灰狼算法，通過大量基準(zhǔn)的仿真實(shí)驗(yàn)測(cè)試算法的計(jì)算性能，并驗(yàn)證其有效性。

1 問題描述

帶AGV柔性作業(yè)車間調(diào)度問題可以描述為：一個(gè)加工任務(wù)中有n個(gè)工件，每個(gè)工件有若干道工序需要在m臺(tái)機(jī)器上加工，每道工序在其可選加工機(jī)器集合中選取一臺(tái)機(jī)器進(jìn)行加工，工件在不同加工機(jī)器之間的轉(zhuǎn)移由r臺(tái)AGV搬運(yùn)機(jī)器人進(jìn)行搬運(yùn)操作。在調(diào)度初始時(shí)刻，AGV和工件均位于裝載站；調(diào)度結(jié)束時(shí)刻，AGV和工件均位于卸載站。調(diào)度過程中，AGV存在負(fù)載和空載2種狀態(tài)。該問題同時(shí)考慮了工件在裝載站與機(jī)器、卸載站與機(jī)器、不同機(jī)器之間被AGV搬運(yùn)的時(shí)間，需要合理安排工件在不同機(jī)器的加工順序和AGV分配，以優(yōu)化加工車間的某些性能指標(biāo)。參數(shù)定義如表1所示。

表1 參數(shù)定義Table1 Parameter definition

以最小化最大完工時(shí)間為優(yōu)化目標(biāo)，目標(biāo)函數(shù)為

約束條件如下。

首道加工工序時(shí)間約束：工件需從裝載站M0搬至其首道工序的加工機(jī)器。

AGV相鄰兩道搬運(yùn)任務(wù)時(shí)間約束：一臺(tái)AGV完成其上道搬運(yùn)任務(wù)，空載到其下一道搬運(yùn)任務(wù)的初始機(jī)器，再將工件搬運(yùn)至其加工機(jī)器。

工件前后工序搬運(yùn)時(shí)間約束：工件前道工序加工完成后才能搬運(yùn)至下道工序。

同一機(jī)器加工順序規(guī)則約束：機(jī)器按先到先服務(wù)的規(guī)則加工。

工件在機(jī)器上的加工過程約束：工件被搬運(yùn)到機(jī)器輸入緩沖區(qū)需等待機(jī)器空閑再對(duì)其進(jìn)行加工。

2 改進(jìn)的灰狼算法(improved grey wolf optimization, IGWO)

灰狼算法是由Mirjalili等[12]提出的一種受灰狼尋找獵物行為所啟發(fā)的優(yōu)化算法。該算法利用灰狼種群嚴(yán)格的社群機(jī)制來搜索最優(yōu)解。灰狼種群被劃分為α、β、δ和ω 4種等級(jí)，其中，種群中最好個(gè)體定義為α狼，次優(yōu)和第三優(yōu)個(gè)體分別定義為β和δ狼，其余為ω狼。灰狼算法中α、β和δ起領(lǐng)導(dǎo)作用，引導(dǎo)種群中余下低等級(jí)的ω狼平衡種群關(guān)系和發(fā)掘獵物，達(dá)到搜尋最優(yōu)解的目的。這種行為的更新方式為

式中，t為當(dāng)前迭代代數(shù)；A和E為協(xié)同系數(shù)向量；D為灰狼個(gè)體與獵物間的距離；Xp和X分別是獵物位置和灰狼位置；r1、r2是[0, 1]之間的隨機(jī)數(shù)；a是收斂因子，隨著迭代代數(shù)從2線性遞減到0。

在α、β和δ引導(dǎo)ω搜索獵物時(shí)，由于獵物的位置是未知的，該算法假設(shè)獵物位于α、β和δ之間。所以在α、β和δ引導(dǎo)下，種群中灰狼ω位置更新采取如下方式。

Xα、Xβ和Xδ分別為灰狼α、β和δ的位置；Dα、Dβ和Dδ分別為α、β和δ與被引導(dǎo)的個(gè)體X之間的距離。

2.1 編碼和解碼

帶AGV柔性作業(yè)車間調(diào)度問題由加工機(jī)器選擇、工序排序和AGV搬運(yùn)序列排序3個(gè)子問題構(gòu)成。首先，根據(jù)機(jī)器集合中存在的約束關(guān)系合理為每道工序選擇合適加工機(jī)器；然后，對(duì)工件的工序進(jìn)行排序；最后，均勻分配產(chǎn)生AGV搬運(yùn)序列，編碼結(jié)構(gòu)如圖1所示。

圖1 三段編碼Figure1 Three-segment encoding

解碼時(shí)，加工機(jī)器選擇的Ms序列中的數(shù)字表示對(duì)應(yīng)工序可選加工機(jī)器集合中的第幾臺(tái)機(jī)器；工序排序Os序列中工件號(hào)表示工件的每道工序，工件號(hào)的第n次出現(xiàn)表示該工件的第n道工序；AGV搬運(yùn)序列Ts中數(shù)字表示與第2層工序排序編碼對(duì)應(yīng)位置的工序被分配到不同型號(hào)的AGV。

如圖2所示，Ms、Os、Ts編碼從左往右讀取。在對(duì)應(yīng)的第1列中，Ts中的1代表AGV1；Os中的2的第1次出現(xiàn)表示工件2的第1道工序；Ms中3表示加工機(jī)器m3。完整表述為AGV1將工件2搬運(yùn)至機(jī)器m3進(jìn)行第1道工序加工。以此類推，得到一個(gè)可行的調(diào)度方案。

圖2 解碼方式Figure2 Decoding method

2.2 種群初始化

種群初始化產(chǎn)生的解對(duì)算法求解的質(zhì)量和收斂速度有較大的影響。本文采用兩種初始化方式，一是機(jī)器負(fù)載平衡的方式，二是隨機(jī)初始化的方式。根據(jù)上文的編碼方式，工件的總加工工序數(shù)目在調(diào)度任務(wù)開始前是已知的，對(duì)于隨機(jī)生成的加工序列編碼Os，需要將每道工序安排在可選的唯一加工機(jī)器上。機(jī)器負(fù)載平衡的方式確保每臺(tái)機(jī)器上加工工序的數(shù)目盡可能一致，即在初始化選擇加工機(jī)器時(shí)，所有工件的總工序數(shù)目被平均分配到每臺(tái)加工機(jī)器上。機(jī)器負(fù)載平衡的方式與隨機(jī)初始化的方式比例為1∶1。

2.3 狼群位置更新

在算法迭代進(jìn)化中，直接利用灰狼ω位置更新公式對(duì)灰狼ω中的每個(gè)個(gè)體的機(jī)器選擇Ms和工序排序Os進(jìn)行更新，AGV搬運(yùn)序列不進(jìn)行更新。

1) 灰狼ω中個(gè)體加工機(jī)器選擇Ms的更新如下。分別取出灰狼α、β和δ的Ms序列和灰狼ω中的一個(gè)個(gè)體的Ms序列，根據(jù)式(13)的引導(dǎo)方式，取整后產(chǎn)生一個(gè)與Ms序列維度相同的數(shù)組。對(duì)于該數(shù)組中的每個(gè)元素，若元素值為該工序可選加工機(jī)器集中的編號(hào)，則選擇對(duì)應(yīng)機(jī)器編號(hào)；若元素值不存在于該工序可選加工機(jī)器集中，則隨機(jī)選擇一個(gè)加工機(jī)器編號(hào)。

2) 灰狼ω中個(gè)體工序排序Os的更新如下。如圖3所示。首先，存在一個(gè)工序數(shù)組存放該調(diào)度任務(wù)的所有工序，按照自然數(shù)順序從1開始將所有工序依次編號(hào)，工序與工序號(hào)用數(shù)字一一對(duì)應(yīng)。然后，分別取出灰狼α、β和δ的Os序列和灰狼ω中的一個(gè)個(gè)體工序排序Os序列，根據(jù)式(13)的引導(dǎo)方式，產(chǎn)生一個(gè)與Os序列維度相同的元素值數(shù)組，將數(shù)組中的元素按照升序的方式編號(hào)產(chǎn)生一個(gè)升序位置號(hào)的數(shù)組，根據(jù)該數(shù)組中的數(shù)值返回到圖3的工序數(shù)組，匹配相同元素編號(hào)下對(duì)應(yīng)的工序和工序號(hào)，該操作如圖4所示。此時(shí)，灰狼ω中個(gè)體工序排序Os完成更新操作。

圖3 工序數(shù)組Figure3 Operation array

圖4 個(gè)體位置轉(zhuǎn)化為工序排序Figure4 Transformation of individual positions into process sequencing

2.4 參數(shù)a和E的優(yōu)化策略

本文采用文獻(xiàn)[13]提出的改進(jìn)非線性收斂因子a計(jì)算公式。該文獻(xiàn)說明了原始灰狼優(yōu)化算法的收斂因子a從2隨著算法迭代次數(shù)線性遞減到0，但在算法的求解過程中并不是一個(gè)線性過程。改進(jìn)的非線性收斂因子能更好地平衡算法在全局搜索和局部搜索的能力。改進(jìn)收斂因子a為

其中，e是自然對(duì)數(shù)的底數(shù)；t為當(dāng)前迭代的次數(shù)；tmax為最大迭代次數(shù)。

此外，本文采用文獻(xiàn)[14]提出的優(yōu)化參數(shù)E的方式。該文獻(xiàn)通過實(shí)驗(yàn)驗(yàn)證了參數(shù)E對(duì)灰狼算法的影響規(guī)律，并明確指出，在算法迭代的初期，當(dāng)E＞1時(shí)，算法的搜索能力不強(qiáng)導(dǎo)致進(jìn)化緩慢；同時(shí)在算法迭代的后期，當(dāng)E＜1時(shí)，算法容易早熟收斂導(dǎo)致陷入局部最優(yōu)。優(yōu)化參數(shù)E的方法，能夠?qū)崿F(xiàn)在算法迭代初期E以較大概率小于1和算法迭代后期E以較大概率大于1，具備平衡算法勘探能力和局部搜索能力。優(yōu)化參數(shù)E為

其中，r3是[0, 1]之間的隨機(jī)數(shù)，E(1)=2r2。

2.5 基于POX的擾動(dòng)機(jī)制

關(guān)于灰狼算法的尋優(yōu)策略，在進(jìn)化后期，種群中灰狼個(gè)體均向最優(yōu)個(gè)體位置靠近，導(dǎo)致種群多樣性降低，如果最優(yōu)個(gè)體為局部最優(yōu)解，則灰狼算法會(huì)早熟收斂陷入局部最優(yōu)。基于工序編碼的交叉算子POX[15]能夠繼承父代的優(yōu)良特征，且產(chǎn)生的子代均為可行解，這種方式以一定概率保證算法跳出局部最優(yōu)，探索其他解空間的最優(yōu)解。

對(duì)于灰狼算法Os編碼采用POX的擾動(dòng)機(jī)制。考慮到在原始灰狼算法中，種群個(gè)體主要依賴α、β和δ這3個(gè)頭狼的引導(dǎo)來更新，而彼此間的相互作用較弱，因此，在每次迭代時(shí)，以一定概率將POX擾動(dòng)機(jī)制應(yīng)用于灰狼種群中的所有個(gè)體，強(qiáng)化種群內(nèi)部信息交流，豐富種群多樣性。

首先，隨機(jī)確定2個(gè)父代灰狼個(gè)體P1和P2，進(jìn)行POX擾動(dòng)操作后產(chǎn)生2個(gè)子代個(gè)體C1和C2。具體操作步驟如下。

Step1隨機(jī)將工件集合{1, 2, 3, ···,n}劃分為2個(gè)非空子集J1和J2。

Step2復(fù)制P1包含在J1的工件到C1，P2包含在J1的工件到C2，保留它們的位置。

Step3復(fù)制P2包含在J2的工件到C1，P1包含在J2的工件到C2，保留它們的順序。

圖5所示為J1={1, 2}，J2={3, 4}，工件數(shù)n=4，每個(gè)工件有2道工序時(shí)，進(jìn)行POX擾動(dòng)操作。

圖5 POX擾動(dòng)操作Figure5 POX disturbance operation

2.6 鄰域結(jié)構(gòu)

灰狼算法在尋優(yōu)過程中，關(guān)鍵在于α、β和δ這3只頭狼在全局中的引領(lǐng)作用，決策層個(gè)體的優(yōu)劣對(duì)算法性能有決定性影響，因此優(yōu)化決策層個(gè)體能強(qiáng)化算法的計(jì)算性能。而鄰域搜索算法是求解組合優(yōu)化問題的有效局部算法，通過不斷計(jì)算初始解鄰域中解集的適應(yīng)度值，選擇更優(yōu)結(jié)果的個(gè)體替代當(dāng)前個(gè)體，能夠幫助算法跳出局部最優(yōu)。鄰域搜索方法的嵌入能幫助這3個(gè)決策層個(gè)體進(jìn)化，從而改善算法性能。針對(duì)α、β和δ的工序排序Os，本文設(shè)計(jì)了3種鄰域結(jié)構(gòu)，記為N1、N2和N3。這3種鄰域結(jié)構(gòu)如下。每代種群的進(jìn)化過程中，以一定概率同時(shí)對(duì)α使用N1，對(duì)β使用N2，對(duì)δ使用N3進(jìn)行鄰域搜索。

1) 鄰域結(jié)構(gòu)N1：任選2個(gè)位置元素，將后一元素插入到前一元素之前。

2) 鄰域結(jié)構(gòu)N2：任選2個(gè)不同工件的工序交換。

3) 鄰域結(jié)構(gòu)N3：交換首尾2個(gè)元素位置。

2.7 改進(jìn)的灰狼算法流程

改進(jìn)灰狼算法的流程如圖6所示。

圖6 改進(jìn)灰狼算法流程圖Figure6 Flow chart of improved gray wolf algorithm

Step1設(shè)置算法參數(shù)a和E并按2.2節(jié)所描述方式創(chuàng)建初始種群。

Step2評(píng)估種群每個(gè)個(gè)體的適應(yīng)度值，進(jìn)行等級(jí)劃分，確定α、β、δ和ω，判斷是否達(dá)到算法終止條件。若達(dá)到，執(zhí)行Step6；否則執(zhí)行Step3。

Step3以一定概率同時(shí)分別對(duì)α使用N1鄰域搜索方式，對(duì)β使用N2鄰域搜索方式，對(duì)δ使用N3鄰域結(jié)構(gòu)進(jìn)行優(yōu)化。

Step4灰狼算法引導(dǎo)機(jī)制更新種群中的ω個(gè)體。

Step5以一定概率將POX交叉算子應(yīng)用于灰狼種群中的所有個(gè)體，兩兩隨機(jī)選擇個(gè)體匹配。

Step6算法終止輸出最優(yōu)解。

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

上述改進(jìn)的灰狼算法利用Matlab編程，程序運(yùn)行環(huán)境為Windows 10系統(tǒng)下內(nèi)存8G的AMD Ryzen 3 2200G @3.50 GHz計(jì)算機(jī)。

3.1 實(shí)驗(yàn)設(shè)計(jì)

AGV運(yùn)輸時(shí)間矩陣和測(cè)試工件的工序加工是由Kumar等[16]提出的關(guān)于柔性制造系統(tǒng)標(biāo)準(zhǔn)算例。車間加工機(jī)器有4種布局方式，有4種不同AGV運(yùn)輸時(shí)間矩陣，測(cè)試工件的工序加工集合有10種不同工件集合，兩兩組合一共40個(gè)測(cè)試案例。制造系統(tǒng)有4臺(tái)加工機(jī)器和2臺(tái)AGV。這4臺(tái)機(jī)器有4種不同組合布局方式，導(dǎo)致AGV在裝載站與機(jī)器、卸載站與機(jī)器，以及不同機(jī)器之間的搬運(yùn)時(shí)間不同。

3.2 算法性能分析

算法最大迭代次數(shù)為100；初始種群規(guī)模為200；收斂因子a按照式(14)設(shè)置，參數(shù)E按照式(15)設(shè)置；POX擾動(dòng)概率為0.8；鄰域搜索概率為0.5；算法的優(yōu)化目標(biāo)為最小化最大完工時(shí)間，每個(gè)算例連續(xù)運(yùn)行20次。

所選對(duì)比組實(shí)驗(yàn)與本文算法均考慮AGV在裝載站、機(jī)器、卸載站三者之間的有效負(fù)載時(shí)間和空載時(shí)間，MAS(multi-agent system)[17]算法與本文提出的IGWO算法作為一組對(duì)比，該組中AGV數(shù)量均為2臺(tái)，但是沒有考慮工序加工機(jī)器的選擇，系統(tǒng)柔性降低。在另一組FMAS(flexible multi-agent system)[18]、IGWO(n=2)和IGWO(n=3)則考慮了工序加工機(jī)器的選擇。

由表2可知，本文提出的IGWO算法產(chǎn)生解的質(zhì)量普遍更高。在被測(cè)試案例中，AGV數(shù)量為2時(shí)，75%的結(jié)果優(yōu)于MAS算法的結(jié)果。FMAS算法測(cè)試案例對(duì)比本文IGWO(n=2)，本文所求解的結(jié)果32.5%優(yōu)于FMAS的結(jié)果，提供了有競(jìng)爭(zhēng)力的解，驗(yàn)證了IGWO算法的有效性。當(dāng)AGV數(shù)量為3臺(tái)時(shí)，IGWO(n=3)中解的質(zhì)量比IGWO(n=2)中的解有了明顯提升，時(shí)間顯著減少。這充分體現(xiàn)了該類問題特征，AGV數(shù)量的變化會(huì)對(duì)系統(tǒng)加工效率產(chǎn)生明顯影響。

表2 IGWO與其他算法測(cè)試結(jié)果對(duì)比Table2 Comparison between IGWO and other algorithm test results

目前，關(guān)于帶AGV柔性作業(yè)車間調(diào)度問題的研究尚未取得有說服力的下界值。Ulusoy等[19]提出了一種特殊的下界值LBU，在EX11 ～ 104這組案例中，假設(shè)AGV在調(diào)度的任意時(shí)刻均是可以使用的狀態(tài)，即生產(chǎn)系統(tǒng)中AGV數(shù)量總是夠用，且每道工序加工前后立刻有AGV搬運(yùn)，不會(huì)造成等待滯留的情況。在這樣一種特殊假設(shè)下，LBU的結(jié)果通過精確數(shù)學(xué)公式得到，此方法耗費(fèi)大量計(jì)算時(shí)間，如表3所示。LBU、GATS+HM(genetic algorithm with tabu search based on clustered holonic multiagent model)[20]

算法與本文IGWO算法結(jié)果對(duì)比，其中CPU Time1和CPU time2分別為GATS+HM和IGWO的計(jì)算時(shí)間。

由表3可知，2種算法的計(jì)算時(shí)間均較小，且都處于同一數(shù)量級(jí)，但是IGWO所求的解有52.5%的結(jié)果同時(shí)優(yōu)于和LBU和GATS+HM，充分證明了該算法的有效性。

表3 特殊下界值測(cè)試結(jié)果對(duì)比Table3 Comparison of test results for special lower bound values

3.3 算法收斂性分析

以EX33案例為例，改進(jìn)灰狼算法(IGWO)和原始灰狼算法(GWO)的收斂曲線如圖7所示。IGWO在迭代前期以較大的搜索步幅在全局范圍內(nèi)探索較優(yōu)解，后期收斂速度變緩，以較小步幅在局部范圍內(nèi)搜尋最優(yōu)解。因此，IGWO具備較強(qiáng)的全局搜索能力和較快的收斂速度。

圖7 算法收斂曲線Figure7 Algorithm convergence curve

3.4 案例結(jié)果展示

以EX32案例作為結(jié)果展示。其中，包含2臺(tái)AGV、4臺(tái)加工機(jī)器和5個(gè)工件，如圖8所示。甘特圖中折線表示AGV的搬運(yùn)路徑，與橫坐標(biāo)軸平行的直線表示AGV在對(duì)應(yīng)機(jī)器位置的等待過程，此調(diào)度方案的最大完工時(shí)間為86 s。

如圖8所示，在該實(shí)驗(yàn)案例EX32中，尋找到的最優(yōu)解存在2種不同的調(diào)度方案，理論上這兩種方案均有效。

圖8 EX32最優(yōu)解Figure8 EX32 optimal solution

AGV運(yùn)行狀態(tài)如表4所示，機(jī)器加工時(shí)長(zhǎng)如表5所示。

表4 AGV運(yùn)行狀態(tài)Table4 AGV running status h

表5 機(jī)器加工時(shí)長(zhǎng)Table5 Machine processing time s

對(duì)于AGV的運(yùn)行狀態(tài)，負(fù)載時(shí)間是值得關(guān)注的。在EX32(a)中，AGV1負(fù)載時(shí)間在總時(shí)間中的占比為27.9%，AGV2的負(fù)載時(shí)間在總時(shí)間中占比為56.4%；在EX32(b)中，AGV1負(fù)載時(shí)間在總時(shí)間中占比為55.8%，AGV2的負(fù)載時(shí)間在總時(shí)間中占比為29.9%。在這2種方案中，2臺(tái)AGV執(zhí)行不同搬運(yùn)任務(wù)，路徑和時(shí)間均有所差別，總優(yōu)化目標(biāo)為最小化最大完工時(shí)間，AGV之間并不存在優(yōu)化負(fù)載時(shí)間使得每臺(tái)AGV負(fù)載均衡。

此外，可以觀察到在EX32(a)和EX32(b)中，機(jī)器加工時(shí)長(zhǎng)有差異。由于4臺(tái)不同機(jī)器處理不同工序的時(shí)間不相等，而且此時(shí)以最小化最大完工時(shí)間為優(yōu)化目標(biāo)，難以同時(shí)保證機(jī)器加工時(shí)長(zhǎng)相對(duì)均衡。

4 結(jié)論

本文主要針對(duì)2臺(tái)和3臺(tái)AGV參與柔性車間作業(yè)調(diào)度的問題，提出了改進(jìn)灰狼算法解決的方法，結(jié)果與標(biāo)準(zhǔn)測(cè)試案例進(jìn)行對(duì)比，較好解決了帶AGV柔性作業(yè)車間調(diào)度問題，驗(yàn)證了算法的有效性。此外，本文實(shí)驗(yàn)結(jié)果說明了算法具備較好的收斂性，在案例分析的結(jié)果中對(duì)AGV運(yùn)行狀態(tài)和機(jī)器加工時(shí)長(zhǎng)進(jìn)行統(tǒng)計(jì)說明。

該類問題還有許多值得深入研究的地方，未來可以更加智能化分配AGV數(shù)量和搬運(yùn)任務(wù)安排，進(jìn)一步提高生產(chǎn)效率。而且不少傳統(tǒng)柔性作業(yè)車間的調(diào)度規(guī)則不能很好地適用于當(dāng)前的調(diào)度環(huán)境。如何通過數(shù)據(jù)和結(jié)果總結(jié)出更加考慮問題屬性的調(diào)度規(guī)則是非常值得探索的。