基于差分進化算法的FMS中機器與AGV同時調度方法

伍 樂，宋豫川，呂向飛，雷 琦

(重慶大學 機械傳動國家重點實驗室，重慶 400044)

在現代制造業(yè)生產中，多品種小批量、多樣化個性化定制的生產模式已成為發(fā)展趨勢，這必將會對柔性制造系統(tǒng)(flexible manufacturing system, FMS)提出更高的要求。生產調度是柔性制造系統(tǒng)的基礎，制定科學合理的調度方案，對柔性制造系統(tǒng)的性能具有重要影響。其中，柔性作業(yè)車間調度問題(flexible job shop scheduling problem，FJSP)是非常復雜的NP難題。在以往的FJSP研究中，為了簡化數學模型解決問題，大多忽略了工件在不同機器之間的運輸時間，或將其包含在工件加工時間內，這都是不合理的，特別是當工件的移動完全依賴于自動導引小車(automated guided vehicle，AGV)并且運輸時間與加工時間相當時[1]。因此，有必要對FMS中的機器與AGV同時調度問題進行研究。

針對機器與AGV同時調度問題，國內外學者進行了很多研究。早期，Bilge等[2]將問題表述為一個非線性混合整數規(guī)劃模型，采用帶滑動時間窗的迭代啟發(fā)式方法進行求解。這種精確求解算法能夠在簡單小規(guī)模問題上取得全局最優(yōu)解，但隨著問題復雜度的增加，無法在合理時間內搜索到滿意解。近年來，智能優(yōu)化算法如遺傳算法[3-8]、差分進化算法[9]、粒子群算法[10-11]、蟻群算法[12]、花授粉算法[13]等，在求解具有復雜約束的同時調度問題上，取得了較好的進步。Abdelmaguid等[3]提出一種新的啟發(fā)式編碼方案，采用混合遺傳算法同時調度機器與AGV。Kumar等[9]提出機器選擇和車輛分配兩種啟發(fā)式算法，并與差分進化算法相結合，為工件分配合適的機器與AGV，但沒有對算法進行改進，僅對工序操作進行了基本差分變換。Zhang等[10]結合主粒子和嵌套粒子的特點，設計了一種改進粒子群優(yōu)化算法來求解同時調度問題。

差分進化(differential evolution，DE)算法是一種基于種群進化的智能優(yōu)化算法，具有全局搜索能力強，操作簡單，魯棒性好的優(yōu)點。為了增強算法性能，通常需要對算法進行改進。Pan等[14]提出一種求解車間調度問題的離散DE算法，并結合局部搜索算法以改善算法性能。楊鋒英等[15]提出一種改進DE算法求解AGV調度問題，設計了基于個體生存時間的種群更新機制以增強種群多樣性，提高算法的搜索能力。吳秀麗等[16]針對分布式柔性作業(yè)車間調度問題，為離散DE算法設計了新的變異和交叉方式，并引入模擬退火方法以提高算法的局部搜索能力。

從現有文獻來看，DE算法在求解復雜組合優(yōu)化問題上能有較好的表現，但在機器與AGV同時調度問題上應用還較少。并且，大多文獻把集成調度問題分解為了機器調度和AGV調度兩個子問題，忽視了機器調度與AGV調度的緊密聯(lián)系，以及忽略了可變工藝路線對AGV搬運的影響。因此，針對FMS中機器與AGV同時調度問題，在完善集成調度數學模型和改進算法性能方面有進一步研究價值。另外，當AGV數量大于1時，可能會發(fā)生沖突，對機器與AGV調度造成影響。但文中主要圍繞零件加工尺寸較小的車間，其運輸的AGV載重和尺寸也較小，雖然可能發(fā)生沖突，但是在車間區(qū)域內能并行通過，沖突問題產生的概率較小。

