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

　　關鍵詞：遺傳算法;柔性作業車間調度;模擬退火;自動引導小車

　　1 引言(Introduction)

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

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

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

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

　　2.1 問題描述

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

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

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

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

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

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

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

　　2.2 模型建立

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

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

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

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

　　3.1 基本原理

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

　　3.2 全局搜索方法

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

　　3.3 編碼與解碼

　　傳統的遺傳算法中，一旦種群規模太大，無法有效淘汰無用的個體，容易出現局部最優的情況，既影響了種群的進化速度，又影響了計算結果的準確性，因此根據第2節含有AGV的柔性車間調度數學模型，本文有兩種編碼方式：一種編碼方式是對機器進行編碼，另一種編碼方式是對工序進行編碼。

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

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

　　3.4 選擇操作

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

　　選擇策略是新種群的4/5用輪盤賭選擇，選擇的概率符合大自然的規律隨機產生。每次選擇大于隨機概率的個體到新種群。新種群剩下的1/5的組成部分通過選擇策略找到當前解中最優個體，然后復制該個體，復制數量是新種群的1/5。

　　3.5 交叉操作

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

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

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

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

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

　　3.6 變異操作

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

　　3.7 局部搜索策略

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

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