利用歷史信息和限制算子求解MOFJSP

吉訓(xùn)生，蔡益青

1.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫214122

2.物聯(lián)網(wǎng)技術(shù)應(yīng)用教育部工程研究中心，江蘇 無錫214122

1 引言

當(dāng)下，智能制造日益成為制造業(yè)發(fā)展的重要趨勢和核心內(nèi)容。從機(jī)器層面上來講，智能制造要求機(jī)器具有柔性的生產(chǎn)制造能力，以實(shí)現(xiàn)“高效化”“綠色化”的生產(chǎn)目標(biāo)[1]。柔性作業(yè)車間調(diào)度問題（Flexible Job-shop Scheduling Problem，F(xiàn)JSP）假設(shè)工序可在多臺機(jī)器上加工，突破機(jī)器唯一性限制，是典型的柔性生產(chǎn)制造問題[2]。相比傳統(tǒng)的作業(yè)車間調(diào)度問題（Job-shop Scheduling Problem，JSP），F(xiàn)JSP 是復(fù)雜度更高的NP-hard 難題，也是智能制造及組合優(yōu)化領(lǐng)域的研究熱點(diǎn)之一[3]。

為了實(shí)現(xiàn)綠色、高效生產(chǎn)，建設(shè)綠色工廠，必須要求合理調(diào)度柔性作業(yè)車間內(nèi)的生產(chǎn)過程。通常，認(rèn)為以滿足消費(fèi)者要求，降低生產(chǎn)成本、減小污染氣體的排放等多個(gè)目標(biāo)的FJSP是一個(gè)多目標(biāo)柔性作業(yè)車間調(diào)度問題（Multi-Objective Flexible Job-shop Scheduling Problem，

MOFJSP）。MOFJSP需要優(yōu)化多個(gè)性能指標(biāo)（最小化最大完工時(shí)間、最小化生產(chǎn)、最小碳排放量等），而多個(gè)性能指標(biāo)之間往往存在沖突。對于一個(gè)解來說，無法使所有性能指標(biāo)都為最優(yōu)值。因此，求解MOFJSP的目的是為了得到各性能指標(biāo)的均衡解，稱為Pareto 最優(yōu)解[4]。多目標(biāo)進(jìn)化算法（Multi-Objective Evolutionary Algorithm，MOEA）因其在求解MOFJSP 時(shí)可獲得一致性的Pareto最優(yōu)解的特點(diǎn)，已成為求解此類問題常用的方法[5]。DEB 等[6]利用解之間Pareto 支配關(guān)系和擁擠距離，提出一種經(jīng)典的MOEA——帶精英策略的非支配排序遺傳算法（Non-dominated Sorted Genetic Algorithm-II，NSGA-II）；張超勇等[7]將NSGA-II 作為求解MOFJSP 的策略，驗(yàn)證了NSGA-II在解決MOFJSP有良好的性能。Zhang等[8]提出一種基于問題分解的多目標(biāo)進(jìn)化算法（Multi-Objective Evolutionary Algorithm based on Decomposition，MOEA/D），此算法的求解速度都遠(yuǎn)高于NSGA-II；隨后，Li等[9]將穩(wěn)定配對思想引入MOEA/D，提出了基于穩(wěn)定配對選擇策略和分解相結(jié)合的多目標(biāo)進(jìn)化算法（Multi-Objective Evolutionary Algorithm based on Decomposition and Stable Matching，MOEA/D-STM），成功解決了MOEA/D“丟失解”的缺點(diǎn)；Wang 等[10]在多目標(biāo)遺傳算法（Multi-Objective Genetic Algorithm，MOGA）的基礎(chǔ)上引入了免疫原則和熵，以保證種群的分布性，從而解決了早熟問題，提高收斂速度。

參考文獻(xiàn)[10]的做法，本文在MOEA/D-STM 基礎(chǔ)上提出一種基于歷史信息和限制算子多目標(biāo)進(jìn)化算法（Multi-Objective Evolutionary Algorithm based on Decomposition with Historical information and Limited operators，MOEA/D-HL），并利用MOEA/D-HL 求解MOFJSP。此算法在保證收斂性的同時(shí)，提高了種群的多樣性，增大進(jìn)化強(qiáng)度，增強(qiáng)全局搜索能力，避免早熟。實(shí)驗(yàn)結(jié)果表明，本文算法在求解MOFJSP問題上比較可行且有效。

