加工時間模糊車間多目標調度與獎懲灰靶決策＊

韓文穎 趙明君 春 蘭 巴特爾

（①內蒙古工業大學工程訓練教學部，內蒙古 呼和浩特 010051；②山西省電力公司超高壓變電分公司，山西 太原 030000）

由于客戶的多樣化需求和企業的內卷化競爭，使得產品定制化、多樣化程度越來越高[1]。為了適應市場發展趨勢和滿足市場需求，具有多樣化產品生產能力的柔性生產車間逐漸取代剛性生產車間[2]。對于柔性生產車間，不同的生產調度方案對應不同的生產效率、生產能耗等。因此，研究柔性車間生產調度問題具有重要的經濟意義和現實價值。

柔性車間生產調度方法是根據調度問題特點的變化而變化的。最初研究的生產調度問題具有生產規模小、設備柔性度不高的特點，因此使用窮舉法、網絡圖法、數學規劃法[3-4]就能夠較好地解決此問題。而后隨著車間柔性度加深、車間規模擴大，數學規劃法的計算量和網絡圖法的網絡規模過大，無法解決大規模車間的調度問題。此時，通過編碼的方式，將調度優化問題轉化為智能算法尋優問題成為主流方法[5]。文獻[6] 針對具有裝配操作的柔性車間調度問題，提出了基于變鄰域搜索粒子群算法的調度方法，通過實驗證明了該方法具有更好性能。文獻[7]針對柔性車間調度問題，通過對遺傳算法的初始化方法和變異方法進行改進，提出了基于改進遺傳算法的調度方法。

上述研究方法都是在確定條件下提出的，但是車間生產過程還受到隨機因素和不確定因素的影響，比如機床故障、訂單加急、訂單插入和加工時間不確定等。文獻[8]針對隱性擾動導致的重調度問題，分析了工序間的動態關聯性，并采用遺傳算法進行求解，通過仿真證明了重調度方法的正確性。文獻[9]分析了機床故障和訂單插入時的能耗特性，以能耗和完工時間為目標，對生產參數和調度問題進行了綜合優化。文獻[10]采用區間灰數表征不確定的加工時間，并提出了基于自適應人工蜂群算法的求解方法，有效提高了企業的生產效率。當前關于隨機因素和不確定因素下車間調度問題的研究存在以下問題：一是對于多目標優化問題，多以加權綜合法進行研究，僅給出單一的調度方法，沒有給出可選方案集合；二是對于Pareto 解集，缺少合理的決策方法。

針對上述問題，本文在考慮加工時間模糊前提下，使用模糊集理論建立調度優化模型，提出了鄰域動態選擇NSGA-II 算法的優化方法；并基于加權灰靶理論決策出了最優染色體。最后通過實際生產案例驗證了本文方法的有效性。

1 基于模糊集的車間調度建模

1.1 問題描述

考慮加工時間不確定的柔性作業車間多目標調度問題描述為：車間中放置了M臺加工機床，記為{Cm}，m∈[1,M]；承擔了N個工件的加工任務，記為{Jn}，n∈[1,N]；工件Jn的工序數量記為Ln，其加工工序記為{Onl}，l∈[1,Ln]。在柔性生產模式下，每一工件可以由多臺機床進行加工，且各機床的模糊加工時間已知。

在本文研究中，柔性車間生產調度的優化目標為

（1）車間模糊完工時間最小。

（2）機床模糊總負載最小。

（3）瓶頸機床模糊負載最小。

柔性車間生產調度的任務為

（1）為各工序的生產順序進行排序。

（2）為各工序安排加工機床。

根據車間生產實際，對柔性車間多目標調度問題作以下假設和設定：

（1）在初始時刻，機床為完好狀態。

（2）工序加工過程為連續不中斷的，即不考慮機床故障等突發情況。

（3）不設置工件的加工優先級，即所有工件的加工優先級一致。

（4）將工件的物流時間考慮在了加工時間內，無須另外考慮材料的物流時間。

1.2 模糊數與去模糊化

三角模糊數和梯形模糊數是模糊集理論中常見的模糊數，前者多用于表征加工時間模糊性，后者多用于表征交貨期模糊性。因此本文采用三角模糊數表示模糊加工時間。本文中設定上標“ ?”的參數為三角模糊數。基于三角模糊數的模糊加工時間記為T?=(t1,t2,t3)，其中t1、t3分別為最小加工時間、最大加工時間，t2為最可能加工時間。三角模糊數的隸屬度函數和運算規則具有明確定義，可參考文獻[11]。

在三角模糊數的研究中，鮮有關于去模糊化的研究。為了后文比較方案的性能優劣，需對三角模糊數進行去模糊化，本文采用期望值法對模糊數去模糊化。對于T?=(t1,t2,t3)，去模糊化為

式中：ET?為模糊數T?的均值；E1、E2分別為模糊數在區間[t1,t2]、(t2,t3]的均值；f(x)、g(x)分別為模糊數在區間[t1,t2]、(t2,t3]的隸屬度函數。

1.3 模糊調度模型

根據設定的3 個調度優化目標，分別建立優化目標模型。

