考慮生產(chǎn)過程能耗的多目標綠色作業(yè)車間調度問題研究

喬東平，柏文通，王雅靜，文笑雨

（1.鄭州輕工業(yè)大學機電工程學院，河南 鄭州 450002；2.河南省機械裝備智能制造重點實驗室，河南 鄭州 450002）

1 引言

十四五規(guī)劃期間，綠色智能制造儼然成為綜合考慮經(jīng)濟效益和資源消耗的必經(jīng)之路，使得綠色車間調度問題的研究受到極大關注[1]。由于車間加工訂單不科學的排程，導致機床長時間處于非加工運行狀態(tài)，降低了車間制造過程的資源利用率，存在較大程度的能源浪費[2]。因此，對綠色作業(yè)車間調度問題的研究具有重要意義。對于綠色作業(yè)車間調度問題，目前國內外學者已經(jīng)做了大量的研究。文獻[3]等建立了多目標綠色車間調度模型，并設計一種改進NSGA?Ⅱ算法實現(xiàn)對完工時間、碳排放和成本三者的集成優(yōu)化。文獻[4]構建了以完工時間、機器負載、運行成本為目標的車間調度模型，并提出基于免疫平衡的改進NSGA?Ⅱ算法對其進行求解。文獻[5]主要考慮到可控操作時間對調度方案的影響，構建了以完工時間和能源消耗為目標的車間調度模型。文獻[6]提出了以車間制造過程中的總碳排放量和總完工時間最小化為優(yōu)化目標的車間布局和調度集成優(yōu)化模型。文獻[7]研究了作業(yè)車間調度完工時間、總碳排放量和總拖期最低問題并設計了NS?GA?Ⅱ算法對該問題進行求解。文獻[8]在加工工件過程中考慮機器之間的運輸時間因素，建立了完工時間和能源消耗的雙目標調度優(yōu)化模型。文獻[9]考慮工件的運輸時間對工件制造周期的影響，構建車間調度模型，反映出實際生產(chǎn)制造過程中的狀況。文獻[10]構建了與序列相關的多目標作業(yè)車間調度問題模型，來提高生產(chǎn)效率降低能源消耗。

上述文獻中，國內外學者基于傳統(tǒng)車間調度問題，考慮綠色制造因素，構建了雙目標、多目標車間調度模型，深入分析機器加工過程中能源消耗對環(huán)境的影響。但是上述研究中并未考慮機器預加熱能耗、工件的運輸時間以及工件的運輸能耗等因素，得到的調度結果并不能真實反映車間實際生產(chǎn)制造情況。以作業(yè)車間調度問題為研究對象，考慮機器的預加熱能耗、工件運輸時間、工件運輸能耗以及各工件完工的滿意程度等因素，構建以完工時間、能源消耗和生產(chǎn)成本為目標的車間調度優(yōu)化模型，并且提出一種改進的NSGA?Ⅱ算法對其進行求解。

2 考慮多種能耗的多目標綠色作業(yè)車間調度模型

2.1 問題描述

多目標作業(yè)車間調度問題可以描述為：n個工件集J=｛J1，J2，…，Jn｝，在m臺機器上M=｛M1，M2，…，Mk，…，Mm｝上加工。每一道工序由對應的一臺機器進行加工，各個機器之間的運輸時間是已知的。針對該問題的假設條件如下：

（1）機器在零時刻被分配工件時，需要提前對機器進行預加熱，只將預加熱能耗計入該機器加工的總能耗；

（2）機器在零時刻沒有被分配工件時，需要合理考慮機器預加熱時間；

（3）機器的加工功率、空載功率、預加熱和低壓待機功率保持不變；

（4）所有工件的第一道工序不計算運輸時間，所有工件的最后一道工序加工完成后不再運輸。

此外，在加工過程中還需要滿足以下約束條件：

（1）同一臺機器在同一時間只能加工一個工件，每個工件的加工，一旦開始不能中斷；

（2）所有工序按照順序進行加工，每一道工序加工完畢后立即運輸?shù)较碌拦ば虻募庸さ臋C器上，下一道工序才能開始加工；