2 MOFJSP模型

MOFJSP 可用集合( M,J,O,T )來描述，其中M 代表機(jī)器，J 代表工件，O 代表工序，T 代表加工時(shí)間。通常設(shè)定有m 臺機(jī)器( Mk,k ∈{1 ,2,…,m} )和n 個(gè)工件(J={ J1,J2,…,Jn} )，每個(gè)工件有多道工序，且工序的先后順序是確定的，每道工序Oij(i=1,2,…,n,j=1,2,…,ni，ni表示工件i 所含的工序數(shù)）可由多臺機(jī)器加工，所用時(shí)間tijk由機(jī)器能力唯一確定[11]。一個(gè)包括3 個(gè)工件、4 臺機(jī)器的MOFJSP問題描述如表1所示。

表1 3×4 MOFJSP問題加工時(shí)間表

本文將最小化最大完工時(shí)間、最小化生產(chǎn)成本和最小化能耗作為優(yōu)化目標(biāo)，構(gòu)建一個(gè)MOFJSP 模型[12-13]。求解MOFJSP 即在滿足電力資源約束和工序先后約束的前提下，根據(jù)目標(biāo)最優(yōu)要求，把工序分配到各機(jī)器上并確定工序的加工序列和開始時(shí)間[14]，達(dá)到高效、綠色生產(chǎn)的目的。

MOFJSP優(yōu)化目標(biāo)如下：

式中，bijk為工件i 的第j 道工序在機(jī)器k 上的開始加工時(shí)刻；tijk為工件i 的第j 道工序在機(jī)器k 上加工所用時(shí)間；Sijk為決策變量，若工序Oij在機(jī)器k 上加工則Sijk=1，否則，Sijk=0。

式中，γi為材料費(fèi)；νijk為人工費(fèi)，為工件的加工費(fèi)用，表示使用第v 種供電方式在單位時(shí)間內(nèi)為正常運(yùn)行（額定負(fù)載）狀態(tài)下的機(jī)器k 供電所需的成本，其中，v=1,2,3 分別表示使用主電網(wǎng)、分布式能源和燃機(jī)三種供電方式為機(jī)器提供能源；為機(jī)器空載運(yùn)行費(fèi)用，tk為機(jī)器k 在整個(gè)加工過程中的空載運(yùn)行時(shí)間表示使用第v 種供電方式在單位時(shí)間內(nèi)為空載狀態(tài)下的機(jī)器k 供電所需的成本。

求解MOFJSP滿足如下約束條件：

（1）在同一時(shí)段內(nèi)，一臺機(jī)器只能加工一個(gè)工件，即在某時(shí)刻h( )h ＞0 ，若1 則在i ≠p 或j ≠q 條件下，Spqk≠1 恒成立。

（2）同一個(gè)工件，只有在前工序完成后，才可加工下道工序，即：

其中，Cij表示工序Oij的完成時(shí)刻。

（3）任何一道工序一旦開始加工，就不可打斷，即：

除了滿足上述約束條件，還應(yīng)做如下假設(shè)：

（1）某工件當(dāng)前工序加工完成后，應(yīng)立即運(yùn)送至加工下一道工序所用機(jī)器前的緩沖器，若機(jī)器空閑應(yīng)立即開始加工，否則在緩沖器中等待加工。

（2）工件在機(jī)器間的傳送時(shí)間、在機(jī)器上的加工時(shí)間、裝卸時(shí)間、調(diào)整時(shí)間統(tǒng)一視為加工時(shí)間。

（3）在加工開始前，所有機(jī)器處于正常待命運(yùn)行狀態(tài)，且所有工件同優(yōu)先級。

3 求解MOFJSP的MOEA/D-HL

利用MOEA/D-STM 求解MOFJSP 時(shí)，在迭代過程中使用了無限制穩(wěn)定配對選擇策略，通過該策略選擇的種群收斂性優(yōu)于多樣性，這將降低最終種群的性能[15]。另外，在交叉操作時(shí)只使用了父代信息，這會降低收斂速度。由于以上原因，本文選擇有限制穩(wěn)定配對策略作為選擇策略，以平衡迭代過程中被選種群的收斂性與多樣性；另外設(shè)置一個(gè)外部存儲器用來存儲每個(gè)個(gè)體的歷史信息。歷史信息表示個(gè)體上一次迭代時(shí)的狀態(tài)。如圖1所示分別表示第g+2 次進(jìn)化操作時(shí)，x2、x4表示當(dāng)前狀態(tài)，則分別表示x2、x4的歷史信息；同理，分別表示x2、x4在g+1 次進(jìn)化操作時(shí)的歷史信息。在交叉操作時(shí)，借助個(gè)體的歷史信息以達(dá)到加速收斂的目的。利用MOEA/D-HL 求解MOFJSP的過程如圖2所示。

圖1 個(gè)體歷史信息示意圖

3.1 染色體編碼與解碼

圖2 MOEA/D-HL算法流程圖

編碼是算法與MOFJSP 之間的橋梁[16]。本文選擇基于工件工序和機(jī)器的雙層整數(shù)編碼，第一層為工序編碼，第二層為機(jī)器編碼。若有m 個(gè)待加工工件，每個(gè)工件有ni道工序，則染色體的每層編碼長度為。具體步驟為：（1）在[0，1]之間，隨機(jī)初始化長度為∑ni的實(shí)數(shù)數(shù)組；（2）根據(jù)每個(gè)位置上實(shí)數(shù)值的排名，確定其代表的工序；（3）通過工序編碼的具體數(shù)值，確定所用的機(jī)器，并得到機(jī)器編碼。

如圖3所示，染色體表示3個(gè)待加工工件，每個(gè)工件有2～3 道工序，有3 臺機(jī)器可用。隨機(jī)初始化一組實(shí)數(shù)數(shù)組，通過比較每個(gè)基因位上的值確定排名，排名前3位的代表工件1 的三道工序，排名4、5 的基因位代表工件2 的兩道工序，排名6、7 的基因位代表工件3 的兩道工序，因此工序編碼為[1 3 2 1 2 3 1]，表示工序[O11,O31,O21,O12,O22,O32,O13]。在確定工序編碼后，從每道工序可用的加工庫中，選擇機(jī)器，并確定機(jī)器編碼[2 1 3 2 2 2 1]，表示加工每道工序所用的機(jī)器分別為[M2,M1,M3,M2,M2,M2,M1]。

圖3 染色體編碼

解碼的具體步驟為：首先根據(jù)工序編碼確定工件及工序，然后從機(jī)器編碼中找出對應(yīng)的加工機(jī)器，并從時(shí)間矩陣中找到機(jī)器加工相應(yīng)工序所需時(shí)間。通過上述操作，一條合法的染色體可通過解碼操作得到一個(gè)可行、完整的調(diào)度方案。

3.2 進(jìn)化操作

進(jìn)化操作包括交叉和變異操作。交叉操作決定算法的全局搜索能力，是算法的關(guān)鍵[17]。如圖1所述，本文交叉操作使用的種群歷史信息存放在外部存儲器中。算法開始時(shí)，初始化父代種群，同時(shí)將父代種群個(gè)體存放在外部存儲器中，以初始化個(gè)體的歷史信息。隨后進(jìn)行交叉操作，步驟如下：首先，從父代種群中選擇三個(gè)染色體e1、e2、e3，并從外部存儲器中選擇染色體e1的歷史信息h1；其次，選擇從左向右依次在工序編碼的基因位處隨機(jī)產(chǎn)生r ∈(0,1]，若r ＜pc（pc為交叉概率），在父代染色體上選擇此基因位為交叉點(diǎn)；最后，將兩交叉點(diǎn)之間的基因進(jìn)行交叉操作，并根據(jù)工序編碼調(diào)整機(jī)器編碼。如圖4所示，選擇a、b 為交叉點(diǎn)，對a、b 之間的基因位進(jìn)行交叉操作：yr=e1+0.5×( e2-e3)+0.5( e1-h1)，生成子代染色體y 后，通過排序操作確定工序編碼，并根據(jù)父代和子代信息確定機(jī)器編碼。經(jīng)上述交叉操作得到的子代染色體滿足約束條件，是可行解。

圖4 交叉操作示意圖

變異操作有利提高算法的局部優(yōu)化能力和種群多樣性，防止算法陷入局部收斂。本文選用變異操作過程如圖5所示：在工序編碼里隨機(jī)選擇基因a、基因b 進(jìn)行交換，此交換將改變工序編碼中每個(gè)基因所代表的工序，改變工序編碼中每個(gè)基因所代表的工序，如c 位置的基因1 在原染色體表示工序O13，在新染色體變?yōu)楸硎綩12，d 位置的基因3在原染色體表示工序O31，在新染色體變?yōu)楸硎綩32，同時(shí)機(jī)器編碼也隨之變化。經(jīng)此變異操作得到的新染色體能夠滿足約束條件。