筆者針對FMS中機器與AGV同時調度問題，建立了以最大完工時間最小為優(yōu)化目標的調度數學模型，提出了基于工序、機器、AGV的3層編碼結構，以解決機器分配和AGV分配。針對DE算法易陷入局部最優(yōu)的問題，設計了一種混合變鄰域搜索的改進離散差分進化算法，以每次迭代的最優(yōu)解作為局部搜索的初始解，設計了3種不同的鄰域結構進行變鄰域搜索，并采用種群更新策略以增強種群多樣性，進而提升算法搜索到更好解的可能性。最后，通過對比實驗，驗證了所提算法求解FMS中機器與AGV同時調度問題的有效性和優(yōu)越性。

1 問題描述及建模

1.1 問題描述

假設柔性作業(yè)車間有n個待加工工件在m臺機器上加工，若干輛相同的AGV負責工件在機器之間運送。每個工件有ni道不同的工序，每道工序可選擇的加工機器不唯一，每臺AGV可以在任意兩臺機器之間運送工件。已知每個工件加工所需的工序，每道工序在對應加工機器上的加工時間，以及小車在不同機器間的運輸時間，要求在滿足一定約束條件下，為每道工序選擇最合適的加工機器和搬運小車，確定每個工件的每道工序在各機器上的最佳加工順序和開工、完工時間，以及在各AGV上的最佳搬運順序和開始搬運、完成搬運時間，最終滿足優(yōu)化目標。

為了簡化FMS中機器和AGV同時調度問題，假設條件如下：

1)零時刻，所有機器與AGV都可用，機器與AGV連續(xù)工作。

2)任意時刻，每臺機器一次只能加工一個工件，每輛小車一次只能搬運一個工件。

3)同工件的工序有先后約束，不同工件之間無約束。

4)AGV數量提前確定。

5)AGV行駛速度恒定，其負重不影響小車行駛速度。

6)AGV在任意兩臺機器之間的運輸路線是固定的，運輸時間僅與機器之間的距離有關。

7)每臺機器前設置有緩沖區(qū)，緩沖區(qū)無限大，以避免死鎖。

8)所有待加工工件在開始加工前都放在裝載臺M0，完成所有工序加工的工件放入卸載臺Mm+1。

9)小車每次執(zhí)行完任務后?？吭诩庸C器旁，不返回起點。

10)小車沒有裝載工件的行駛過程稱為空載，裝載工件的運送過程稱為負載。

11)不考慮AGV可能發(fā)生沖突、故障、電量不足等問題。

1.2 數學模型

為了建立問題的模型，引入如下符號和變量：

為了便于理解，變量的表示含義如圖1所示。假設工序Oij在機器Mk上加工，工件i的前一道工序Oi(j-1)在機器Mk′上加工，工序Opq在機器Mh上加工。若小車Rv有一搬運任務Tij，需從當前位置Mh空載行駛至Mk′領取工件i，再從Mk′搬運工件i至Mk進行加工。

圖1 變量含義示意圖Fig. 1 Schematic diagram of variable meaning

以最大完工時間最小為優(yōu)化目標，針對FMS中機器與AGV同時調度問題，建立數學模型如下。

目標函數：

(1)

約束條件：

1)每道工序一次只能分配給一臺機器加工。

(2)

2)每道搬運任務一次只能分配給一輛小車運送。

(3)

3)同一輛小車，只有前一道任務Tpq搬運完后，才能開始下一道任務Tij的搬運。

(4)

4)小車從當前的機器位置Mh行駛至該工件前一道工序的加工機器Mk′處領取工件。

(5)

5)小車空載到達機器Mk′并且工序Oi(j-1)加工完成，才能開始搬運。

(6)

6)小車從機器Mk′搬運工件到工序Oij的加工機器Mk處進行加工。

對于寶寶來數，由于宮縮力度過強、頻率過快、子宮收張的間隔太短，會導致胎盤血液循環(huán)受阻，寶寶易在分娩過程中出現缺血、缺氧。而且，胎兒出生過快，由于宮內和外界壓力的變化，很容易造成寶寶皮膚下的毛細血管破裂，出現面部發(fā)紅紫，嚴重者會引起頭部血管破裂，發(fā)生顱內出血。胎兒骨折、產傷風險亦升高。

