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

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

　　1 引言(Introduction)

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

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

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

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

　　2.1 問題描述

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

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

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

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

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

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

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

　　2.2 模型建立

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

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

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

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

　　3.1 基本原理

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

　　3.2 全局搜索方法

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

　　3.3 編碼與解碼

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

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

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

　　3.4 選擇操作

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

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

　　3.5 交叉操作

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

　　IPOX操作是在POX操作基礎(chǔ)上經(jīng)改進而形成的。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 變異操作

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

　　3.7 局部搜索策略

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

　　推薦閱讀：交通運輸研究交通類期刊征稿