基于遺傳算法的RGV 動態調度問題

李新靚，王心如，車東宇，吳宇航

(1. 華北理工大學以升創新教育基地，河北 唐山 063210；2. 華北理工大學理學院，河北 唐山 063210； 3. 華北理工大學數學建模創新實驗室，河北 唐山 063210；4. 河北省數據科學與應用重點實驗室，河北 唐山 063210)

0 引言

隨著我國科學技術的發展和WTO 的加入，RGV（有軌穿梭小車）應運而生，提高了勞動生產率，而在制造業，調度是實現制造業生產高效率、高柔性和高可靠性的關鍵，制定合理的RGV 動態調度策略擁有強大的時代背景和現實意義。RGV（有軌穿梭小車）提高了勞動生產率，在制造業，調度是實現制造業生產高效率、高柔性和高可靠性的關鍵，分別考慮一道工序與兩道工序的物料加工形式、正常工作與發生故障的情況，制定合理的RGV 動態調度策略擁有強大的時代背景和現實意義。

1 模型假設

（1）假設人力資源為無限資源，不考慮人力資源的調度影響；

（2）假設工件的任一工序必須在其前道工序完成后才能開始，即前一個工序未完成，則后面工序需要等待，保證同一工件不會同時在兩臺機器上加工；

（3）假設任一臺機器每次只能加工一個工件，且一旦開工就不能中斷；

（4）假設各工件經過其準備時間后可開始加工，工件的加工時間事先給定，且在整個加工工程中保持不變。

2 模型建立及求解

2.1 模擬工件到達個數

根據許多研究表明[1]，在一定的時間內，制造車間中的工件隨機到達相應的CNC 處理機器的個數可呈泊松分布[2]。利用泊松分布公式可模擬一班次（8 個小時）內加工工件的個數。

設泊松分布系數為λ，任意兩個先后到達同一CNC 的工件之間的時間間隔服從參數為λ 的指數分布，則根據泊松分布方程[3]：

其中λ 為工件平均到達率，U 為車間利用率，m 為車間機器數量，μ 為工序的平均加工時間， μg為每個工件的平均加工序數。代入各加工參數得到λ=0.00879，則一班次之內加工工件的個數大約為235 件。

2.2 確定優化系統效率的指標

2.2.1 建立實際生產的指標體系[4]

RGV 動態調度的目標是確定最佳的產品加工順序，滿足裝配時間的合理調度，使得加工系統的各性能指標達到最優。RGV 的動態調度的性能指標主要包括：縮短生產周期、降低生產成本、提高生產柔性，基于此目的考慮動態調度的性能指標，如圖1 所示：

圖1 RGV 動態調動指標體系 Fig.1 RGV dynamic mobilization indicator system

2.2.2 構造優化系統的目標函數

分析實際情況可知，時間的指標T越小，成本C越低，資源R利用效率越高，越符合優化的條件，由此建立RGV 車間生產作業的動態調度數學模型，以及模型的目標函數[5]。

（1）關于時間指標T

包括有生產周期T1、提前或拖延完工時間T2、無效時間 T3。生產周期 T1是指完成所有的裝配任務所需的總時間，是反映車間的生產效率的重要的指標之一，1T 計算公式如下：

其中，tijk為單位工件的加工時間，nijk為工件規定的生產數量，mijk為CNC 移動的時間，Tijkb為故障修復時間， Tcijk為轉移機器的時間，dijk為上一個工件與下一個工件加工的沖突時間。求和部分表示的是裝配線完成所有裝配任務的完工時間。

提前或拖延時間 T2，客戶規定的交貨期通常采用時間窗函數，計算公式如下：

其中[ pi, qi]為客戶規定的完工時間的區間，T 為產品完工時間即產品在各裝配線上最晚的完工時間。

無效生產時間 T3，包括生產準備的時間、產品換加工CNC 的時間、CNC 故障維修的時間等，其計算公式如下：

（2）關于成本C

根據對實際生產的理解，將成本分為原材料的成本 C1、故障成本 C2、人工成本 C3、庫存成本 C4、加工成本 C5。

其中cwijk為單個的工件材料的成本，bk為故障率且其值為1%。

其中cmijk為單個工件的加工成本，cgijk為單位故障時間的損失費用。

其中 cf為單個機器的維修費用。

庫存成本指的是提前完成的產品其必須保留到交貨期而耗用的成本，計算公式如下：

Cs的含義為單個工件的存儲費用，a、 b 分別表示規定的取貨日期前、后的取貨時間。

（3）關于資源指標R

2.3 嵌入貪婪解碼算法的遺傳算法

算法框圖如圖2 所示。

圖2 遺傳算法的基本過程 Fig.2 Basic process of genetic algorithm

2.3.1 編碼

編碼就是解的遺傳基因[6]，為其的數字化表示，它是在應用的遺傳算法實施優化過程中遇到的首要問題，也是應用成功與否的關鍵之一。在眾多編碼方法中，目前基于工序的編碼方式是最為合理的：編碼方式和相對應的解碼方案簡單，柔性高、容易實現。

圖3 解碼方式 Fig.3 Decoding mode

2.3.2 貪婪解碼算法

將插入式貪婪解碼算法，應用到給定的主動調度的反轉染色體、反轉工藝的路線，就能得到全主動調度[7]。

表1 貪婪解碼算法 Tab.1 Greedy decoding algorithm

對于一個給定的主動調度，通過反轉該調度，關于工序編碼的染色體及解決問題的工藝的路線，按半主動解碼方式，對反轉的染色體解碼，可將原來的主動調度轉變成一個新的動態調度，與原主動調度在每臺機器上的加工順序相反。

2.3.3 交叉操作

