含有運輸小車的柔性作業(yè)車間調度研究

周鑫

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

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

中圖分類號：TP301? ? ?文獻標識碼：A

Abstract： In the actual flexible job-shop scheduling， it is more of practical significance to consider transportation time of Automatic Guided Vehicle （AGV） in flexible job-shop scheduling Research， because workpieces not only require processing time， but also take a certain amount of time to be transferred between machines using AGV. Aiming at this problem， this paper proposes to establish a mathematical model of flexible job-shop scheduling with AGV and improve genetic algorithm according to characteristics of the problem. Local search strategy is introduced to strengthen the local optimization ability， and simulated annealing algorithm is added as a local search strategy to global search in order to enhance algorithm convergence performance. Experimental data from simulation experiment platform show that this algorithm is comparatively effective.

Keywords： genetic algorithm; flexible job-shop scheduling; simulated annealing; automatic guided vehicle

1? ?引言（Introduction）

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

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

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

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

2.1? ?問題描述

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

r

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

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

（2）一臺機器一次處理一個零件。

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

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

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

2.2? ?模型建立

根據(jù)以上描述的資源約束條件建立模型，在車間調度中有多目標優(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表示加工開始和結束的時間;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的基本框架，并用模擬退火作為局部搜索讓算法的收斂性能更好，并且在每次全局搜索過程中的交叉變異之后都要進行局部搜索，從而能夠達到獲得較好質量的最優(yōu)解的目的。改進GA的程序結構流程圖，如圖1所示。

3.2? ?全局搜索方法

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

3.3? ?編碼與解碼

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

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

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

3.4? ?選擇操作

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

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

3.5? ?交叉操作

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

IPOX操作是在POX操作基礎上經(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? ?變異操作

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

3.7? ?局部搜索策略

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

以下是模擬退火算法的基本原理解釋，T為溫度，降溫過程具體的表示為：

公式（10）中k是一個自然常數(shù)，并且dE<0，表示溫度退火的過程。從該公式中可以得出：

exp（dE/kT）取值是（0，1），dE代表下降的溫度，那么P（dE）的函數(shù)取值范圍是（0，1）。隨著溫度T的降低，P（dE）會逐漸降低。我們認為向更差解的轉變是溫度躍遷過程，我們以概率P（dE）接受它，當算法結束時所得到的解即為所得到的最佳結果。

4? 實驗結果與分析（Experimental results and analysis）

本文實驗的環(huán)境為Windows 10系統(tǒng)，在VS開發(fā)環(huán)境下求得程序的最優(yōu)解，并將最后結果與文獻中的算法結果相比較。在仿真實驗中，設置種群的數(shù)目為5，初始交叉概率為0.4，種群的大小為1，000，初始突變概率是0.05，分段函數(shù)中的片段數(shù)為n/5。

表3表示五個工件在五臺機器上的加工工藝，每個工件有三道不同的工序，用Oij表示，機器用M表示。小車的運輸時間表如表4所示，機器之間的距離不同，導致不同機器之間的運輸時間不同。

本文測試了實驗數(shù)據(jù)，設置機器的數(shù)量為10。從表5的實驗結果中的數(shù)據(jù)可以看出，本文改進的算法性能有一定的提升。圖4為改進遺傳算法和平均值的對比結果。圖5是本次實例中的調度的甘特圖。綜合圖表的數(shù)據(jù)可以得出本文的算法比平均值的進化速度更快。

5? ?結論（Conclusion）

本文考慮AGV的運輸時長這一實際生產環(huán)境中的因素，讓本文的研究更加符合實際生產環(huán)境。建立了含有AGV的柔性作業(yè)車間調度的數(shù)學模型，針對問題自身特點對遺傳算法進行改進，引入局部搜索策略加強局部尋優(yōu)能力，將模擬退火算法作為局部搜索策略加入全局搜索中，增強了算法的收斂性能。遺傳算法是進行全局范圍的搜索求解，加入局部搜索是為了更快地找到最優(yōu)近似解或者次優(yōu)解的個體。本文中的實驗測試數(shù)據(jù)充分體現(xiàn)了本文算法的有效性和可行性。

參考文獻（References）

[1] S. Karthikeyan， P. Asokan， S. Nickolas， et al. A hybrid discrete firefly algorithm for solving multi-objective flexible job shop scheduling problems[J]. Int. J. of Bio-Inspired Computation， 2015， 7（6）：386-401.

[2] ZHANG G H， GAO L， SHI Y. An effective genetic algorithm for the flexible job-shop scheduling problem[J]. Expert Systems with Applications， 2011， 38（4）：3563-3573.

[3] SHAO X Y， LIU W Q， LIU Q， et al. Hybrid discrete particle

swarm optimization for multi-objective flexible job-shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology， 2013， 67（9）：2885-2091.

[4] 余建軍，孫樹棟，郝京輝.免疫算法求解多目標柔性作業(yè)車間調度研究[J].計算機集成制造系統(tǒng)，2006，12（10）：1643-1650.

[5] YAO B Z， YANG C Y， HU J J， et al. An improved ant colony optimization for flexible job shop scheduling problems[J]. Advanced Science Letters， 2011， 4（6）：2127-2131.

[6] 張國輝，高亮，李培根，等.改進遺傳算法求解柔性作業(yè)車間調度問題[J].機械工程學報，2009，45（7）：145-151.

[7] 趙詩奎，方水良，顧新建.柔性車間調度的新型初始機制遺傳算法[J].浙江大學學報（工學版），2013，47（6）：1022-1030.

[8] 張立果，黎向鋒，左敦穩(wěn)，等.求解多目標柔性作業(yè)車間調度問題的兩層遺傳算法[J].計算機應用，2020，40（S1）：14-22.

[9] 付建林，張恒志，張劍，等.自動導引車調度優(yōu)化研究綜述[J].系統(tǒng)仿真學報，2020，32（09）：1664-1675.

[10] 戴敏，張玉偉，曾勵.綠色作業(yè)車間機器與AGV的集成調度研究[J].南京航空航天大學學報，2020，52（03）：468-477.

[11] 劉二輝，姚錫凡，陶韜，等.基于改進花授粉算法的共融AGV作業(yè)車間調度[J].計算機集成制造系統(tǒng)，2019，25（09）：2219-2236.

[12] 徐云琴，葉春明，曹磊.含有AGV的柔性車間調度優(yōu)化研究[J].計算機應用研究，2018，35（11）：3271-3275.

[13] 賀長征，宋豫川，雷琦，等.柔性作業(yè)車間多自動導引小車和機器的集成調度[J].中國機械工程，2019，30（04）：438-447.

[14] 張超勇，董星，王曉娟，等.基于改進非支配排序遺傳算法的多目標柔性作業(yè)車間調度[J].機械工程學報，2010，46（11）：156-164.

作者簡介：

周? ?鑫（1991-），男，碩士生.研究領域：智能調度算法，決策分析.