基于遺傳算法的RGV 動態(tài)調(diào)度問題

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

(1. 華北理工大學(xué)以升創(chuàng)新教育基地，河北 唐山 063210；2. 華北理工大學(xué)理學(xué)院，河北 唐山 063210； 3. 華北理工大學(xué)數(shù)學(xué)建模創(chuàng)新實(shí)驗(yàn)室，河北 唐山 063210；4. 河北省數(shù)據(jù)科學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河北 唐山 063210)

0 引言

隨著我國科學(xué)技術(shù)的發(fā)展和WTO 的加入，RGV（有軌穿梭小車）應(yīng)運(yùn)而生，提高了勞動生產(chǎn)率，而在制造業(yè)，調(diào)度是實(shí)現(xiàn)制造業(yè)生產(chǎn)高效率、高柔性和高可靠性的關(guān)鍵，制定合理的RGV 動態(tài)調(diào)度策略擁有強(qiáng)大的時(shí)代背景和現(xiàn)實(shí)意義。RGV（有軌穿梭小車）提高了勞動生產(chǎn)率，在制造業(yè)，調(diào)度是實(shí)現(xiàn)制造業(yè)生產(chǎn)高效率、高柔性和高可靠性的關(guān)鍵，分別考慮一道工序與兩道工序的物料加工形式、正常工作與發(fā)生故障的情況，制定合理的RGV 動態(tài)調(diào)度策略擁有強(qiáng)大的時(shí)代背景和現(xiàn)實(shí)意義。

1 模型假設(shè)

（1）假設(shè)人力資源為無限資源，不考慮人力資源的調(diào)度影響；

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

（3）假設(shè)任一臺機(jī)器每次只能加工一個(gè)工件，且一旦開工就不能中斷；

（4）假設(shè)各工件經(jīng)過其準(zhǔn)備時(shí)間后可開始加工，工件的加工時(shí)間事先給定，且在整個(gè)加工工程中保持不變。

2 模型建立及求解

2.1 模擬工件到達(dá)個(gè)數(shù)

根據(jù)許多研究表明[1]，在一定的時(shí)間內(nèi)，制造車間中的工件隨機(jī)到達(dá)相應(yīng)的CNC 處理機(jī)器的個(gè)數(shù)可呈泊松分布[2]。利用泊松分布公式可模擬一班次（8 個(gè)小時(shí)）內(nèi)加工工件的個(gè)數(shù)。

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

其中λ 為工件平均到達(dá)率，U 為車間利用率，m 為車間機(jī)器數(shù)量，μ 為工序的平均加工時(shí)間， μg為每個(gè)工件的平均加工序數(shù)。代入各加工參數(shù)得到λ=0.00879，則一班次之內(nèi)加工工件的個(gè)數(shù)大約為235 件。

2.2 確定優(yōu)化系統(tǒng)效率的指標(biāo)

2.2.1 建立實(shí)際生產(chǎn)的指標(biāo)體系[4]

RGV 動態(tài)調(diào)度的目標(biāo)是確定最佳的產(chǎn)品加工順序，滿足裝配時(shí)間的合理調(diào)度，使得加工系統(tǒng)的各性能指標(biāo)達(dá)到最優(yōu)。RGV 的動態(tài)調(diào)度的性能指標(biāo)主要包括：縮短生產(chǎn)周期、降低生產(chǎn)成本、提高生產(chǎn)柔性，基于此目的考慮動態(tài)調(diào)度的性能指標(biāo)，如圖1 所示：

圖1 RGV 動態(tài)調(diào)動指標(biāo)體系 Fig.1 RGV dynamic mobilization indicator system

2.2.2 構(gòu)造優(yōu)化系統(tǒng)的目標(biāo)函數(shù)

分析實(shí)際情況可知，時(shí)間的指標(biāo)T越小，成本C越低，資源R利用效率越高，越符合優(yōu)化的條件，由此建立RGV 車間生產(chǎn)作業(yè)的動態(tài)調(diào)度數(shù)學(xué)模型，以及模型的目標(biāo)函數(shù)[5]。

（1）關(guān)于時(shí)間指標(biāo)T

包括有生產(chǎn)周期T1、提前或拖延完工時(shí)間T2、無效時(shí)間 T3。生產(chǎn)周期 T1是指完成所有的裝配任務(wù)所需的總時(shí)間，是反映車間的生產(chǎn)效率的重要的指標(biāo)之一，1T 計(jì)算公式如下：