(7)

7)小車負載到達機器Mk并且機器空閑，才能開始加工。

(8)

8)工序Oij在機器Mk上加工。

(9)

2 混合變鄰域搜索的改進離散差分進化算法

基本DE算法是基于實數編碼的，主要作用于連續(xù)域的優(yōu)化問題。而柔性作業(yè)車間的調度問題是離散的組合優(yōu)化問題，所以需要改進DE算法的變異、交叉操作，以適應算法的離散搜索過程。同時，變鄰域搜索(variable neighborhood search，VNS)算法能夠有效避免算法陷入局部最優(yōu)，提高算法的局部搜索能力。因此，提出混合變鄰域搜索的改進離散差分進化(improved discrete differential evolutionVNS，IDDE-VNS)算法求解FMS中機器與AGV同時調度問題。

2.1 總體流程設計

IDDE-VNS算法的總體流程設計如圖2所示。

圖2 IDDE-VNS算法流程圖Fig. 2 Flow chart of IDDE-VNS algorithm

具體步驟如下。

步驟1：輸入調度信息，工件加工信息和小車運輸時間。設置DE算法控制參數，初始種群規(guī)模P，最大迭代次數Gmax，變異概率F，交叉概率Cr，小車數量Nagv，初始溫度T0。

步驟2：根據編碼方式和初始種群規(guī)模，隨機生成初始種群。

步驟4：全局搜索。

1)根據變異概率F，選擇初始目標種群X執(zhí)行變異操作得到變異種群V。

2)根據交叉概率Cr，對目標種群X與變異種群V進行交叉操作得到試驗種群U。

3)重新計算試驗種群U的適應度值。

4)引入模擬退火思想，比較目標種群X與試驗種群U，按退火概率選擇相應的個體進入下一代。

2.2 詳細設計

2.2.1 編碼和解碼方法

為了表示問題的解，首先需要設計編碼。算法的性能和效率很大程度上取決于染色體的編碼，需要考慮染色體的可行性、完備性、健全性和非冗余性。對于FMS中機器與AGV同時調度問題，不光要安排工序的加工順序，還要確定每道工序的加工機器和每次負責搬運的小車。因此，編碼分為3個部分。第1行表示基于工序的編碼，第2行表示基于機器的編碼，第3行表示基于AGV的編碼。為了便于解釋編碼過程，采用一個3×3FJSP算例來描述，其工件加工信息如表1所示。2臺AGV在任意機器之間的運輸時間如表2所示。

表1 FJSP算例的工件加工信息

表2 各機器之間AGV的運輸時間

圖3 基于工序、機器、AGV的3層編碼結構Fig. 3 The three-layer coding structure of operation, machine and AGV

考慮AGV約束的柔性作業(yè)車間調度問題解碼時，比傳統(tǒng)的車間調度問題更加復雜。除了要確定每個工件的每道工序的開工時間和完工時間，還要確定AGV運送工件的空載、負載開始和完成時間。針對1個工件的某道工序Oij加工過程，如圖1所示，設計解碼方法如下。

1)確定AGV運送工序Oij空載、負載開始和完成時間，具體步驟如下。

步驟1：讀取由上述編碼方式生成的染色體信息，工序順序P、對應加工機器Mk和運送小車編號Rv。

步驟2：記錄AGV當前位置及其走過的路徑。

步驟3：判斷本道工序Oij是否為工件i的第1道工序。若是，跳轉步驟4；若否，跳轉步驟6。

步驟4：判斷AGV的當前位置是否在裝載臺M0。

①若是，AGV空載運輸時間t′= 0。

②若不是，AGV需要從當前位置Mh行駛到裝載臺M0領取工件，AGV空載運輸時間t′=Mh→M0。

步驟5：AGV從裝載臺M0運送工件行駛到本道工序的加工機器Mk處，AGV負載運輸時間t=M0→Mk。

步驟6：判斷AGV的當前位置是否在緊前工序加工機器Mk′處。

