智能RGV動態調度多目標規劃模型

衛 巍 楊志輝 謝浩然 胡倚薇

1(東華理工大學化學生物與材料科學學院 江西 南昌 330013)2(東華理工大學理學院 江西 南昌 330013)3(東華理工大學地球物理與測控技術學院 江西 南昌 330013)

0 引 言

自1954年以來，學者們對生產調度問題進行了大量的研究。但是由于以往的生產調度模型都使用了大量的前提與假設，造成其模型在生產實踐中很難被應用[1]。因此，對于更符合實際情況下的柔性作業車間調度問題(FJSP)具有非常重要的研究價值[2]。

21世紀，針對FJSP問題常使用啟發式的方法對問題進行研究求解。Ho等[3]對FJSP使用組合分派方法；Chen等[4]用圖論模擬分段為兩部分染色體求解FJSP；王雷等[5]考慮快速解碼算法避免非法解產生，通過精英策略提高求解效率和求解的總適應度；張曉星等[6]通過研究最大完工時間及總加工能耗，使用混合蛙跳算法求解FJSP，得到不同權重下的調度方案；Kato等[2]將問題分為粒子群優化(Particle Swarm Optimization,PSO)，及隨機重啟爬山(Random-Restart Hill Climbing,RRHC)；Zandieh等[7]模擬了FJSP基于狀態的維護(Condition Based Maintenance,CBM)，并考慮Sigmoid函數和高斯分布的組合改進CBM，提出了一種改進的帝國競爭算法(Imperialist Competitive Algorithm,ICA)；Gao等[8]提出了一種改進的人工蜂群(Improved Artificial Bee Colony,ABCIABC)算法，其中基于處理時間的不確定性，將其建模為模糊處理時間；趙詩奎[9]對已有鄰域進行精簡與有效移動的拓展，提出了融合改進鄰域的混合算法；張新等[10]對入侵雜草算法做出了新的改進；徐文豪等[12]對花授粉算法對問題的解進行離散化，在過程中為平衡前期全局搜索能力與防止后期陷入局部優解引入自適應正則化因子。

在實際生產中，存在FJSP問題未考慮實際因素。在近年來，國內外學者對實際問題的不同方面進行了分析。Lin等[13]對工件運輸過程消耗的時間進行考慮，使用集成的GA-GSO-GTHS(Genetic Algorithm-Glowworm Swarm Optimization-green tra-nsport heuristic strategy)算法解決問題；Zhang等[14]與張國輝等[15]分別對FJSP問題在生產過程中綠色制造問題進行了考慮，前者開發了基于動態博弈的雙層調度算法，后者構建了碳排放的定量模型，通過多目標求最值獲得最優解；Yazdani等[16]對流水線最早與延遲兩類情況分別的總時長作為目標函數，針對問題的復雜性，構建了基于有效鄰域混合的帝國競爭算法(ICA)；Rahmati等[17]考慮了糾正性維護(Corrective Maintenance,CM)和預防性維護(Preventive Maintenance,PM)方面的兩種維護方案，同時對多步驟間的加工過程進行了考慮。

針對現有方法對于機器出現故障[18]時的調度考慮以及系統的穩定性[19]方面考慮不足的局限，本文提出改進的遺傳算法編碼方式及求解方法。通過結合多因素、多目標的問題特征構建編碼方式，利用改進的遺傳算法對加工次序進行求解，得到一組與最優解總時間差距不大的較優解。該方法不僅可以方便快速地求解此類問題，還可以提升此類問題的可解釋性和準確程度，并且得到優化的編碼形式更利于人們理解。

1 改進遺傳算法解決RGV調度問題

1.1 相關工作

遺傳算法最早由美國密執安大學Holland教授[20]根據物競天擇理論于20世紀60年代提出,至20世紀80年代形成基本的框架。2005年，江雷等[21]將遺傳算法并行化求解旅行商問題(Traveling Salesman Problem，TSP)，此算法進一步提高了種群的多樣性和結果的準確性。

RGV是一類可以根據指令自動控制移動方向和距離、作用是搬運物料的智能車，并且此智能車運行在固定軌道上，自帶一個機械手臂、兩個機械手爪與物料清洗位，可以對上下料及清洗物料等作業任務進行操作完成，進一步提升了加工的效率，并體現了其相對的智能性。

