摘 要：在實(shí)際的柔性作業(yè)車間調(diào)度中，不但工件需要加工時間，而且工件在各個機(jī)器之間利用AGV(自動導(dǎo)引小車)轉(zhuǎn)移也需要占用一定的時間，因此對柔性作業(yè)車間調(diào)度中考慮AGV運(yùn)輸時間的研究更具有實(shí)際意義。針對此問題，本文建立含有AGV的柔性作業(yè)車間調(diào)度的數(shù)學(xué)模型，針對問題自身特點(diǎn)對遺傳算法進(jìn)行改進(jìn)，引入局部搜索策略加強(qiáng)局部尋優(yōu)能力，將模擬退火算法作為局部搜索策略加入全局搜索中，增強(qiáng)了算法的收斂性能。通過在仿真實(shí)驗(yàn)平臺上的實(shí)驗(yàn)數(shù)據(jù)結(jié)果可以看出，本算法有比較好的效果。

　　關(guān)鍵詞：遺傳算法;柔性作業(yè)車間調(diào)度;模擬退火;自動引導(dǎo)小車

　　1 引言(Introduction)

　　FJSP是公認(rèn)的NP難問題，所以FJSP一直是國內(nèi)外學(xué)者研究的熱點(diǎn)[1]。這個問題從20世紀(jì)90年代Bruker等人提出后，國內(nèi)外的專家學(xué)者進(jìn)行了深入廣泛的研究。FJSP是JSP的擴(kuò)展，JSP工件的工序所在的加工機(jī)器是固定的，F(xiàn)JSP更加符合實(shí)際車間中的生產(chǎn)環(huán)境。目前求解FJSP的主要智能算法有遺傳算法[2]、免疫算法[3]、粒子群算法[4]、蟻群算法[5]等。張國輝等[6]使用隨機(jī)初始化種群優(yōu)化方法。趙詩奎[7]等基于設(shè)備均衡的策略并運(yùn)用均勻設(shè)計的思想優(yōu)化了種群的初始化方法。張立果[8]等針對多目標(biāo)的柔性作業(yè)車間調(diào)度問題提出新的交叉策略來進(jìn)行求解。在實(shí)際的生產(chǎn)環(huán)境中，工件在不同的加工機(jī)器之間通過AGV小車進(jìn)行搬運(yùn)。

　　對于AGV參與集成車間調(diào)度問題的研究也得到一些學(xué)者的廣泛研究，付建林等[9]對AGV和車間調(diào)度之間的融合調(diào)度方法——AGV調(diào)度優(yōu)化問題做了一個分類，為研究AGV融合車間調(diào)度的學(xué)者提供了學(xué)習(xí)的建議。戴敏等[10]針對加工機(jī)器和AGV的集成調(diào)度提出了改進(jìn)的分布估計算法進(jìn)行優(yōu)化研究。劉二輝等[11]通過改進(jìn)花授粉算法對AGV和機(jī)器的集成調(diào)度進(jìn)行了研究。徐云琴等[12]研究了AGV在柔性作業(yè)車間調(diào)度中的數(shù)量變化對加工時間的影響。賀長征等[13]對AGV在柔性作業(yè)車間中的路徑進(jìn)行了優(yōu)化。

　　通過閱讀以上文獻(xiàn)發(fā)現(xiàn)，目前AGV在柔性作業(yè)車間調(diào)度中的集成調(diào)度相關(guān)研究較少，大部分的文獻(xiàn)都沒有研究車間調(diào)度和AGV相融合的問題。針對此問題，本文將考慮AGV在實(shí)際生產(chǎn)環(huán)境中發(fā)揮調(diào)度作用這一因素，研究柔性作業(yè)車間AGV的融合問題，讓本文的研究更加符合實(shí)際的生產(chǎn)環(huán)境。本文內(nèi)容和以上文獻(xiàn)的主要區(qū)別為：本文在遺傳算法中加入局部搜索增強(qiáng)局部尋優(yōu)能力，并研究了有AGV情況下的車間調(diào)度問題。

　　2 含有AGV的柔性作業(yè)車間調(diào)度模型(Flexible job-shop scheduling model with AGV)

　　2.1 問題描述

