加工時間模糊車間多目標(biāo)調(diào)度與獎懲灰靶決策＊

韓文穎 趙明君 春 蘭 巴特爾

（①內(nèi)蒙古工業(yè)大學(xué)工程訓(xùn)練教學(xué)部，內(nèi)蒙古 呼和浩特 010051；②山西省電力公司超高壓變電分公司，山西 太原 030000）

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

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

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

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

1 基于模糊集的車間調(diào)度建模

1.1 問題描述

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

在本文研究中，柔性車間生產(chǎn)調(diào)度的優(yōu)化目標(biāo)為

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

（2）機(jī)床模糊總負(fù)載最小。

（3）瓶頸機(jī)床模糊負(fù)載最小。

柔性車間生產(chǎn)調(diào)度的任務(wù)為

（1）為各工序的生產(chǎn)順序進(jìn)行排序。

（2）為各工序安排加工機(jī)床。

根據(jù)車間生產(chǎn)實際，對柔性車間多目標(biāo)調(diào)度問題作以下假設(shè)和設(shè)定：

（1）在初始時刻，機(jī)床為完好狀態(tài)。

（2）工序加工過程為連續(xù)不中斷的，即不考慮機(jī)床故障等突發(fā)情況。

（3）不設(shè)置工件的加工優(yōu)先級，即所有工件的加工優(yōu)先級一致。

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

1.2 模糊數(shù)與去模糊化

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

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

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

1.3 模糊調(diào)度模型

根據(jù)設(shè)定的3 個調(diào)度優(yōu)化目標(biāo)，分別建立優(yōu)化目標(biāo)模型。

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

車間完工時間應(yīng)以最后一道工序完工時間為準(zhǔn)，則車間模糊完工時間最小的目標(biāo)函數(shù)為

式中：f1為車間模糊完工時間最小的目標(biāo)函數(shù)；為工序Onl的模糊完工時間。

（2）機(jī)床模糊總負(fù)載最小

首先設(shè)置一個標(biāo)識參數(shù)xnlm，并定義

則機(jī)床模糊總負(fù)載最小的目標(biāo)函數(shù)為

式中：f2為機(jī)床模糊總負(fù)載最小目標(biāo)函數(shù)；為工序Onl在機(jī)床Cm上的模糊加工時間。

（3）瓶頸機(jī)床模糊負(fù)載最小

瓶頸機(jī)床是指負(fù)載最大的機(jī)床，設(shè)置瓶頸機(jī)床負(fù)載最小這一目標(biāo)，本質(zhì)是以負(fù)載均衡為目標(biāo)，則：

式中：f3為瓶頸機(jī)床模糊負(fù)載最小目標(biāo)函數(shù)。

柔性車間調(diào)度在優(yōu)化過程中需滿足以下約束：

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

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

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

（4）加工過程連續(xù)不間斷。

上述約束條件的對應(yīng)公式描述為

2 鄰域動態(tài)選擇NSGA-II 調(diào)度算法

針對柔性車間多目標(biāo)調(diào)度優(yōu)化問題，本節(jié)提出了基于鄰域動態(tài)選擇NSGA-II 算法的調(diào)度方法。

2.1 鄰域動態(tài)選擇NSGA-II 算法

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

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

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

標(biāo)準(zhǔn)NSGA-II 算法的選擇方法問題在于：①在最后一層非支配層選擇時，是一種靜態(tài)選擇方法，選擇過程中沒有動態(tài)更新?lián)頂D度，導(dǎo)致染色體分布不均勻，即染色體多樣性較差；②擁擠度計算僅以本層染色體為依據(jù)，忽略了鄰域內(nèi)的分布情況，是一種片面的衡量標(biāo)準(zhǔn)。

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

式中：di為鄰域范圍的擁擠度；Pnei為鄰域內(nèi)染色體數(shù)量； ?nei為染色體xi的鄰域；xq為鄰域內(nèi)染色體；為染色體xq在第j個目標(biāo)上的取值。

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

2.2 基于改進(jìn)NSGA-II 算法的調(diào)度優(yōu)化方法