（3）同一工件的相鄰兩道工序存在運輸時間，機器之間的運輸時間是已知的。

為了描述方便，對相關符號進行定義，如表1所示。

表1 相關符號含義Tab.1 Definition of Related Symbols

2.2 模型建立

從文獻［11］可知，機器在制造過程中存在多種運轉狀態(tài)，例如，機器啟∕停、機器預加熱、機器低壓低頻待機、機器加工以及機器空載等狀態(tài)，如圖1所示。故本章考慮了機器多種運轉狀態(tài)下的能耗和工件完工時間的滿意程度等因素，構建考慮生產(chǎn)過程能耗的多目標綠色作業(yè)車間調度模型。其目標函數(shù)及其約束條件，如圖1所示。

圖1 設備狀態(tài)?能耗曲線Fig.1 Equipment Status Energy Consumption Curve

空載能耗Eidle：該能耗是指該臺機器處于空轉狀態(tài)所消耗的不必要的能量。

生產(chǎn)輔助能耗Epf：該能耗是指機器在生產(chǎn)制造過程中用于燈光照明、通風、制暖等輔助設備消耗的能量。

為了降低工件完工時間與交貨期之間的偏離程度，引入工件的完工時間滿意度[12]，以工件的完工時間滿意度大于零為前提，構建了分段拖期懲罰成本函數(shù)，由此反映出因拖期而產(chǎn)生的拖期成本的變化趨勢以及工件完工時間的滿意度，分段拖期懲罰成本函數(shù)，如圖2所示。

圖2 分段拖期懲罰成本函數(shù)Fig.2 Penalty Cost Function of Piecewise Tardiness

3 改進NSGA?Ⅱ算法求解多目標綠色作業(yè)車間調度問題

針對NSGA?Ⅱ算法在求解多目標作業(yè)車間調度問題時，難以平衡空間中非支配解分布的均勻性以及解的收斂性等問題［13］，提出一種改進的NSGA?Ⅱ算法（Improve NSGA?ⅡAlgorithm，INSGA?Ⅱ），在父代、子代種群合并的時，引入鄰域排擠機制以及改進擁擠距離計算方法，提高算法的收斂性，并設計相應的鄰域搜索機制來增強算法的局部搜索能力，INSGA?Ⅱ算法流程，如圖3所示。

圖3 改進NSGA?Ⅱ算法流程圖Fig.3 Flow Chart of Improved NSGA?ⅡAlgorithm

INSGA?Ⅱ多目標優(yōu)化算法的具體操作流程如下：

（1）設置NSGA?Ⅱ算法的參數(shù)：算法迭代次數(shù)Gmax；交叉概率：Pc；變異概率Pm；懲罰拖期成本W(wǎng)i1，Wi2。

（2）利用隨機策略生成初始種群，并采用貪婪式插入解碼方法評價種群個體的適應度值：f1、f2和f3。

（3）對種群執(zhí)行選擇、交叉、變異操作、鄰域結構搜索，生成子代種群。

（4）父、子代種群合并成新的種群，對新種群執(zhí)行鄰域排擠機制。

（5）對新種群執(zhí)行改進選擇策略，確定每一非支配等級中個體保留的數(shù)量，采用改進的擁擠距離計算方法篩選同一非支配等級中需要保留的個體。

（6）生成新的父代種群，并進行父代種群進行非支配解排序，更新外部記憶庫解集，將更新后的非支配等級為1的Pareto解集與外部記憶庫中的解集進行合并，然后進行非支配等級排序，更新外部記憶庫中的個體。

（7）Gmax=Ggen+1。

（8）判斷迭代次數(shù)是否達到最大迭代次數(shù)；如果達到最大迭代次數(shù)，執(zhí)行（9）；否則，跳轉（4）。

（9）輸出外部記憶庫中的Pareto解集。

3.1 編碼和解碼