圖5 變異操作示意圖

當(dāng)一次進(jìn)化操作結(jié)束后，將父代種群個(gè)體按順序送入外部存儲器，更新外部存儲器所含歷史信息，為下一次交叉操作提供歷史信息。

3.3 選擇操作

MOEA/D-STM 因其在構(gòu)造偏好矩陣時(shí)，只用了解與子問題之間的歐氏距離和切比雪夫距離這兩類信息，造成選擇到的解多樣性較差。如圖6（a）所示，解擁擠在p1、p2之間，在下一次交叉和變異操作時(shí)，由于多樣性的不足，使得生成的新染色體改變較小，一方面使收斂速度降低，另一方面容易使尋優(yōu)過程陷入局部最優(yōu)。為了提高父代種群的多樣性，加速收斂，本文將解的位置信息引入到子問題對解的偏好矩陣的構(gòu)造過程中，以增加那些離Pareto Front 遠(yuǎn)但分布均勻的解的被選擇概率。主要操作有：（1）處理目標(biāo)空間與生成待選解集；（2）獲取解的位置信息，將位置信息代入自適應(yīng)轉(zhuǎn)移函數(shù)中，以得到限制信息；（3）構(gòu)造帶限制信息的子問題對解的偏好矩陣，以及解對子問題的偏好矩陣，并根據(jù)兩偏好矩陣的信息選擇父代種群。