　　含有AGV的柔性車間調(diào)度問題可以描述為：n個工件由多臺AGV運(yùn)送到多臺不同的機(jī)器上加工，工件的不同工序在不同的機(jī)器上進(jìn)行加工的加工時間不同，每臺加工機(jī)器之間的距離也不相同。每個工件有ni道不同的工序、r個AGV，且

　　r　　未加工的工件和已加工的工件分別放置在未加工的區(qū)域P1和已加工的區(qū)域P2。

　　(1)AGV的搬運(yùn)速度是不變的，搬運(yùn)時間和機(jī)器之間的距離有關(guān)，設(shè)相鄰的機(jī)器之間距離相等。

　　(2)一臺機(jī)器一次處理一個零件。

　　(3)不計算工件在設(shè)備緩沖區(qū)中的時間。

　　(4)在最初的時刻，所有的機(jī)器和工件都可以使用。

　　(5)AGV的運(yùn)輸路線是固定的，AGV的運(yùn)輸沒有延遲，并且不同AGV的運(yùn)輸不會相互干擾。

　　2.2 模型建立

　　根據(jù)以上描述的資源約束條件建立模型，在車間調(diào)度中有多目標(biāo)優(yōu)化和單目標(biāo)優(yōu)化，本文采用比較常見的單目標(biāo)優(yōu)化方案，以所有工件加工完成的最小時間為目標(biāo)。

　　式中，i為工件(i=1，2，…，h)，h為工件數(shù);j為工序(j=1，2，…，k)，k為工序數(shù);m為機(jī)器(m=1，2，…，M)，M為機(jī)器的數(shù)量;Tms和Tme表示加工開始和結(jié)束的時間;Tagvs和Tagve為小車運(yùn)輸工件的過程所消耗的時間;Tmn表示工件從機(jī)器m到機(jī)器n之間所花費(fèi)的時間;Tijs和Tije是第i個工件的第j道工序的加工開始和結(jié)束時間;是第i個工件的第j道工序的加工時間;和分別表示工序Oij是否在機(jī)器上加工，0表示不加工，1表示加工。

　　公式(1)為最小完工時間;公式(2)表示AGV的運(yùn)輸時間由兩臺設(shè)備之間的距離決定;公式(3)表示AGV運(yùn)輸工件是獨(dú)立運(yùn)行的;公式(4)表示小車能使工件的每一道工序完成后瞬間被小車運(yùn)往下一個機(jī)器;公式(5)表示一道工序開始后不能停止;公式(6)和公式(7)表示一個工件的一道工序在某一時刻只能被一臺加工機(jī)器加工;公式(8)表示相同工件的工序是有順序進(jìn)行加工的;公式(9)表示將工序累加。

　　3 改進(jìn)遺傳算法設(shè)計(Improved genetic algorithm design)

　　3.1 基本原理

　　本文算法的基本原理是在原有GA的基礎(chǔ)上加以改進(jìn)，延用GA的基本框架，并用模擬退火作為局部搜索讓算法的收斂性能更好，并且在每次全局搜索過程中的交叉變異之后都要進(jìn)行局部搜索，從而能夠達(dá)到獲得較好質(zhì)量的最優(yōu)解的目的。改進(jìn)GA的程序結(jié)構(gòu)流程圖，如圖1所示。

　　3.2 全局搜索方法

　　本文研究的算法是基于傳統(tǒng)的遺傳算法的基本原理，并結(jié)合車間調(diào)度的實(shí)際生產(chǎn)環(huán)境加以改進(jìn)。在實(shí)際的車間調(diào)度中要考慮工件在不同機(jī)器之間的運(yùn)輸過程等因素，因此本文在結(jié)合GA的基礎(chǔ)上將AGV和機(jī)器進(jìn)行融合調(diào)度研究。在全局搜索方法中加入局部搜索，延用GA的基本框架，并用模擬退火作為局部搜索讓算法的收斂性能更好。GA的基本框架原理是由隨機(jī)產(chǎn)生初始解，經(jīng)過評估、選擇、交叉、變異等操作最終獲得最優(yōu)解的過程。

　　3.3 編碼與解碼

　　傳統(tǒng)的遺傳算法中，一旦種群規(guī)模太大，無法有效淘汰無用的個體，容易出現(xiàn)局部最優(yōu)的情況，既影響了種群的進(jìn)化速度，又影響了計算結(jié)果的準(zhǔn)確性，因此根據(jù)第2節(jié)含有AGV的柔性車間調(diào)度數(shù)學(xué)模型，本文有兩種編碼方式：一種編碼方式是對機(jī)器進(jìn)行編碼，另一種編碼方式是對工序進(jìn)行編碼。