采用GEN[14]中提出的基于工序的編碼方式，即染色體由n×m個工序組成，染色體中所有的工序采用對應的工件號來表示，染色體中工件號出現(xiàn)的次數(shù)表示該工件的第幾道工序。為了理解方便給出具體的作業(yè)車間調度問題案例，如表2、表3所示。隨機生成一條染色體[1 2 3 4 5 6 1 2 3 5 4 6 1 6 5 4 3 2 1 2 3 6 5 4 1 2 3 4 5 6 6 5 1 2 3 4]，其中，數(shù)字代表工件的序號，從左到右同一數(shù)字出現(xiàn)的次數(shù)代表該工件的第幾道工序。

表2 工件的加工時間/交貨期Tab.2 Processing Time/Delivery Time of Job

表3 機器之間的運輸時間Tab.3 Transport Time Between Machines

采用SALIDO[15]中提出的插入式貪婪式解碼算法，即為主動調度方法。從左到右依次讀取染色體上的工序排列順序，如果工序Oij是機器k分配的第一道工序，則機器k直接加工工序Oij；如果機器k已經(jīng)加工過其他工件，則依次檢查該機器第一個加工工件之前的空閑時間和各個已加工工件之間空閑時間段，將工序Oij插入到滿足工序先后順序以及同一工件前后工序的工件運輸時間等約束條件的空閑時間段。對染色體[1 2 3 4 5 6 1 2 3 5 4 6 1 6 5 4 3 2 1 2 3 6 5 4 1 2 3 4 5 6 6 5 1 2 3 4]進行解碼獲得的甘特圖，如圖4所示。從解碼結果可知，加工能耗：57.33kW；空載能耗：4.58kW；工件的運輸能耗：150.92kW；總機器預加熱能耗：12.57kW；總低壓低頻待機能耗：1.76kW；機器啟停能耗：0.75kW；生產(chǎn)輔助能耗：70.8kW。

圖4 基于工序解碼的甘特圖Fig.4 Gantt Chart Based on Process Decoding

3.2 選擇策略的改進

選擇操作的本質是促使種群中優(yōu)良個體得以保留，進而加快算法對最優(yōu)解或近似最優(yōu)解的探索[16]，快速非支配排序方法的選擇能夠促使種群中優(yōu)良個體得以保留，進而加快算法對Pareto前沿解的搜索。所以，選用快速非支配排序的方法選擇非支配等級越低的個體被選中的概率越大，同一非支配等級的個體擁擠度較大者優(yōu)先被選擇。

對種群進行選擇、交叉變異操作之后，將父、子代種群合并選擇出下一代種群，為增加種群的多樣性，提出一種改進的快速非支配排序方法的選擇策略。改進的快速非支配排序選擇不僅考慮各個非支配等級中選擇個體的數(shù)量，而且還考慮到隨著迭代次數(shù)的增加各個非支配等級的權重也隨之變化，所以各非支配等級的權重不宜過大。各非支配等級中選取的個體數(shù)量的公式如下。式中：ni—非支配等級i中被選中個體的數(shù)量；Fi—非支配等級i中所有個體的數(shù)量；ri—各個非支配等級選擇參數(shù)；G—種群最大迭代次數(shù)；g—當前種群迭代次數(shù)。

3.3 鄰域排擠機制

針對NSGA?Ⅱ算法在求解多目標問題優(yōu)化時，無法平衡種群個體之間的密集程度，造成最終的Pareto 最優(yōu)解集分布不均勻，針對于上述問題，引入個體鄰域排擠機制[17]，其原理如下：按照非支配等級的大小順序依次進行執(zhí)行鄰域排擠機制；從最低的非支配等級中隨機挑取一個個體，計算該個體的鄰域半徑，依次計算該個體與其他個體的擁擠距離，對于擁擠距離小于鄰域半徑的個體進行淘汰。從非支配等級低到非支配等級高篩選個體，較大概率保留精英個體并兼顧了算法的多樣性。鄰域半徑公式如下，其中：N表示該種群的規(guī)模。

3.4 擁擠距離計算方式的改進

3.5 交叉與變異

采用文獻[18]所提出的交叉方法，提高算法的全局搜索能力。變異操作則可以有效維持種群的多樣性并防止算法陷入局部最優(yōu)解，故選用隨機位置[19]交換完成變異操作。