車間調度問題(JSP)作為一個最為常見的NP hard問題，它的調度目標就是事先得到機器加工工序的時間，最終使得耗費的資源最少。柔性作業車間調度問題(FJSP)是以上問題的擴展問題。1990年，Bruker等[22]首次提出了FJSP的概念，即帶有機器柔性的JSP問題。與上述問題不同的是，柔性作業車間調度問題則是工件不確定其加工機器，也不確定加工工序，其靈活性較高，因此，此類問題是個有待解決的熱門問題。

(1) 此問題屬于NP難問題，大多數解法或多或少都會陷入局部收斂的障礙；

(2) 機器在運作中還會有一定可能發生故障，從而影響整體結果。

針對上述不足,本文根據FJSP問題對遺傳算法進行改進，減少局部收斂出現的概率，使改進后的方法所得到的解更接近最優解。

(1) 在解決陷入局部收斂方面，將遺傳算法編碼分為機器選擇部分、工序排序部分、故障概率部分和工序分配部分；

(2) 在解決故障影響方面，本文引入了機器故障概率和機器維修時間概念。

本文中，智能RGV動態調度問題的解決方法是通過使用解決柔性車間調度問題的方法來解決的。其問題本身就是一類在柔性前提下的作業車間調度問題，因而兩者一個為實際問題，一個為構建的模型，并通過對此模型的求解得到智能RGV問題的調度方案。

1.2 問題描述

智能化RGV動態調度問題中，智能RGV要在n臺機器之間來回移動ω個獨立物料。其中工件集合為I={I1,I2,…,Im}，機器集合為J={J1,J2,…,Jm}，不確定每個工件的加工機器，也不確定加工不同工件的工序的先后順序，因此具有較大的靈活性。其中：工件具有H道工序；Oih表示第i個工件的第h道工序，每個Oih可以在相容的機器上任意加工，且不可重復加工同一個工件的同一道工序；pijh表示工件i的第h道工序在機器j上加工時間。在日常的加工過程中，除了機器加工時間之外，RGV移動、物料上下料、清洗加工完成的工件都是不可忽略的。因此本文引入以下參數：eijh表示工件i的第h道工序在機器j上加工結束時間；qijh表示工件i的第h道工序在機器j上下料所需時間；a表示RGV完成一個物料清洗作業所需時間；rijh表示工件i的第h道工序移動到機器上的時間。然而某些突發性事件，比如機器加工中途的損壞，也可能會極大地影響加工的結果，形成擁堵現象，顯著降低效率和穩定性，得到的調度結果由于這樣的現象因而無法適用于實際的加工中，或者說由于效率和穩定性的不足，只能適用于特定的加工環境中，不具有通用性。為此本文也引入了第i次維修所花的時間di、工件在機器加工時損壞的平均概率Eerr和用Nij表示工件i在機器j上是否發生故障，且假設工件一旦在加工時發生損壞后就不能再次加工或者當作成品使用，即當作廢料處理，這將顯著提高本問題在實際應用中的實用性。因此，如何得到并解決具有最優的系統穩定性和加工效率的動態調度多目標規劃模型是一個具有實際意義的問題。

1.3 動態調度模型的建立

1.3.1模型的約束條件

根據實際生產中工序的加工順序不同，并且一個工序不能同時在兩臺機器上進行。與之相對的，任意機器一次也只能加工一個工件，因此需建立如下約束條件：

(1)

(2)

eijhi≤Tii∈[1,n],j∈[1,ω]

(3)

(4)

(5)

(6)

(7)

bih≥0,eih≥0i∈[1,n],h∈[1,hi]

(8)

式(1)和式(2)表示第i個工件在工序上存在先后順序，即工件的加工次序不可隨意打亂，bijh表示工件i的第h道工序在機器j上加工開始時間，pijh表示工件i的第h道工序在機器j上的加工花費時間；式(3)表示任何一個工件的完工時間一定是小于最大完工時間，Ti表示最大完成時間，即加工所有工件的總時間；式(4)表示對一臺機器不能同時加工兩個工件，M表示一個足夠大的正數；式(5)表示第i個物料加工第h道工序所花費的總時間，Pij表示工件i從開始向機器j移動到在機器上結束加工所需的總時間，包含工件的上下料時間、RGV的移動時間、機器加工時間以及完成一次清洗作業所需時間；式(6)表示任意時刻的一道工序只能在一臺機器加工；式(7)表示任意時刻同時加工機器的總數一定小于機器總數，Lijh表示工件i的第h道工序是否在機器j上加工，其值為1表示肯定，反之0表示否定；式(8)表示任意變量參數必須為正數。

1.3.2存在故障的模型優化

