基于變鄰域遺傳算法的離散制造物料配送調(diào)度優(yōu)化

李廣博，于 東，胡 毅

(1.中國科學(xué)院大學(xué)，北京 100049；2.中國科學(xué)院沈陽計算技術(shù)研究所 高檔數(shù)控國家工程研究中心 ，沈陽 110168；3.沈陽高精數(shù)控智能技術(shù)股份有限公司，沈陽 110168)

0 引言

離散制造車間加工件種類繁多，加工工藝復(fù)雜，對車間實(shí)時監(jiān)控和物流調(diào)度有較高要求。目前,許多的企業(yè)采用RFID技術(shù)實(shí)現(xiàn)對車間設(shè)備的實(shí)時監(jiān)控，使用自動導(dǎo)引車(Automatic Guided Vehicle，AGV)來實(shí)現(xiàn)加工件的集中管理和無人搬運(yùn)[1]。AGV具有精確的室內(nèi)定位能力以及自動駕駛能力，可以與離散制造車間生產(chǎn)無縫融合，結(jié)合AGV搬運(yùn)與FJSP車間調(diào)度的優(yōu)化研究對實(shí)現(xiàn)生產(chǎn)物料的高效穩(wěn)定運(yùn)送和提高企業(yè)生產(chǎn)效益具有重要的意義。

近年來，人工智能方法在調(diào)度研究方面取得了長足進(jìn)展，以遺傳算法、粒子群算法等為代表的智能算法被諸多學(xué)者研究改進(jìn)并取得了良好的效果。歐陽森山等[2]采用粒子群算法求解評價與遺傳算法結(jié)果擇優(yōu)進(jìn)化的方式進(jìn)行協(xié)同求解；黃海松等[3]和YUAN Y等[4]分別對模擬退火算法和鄰域結(jié)構(gòu)進(jìn)行改進(jìn)；以上算法均未對加工件搬運(yùn)時間進(jìn)行計算。王雷等[5]改進(jìn)了遺傳算法對含AGV柔性車間作業(yè)調(diào)度進(jìn)行求解，但作者只考慮了工件運(yùn)輸時間，忽略了AGV的調(diào)度時間； Zheng Y等[6]采用禁忌搜索算法研究了機(jī)器和自動引導(dǎo)車輛調(diào)度問題，但只考慮了一臺AGV的情況；龍傳澤等[7]采用遺傳算法與啟發(fā)式混合算法對含有AGV的JSP問題進(jìn)行研究，沒有對機(jī)器柔性調(diào)度進(jìn)行研究。

針對遺傳算法局部搜索能力差的問題，根據(jù)已有文獻(xiàn)的研究，設(shè)計了一種變鄰域混合算法對AGV柔性車間調(diào)度問題進(jìn)行求解，調(diào)整了遺傳算法種群初始化方式，使用隨機(jī)方式與機(jī)器使用率優(yōu)先的初始化策略，采用了工序、機(jī)器與AGV編號的分段編碼技術(shù)，使用錦標(biāo)賽選擇方法對個體進(jìn)行選擇，并融合了基于移動和交換工序的變鄰域搜索算法提高了算法的求速度和解的質(zhì)量。

1 問題描述

1.1 AGV調(diào)度模型

以某飛機(jī)制造企業(yè)離散生產(chǎn)車間為模型，含有AGV搬運(yùn)的柔性車間作業(yè)模型如圖1所示，通過立體倉庫將工件分配到AGV上，再由AGV將工件運(yùn)送到相應(yīng)工位上進(jìn)行加工，每個工位上都存在物料緩存區(qū)，將待加工的工件和加工完畢的工件放到緩存區(qū)，通過調(diào)度系統(tǒng)可以實(shí)現(xiàn)AGV對工件在工位之間的搬運(yùn)控制。

圖1 AGV搬運(yùn)模型示意圖

含有AGV搬運(yùn)的FJSP問題是傳統(tǒng)FJSP問題的擴(kuò)展，不僅需要考慮工序的順序約束和每道工序可用機(jī)器集的選擇情況，還需要考慮AGV對加工件的搬運(yùn)調(diào)度。模型中所涉及的機(jī)器、工件、AGV等需要符合的約束規(guī)則如下：

