GA?COA求解柔性作業(yè)車間多資源調(diào)度問題

姜鵬，方成剛，楊帆

（南京工業(yè)大學機械與動力工程學院，江蘇 南京 210000）

1 引言

制造業(yè)是國民經(jīng)濟的支柱性產(chǎn)業(yè)“，工業(yè)4.0”以及“中國制造2025”的背景下，制定合理的車間調(diào)度方案是企業(yè)掌握核心競爭力的基礎。柔性作業(yè)車間（FJSP）突破了傳統(tǒng)作業(yè)車間加工機床唯一性的約束，越來越適用于當今小批量、多品種的生產(chǎn)模式，且在實際作業(yè)車間中需考慮多種資源的分配，因此研究柔性作業(yè)車間多資源調(diào)度（MRFJSP）具有重大的理論意義和實際價值。

近年來，國內(nèi)外學者一直注重對MRFJSP的研究。文獻[1]將自動導引小車（AGV）與機器調(diào)度同時考慮，利用改進的遺傳算法求解。文獻[2]考慮工件制造、裝配以及運輸，提出了一種考慮裝配及組裝的MRFJSP，并通過帶優(yōu)選策略的粒子群算法進行求解。文獻[3]提出基于時間窗和Dijkstra算法的混合遺傳算法，求解綜合考慮機器調(diào)度和多AGV 路徑規(guī)劃的調(diào)運輸和處理時間有限的FJSP。文獻[4]利用帶禁忌搜索的遺傳算法來解決一個考慮運輸和處理時間有限的FJSP。文獻[5]建立考慮運輸和多個機器人的MRFJSP 模型，在粒子群算法中混合了局部搜索算法求解該問題。文獻[6]提出一種包含運輸約束的調(diào)度析取圖模型。文獻[7]建立包含運輸時間的FJSP混合整數(shù)線性規(guī)劃模型，運用混合模擬退火算法的自適應帝國競爭算法求解該問題。文獻[8]提出一種遺傳、粒子群混合算法，用于求解包含運輸、裝配的MRFJSP。

郊狼優(yōu)化算法（COA）是2018年文獻[9]提出的，其是通過模擬郊狼成長、生與死、被驅(qū)離等現(xiàn)象的新型全局優(yōu)化的群體智能算法。文獻[10]首先將此算法運用在復雜函數(shù)和醫(yī)學圖像等方面，并通過實驗證明，其具有良好的全局搜索能力和收斂速度。

從以上文獻發(fā)現(xiàn)：大多數(shù)考慮運輸?shù)腇JSP調(diào)度模型均假設所有工件的原材料在0時刻都可開始加工，且未考慮工件成品回庫，倉儲作為工件原材料、成品的存儲設備，是車間調(diào)度中不可忽視的一環(huán)節(jié)，與運輸處于同等重要的位置。因此，在目前的考慮運輸?shù)腇JSP調(diào)度模型的基礎上，進一步細化、完善調(diào)度模型，加入倉儲資源約束，建立考慮倉儲及運輸?shù)腗RFJSP調(diào)度模型。針對該問題設計了一種遺傳—郊狼混合算法（GA—COA），運用算例進行驗證，將GA?COA 與遺傳算法（GA）和郊狼優(yōu)化算法（COA）對比，并對模型和算法進{1，2，···，n}，p={1，2，···，Cn}。

2 問題建模

本問題的加工完成時間為工件最終回庫時間，以最小化完工時間為目標函數(shù)，即行分析。

該車間調(diào)度問題的數(shù)學模型存在以下約束：

3 問題描述

柔性作業(yè)車間中有n個工件，m臺機床，一臺AGV，每個工件有多道工序，每道工序可選一臺或多臺機床進行加工，工序在不同機床上的加工時間不同。AGV用于工件在倉庫與機床、機床與機床之間的運輸，AGV每次僅運輸一個工件，且工件的第一道工序由AGV從立體倉庫中取出該工件的原材料運至對應機床的線邊庫后開始加工、工件的最后一道工序完成后由AGV將其運回倉庫。

每臺機床間的距離相等，因此AGV在每臺機床間的運輸時間相同，且AGV空載、負載的速度不變；線邊庫有充足的存儲能力，并將上下料等準備時間考慮到機加工時間內(nèi)；最后一個工件回庫標志著整個加工的結束。變量符號定義，如表1所示。

表1 符號定義Tab.1 Symbol Definition

Xipj為布爾變量，若工件i的工序p由機床j加工，則Xipj=1，否則Xipj=0，其中，i={1，2，···，n}，p={1，2，· ··，Cn}，j={1，2，···，m}；Yipjt為布爾變量，若t時刻機床j加工工件i的工序p，則Yipj=1，否則Yipj=0，其中，i={1，2，···，n}，p={1，2，···，Cn}，j={1，2，···，m}；Zipt1t2為布爾變量，若AGV在t1到t2時刻運輸工件i的第p道工序，則Zipt1t2=1，否則Zipt1t2=0。