根據實際情況，需考慮機器可能在工件加工過程中發生故障的作業情況，因此需要引入故障發生的概率及其發生的時間，增加約束條件，以保證模型的合理。

多道工序發生故障的動態調度模型相對上文，將所有bijh、eijh替換為sijh、cijh，其中：sijh表示考慮機器損壞時工件i的第h道工序在機器j上加工開始的時間；cijh表示考慮損壞時工件i的第h道工序在機器j上加工結束時間，在此之后增加如下約束條件：

(9)

di∈[Errmin,Errmax]

(10)

式中：Nij表示第i個工件的第j個工序是否發生故障，其中1表示發生，0表示不發生。

之后將式(2)、式(4)分別轉化成：

(11)

(12)

式(9)表示工件i在機器j上加工發生故障的概率，本文中的概率設置為0.1；式(10)表示故障發生一次的時間的范圍，di表示第i次發生故障維修時間，Errmin、Errmax表示故障維修的時間上下限；式(11)表示在存在損壞的前提下第i個工件的加工順序存在先后關系，本文假定當機器發生損壞時，其加工工件當作廢料丟棄處理，即丟棄的工件后一道工序的開始時間無限延期；式(12)表示在存在損壞的前提下同一時刻同一臺機器能加工的工序是唯一的，tijh表示工件i的第h道工序在機器j上發生故障時此工序已加工時間。

1.3.3目標函數與綜合評價函數

最終的目標是在加工工件的個數固定前提下時間達到最小，其目標函數是：

f1=min{Ti}

(13)

同時機器在加工過程中可能出現故障，為了量化目標在規定時間內加工的工件的相對優略，檢驗在消除損壞影響下的機器執行效率，故引入綜合評價函數：

(14)

式中：α和β為各自權重；Ti1是無維修時的完成時間；Ti2是有維修時的完成時間，使得在保證加工系統的穩定性的同時也能保證加工的完成時間較小。

2 多分段遺傳編碼改進遺傳算法

2.1 多分段遺傳編碼的構建

本文針對實際生產中的復雜情況設計了一種整數編碼，由機器選擇部分、工序排序部分、故障概率部分和工序選擇部分四部分組成。

機器選擇(Machine Selection,MS)部分：此部分染色體長度為T0。要求每個編碼必須是整數,每一個編碼中的整數代表當前工序選擇的加工機器在可加工機器里的編號。這就保證了后續的操作都能得到可行解。

工序排序(Operations Sequencing,OS)部分：染色體長度為T0。采用整數編碼，其中整數為工件號，工件號出現的先后順序代表加工的先后順序。這種方法使得編碼更加穩定,也能保證后續的操作都能得到可行解。

故障概率(Failure Probability,FP)部分：染色體長度等于所有工件的工序之和T0。其順序與工序排序部分的順序相對應。其中：1表示機器出現故障；0表示機器正常運行，而在實際的生產過程中，對于加工損壞的工件是進行丟棄處理。

工序選擇(Process Selection,PS)部分：染色體長度等于所有機器的個數T1。第j個空格表示第j個機器只可執行的工序。其中：空格中數字為1表示此機器加工第一工序；數字為2表示加工第二工序，以此類推。

染色體編碼如圖1所示，此處只例舉工件1和工件2的所有工序。工件1的第一道工序有五臺機器可選擇進行加工，與之對應的4表示第四臺機器是可加工的，即表示工件O11在機器上加工。而對于后續的工序排序部分，假設一開始進行加工的工序染色體為[22112]，其中第一個2代表第二個工件的第一道工序，即O21，故各工件的工序加工順序為：O21-O22-O11-O12-O23。

圖1 多分段遺傳編碼

2.2 遺傳算法的求解

2.2.1初始化

初始化是遺傳算法中的第一步，T是最大進化代數，隨機生成M個基因個體作為初始群體。本文根據需要考慮機器選擇帶來的機器負荷問題的原因，使用全局選擇操作對染色體進行初始化，使得每個被選取的機器都能保證在工作，進而提高利用率。

全局選擇的步驟如下：首先取一個長度與機器數目相同的整形數組，其中數組的序號依次為機器的序號，數組位置上的值初始化為0。隨機選擇當前要加工的工件，在可選機器中找到所花時間最小(工件移動到該機器的時間、機器上料時間以及機器加工工件的所需時間)的加工機器，將所選擇的加工機器加工對應的數值更新到數組中，以此類推直到該工件加工完成。再重新選擇一個工件開始，直到所有的加工任務完成。用全局選擇方法可以保證機器加工時間最短的先被選中且機器加工的工作負荷平衡。