①若是，AGV空載運輸時間t′= 0。

②若不是，AGV需要從當前位置Mh行駛至該工件的前一道工序的加工機器Mk′領取工件。若該工件正在機器Mk′上加工，需等待加工完成后再搬運。AGV空載運輸時間t′=Mh→Mk′。

步驟7：AGV從緊前工序加工機器Mk′運送工件行駛到本道工序的加工機器Mk處，AGV負載運輸時間t=Mk′→Mk。

步驟8：輸出AGV空載開始和完成時間，負載開始和完成時間。

2)確定工序Oij的開工時間和完工時間。

(10)

(11)

根據設計的編碼和解碼方法，結合工件的加工信息和2臺AGV的運輸信息，隨機產生一個可行調度方案，其甘特圖如圖4所示。分析甘特圖可知，工件加工過程和小車的運輸過程具體如下，其中“*→”表示AGV空載運行。

圖4 調度方案的甘特圖Fig. 4 Gantt chart of scheduling scheme

R1的運輸過程：M0*→M2(取工件2)→M3(加工O23并取工件1)→M1(等待加工O12)*→M3(取工件2)→M4(工件2完成加工后運到卸載臺)。

R2的運輸過程：M0(取工件2)→M3(加工O21)*→M0(取工件3)→M2(加工O31)*→M0(取工件1)→M3(加工O11并取工件2)→M2(等待加工O22并取工件3)→M1(加工O32)→M4(工件3完成加工后運到卸載臺)*→M3(加工O24)*→M1(取工件1)→M4(工件1完成加工后運到卸載臺)。

2.2.2 全局搜索

根據上述編碼方式，為了使個體直接在離散域搜索，以提高算法搜索速度，對DE算法的操作算子進行了改進。

(12)

(13)

(14)

對基于工序編碼的基因串，采用IPOX交叉[18]。其具體交叉過程為：將工件集{1,2,…,n}隨機分為非空互補的兩個子集S1和S2，復制父代染色體P1中包含S1的工件號到子代染色體C1，復制P1中包含S2的工件號到C2，保留它們的位置；同樣復制P2中包含S1的工件號到C1，復制P1中包含S1的工件號到C2，也保留它們的位置，如圖5所示。

圖5 IPOX交叉過程圖Fig. 5 Crossover process of IPOX

對基于機器編碼的基因串，采用MPX交叉[18]。其具體交叉過程為：首先隨機產生一行長度與父代染色體相等，由0和1組成的基因串。將父代染色體P1中1對應位置的機器號復制到子代染色體C2，父代染色體P2中1對應位置的機器號復制到C1，P1中剩余的機器號保留到子代C1，P2中剩余的機器號保留到子代C2，如圖6所示。

圖6 MPX交叉過程Fig. 6 Crossover process of MPX

對基于AGV編碼的基因串，采用簡單的兩點交叉。

(15)

(16)

式中，T為退火溫度，為了提高算法搜索效率，采用自適應變溫方法，不進行循環(huán)。T的變化見式(17)。

(17)

2.2.3 局部搜索

變鄰域搜索算法比單一的鄰域搜索算法性能更強，它通過改變算法的鄰域結構來擴大其搜索范圍，從而找到更優(yōu)解。文中對當前種群中的最優(yōu)個體執(zhí)行變鄰域搜索，以提高DE算法的局部搜索能力。

設計VNS算法首先需要構造鄰域結構，算法采用了以下3種鄰域結構來產生局部最優(yōu)解：

1)鄰域結構N1。在基于工序編碼的染色體上，隨機選擇2個基因位置，所選的2個位置對應2道不同工件的工序，互換這2個位置。

2)鄰域結構N2。在基于機器編碼的染色體上，隨機選擇1個基因位置，所選位置對應工序的可加工機器不唯一，重新從該工序的可選機器集合中選擇不同的機器替換該位置的機器。

3)鄰域結構N3。在基于AGV編碼的染色體上，隨機選擇1個基因位置，從可選AGV集合中選擇不同的AGV編號替換該位置的AGV編號。