①工件的某道工序一旦選定對應(yīng)的工位機(jī)器在完工前不允許更換。

②工件的某道工序從開始被工位設(shè)備處理到完成必須保持連續(xù)。

③所有的工件都有同級別的優(yōu)先度，都可以從零時刻開始被機(jī)器加工。

④AGV必須等待工件當(dāng)前任務(wù)處理完畢后，才可以將工件送到下一臺工序的機(jī)器工位。

⑤AGV運(yùn)送工件上下料的時間忽略不計。

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

本文參數(shù)符號定義如下：

n:工件總數(shù)，工件Jj:{J1,J2,…Jn}；

m：機(jī)器總數(shù)，機(jī)器Mi:{M0,M1,…Mn}，其中M0表示立體倉庫；

w：AGV總數(shù)，AGVAi:{A1,A2,…An}；

kj:第j個工件的工序總數(shù)；

l:工序序號，l= 1,2,3，kj；

Ojk:第j個工件的第k道工序；

Mijk:表示在工位機(jī)器i上對工件j的第k個待處理工序進(jìn)行加工；

mjk:可以對工件j的工序k加工的機(jī)器數(shù)；

yijk:工位i上對應(yīng)工件j第k道工序的時間；

sjk:工件j的工序k開始被加工時間；

cjk:工件j的工序k被機(jī)器處理完成時間；

ativ:AGV從機(jī)器i到機(jī)器v所花費(fèi)的時間；

rtijkw:AGV搬運(yùn)工件j的工序k到機(jī)器i時刻；

Wtj:AGV完成搬運(yùn)工件j到達(dá)倉庫的時間；

評價指標(biāo)函數(shù)：

(1)

約束條件：

①工件加工順序約束，最大加工時間不能小于任意工件完工時間，工件某道工序開始時間不能超過工件完成時間。

cjk≤sj(k+1)

(2)

cjk≥sjk+qijk×yijk

(3)

②在相同工位上某一時刻只能對一道工序進(jìn)行處理，其中E代表足夠大的正整數(shù)。

qijk+sjk≤shl+E-E×rijkgl

(4)

cjk-sj(l+1)≤+E-E×rijkg(l+1)

(5)

③AGV在工件上一個待處理工序完成才能開始搬運(yùn)工件到下一個設(shè)備上。

sjk+qijk≤ativ+rtijkw

(6)

2 混合算法設(shè)計

2.1 編碼與初始化

含有AGV搬運(yùn)的FJSP問題由機(jī)器選擇、工序排序以及AGV序列編碼三個子問題構(gòu)成，根據(jù)不同機(jī)器加工時間、空閑情況等約束為每道工序選擇合適的機(jī)器，然后對工件的工序進(jìn)行排序，最后按均勻分配的方式根據(jù)工序編碼生成AGV搬運(yùn)序列，確定加工順序和時間。對Ho等[8]編碼實(shí)現(xiàn)進(jìn)行了改進(jìn)，機(jī)器選擇部分由二進(jìn)制編碼改為整數(shù)編碼。表1所示為一個3×4FJSP問題實(shí)例，表中的整數(shù)代表工序在相應(yīng)工位上所需要花費(fèi)的時間，AGV在機(jī)器之間的搬運(yùn)時間如表2所示。

表1 3×4 FJSP問題實(shí)例

表2 AGV搬運(yùn)時間

最終編碼的實(shí)現(xiàn)結(jié)構(gòu)如圖2所示，機(jī)器選擇編碼中的數(shù)字對應(yīng)工件加工順序的可加工設(shè)備集合中第幾臺機(jī)器，工序順序的編碼中的整數(shù)代表所有工件相應(yīng)的每道工序，基因序列中的每一位整數(shù)代表加工的工件號，其相對出現(xiàn)的位置對應(yīng)表示第幾道加工工序，以兩臺AGV小車搬運(yùn)情況的編碼序列為例，AGV序號中的整數(shù)表示AGV車的編號。