（1）車間模糊完工時間最小

車間完工時間應以最后一道工序完工時間為準，則車間模糊完工時間最小的目標函數為

式中：f1為車間模糊完工時間最小的目標函數；為工序Onl的模糊完工時間。

（2）機床模糊總負載最小

首先設置一個標識參數xnlm，并定義

則機床模糊總負載最小的目標函數為

式中：f2為機床模糊總負載最小目標函數；為工序Onl在機床Cm上的模糊加工時間。

（3）瓶頸機床模糊負載最小

瓶頸機床是指負載最大的機床，設置瓶頸機床負載最小這一目標，本質是以負載均衡為目標，則：

式中：f3為瓶頸機床模糊負載最小目標函數。

柔性車間調度在優化過程中需滿足以下約束：

（1）同一工件的工序需滿足前后加工順序。

（2）任一機床在同一時間最多加工一道工序。

（3）每一道工序必須且只能加工一次。

（4）加工過程連續不間斷。

上述約束條件的對應公式描述為

2 鄰域動態選擇NSGA-II 調度算法

針對柔性車間多目標調度優化問題，本節提出了基于鄰域動態選擇NSGA-II 算法的調度方法。

2.1 鄰域動態選擇NSGA-II 算法

NSGA-II 算法[12-13]本質是在遺傳算法中引入了非支配排序的選擇方法。

在標準NSGA-II 算法中，選擇過程為：首先依據非支配層排序依次保留非支配層1、非支配層2，直到保留數量超過設定規模時結束；而后計算最后一層非支配層中染色體的擁擠度，保留擁擠度較大的若干染色體，直至染色體數量達到設定規模。擁擠度的計算方法：端點處的染色體擁擠度設置為+∞，其余染色體計算方法為

式中：di為染色體xi的擁擠度；j為目標函數編號；分別為染色體xi的緊鄰個體適應度值。分析式（7）可知，擁擠度越大，則染色體分布越稀疏、多樣性越好。

標準NSGA-II 算法的選擇方法問題在于：①在最后一層非支配層選擇時，是一種靜態選擇方法，選擇過程中沒有動態更新擁擠度，導致染色體分布不均勻，即染色體多樣性較差；②擁擠度計算僅以本層染色體為依據，忽略了鄰域內的分布情況，是一種片面的衡量標準。

針對上述問題，本節提出了鄰域動態選擇策略，實施方法為：依據非支配層排序依次保留染色體，直到保留數量超過設定規模時結束；而后，從最后一支配層動態刪除染色體，首先刪除擁擠度最小的個體，而后動態更新染色體擁擠度，重復刪除過程，直至染色體數量與設定規模一致。在動態選擇策略中，基于鄰域范圍計算染色體的擁擠度為

式中：di為鄰域范圍的擁擠度；Pnei為鄰域內染色體數量； ?nei為染色體xi的鄰域；xq為鄰域內染色體；為染色體xq在第j個目標上的取值。

對比式（7）和式（8）可知，式（7）僅考慮的最后一層支配層染色體分布的擁擠度，而式（8）考慮了包括其他支配層在內的鄰域范圍，是一種更加全面的計算方式。有利于在整體分布上挑選出多樣性較好的染色體。

2.2 基于改進NSGA-II 算法的調度優化方法

基于鄰域動態選擇NSGA-II 算法的車間調度優化方法主要包括編碼、交叉、變異和選擇等關鍵步驟，其中選擇方法在2.1 節已經明確，在此僅對編碼、交叉和變異進行分析和改進。

（1）編碼。根據車間調度任務，將染色體編碼為雙鏈形式，一條為工序選擇，對應工序的生產順序；另一條為機床分配，對應各工序的加工機床。以3 個工件和3 個機床為例，某一染色體編碼如圖1所示。

圖1 染色體編碼

圖1 “工序選擇基因鏈”中，數字“2”第一次出現表示工序O21，第二次出現表示工序O22，其余數字含義與此一致。“機床分配鏈”中，各基因位分別為O11、O12、O21、O22、O31、O32的加工機床。

（2）交叉。機床分配鏈的編碼方式使2 個父代染色體的對應基因位可以互換，因此采用傳統單點交叉法即可。工序選擇鏈需遵守“各工序必須加工1 次且只能加工1 次”的約束，因此采用POX交叉法[14]，具體實現方法如圖2 所示。

圖2 交叉操作

圖2 中父代工件2 和4 的各工序基因不變，將工件1 和3 的各工序基因交叉，得到子代染色體。

（3）變異。對于機床分配鏈，隨機選擇2 個基因位，將其變異為其他可用機床即可。對于工序選擇鏈，采用切割基因段并右移循環變異的方法，如圖3 所示。

圖3 右移循環變異

圖3 中隨機截取基因段1323，將其右移一位循環變異為3132，并嵌入原位置得到子染色體。

3 考慮獎懲的加權灰靶決策方法

車間調度多目標優化研究中，一般僅給出優化方案的Pareto 集，但是未給出決策方法，本節針對這一問題展開研究。

3.1 考慮獎懲的決策矩陣