（1）處理目標(biāo)空間與生成待選解集

設(shè)目標(biāo)空間為F(s)=[f1(s),f2(s),…,fd(s)]∈Rd,d 為目標(biāo)空間的維數(shù)。使用一組均勻的權(quán)向量w={w1,w2,…,，將目標(biāo)空間劃分為N 個(gè)子空間，其中wt=(wt,1,…,wt,j,…,wt,d)∈Rd,wt,j≥0，且1，同時(shí)得到對應(yīng)的子問題P={ p1,…,pl,…,pN}。將待選種群S={s1,…,sN,…,s2N}中的所有染色體通過目標(biāo)函數(shù)值的計(jì)算，映射到目標(biāo)空間中，得到待選解集X={x1,…,xN,…,x2N}，其中，x=[ f1( s),f2( s),…,fd( s )]∈Rd。

（2）獲取限制信息

本文選用解相對于子問題的角度作為位置信息。將d 維目標(biāo)空間F( s )=[ f1( s),f2( s),…,fd( s )]∈Rd轉(zhuǎn)化為個(gè)二維空間，其中，表示從d 個(gè)變量中選出2個(gè)所有的組合方法。對于二維空間Fc( s )=[ fu( s),fv( s )],c=1,2,…,,u,v ∈[1 ,2,…,d ]，解x 在此空間中的目標(biāo)值分別為fu( s),fv( s )，子問題ph對應(yīng)的權(quán)向量wh在此二維空間的分量為wh,uv=( wh,u,wh,v)，則夾角分量為：arctan(| fu( s )-ωh,u|| fv( s )-ωh,v|),θuv∈[0 ,π/2]。角度θ 定義為：子問題ph與解x 在個(gè)二維平面上的夾角分量之和。

構(gòu)造一個(gè)自適應(yīng)轉(zhuǎn)移函數(shù)，并引入位置信息θ，即：

（3）選擇操作

將上述限制信息引入到子問題pr,r=1,2,…,N 對候選解x,x ∈X 的偏好值計(jì)算式中，如式（7）。利用式（7）可計(jì)算出子問題對所有候選解的偏好值，按升序排列則構(gòu)成子問題對解的偏好矩陣ψp(N×2N)維 中的一行。

候選解x,x ∈X 對子問題pr,r=1,2,…,N 的偏好值計(jì)算式如式（8）。利用式（8）可計(jì)算出解對所有子問題的偏好值，按升序排列則構(gòu)成解對子問題的偏好矩陣ψX( 2N×N維 )中的一行。

其中，‖ · ‖為歐氏距離，F(xiàn)( si)是將F( xi)歸一化處理后的目標(biāo)函數(shù)值，其第l 個(gè)目標(biāo)函數(shù)值)/l=1,2,…,d ，其中，為最差點(diǎn)，可通過,l=1,2,…,d 計(jì)算。