圖2 染色體編碼示意圖

種群初始解的生成對算法求解問題的速度和質(zhì)量有較大的影響，當(dāng)前大多數(shù)研究以隨機(jī)、啟發(fā)式、主動調(diào)度等方式進(jìn)行初始解的編碼生成，本文在以上文獻(xiàn)研究基礎(chǔ)上，將機(jī)器利用率納入初始考慮條件，采用機(jī)器最大利用率優(yōu)先、工件工序的AGV最大利用率優(yōu)先、隨機(jī)生成相結(jié)合的初始化方式，三種初始化方式的比例為0.4:0.4:0.2。

2.2 遺傳操作

2.2.1 選擇操作

選擇操作可以使適應(yīng)度較高的基因有更大的生存概率，保證基因后代繼承父代的優(yōu)秀特性，可以使算法求解效率得到有效提升。采用錦標(biāo)賽選擇(tournament selection)方式對編碼個體進(jìn)行篩選選擇出符合適應(yīng)度要求的目標(biāo)，每次從父代染色體編碼群體中隨機(jī)地選出d個基因，根據(jù)最大加工時間適應(yīng)度規(guī)則計算函數(shù)求解出適應(yīng)度f(j)，將滿足條件適應(yīng)度的個體保存到交叉池中，重復(fù)操作直到選擇池中基因的數(shù)量滿足要求。

2.2.2 交叉操作

交叉操作是利用父代個體經(jīng)過一定策略的組合后產(chǎn)生新的個體，使部分優(yōu)良的基因序列得以保留到子代中。機(jī)器選擇編碼采用均勻交叉(uniform crossover，UX)操作，在[1,Z0]范圍內(nèi)通過程序生成隨機(jī)整數(shù)r，然后將父代染色體P1和P2對應(yīng)機(jī)器選擇編碼基因復(fù)制到子代中，最后將父代余下的基因復(fù)制到子代C2和C1中，機(jī)器選擇的均勻交叉過程如圖3所示。

圖3 機(jī)器選擇均勻交叉示意圖

工序順序染色體編碼的交叉操作借鑒了優(yōu)先操作方法[9]和KACEM等[10]的POX混合交叉的優(yōu)點(diǎn)，隨機(jī)將工件集{J1,J2,…Jn}分為兩部分，復(fù)制P1和P2對應(yīng)工件集合基因到子代C1和C2中，將不包含在工件集的基因復(fù)制到C2和C1中，編碼交叉過程如圖4所示。

圖4 工序編碼交叉示意圖

2.2.3 變異操作

變異操作是染色體編碼產(chǎn)生全新解的重要方式，通過改變?nèi)旧w的某些基因來生成新個體，可以保證算法的全局搜索能力，防止過早出現(xiàn)收斂的情況。采用動態(tài)變異的策略，變異概率求解公式為：

pm=pmax-(pmax-pmin)×gn÷gnmax

(7)

Pm代表當(dāng)前變異概率，隨著程序迭代的次數(shù)自適應(yīng)的改變概率，gn表示程序當(dāng)前迭代進(jìn)行的次數(shù)，gnmax表示初始設(shè)置的程序最大運(yùn)行次數(shù)。機(jī)器編碼采用單點(diǎn)變異，工序編碼采用交換變異策略。

2.3 變鄰域結(jié)構(gòu)

變鄰域搜索(variable neighborhood search,VNS)算法是求解組合優(yōu)化問題的有效局部算法。VNS通過不斷計算初始解鄰域中解集的評價適應(yīng)度，選擇出更優(yōu)秀的結(jié)果則替換當(dāng)前基因編碼，如此反復(fù)循環(huán)計算直到滿足程序設(shè)定的約束條件。含有AGV約束的FJSP問題在鄰域結(jié)構(gòu)設(shè)計生成時需要考慮加工設(shè)備選擇的條件，本文采用了移動工序和關(guān)鍵工序塊交換的鄰域結(jié)構(gòu)。在移動工序鄰域結(jié)構(gòu)中，通過求解關(guān)鍵路徑計算出車間調(diào)度中的對應(yīng)的關(guān)鍵工序集{O1，O2，…,On}，從上述工序集合中隨機(jī)選擇出一道關(guān)鍵工序v，將v插入到上述染色體中得到鄰域解；工序塊交換鄰域求解過程如圖5所示，通過交換關(guān)鍵工序子塊中非同一工件末尾相連的兩道工序，求解出新的鄰域編碼。