（1）工件的一道工序只能同時由一臺機床加工，不能由多個機床加工。

（2）一臺機床只能同時對一個工件的一道工序進行加工。

（3）AGV小車一次只能運輸一個工件。

（4）任一工件的第一道工序均是從倉庫中取出工件原材料運輸至該工序所對應的機床線邊庫中。

這里定義初始工序：該工序是此工藝路線中第一道工序；設倉庫位置簡稱為M0，機床m所在位置簡稱為Mm。

若工件i的第一道工序是初始工序，對應的機床為j，則工件i的第一道工序開始加工時間為：

若工件i的第一道工序不是初始工序，則工件i的第一道工序開始加工時間為：（TAGVx0中x代表：該工序的前一道工序所在的機床為Mx，則該機床所在位置也是x；設該工序所在的機床為My，該機床y可開始加工時間為：TMSy）

（5）工件的前后工序不在同一臺機床上加工，則下一道工序的開始加工時間根據(jù)前道工序的完工時間、AGV當前可開始使用時間、AGV在機床間的運輸時間以及負責下一道工序的機床的可開始加工時間而定。

假設工件i的第p和p+1道工序分別在機床j1和j2上加工，運輸工具AGV小車當前所處機床為r。若TAGVS+TAGVrj1?TFipj1≤0，則：

4 算法設計

GA 的交叉步驟只是針對父代種群中的部分染色體進行操作，不具有全局性。COA有多組結構這種良好的搜索框架，有較強的搜索能力，且COA組內(nèi)郊狼的成長、生與死，有一定的全局搜索能力，但多組結構使得組與組之間的信息不聯(lián)通，導致后期收斂速度慢。因此，針對以上GA和COA的特點，提出一種帶隨機動態(tài)分組的GA—COA混合算法，可以很好地解決MRFJSP問題。采用一個實例來描述GA—COA混合算法具體步驟，工件加工及運輸信息，如表2所示。

表2 工件加工及運輸信息表Tab.2 Workpiece Processing and Transportation Information Sheet

4.1 編碼，種群初始化

此處采用基于工序的單層編碼，將工件回庫作為該工件的最后一道工序，設機加工時間為0，僅需AGV運輸時間，最后一個工件的回庫代表著整個加工流程的完工。編碼為：111122223333，初始化隨機將其打亂，可得：123321213123，i出現(xiàn)的次數(shù)j表示工件i的第j道工序，最后一個i表示其回庫。

4.2 解碼，適應度函數(shù)計算

以上述編碼123321213123為例，解碼步驟如下：

（1）在每道工序的可選機床中隨機選取機床，可得相應的機床號：[M1 M2 M3 M2 M2 M3 M1 M2 M1 M0 M0 M0]

（2）以編碼順序可得到AGV相應的運輸順序，根據(jù)運輸順序和相應的機床號可得到AGV的運輸路線。

運輸順序為：O1，1→O2，1→O3，1→O3，2→O2，2→O1，2→O2，3→O1，3→O3，3→O1，4→O2，4→O3，4，其中工序O1，4、O2，4、O3，4表示該工件加工完成由AGV運回倉庫中。

以完工時間最短為目標函數(shù)，求解值的大小對應該組染色體的優(yōu)劣。

4.3 精英選擇，隨機動態(tài)分組

組內(nèi)染色體的成長受組內(nèi)alpha 染色體和組文化趨勢的影響，若alpha是局部最優(yōu)染色體，則可能導致收斂慢、易陷入局部最優(yōu)。因此，利用精英選擇策略，將其作為全局引導的組內(nèi)newalpha染色體，并放入子代種群，使算法加快收斂速度，更好地向全局最優(yōu)解逼近。

COA的多組結構對性能影響較大，N（種群規(guī)模）=Np（組數(shù)）×Nc（組內(nèi)個體數(shù)）。在N固定不變的情況下，Np越大，Nc越小，全局最優(yōu)解的作用強；反之，全局最優(yōu)解的作用弱。采用動態(tài)分組方式，根據(jù)文獻［12］，每組的個體數(shù)Nc限制在14以內(nèi)，有利于各組之間的信息交流，增加郊狼的多樣性。假設N=100，Np和Nc必須是100的因子且Nc必須大于3，所以Nc可為4、5、10。在算法迭代前期，設Np=10、Nc=10，全局搜索能力強；在算法迭代后期，設Np=20、Nc=5，局部搜索能力強。隨機動態(tài)分組的采用，可省去COA的郊狼被驅(qū)離這一步驟，改善算法的操作性能。隨機動態(tài)分組，計算第p組第c個染色體的社會適應能力SOCp，c。