將由K個可選方案組成的集合記為{Sk}，k=1,2,···,K，可選方案Sk對第j個優化目標的函數值記為yk j，則由yk j構成了效用矩陣Y。

為了統一標準，在做決策時需對效用矩陣進行歸一化處理。當前研究中一般將效用矩陣Y歸一化為0～1 間的實數[15-16]，但是這是一種只獎不懲的處理方法，導致決策的不合理性。針對這一問題，本節設計了獎懲算子，當效用值yk j好于均值時，歸一化為[0,1] 間實數；當效用值yk j差于均值時，歸一化為[-1,0]間實數。實施獎懲方法為

式中：rk j∈[-1,1]為決策因子；yˉj為效用矩陣Y第j列元素的均值。

由決策因子rk j構成了考慮獎懲的決策矩陣R：

3.2 基于靶心距的決策方法

式中： εk為方案rk與靶心的距離（簡稱靶心距）；wj為指標權值，j∈[1,J]。計算各可選方案的靶心距，靶心距越小說明調度方案越優。

式（11）中權值一般依據專家經驗給出，但是這種方法的主觀性太強。本文基于信息熵計算各指標權值，賦權思路為：當指標的信息熵較小時，說明該指標的規律性越強，則在決策中的權重越大；當指標的信息熵較大時，說明該指標的規律性越弱，則在決策中的權重越小。則優化目標j的熵權值為

式中：pk j為第k個可選方案中第j個指標的占比；ej為第j個指標的信息熵。

將式（12）計算得到的熵權值代入到式（11）中計算靶心距，靶心距最小的調度方案為最優調度方案。

4 實驗與分析

4.1 實驗設置

以合作單位某沖壓車間的生產任務為例，對本文的調度和決策方法進行驗證。該沖壓車間中布置了8 臺沖壓機床，承擔了8 個工件共28 道工序的生產任務，各工序的可用機床及模糊生產時間見表1。

表1 可用機床及模糊加工時間min

4.2 結果對比與分析

針對4.1 節的柔性沖壓車間多目標生產調度問題，同時使用標準NSGA-II 算法、鄰域動態選擇NSGA-II 算法、混沌映射NSGA-II 算法[17]、雙層遺傳算法[18]進行調度優化。后兩個算法參數設置同原文一致，前兩個算法參數設置為：種群規模為40、最大迭代次數為300、交叉概率0.5、變異概率0.1。以上各算法搜索的Pareto 前沿解分布如圖4 所示。

圖4 Pareto 解集分布

由圖4 可以直觀看出，鄰域動態選擇NSGA-II算法搜索的Pareto 前沿解相對于其他Pareto 解集處于支配地位，即鄰域動態選擇NSGA-II 算法的優化結果更好。為了更加有力地比較各Pareto 解集的優劣性，計算解集的C測度。

C測度又稱為集覆蓋測度，假設存在2 個Pareto 解集A 和B，則C(A,B) 表示集合B 被集合A 所支配解的占比：

式中：num{}為計數函數；a?b表示解a支配b。

將鄰域動態選擇NSGA-II 算法、混沌映射NSGA-II 算法、雙層遺傳算法、標準NSGA-II 算法搜索的Pareto 解集分別記為集合A、B、C、D。Pareto 解集的C測度值見表2。

表2 C 測度值

由表2 可以看出，C(A,B)>C(B,A)、C(A,C)>C(C,A)、C(A,D)>C(D,A)，這意味著解集A 相對于解集B、C、D 具有支配地位，因此鄰域動態選擇NSGAII 算法的優化算法好于另外3 種算法。這是因為該算法在選擇染色體時，考慮了鄰域范圍內染色體分布，且使用了一種動態刪除和選擇方法，較好地維持了染色體多樣性，因此算法的優化能力好于其他算法。

4.3 決策結果與最優調度方案

從鄰域動態選擇NSGA-II 算法優化的Pareto 解集中，基于考慮獎懲的加權灰靶決策方法選擇最優染色體，計算的熵權值為w=(0.400,0.333,0.267)，靶心為rbest={0.8134,0.9326,0.7318}。根據靶心距得到的最優染色體見表3。

表3 最優染色體

將決策得到的最優染色體進行解碼，得到最優調度方案如圖5 所示。

圖5 最優調度方案

分析圖5 可知：①圖中調度方案考慮了加工時間不確定性，符合本文的研究背景和研究立意；②圖5 給出的調度方案滿足工序加工的時間約束、邏輯約束等，是一種可行的調度方案。結合圖4 和圖5可知，本文提出的柔性車間多目標調度和決策方法是有效的，且具有一定的優越性。

5 結語

本文針對加工時間模糊條件下的車間生產調度問題，基于模糊集理論建立了調度優化模型，提出了基于鄰域動態選擇NSGA-II 算法的求解方法；針對最優方案選擇問題，提出了獎懲灰靶決策方法。經驗證得出以下結論：

（1）動態鄰域選擇NSGA-II 算法的優化能力更強，其搜索的Pareto 解集相較于對比算法處于支配地位。

（2）獎懲灰靶決策方法能夠從可行解集中選擇出信息熵意義下的最優解，是一種有效的決策方法。