舉例說明，假設第一次隨機抽取到工件I1，第二次隨機抽取到工件I2，則執行前兩道工序的過程如圖2所示。

圖2 全局選擇流程圖

2.2.2選 擇

用上文全局選擇方法對種群進行初始化后要執行選擇操作，對機器選擇、工序排序、故障概率和工序選擇四個部分每次選取全局最優解中的90%，淘汰相對情況不太好的10%，以此得到最終較優的局部最優解。

2.2.3交 叉

對于選擇進化出下一代的個體，隨機找到兩個不同的基因，根據交叉發生的概率，進行相互交換，產生新的下一代個體。交叉操作中一共分為機器選擇部分、工序排序部分、故障概率部分以及工序選擇四部分。

(1) 機器選擇部分：為保證每個基因的先后順序不變，此部分采用了均勻交叉的操作。主要步驟如下：

Step1在[1,T0]內隨機產生一個整數r1，再隨機得到r1個不同的整數；

Step2依據上述步驟得到整數r1，進而將父代染色體P1和P2內對應位置的基因根據目標位置機器數范圍比例復制到子代染色體C1和C2中，保持它們的位置和順序；

Step3將P1和P2余下的基因順次復制到C1和C2中，保證它們的位置一致，順序不變。

圖3為機器選擇部分的互換交叉過程。

圖3 機器選擇部分的交叉

(2) 工序排序部分：將每個染色體中對多個工件進行操作，更好地繼承父輩的優良基因。

Step1使得工件集{I1,I2,…，In}隨機劃分成兩個不同的工件集；

Step2將父代染色體P1和P2中包含在上述劃分的兩個工件集中的工件復制到C1和C2，保證它們的位置一致，順序不變；

Step3將P1和P2中不包括在上面劃分的兩個工件集中的工件復制到C2和C1，同時要保證它們的順序不變。

圖4為工序排序部分的互換交叉過程。

圖4 工序排序部分的交叉

(3) 故障概率部分：

Step1在區間[1,T0]內隨機產生一個整數r1，再次隨機產生r1個互不相同的整數；

Step2將染色體P1和P2中對應的位置進行交叉。

圖5為故障概率部分的互換交叉過程。

圖5 故障概率部分的交叉

(4) 工序選擇部分：

Step1在區間[1,T1]內隨機產生一個整數r2，再隨機產生r2個互不相同的整數；

Step2將染色體P1中r2個位置相互交換，P2以此類推。

圖6為工序選擇部分的互換交叉過程。

圖6 工序選擇部分的交叉

2.2.4變 異

變異通過對染色體的隨機微小改變，使得產生一組新的個體，提高了種群多樣性，并且一定程度上改變了局部搜索能力。

(1) 機器選擇部分：

Step1在變異染色體中隨機選取r1個位置；

Step2順序選擇所有的基因，對所有位置的機器設置為現在工序機器集合里可被選擇且同時加工時間最短的機器。

(2) 工序排序部分：

Step1在變異染色體中隨機選擇r1個不同基因，然后根據選取基因生成此排序的所有鄰域；

Step2將所有的鄰域相應適應值進行評價，選出其中最優的個體作為下一子代。

(3) 故障概率部分：

Step1按照隨機數r1再隨機產生r1個互不相等的整數；

Step2將染色體P1和P2中對應的位置進行互換變異。

(4) 工序選擇部分：

Step1按照隨機數r1再隨機產生r2個互不相等的整數；

Step2將染色體P1中r2個位置自身變異，變異成一個在工序數以內的隨機正整數。

2.2.5創新特點

為了解決如何在機器的加工工序未知、引入機器故障的情況下選擇出較優的加工分配方案的問題，本文在遺傳編碼中引入了工序排序部分和機器故障部分，提高了算法的并行性和準確性，進一步增加了此類問題結果的有效性。

3 算例實驗

為了驗證所建模型，本文使用一種在實際生產中被使用的智能化RGV動態調度測試算例進行驗證。

根據不同的加工參數，此算法都能得到同時考慮系統穩定性和效率的解決方案，而不單單只考慮效率，并且不只使用同一種解決方案，體現了算法的動態性。

假設情況中可進行加工的機器共有8臺，由1輛軌道式自動引導車(RGV)、8臺計算機數控機床(Computer Number Controller，CNC)、1條直線軌道、1條下料傳送帶、1條上料傳送帶等附屬設備組成，模擬圖如圖7所示。

圖7 智能加工系統示意圖