基于上述3種鄰域結構，變鄰域搜索算法的操作步驟如下。

步驟1：算法初始化，將全局搜索得到的最優(yōu)解設為初始解X，設置q←1，qmax=3，cmax=40。

步驟2：判斷循環(huán)終止條件q>qmax是否滿足，若滿足，輸出最優(yōu)個體；否則，轉到步驟3。

步驟3：振動環(huán)節(jié)。初始解X通過鄰域結構Nq搜索得到1個擾動解。

步驟4：局部搜索。

①以振動后的新解作為局部搜索的初始解X′，設置c←1。

②判斷循環(huán)終止條件c>cmax是否滿足，若滿足，輸出局部最優(yōu)解X′；否則轉到步驟③。

③使當前解X′在Nq中搜索得到一個新解X″，若滿足f(X″)

④設置c←c+1，返回步驟②循環(huán)。

步驟5：判斷鄰域移動條件f(X′)

3 實驗分析

實驗測試以MATLAB2016b為開發(fā)環(huán)境，運行環(huán)境為Intel Core i5-6200 CPU，2.40 GHz主頻，4 GB內存。

為了驗證IDDE-VNS算法的性能，展開以下測試實驗：

1)算法對比試驗。針對遺傳算法、差分進化算法和混合變鄰域搜索的改進差分進化算法，對比這3種算法產生的解的質量，為客觀評價提出的改進方法提供依據。

2)非柔性算例實驗。選取Bilge等[2]提出的82個算例中的一部分進行實驗，與其他文獻使用各種優(yōu)化算法得到的計算結果進行對比，為客觀評價IDDE-VNS算法的性能提供依據。

3)柔性算例實驗。選取Zhang等[10]提出的柔性算例進行計算，并與Zhang等[10]得到的優(yōu)化結果對比，為客觀評價IDDE-VNS算法作用在柔性作業(yè)車間時的性能提供依據。

3.1 算法對比實驗

為了驗證提出的改進方法的有效性和可行性，采用Bilge等[2]提出的測試算例中的EX11算例進行實驗。將遺傳算法，差分進化算法和混合變鄰域的改進差分進化算法分別命名為GA、DE、IDDE-VNS，重復運行20次，對比3種算法的迭代曲線和優(yōu)化結果。

3種算法的種群規(guī)模、迭代次數和小車數量都設為：P=80，Gmax=200，Nagv=2；GA的交叉概率和變異概率設為：Pc=0.8，Pm=0.4；DE的變異概率和交叉概率設為：F=0.7，Cr=0.5；IDDE-VNS的變異概率、交叉概率和初始退火溫度設為：F=0.7，Cr=0.5，T0=20。

3種算法的搜索過程曲線如圖7所示，紅色實線為GA，藍色虛線為DE，黃色點劃線為IDDE-VNS。由收斂曲線圖可知，GA能快速收斂到一個較優(yōu)解，但易陷入局部最優(yōu)；DE在進化前期較GA收斂得慢，但在搜索后期發(fā)現更優(yōu)解的可能性更大，使搜索最終得到更好的解；改進后的IDDE-VNS的收斂速度在GA和DE之間，在進化后期，由于引入了變鄰域搜索算法增強了DE算法的局部搜索能力，使其最終搜索到的解的質量在3種算法中最好。

圖7 3種算法收斂曲線對比Fig. 7 Comparison of convergence curves of three algorithms

3種算法計算EX11算例的優(yōu)化結果如表3所示，采用GA進行實驗20次，得到的最優(yōu)解的平均值為100.5，搜索到全局最優(yōu)解96的概率為5%；采用DE進行實驗20次，得到的最優(yōu)解的平均值為98.5，搜索到全局最優(yōu)解96的概率為10%；采用IDDE-VNS進行實驗20次，得到的最優(yōu)解的平均值為97.1，搜索到全局最優(yōu)解96的概率為35%。由此可得，3種算法搜索到的解的質量和穩(wěn)定性的關系為IDDE-VNS>DE>GA。