利用兩個(gè)偏好矩陣的信息和延遲接受程序[18]，得到最終配對結(jié)果如圖6（c）所 示：} 。很明顯，此種方法選擇的解比不加限制信息的配對策略選擇的解多樣性更好。

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

NSGA-II 因其快速排序、快速估算擁擠距離以及容易比較擁擠距離的三個(gè)特點(diǎn)，成為CIMS 領(lǐng)域最常用的多目標(biāo)算法之一。因此，本文將與NSGA-II 比較。NSGA-II和MOEA/D-STM需要設(shè)置的參數(shù)參照文獻(xiàn)[19]。MOEA/D-HL 參數(shù)設(shè)置：種群染色體數(shù)目N=40，迭代次數(shù)K=400。為驗(yàn)證交叉概率pc，變異概率pm，限制算子控制參數(shù)L，鄰域大小T 對生成調(diào)度方案的影響，本文進(jìn)行了各相關(guān)參數(shù)的靈敏度分析。

4.1 靈敏度分析

采集某制桶公司實(shí)際生產(chǎn)車間的原始數(shù)據(jù)，取整處理后的數(shù)據(jù)如表2、3。車間設(shè)備名稱與編號列于表2，6種桶，每種桶加工所需的20工序、可用的加工機(jī)械及所用加工時(shí)間列于表3。

以制桶車間實(shí)際訂單為例，設(shè)置不同的實(shí)驗(yàn)參數(shù)，以三個(gè)目標(biāo)值為參考，所得實(shí)驗(yàn)結(jié)果如表4所示。

從表5 可知，三種算法對pc、pm的值不敏感。另一方面，MOEA/D-HL中限制算子的控制參數(shù)對實(shí)驗(yàn)結(jié)果有較大的影響。因此，為了得到最佳實(shí)驗(yàn)結(jié)果，本文設(shè)置交叉概率pc=0.8，變異概率pm=0.6，限制算子控制參數(shù)L=1，鄰域大小T=10。

4.2 實(shí)例仿真及結(jié)果分析

用3種算法求解該調(diào)度問題，不考慮工件在機(jī)器間轉(zhuǎn)移的時(shí)間，實(shí)驗(yàn)參數(shù)不變。收斂性能見表5，MOEA/D-HL 所需最大完工時(shí)間、生產(chǎn)成本和C 排放量最優(yōu)解分別為4 105 s、4 223.6元和39.5 g。從加工實(shí)時(shí)性上考慮，MOEA/D-HL性能優(yōu)于NSGA-II、MOEA/D-STM，分別提高了0.8%，1.4%；在生產(chǎn)成本控制上，MOEA/D-HL較NSGA-II、MOEA/D-STM 提高了0.8%和1.8%；碳排放量是衡量綠色生產(chǎn)車間的一個(gè)重要指標(biāo)，通過MOEA/D-HL 得到的調(diào)度方案對環(huán)境更加友好，較NSGA-II、MOEA/D-STM減少了2.5%和4.8%的碳排放量。另外，如圖7 所示，MOEA/D-HL 收斂速度在整個(gè)進(jìn)化過程中優(yōu)于另外兩種算法，也即MOEA/D-HL能更快地得到調(diào)度方案。

圖6 MOEA/D-STM和MOEA/D-HL兩者對比

表2 設(shè)備及編號

表3 工序與加工設(shè)備

表4 參數(shù)靈敏度分析

表5 實(shí)例仿真結(jié)果

圖7 最大完工時(shí)間平均收斂曲線

5 結(jié)論

本文利用歷史信息和帶限制算子的選擇策略，在保證良好收斂性的同時(shí)，加快了收斂速度。在生成子代的過程中，利用個(gè)體的歷史信息，生成較大的進(jìn)化量，在選擇過程中，本文利用解在目標(biāo)空間中的位置信息得到自適應(yīng)限制信息，并將其加入到偏好矩陣的構(gòu)造過程中，以獲得分布性能好的父代種群，從而加快收斂速度。以某企業(yè)生產(chǎn)訂單為例，驗(yàn)證MOEA/D-HL在解決實(shí)際生產(chǎn)車間調(diào)度問題時(shí)，收斂性和收斂速度優(yōu)于MOEA/DSTM和NSGA-II，能夠快速地獲得收斂性能好的調(diào)度方案指導(dǎo)實(shí)際生產(chǎn)。