由于尚沒有可靠的標準算例可以用于此類柔性流水車間調度問題并被驗證可靠，因此將其工作時的相關參數進行如表1所示的定義。

表1 加工系統作業參數 s

其在遺傳算法中的參數、加工過程中的參數與穩定性函數中參數的數值定義如表2所示。

表2 參數設置

表中:pm是變異概率；pc是交叉概率；α、β是綜合評價函數的兩個參數；Errmin、Errmax是機器損壞時間的上下界。

假設一個元件被2臺平行機器進行加工，一個加工第一道工序，另一個加工第二道工序。分別假設加工機器為單臺加工機器和兩臺平行放置的機器，故用表1中的數據進行模擬時沒有RGV的移動時間，8臺機器加工的工件件數與2臺機器加工的工件件數之比分別會小于4。為了評價該模型的實用性，2臺機器加工設置了4、3、2三個指標，數值越高代表模型實用性較優，數值越低代表模型實用性較差。

表1中所給的三組數據共分為兩種情況：情況一為加工第一道工序所需時間大于加工第二道工序所需時間，即算例1、算例3；情況二為加工第一道工序所需時間小于加工第二道工序所需時間，即算例2。兩類流水線的示意圖如圖8所示。

(a)(b)圖8 兩類流水線的示意圖

假定使用2臺機器分別加工第一道工序和第二道工序并且平行放置，則加工工件的最大值滿足：

(15)

式中：ehk代表數組k中CNC加工第h道工序所需時間；q1k代表數組k中部分CNC一次上下料所需的時間；q2k代表數組k中另一部分CNC一次上下料所需的時間；ak代表數組k中RGV完成一個物料的清洗作業所需時間；e(3-h)k代表數組k中的CNC加工第3-h道工序所需時間，并要求ehk大于e(3-h)k。

以加工150個工件為例，計算8臺機器在規定件數下加工所需的時間與只有2臺機器時在規定件數下加工所需的時間長度數之比，結果如表3所示。并計算3種算例的平均數表示該模型的實用性，其平均值為3.34。由于作業參數比例越大越好并且其最大值為4，故該模型實用性較好。

表3 加工系統作業參數

同樣以加工150件工件為例，對于無故障的加工時間求解來說就是在前面的基礎上將故障概率部分都設為0。根據是否使用此調度算法得到了兩種調度方案，不使用此調度方案的執行方式是可能在遇到損壞并還未維修完成的機器上仍舊進行加工，其可能導致之后將要加工時出現擁堵現象。對得到的兩種不同的帶有故障的時間與未帶故障時求解得到的時間計算穩定性函數。

由于遺傳算法的局限性和故障發生的隨機性，一次運算的結果往往不具有代表性，因此本文對大量運算結果進行了處理。

在配置為：Intel i5-6300HQ的CPU，主頻為2.3 GHz，內存為16 GB的個人電腦上運行。對每組進行50次重復實驗，并求取各算例下不同算法的加工總時間，進一步求取平均值，得到減小每次隨機誤差后的綜合評價值，結果如表4所示。

表4 模型的綜合評價

將各個算例下不同算法的時間做成折線圖，如圖9所示。

圖9 兩類算法的時間對比

綜上所述，此模型可以得到一個既滿足穩定性高又滿足所花時間少的調度優化結構。

4 結 語

本文在研究此柔性作業車間調度問題的相應特點的前提下，提出了解決該問題的多段染色體編碼的遺傳算法優化算法。該算法對機器選擇部分、工序排序部分、故障概率部分和工序選擇部分四部分，分別使用了不同的編碼方式。多段編碼保證了在求解過程中問題解的穩定性與可解性的提升。在實際問題的模型構建中，考慮了對于機器損壞的時間以及機器運動的時間，進而減少了約束條件，保證問題與實際相符合。同時通過使用相應算例對模型進行驗證，由數據與對比結果進一步驗證了此算法的有效性以及實用性。根據兩種調度方案所需時間以及與得到的加工系統作業參數均值為3.34進行對比，進而驗證本文所構建模型的實用性較好。

在實際問題中常常會出現機器的損壞，從而給最終結果造成極大的誤差。為了避免此類問題的發生，我們引入了綜合評價函數，使得最終結果在滿足穩定性高的情況下得到數據的最大化。同時更貼近實際生產過程中會出現機器損壞導致作業中斷的情況，即可能導致之后將要在損壞并還未維修完成的機器上進行加工時造成擁堵現象。最后通過調度算法有效緩解了該擁堵現象。