表3 3種算法求解EX11算例實驗結果

綜上所述，IDDE-VNS比GA、DE的穩(wěn)定性和尋優(yōu)能力更好，證明了文中提出的改進方法是有效可行的。

3.2 非柔性算例實驗

Bilge等[2]提出了82個算例用來測試算法的有效性，由裝載臺、卸載臺、4臺加工機器和2臺AGV構成的4種不同布局和10個不同的工件集組成。EX后面的數字中第一個表示工件集編號，第二個表示布局編號，如“EX32”表示工件集3-布局2。為了驗證IDDE-VNS相比其他算法的優(yōu)越性，選取其中一部分算例進行了測試。IDDE-VNS算法的控制參數設置為：種群規(guī)模P=80，最大迭代次數Gmax=500，變異概率F=0.7，交叉概率Cr=0.5，初始退火溫度T0=20，小車數量Nagv=2。

每個算例獨立計算20次取最優(yōu)值，與其他文獻得到的最優(yōu)解進行對比，如表4所示。其中STW表示文獻[2]采用滑動時間窗求得的最優(yōu)解，AGA表示文獻[3]采用遺傳算法混合啟發(fā)式方法求得的最優(yōu)解，FDE表示文獻[9]采用差分進化算法求得的最優(yōu)解，FMAS表示文獻[19]采用基于MAS方法求得的最優(yōu)解。

由表4可知，IDDE-VNS算法計算測試算例時，其中100%的解優(yōu)于或等于STW和AGA的實驗結果；85%的解優(yōu)于或等于FDE的實驗結果；90%的解優(yōu)于或等于FMAS的實驗結果。特別地，IDDE-VNS算法計算EX71和EX92的解在對比實驗中結果最好。由此可看出，IDDE-VNS在計算機器與AGV同時調度問題時表現優(yōu)秀，與其他優(yōu)秀算法相比有較高的搜索質量，證明了IDDE-VNS算法的優(yōu)越性。

表4 非柔性算例實驗結果

3.3 柔性算例實驗

上述算例中工件的每道工序可選擇的加工機器是唯一的，沒有體現生產系統(tǒng)的柔性。在FMS中，不同加工機器的選擇會影響AGV路線的選擇，從而影響AGV的空載時間和負載時間以及工序的開工時間和完工時間。為了更好體現IDDE-VNS算法在FMS中的作用，借鑒Zhang等[10]給出的柔性作業(yè)車間集成調度算例，由6個工件、6臺機器和4臺AGV構成。

IDDE-VNS算法的控制參數設置與非柔性算例實驗一致，其中最大迭代次數與文獻[10]一致，小車數量改為Nagv=4，運行10次取最優(yōu)值，最優(yōu)實驗結果的調度甘特圖見圖8，最大完工時間為75.6 min。對比Zhang等[10]采用改進粒子群優(yōu)化算法得到的最大完工時間85 min，IDDE-VNS算法搜索到的解的質量更好，證明了IDDE-VNS算法求解FMS中機器與AGV同時調度問題的優(yōu)越性。

圖8 柔性算例調度方案的甘特圖Fig. 8 Gantt chart of flexible example scheduling scheme

4 結 論

針對FMS中機器與AGV同時調度問題，提出了IDDE-VNS算法。

1)基于工序、機器、AGV的3層編碼方案，提出了改進離散差分進化算法，使個體直接在離散域搜索，提高了算法的全局搜索能力和搜索速度。

2)將變鄰域搜索算法嵌入改進差分進化算法中，并按策略對種群進行擾動操作，增加了種群多樣性，提高了算法跳出局部最優(yōu)的能力，從而獲得質量更好的解。

3)實驗結果和比較證明了IDDE-VNS算法求解FMS中機器與AGV同時調度問題的有效性，穩(wěn)定性和優(yōu)越性。

4)在文中研究問題基礎上，結合實際生產情況，下一步將考慮更多影響因素和約束條件，如小車沖突問題，或多目標問題。