3.6 鄰域搜索

鄰域搜索算法[20]主要利用鄰域結構搜索思想，通過搜索多個鄰域結構，提高算法的局部搜索能力。采用的鄰域搜索如下：

鄰域結構N1：在工序向量中隨機選擇兩個不相等工序進行交換；

鄰域結構N2：在工序向量中隨機挑選一個工序片段進行工序順序倒置；

鄰域結構N3：在工序向量中隨機挑選一個工序片段，并將該工序片段隨機插入除該工序片段的其他工序位置；

鄰域搜索的具體步驟如下：

（1）根據(jù)概率從優(yōu)秀個體中選擇個體作為初始解X；

（2）由鄰域結構N1、N2、N3和N4生成新解XN1、XN2、XN3和XN4；

（3）對解X、XN1、XN2、XN3和XN4進行非支配解排序；

（4）判斷新解XN1、XN2、XN3和XN4中是否存在支配初始解X，如果支配，替換初始解X，否則，保留初始解X；

（5）鄰域搜索結束。

4 案例分析

采用C++編程語言，運行環(huán)境為Windows 7，計算機CPU 主頻3.30GHz，內存4.00GB，64位操作系統(tǒng)的筆記本上運行。采用上述改進NSGA?Ⅱ算法，其相關參數(shù)設置如下：種群規(guī)模大小為300；交叉概率為0.8；變異概率為0.1；外部記憶庫容量為100；拖期懲罰成本函數(shù)為Wi1=0.568，Wi2=1.476；傳輸功率Ptran=2.156；生產(chǎn)輔助能耗PF=1.142；最大迭代次數(shù)為100；工件的運輸時間時是該工件所有工序中最大的加工時間的（5～15）%；這里β取值為1.4，γ取值為1.9；工件的交貨期中的α取值范圍為（1.3～1.7）。

4.1 基準案例測試

為了比較出INSGA?Ⅱ算法具有較好的分布性和收斂性，采取了文獻[21]所提出的評價方法，來反映算法在進化過程中解的分布性，SP值越小，說明解分布越均勻。另外采用世代距離GD[22]作為收斂性作為評價指標，來衡量Pareto最優(yōu)解對理想最優(yōu)解的逼近程度，GD的數(shù)值越小，解的收斂性越強。

從表4中的數(shù)據(jù)可以看出，傳統(tǒng)NSGA?Ⅱ算法獲取的Pareto最優(yōu)解數(shù)量最多，程序運行時間最多，INSGA?Ⅱ算法獲得的Pa?reto最優(yōu)解集無論從解集的分布性還是解的收斂性都要優(yōu)于NS?GA?Ⅱ算法，這表明INSGA?Ⅱ算法具有更強的全局搜索能力、較好的種群分布性以及收斂性。

表4 兩種算法獲得的Pareto解的數(shù)目Fig.4 The Number of Pareto Solutions Obtained by the Two Algorithm

INSGA?Ⅱ和NSGA?Ⅱ算法求解Abz5基準案例的Pareto解集分布圖，如圖5所示。從圖5中可以看出，NSGA?Ⅱ算法求解的Pareto解分布集中在兩個區(qū)域，解的均勻分布性較差且都處于坐標軸的最上方，INSGA?Ⅱ算法獲得的Pareto解集最接近坐標軸中心處且解集分布比較均勻，大部分INSGA?Ⅱ算法獲得的解是能夠支配NSGA?Ⅱ算法的解。這表明INSGA?Ⅱ算法具有更好的收斂性和全局搜索能力。所以，在該組基準案例的求解中，IN?SGA?Ⅱ算法的性能優(yōu)于NSGA?Ⅱ算法。

圖5 Abz5 Pareto解集分布對比圖Fig.5 Abz5 Pareto Solution Set Distribution Comparison Chart