圖5 關(guān)鍵工序塊鄰域求解示意圖

2.4 混合算法流程

改進(jìn)變鄰域遺傳算法流程如圖6所示，首先設(shè)置種群規(guī)模等基本參數(shù)，采用啟發(fā)式與隨機(jī)結(jié)合方式生成初始種群，并對種群適應(yīng)度進(jìn)行計算，然后采用全局最優(yōu)庫和錦標(biāo)賽策略選擇個體，進(jìn)行交叉、變異后采用移動工序和關(guān)鍵工序塊交換方式的變鄰域搜索擴(kuò)大搜索范圍，最后當(dāng)程序循環(huán)次數(shù)達(dá)到預(yù)設(shè)值時結(jié)束算法。

圖6 變鄰域遺傳算法流程圖

3 算例測試

為了對本文提出混合算法的有效性進(jìn)行實(shí)例化驗(yàn)證，使用MATLAB編寫代碼實(shí)現(xiàn)變鄰域遺傳算法，測試了Bilge等提出的40個基準(zhǔn)算例，包含4種設(shè)備布局方式、4臺加工設(shè)備以及10個加工集。算法最大迭代次數(shù)設(shè)為100,初始種群規(guī)模200,種群初始化策略比例4:4:2,編碼的最小的最大交叉概率為(0.5，0.9)，自適應(yīng)動態(tài)變異概率設(shè)計為(0.01，0.1)，算法的優(yōu)化目標(biāo)為最大完工時間最短，連續(xù)運(yùn)行100次。

首先將本該改進(jìn)的變鄰域遺傳算法(GAVNS)與傳統(tǒng)遺傳算法(GA)進(jìn)行測試對比，在兩臺AGV情況下，對Ex32算例進(jìn)行計算出，兩種算法每代最優(yōu)均值變化曲線結(jié)果如圖7所示，從圖中可以看出GAVNS算法較GA能更快的收斂，避免了算法過早的陷入局部最優(yōu)。Ex32算例的AGV搬運(yùn)和工件調(diào)度的甘特圖如圖8所示，最佳調(diào)度時間為83。

圖7 兩種算法對比曲線圖

圖8 Ex32最佳調(diào)度甘特圖

選取文獻(xiàn)[7]中所提出的改進(jìn)啟發(fā)式遺傳算法(HGA)、EROL等[11]采用的MAS算法以及CENK等[12]所提出的FMAS算法與本文的變鄰域遺傳算法結(jié)果進(jìn)行比較，計算了AGV數(shù)量R為2、3兩種情況下最大加工時間。從表3可以看出本文算法100%的結(jié)果優(yōu)于MAS算法，在兩臺AGV的情況下83.3%的結(jié)果優(yōu)于HGA算法，在三臺AGV搬運(yùn)情況下75%的結(jié)果優(yōu)于HGA算法，與FMAS算法相比在兩臺AGV情況下有66.6%的算例求取了最優(yōu)結(jié)果，驗(yàn)證了變鄰域遺傳算法解決含有AGV搬運(yùn)FJSP問題的有效性。

表3 算例結(jié)果對比表

4 結(jié)束語

本文提出一種改進(jìn)群初始化和編碼策略的遺傳算法，通過融合移動和交換工序的兩級變鄰域搜索策略提高了混合算法的局部搜索能力。最后對算例進(jìn)行實(shí)例測試并與其他算法求解的最優(yōu)結(jié)果進(jìn)行比較，驗(yàn)證了GAVNS混合算法對解決AGV柔性車間調(diào)度問題的穩(wěn)定性、可靠性。后續(xù)將對算法進(jìn)行改進(jìn)研究并應(yīng)用到解決多目標(biāo)約束的柔性離散制造車間調(diào)度問題中。