基于鄰域動態(tài)選擇NSGA-II 算法的車間調(diào)度優(yōu)化方法主要包括編碼、交叉、變異和選擇等關(guān)鍵步驟，其中選擇方法在2.1 節(jié)已經(jīng)明確，在此僅對編碼、交叉和變異進(jìn)行分析和改進(jìn)。

（1）編碼。根據(jù)車間調(diào)度任務(wù)，將染色體編碼為雙鏈形式，一條為工序選擇，對應(yīng)工序的生產(chǎn)順序；另一條為機(jī)床分配，對應(yīng)各工序的加工機(jī)床。以3 個工件和3 個機(jī)床為例，某一染色體編碼如圖1所示。

圖1 染色體編碼

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

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

圖2 交叉操作

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

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

圖3 右移循環(huán)變異

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

3 考慮獎懲的加權(quán)灰靶決策方法

車間調(diào)度多目標(biāo)優(yōu)化研究中，一般僅給出優(yōu)化方案的Pareto 集，但是未給出決策方法，本節(jié)針對這一問題展開研究。

3.1 考慮獎懲的決策矩陣

將由K個可選方案組成的集合記為{Sk}，k=1,2,···,K，可選方案Sk對第j個優(yōu)化目標(biāo)的函數(shù)值記為yk j，則由yk j構(gòu)成了效用矩陣Y。

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

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

由決策因子rk j構(gòu)成了考慮獎懲的決策矩陣R：

3.2 基于靶心距的決策方法

式中： εk為方案rk與靶心的距離（簡稱靶心距）；wj為指標(biāo)權(quán)值，j∈[1,J]。計算各可選方案的靶心距，靶心距越小說明調(diào)度方案越優(yōu)。

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

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

將式（12）計算得到的熵權(quán)值代入到式（11）中計算靶心距，靶心距最小的調(diào)度方案為最優(yōu)調(diào)度方案。

4 實驗與分析

4.1 實驗設(shè)置

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

表1 可用機(jī)床及模糊加工時間min

4.2 結(jié)果對比與分析

針對4.1 節(jié)的柔性沖壓車間多目標(biāo)生產(chǎn)調(diào)度問題，同時使用標(biāo)準(zhǔn)NSGA-II 算法、鄰域動態(tài)選擇NSGA-II 算法、混沌映射NSGA-II 算法[17]、雙層遺傳算法[18]進(jìn)行調(diào)度優(yōu)化。后兩個算法參數(shù)設(shè)置同原文一致，前兩個算法參數(shù)設(shè)置為：種群規(guī)模為40、最大迭代次數(shù)為300、交叉概率0.5、變異概率0.1。以上各算法搜索的Pareto 前沿解分布如圖4 所示。

圖4 Pareto 解集分布

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

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

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

將鄰域動態(tài)選擇NSGA-II 算法、混沌映射NSGA-II 算法、雙層遺傳算法、標(biāo)準(zhǔn)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 具有支配地位，因此鄰域動態(tài)選擇NSGAII 算法的優(yōu)化算法好于另外3 種算法。這是因為該算法在選擇染色體時，考慮了鄰域范圍內(nèi)染色體分布，且使用了一種動態(tài)刪除和選擇方法，較好地維持了染色體多樣性，因此算法的優(yōu)化能力好于其他算法。

4.3 決策結(jié)果與最優(yōu)調(diào)度方案

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

表3 最優(yōu)染色體

將決策得到的最優(yōu)染色體進(jìn)行解碼，得到最優(yōu)調(diào)度方案如圖5 所示。

圖5 最優(yōu)調(diào)度方案

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

5 結(jié)語

本文針對加工時間模糊條件下的車間生產(chǎn)調(diào)度問題，基于模糊集理論建立了調(diào)度優(yōu)化模型，提出了基于鄰域動態(tài)選擇NSGA-II 算法的求解方法；針對最優(yōu)方案選擇問題，提出了獎懲灰靶決策方法。經(jīng)驗證得出以下結(jié)論：

（1）動態(tài)鄰域選擇NSGA-II 算法的優(yōu)化能力更強(qiáng)，其搜索的Pareto 解集相較于對比算法處于支配地位。

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