其中，tijk為單位工件的加工時(shí)間，nijk為工件規(guī)定的生產(chǎn)數(shù)量，mijk為CNC 移動的時(shí)間，Tijkb為故障修復(fù)時(shí)間， Tcijk為轉(zhuǎn)移機(jī)器的時(shí)間，dijk為上一個(gè)工件與下一個(gè)工件加工的沖突時(shí)間。求和部分表示的是裝配線完成所有裝配任務(wù)的完工時(shí)間。

提前或拖延時(shí)間 T2，客戶規(guī)定的交貨期通常采用時(shí)間窗函數(shù)，計(jì)算公式如下：

其中[ pi, qi]為客戶規(guī)定的完工時(shí)間的區(qū)間，T 為產(chǎn)品完工時(shí)間即產(chǎn)品在各裝配線上最晚的完工時(shí)間。

無效生產(chǎn)時(shí)間 T3，包括生產(chǎn)準(zhǔn)備的時(shí)間、產(chǎn)品換加工CNC 的時(shí)間、CNC 故障維修的時(shí)間等，其計(jì)算公式如下：

（2）關(guān)于成本C

根據(jù)對實(shí)際生產(chǎn)的理解，將成本分為原材料的成本 C1、故障成本 C2、人工成本 C3、庫存成本 C4、加工成本 C5。

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

其中cmijk為單個(gè)工件的加工成本，cgijk為單位故障時(shí)間的損失費(fèi)用。

其中 cf為單個(gè)機(jī)器的維修費(fèi)用。

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

Cs的含義為單個(gè)工件的存儲費(fèi)用，a、 b 分別表示規(guī)定的取貨日期前、后的取貨時(shí)間。

（3）關(guān)于資源指標(biāo)R

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

算法框圖如圖2 所示。

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

2.3.1 編碼

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

圖3 解碼方式 Fig.3 Decoding mode

2.3.2 貪婪解碼算法

將插入式貪婪解碼算法，應(yīng)用到給定的主動調(diào)度的反轉(zhuǎn)染色體、反轉(zhuǎn)工藝的路線，就能得到全主動調(diào)度[7]。

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

對于一個(gè)給定的主動調(diào)度，通過反轉(zhuǎn)該調(diào)度，關(guān)于工序編碼的染色體及解決問題的工藝的路線，按半主動解碼方式，對反轉(zhuǎn)的染色體解碼，可將原來的主動調(diào)度轉(zhuǎn)變成一個(gè)新的動態(tài)調(diào)度，與原主動調(diào)度在每臺機(jī)器上的加工順序相反。

2.3.3 交叉操作

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

圖4 POX 算法 Fig.4 POX algorithm

2.3.4 變異操作

通過改進(jìn)遺傳機(jī)制中的變異操作來改良遺傳算法，使得整個(gè)體制可以得到優(yōu)秀的有效解，所以決定采用基于鄰域搜索的一種新型變異算子，它可以保持群體的狀態(tài)多樣性，而且能通過局部的搜索來改善系統(tǒng)的穩(wěn)定性，提高最優(yōu)解的出現(xiàn)頻率。

2.3.5 選擇操作

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

2.3.6 適應(yīng)度函數(shù)

將染色體經(jīng)過交叉、變異等過程變?yōu)樾碌娜旧w子代，但并不是所有的子代染色體都可以使RGV的動態(tài)調(diào)度策略變得更滿足于給定的指標(biāo)，提高系統(tǒng)效率。

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

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

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

發(fā)生故障的時(shí)候，兩種情況如下：

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

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

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

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

算法有效性的分析，測試算法的性能，進(jìn)行仿真及分析。

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

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

表2 改進(jìn)遺傳算法 Tab.2 Improved genetic algorithm

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

通過解的變化和種群均值的變化，可見應(yīng)用改進(jìn)的遺傳算法的收斂性。

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

3 結(jié)論

遺傳算法利用簡單的編碼技術(shù)和繁殖機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象，僅根據(jù)個(gè)體個(gè)體的適應(yīng)度值進(jìn)行搜索，不受限制條件的約束，操作簡單且具有高效性、魯棒性、強(qiáng)通用性等特點(diǎn)。

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

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