從五組基準案例測試結果可以看出，在求解Abz5、Abz6、Abz7、Abz8、Abz9基準案例時，INSGA?Ⅱ算法獲得的Pareto解集都具有明顯的優(yōu)勢，INSGA?Ⅱ算法體現(xiàn)出更強的全局搜索能力和局部搜索能力。從Pareto解集中最優(yōu)解的數(shù)量和獲得的非支配解對真實Pareto最優(yōu)解的逼近程度等方面來說，INSGA?Ⅱ算法不僅能夠獲得分布更均勻最優(yōu)Pareto解，而且INSGA?Ⅱ算法Pareto解集更靠近坐標軸中心處，反映出改進的快速非支配排序方法的選擇策略結合鄰域排擠機制和擁擠距離計算方式的改進是可行的。從Pareto解集的分布性SP和世代距離GD的數(shù)值可以看出，INSGA?Ⅱ算法的Pareto解集的SP和GD數(shù)值更小，這表明INSGA?Ⅱ算法具有更好的分布性、收斂性以及穩(wěn)定性。綜上所述，INSGA?Ⅱ算法在求解多目標作業(yè)車間調度問題時，具有更強的全局搜索能力和更好的求解效率。同時也給出了INSGA?Ⅱ算法求解基準案例Abz5的甘特圖，如圖6所示。

圖6 Abz5基準案例的甘特圖Fig.6 Gantt Chart of Abz5 Benchmark Case

4.2 工程案例測試

以某機械加工廠中的四柱液壓機為研究對象，該離散制造車間主要有七種機床，即數(shù)控銑床（M1）、鉆床（M2）、鏜床（M3）、磨床（M4）、鉗床（M5）、車床（M6）和特種加工機床（M7），對于體積較大的零件其原材料采用鑄造件形式，其中，各個零件的加工時間已經(jīng)包含了對加工零件時的準備時間。四柱液壓機各個零件的工藝信息，如表5、表6所示。其中，—表示工件中并無相關工序。

表5 工件的加工機器、加工時間Tab.5 Job Processing Machine、Processing Time

表6 機器的加工參數(shù)Tab.6 Processing Parameters of Each Machine

在求解該工程實例的7個零件的加工工藝路線中，INSGA?Ⅱ算法獲得8 個Pareto 前沿解，獲得完工時間f1最小值為（804，1052，1070.74）、能耗f2最小值為（810，1026.56，1718.99）、生產(chǎn)成本f3最小值為（823，1055.07，755.477），如表7所示。其中，Pareto解集的分布性SP=0.800021、收斂性GD=0.108582，并且給出INS?GA?Ⅱ算法求解四柱液壓機的甘特圖，如圖7所示。

表7 INSGA-Ⅱ算法獲得的Pareto解集Tab.7 Pareto Solution Set Obtained by INSGA-ⅡAlgorithm

INSGA?Ⅱ算法求解工程案例的甘特圖，如圖7所示?？梢悦黠@看出機器啟∕停策略、工件運輸時間在實際生產(chǎn)過程對調度方案存在較大的影響，通過啟停策略可以有效地降低生產(chǎn)過程中能源消耗。同時可以看出帶有機器預加熱、機器啟停、低壓低頻待機、工件的運輸時間的調度問題更復雜，更加符合實際生產(chǎn)制造過程，使多目標作業(yè)車間調度問題更加滿足實際需求。

圖7 INSGA?Ⅱ算法求解工程案例甘特圖Fig.7 Solving Gantt Chart of Engineering Case by INSGA?ⅡAlgorithm

5 結論

實際生產(chǎn)過程中，需要對機器進行預加熱處理，并且機器在加工過程中多種運轉狀態(tài)不斷轉換，為了能夠更有效的指導實際生產(chǎn)?？紤]了機器預加熱能耗、機器啟∕停能耗、機器低壓低頻待機、工件的運輸能耗以及工件完工的滿意度等約束條件同時存在的情況下，構建以完工時間、能源消耗和生產(chǎn)成本為目標的作業(yè)車間調度問題模型，并提出改進NSGA?Ⅱ算法進行求解，利用五組基準案例和工程案例進行測試，驗證了所構建模型和改進算法是可行性和有效性，能夠更有效的指導實際車間生產(chǎn)制造。