　　為了展示本文算法所提出的編碼，用三臺加工機(jī)器和三個加工工件為實(shí)驗(yàn)例子模擬實(shí)際加工環(huán)境。表1和表2表示三臺加工機(jī)器上三個工件的不同工藝的加工條件，不同加工機(jī)器之間工件的運(yùn)輸時間不同，以及不同加工機(jī)器之間的距離不同。其中，Oij表示工件i的第j道工序。

　　假設(shè)工序Oij在機(jī)器Mi上加工，各工件的加工順序是按照同一個工件有先后順序的約束，以選取322321321為機(jī)器的編碼、112233123為工序的編碼為例，其對應(yīng)的解碼過程如圖2(a)和圖2(b)所示。

　　3.4 選擇操作

　　選擇操作是算法流程中關(guān)鍵的一步，通過選擇操作這一步驟獲得質(zhì)量較高的解，選擇的過程中確定選擇的策略和選擇優(yōu)質(zhì)解的比例至關(guān)重要。選擇的目標(biāo)性過強(qiáng)可能會導(dǎo)致進(jìn)入早熟的狀態(tài)，導(dǎo)致結(jié)果局部最優(yōu)的情況;選擇優(yōu)秀質(zhì)量解的比例太小會導(dǎo)致淘汰的速度變慢，增加算法的運(yùn)行時長，降低算法的性能。

　　選擇策略是新種群的4/5用輪盤賭選擇，選擇的概率符合大自然的規(guī)律隨機(jī)產(chǎn)生。每次選擇大于隨機(jī)概率的個體到新種群。新種群剩下的1/5的組成部分通過選擇策略找到當(dāng)前解中最優(yōu)個體，然后復(fù)制該個體，復(fù)制數(shù)量是新種群的1/5。

　　3.5 交叉操作

　　交叉操作在遺傳算法中是必不可少的，是模擬生物進(jìn)化過程中兩條染色體之間互相交叉重組新的染色體的過程。根據(jù)所采用的編碼的特點(diǎn)，采用IPOX[14]交叉操作，基于工序編碼。

　　IPOX操作是在POX操作基礎(chǔ)上經(jīng)改進(jìn)而形成的。IPOX的具體操作如圖3所示。P1、P2和C1、C2表示一對染色體經(jīng)過交叉后又重新組合成的一對新的染色體。IPOX交叉操作過程為：

　　(1)將全部工件分為B1和B2兩個集合。

　　(2)將P1染色體中有B1集合中的工件序列加入C1，P2染色體中有B2集合中的工件序列加入C2。

　　(3)將P2染色體中有B2集合中的工件序列加入C1，P1染色體中有B1集合中的工件序列加入C2。

　　3.6 變異操作

　　變異操作是模擬生物的基因突變過程，可以防止進(jìn)入結(jié)果過早收斂，在一定程度上增加了種群的多樣性，增加了跳出局部極小的可能性。本文采用兩種變異的操作方式：第一種在染色體的n個基因中，隨機(jī)產(chǎn)生位置i和j(i

　　3.7 局部搜索策略

　　局部搜索是為了解決非常復(fù)雜的問題而出現(xiàn)的一種解決最優(yōu)問題的算法，最優(yōu)解的時間有可能是很長的，局部搜索策略為了防止整個算法的尋優(yōu)時間過長，通過局部搜索尋找近似最優(yōu)解。局部搜索算法是從爬山法改進(jìn)而來的，其過程和原理同貪心搜索算法類似，總是從當(dāng)前解的領(lǐng)域解空間中選擇一個最好質(zhì)量解作為下次迭代過程中的當(dāng)前解，直到達(dá)到一個局部最優(yōu)解(Local Optimal Solution)。局部搜索算法的基本過程可以描述為：選取一個初始的解，然后通過某種領(lǐng)域動作產(chǎn)生初始解的鄰居解，再選擇更優(yōu)的鄰居解。一直重復(fù)以上過程，直到達(dá)到終止條件。

　　推薦閱讀：交通運(yùn)輸研究交通類期刊征稿