其中，lbc和ubc—染色體社會因子的下界和上界，rand為［0，1］內(nèi)均勻分布的隨機數(shù)。

4.4 組內(nèi)染色體成長、生與死

確定全局最優(yōu)染色體newalpha、組內(nèi)文化趨勢culture（也稱組內(nèi)中值染色體），隨機選取組內(nèi)兩條染色體Cr1、Cr2。組內(nèi)染色體成長受δ1和δ2的影響，δ1為alpha與Cr1的差異、δ2為culture與Cr2的差異。

組內(nèi)染色體成長的新解：

更新組內(nèi)染色體成長后的社會適應度值，

組內(nèi)染色體成長后，通過貪婪選擇保留下優(yōu)質(zhì)染色體，加快算法收斂速度。

染色體的新生受隨機選取父代染色體的社會條件和整個社會環(huán)境所共同影響。

式中：j1和j2—新生染色體的兩個隨機選取的維度；rj—[0，1]內(nèi)均勻分布的隨機數(shù)；Rj—決策變量在第j維范圍內(nèi)隨機產(chǎn)生的變異值；Ps—分散概率；Pa—關聯(lián)概率。

新生染色體的生與死由其社會適應能力決定，具體描述如下：（1）組內(nèi)有一或多條染色體比新生染色體差，則新生染色體生而最差的染色體死；（2）組內(nèi)無染色體比新生染色體差，則新生染色體死。

4.5 變異

變異操作為GA中增加種群多樣性的步驟，有利于改善算法的早熟收斂。在車間調(diào)度領域常用的變異操作為：互換操作、逆序操作、插入操作等。采用的是互換變異，按照變異概率隨機交換父代染色體除精英選擇保留到子代種群外的染色體兩不同位置上的基因。

GA—COA混合算法流程，如圖1所示。

圖1 GA—COA流程圖Fig.1 GA?COA Flow Diagram

5 實例分析

利用一個標準算例，對所提出的MRFJSP 模型和GA—COA混合算法進行驗證，在MATLAB中編程實現(xiàn)。根據(jù)文獻[14]中提出的（6×10）FJSP 算例（工件數(shù)6，機床數(shù)10）的基礎上加入倉儲和運輸（AGV），設機床間的距離相等，AGV在各機床間的運輸時間為1，則工件運輸時間，如表3 所示（0 代表倉庫，1?10 代表機床號），工件的加工時間，如表4所示。

表3 工件運輸時間表Tab.3 Workpiece Transport Schedule

表4 工件加工時間表Tab.4 Workpiece Processing Schedule

根據(jù)文獻[9?12]，GA、COA及GA—COA參數(shù)設置，如表5所示。

表5 參數(shù)設置Tab.5 Parameter Setting

GA、COA 及GA—COA 三者運行100 次最優(yōu)結果，如圖2 所示。對比可見COA 的尋優(yōu)能力是強于GA的，GA—COA 混合算法是優(yōu)于前兩者的。GA的交叉操作增強了種群的多樣性，且引入隨機動態(tài)分組加快了種群收斂并改善了算法的操作性，表明GA?COA混合算法在MRFJSP求解中的優(yōu)越性。

圖2 迭代結果對比圖Fig.2 Comparison Diagram of Iteration Results

獲得最優(yōu)的調(diào)度甘特圖，如圖3所示。最優(yōu)調(diào)度周期為162。柔性作業(yè)車間中工件初始存儲于倉庫中，由AGV運輸至相應機床的線邊庫中；工件在機床間的運輸時間是不確定的，需要單獨考慮；加工完的工件由AGV運回倉庫，當最后一個工件的回庫表明整個加工流程的完結。因此，將倉儲和運輸考慮到FJSP中是必要的，為精細化調(diào)度做出更好的指導參考。

圖3 調(diào)度甘特圖Fig.3 Schedule the Gantt Chart

6 結論

將倉儲和運輸兩個環(huán)節(jié)考慮到FJSP中，對該MRFJSP 進行建模，并設計了一種混合算法用于求解該問題。GA—COA混合算法將COA中多組結構、組內(nèi)郊狼成長、生與死代替GA中的交叉操作，并加入隨機動態(tài)分組和精英保留策略，增強混合算法的操作性能，避免算法陷入早熟收斂的不足。通過對比求解結果，證明混合算法在求解MRFJSP中的優(yōu)越性。另外，倉儲作為工件的存儲裝置，是生產(chǎn)環(huán)節(jié)不可忽視的一重要環(huán)節(jié)，而運輸時間影響著整個生產(chǎn)過程，因此將倉儲和運輸考慮到FJSP中是必要的、更貼近實際情況的。