交叉是遺傳算法中的最重要的操作[8]，并決定了的遺傳算法的全局搜索能力。采用POX 交叉算法的能夠很好地繼承父代特征。

圖4 POX 算法 Fig.4 POX algorithm

2.3.4 變異操作

通過改進遺傳機制中的變異操作來改良遺傳算法，使得整個體制可以得到優秀的有效解，所以決定采用基于鄰域搜索的一種新型變異算子，它可以保持群體的狀態多樣性，而且能通過局部的搜索來改善系統的穩定性，提高最優解的出現頻率。

2.3.5 選擇操作

選擇操作的作用是避免有效基因的損失，使高性能的個體更大的概率生存，結合最佳個體保存和比例選擇，引入個體競爭，從而提高全局的收斂效率和系統的計算的效率。采用最佳個體的保存和比例選擇兩種策略的相結合的方式，產生隨機數rand∈[0,1]，滿足：

2.3.6 適應度函數

將染色體經過交叉、變異等過程變為新的染色體子代，但并不是所有的子代染色體都可以使RGV的動態調度策略變得更滿足于給定的指標，提高系統效率。

圖5 只含一道工序的各工序甘特圖 Fig.5 Gantt chart of each process with only one process

對于兩道工序的過程，最大完成工時分別為28378 s、35280 s、27482 s。

圖6 含兩道工序的各工序甘特圖 Fig.6 Gantt diagram of each process with two processes

發生故障的時候，兩種情況如下：

（1）只含有一道工序時，CNC#6 在12760 s 時發生故障，由求解過程中的輸出P 可知，發生故障時第161 個工件正在第六臺上加工，工件報廢，在發生故障的期間，凍結CNC#6 在發生故障之前的已預約工件202 號與207 號，直至13340 s 時機器設備維修好立即投入使用，以13340 s 為起始點對剩余工件進行調度，由模型求得完成該系統最大完工時為18840 s，知得原工時為19720 s，所以發生故障時的RGV 的動態調度方案對于系統的效率具有促進作用。

圖7 只含一道工序故障甘特圖 Fig.7 Contains only one process fault gantt diagram

（2）當系統包含兩道工序時，CNC#3 在7560s 時發生故障，由求解過程中的輸出P 可知，發生故障時第72 個工件正在第六臺上加工，據題意可知該工件報廢，在發生故障的期間，凍結CNC#3 在發生故障之前的已預約工件98 號、86 號等工件，直至8400 s 時機器設備維修好立即投入使用，以8400 s為起始點對剩余工件進行調度，由模型求得完成該系統最大完工時為35270 s，知得原工時為35280 s，所以發生故障時的RGV 的動態調度方案對于系統的效率具有促進作用。

圖8 含兩道工序的故障甘特圖[9] Fig.8 Fault gantt diagram with two processes

算法有效性的分析，測試算法的性能，進行仿真及分析。

為測試算法性能，采用柔性車間調度的兩個問題Q1（十工件十機器）以及Q2（六工件四機器）和選擇能確定性能的加工數據作為算法好壞的指標，構造2 個不相同的RGV 動態調度的測試。且將測試問題看作一般性調度問題，即工序的加工機器與各工序的時間已知，找到工序的最優排序即RGV 的最佳調度策略并輸出該系統完成加工固定工件數所需要的最大工時。

提前規定好算法內的參數：最大遺傳代數MAXGEN=500，個體數目NIND=20，代溝GGAP=0.9，交叉率XOVR=0.8，變異率MUTR=0.6，分別采用建立的模型和基本遺傳算法對每個測試隨機計算20次，得到結果如表所示，其中，Tmax，AMN、No.BMN 和AG 分別表示兩種算法運行20 次結果后，其中所得的最大完工時，平均的生產周期、得到最優的生產結果的次數以及得到最優解的代數平均值。

表2 改進遺傳算法 Tab.2 Improved genetic algorithm

表2 為所得的測試結果，可知改進的遺傳算法采用了貪心解碼算法以及基于鄰域搜索[10]的變異操作后可獲得最優生產結果的次數增多，比原來的基本遺傳算法的穩定性提高顯著；相比采用基本單點式或隨機式交叉方式，改進后的遺傳算法應用POX 交叉算子進行交叉操作，使其可繼承父代優良特征的性能大大提高；改進的算法的AG 指標較大，說明在選擇操作過程中結合最佳個體保存和比例選擇，有效提高了全局收斂和計算效率，進而說明改進的算法可以較優良的跳出尋找局部最優解，避免早熟收斂。

通過解的變化和種群均值的變化，可見應用改進的遺傳算法的收斂性。

圖9 解的變化與種群均值變化的過程 Fig.9 Change of solution and change of population mean

3 結論

遺傳算法利用簡單的編碼技術和繁殖機制來表現復雜的現象，僅根據個體個體的適應度值進行搜索，不受限制條件的約束，操作簡單且具有高效性、魯棒性、強通用性等特點。

利用貪婪解碼算法優化遺傳算法，將搜索空間限于主動調度集，不僅能保證最優調度存在，而且能提高搜索效率。

基于工序編碼的染色體只具有半Lamark 特性，遺傳操作的設計對算法的性能有較大影響。 一班（8 個小時）內加工工件數約為235 個。選取產品完成時間、生產周期等時間指標，原材料成本、人工成本等成本指標，人員利用率、時間利用率等資源指標作為優化約束條件。應用遺傳算法對RGV 動態調度問題進行求解，編碼方式應用基于工序的編碼方式；插入貪婪解碼算法對傳統遺傳算法進行優化；應用POX 交叉算子進行交叉操作；采用基于鄰域搜索的變異操作；在選擇操作過程中結合最佳個體保存和比例選擇，引入個體競爭，提高全局收斂和計算效率；得出235 個工件一班之內的加工順序流程。