基于改進NSGA-Ⅲ的低碳柔性作業(yè)車間調(diào)度優(yōu)化

摘 要：隨著環(huán)境保護意識的提高和低碳經(jīng)濟蓬勃發(fā)展，碳排放成本逐漸成為企業(yè)決策中必須考慮的重要因素。為實現(xiàn)碳排放成本、完工時間、拖期時長和機器負荷４個優(yōu)化目標，本文建立了碳排放成本的高維目標柔性車間調(diào)度優(yōu)化模型，并根據(jù)模型特點設計了一種基于生物激素調(diào)節(jié)機理的改進NSGA-Ⅲ算法。采用MATLAB軟件對實際生產(chǎn)數(shù)據(jù)進行模擬仿真，證明所提出的優(yōu)化方法可在保證完工時間和總拖期時間不受影響的情況下，控制碳排放成本、提高設備效率，同時滿足工件加工工序的要求。

關(guān)鍵詞：碳排放成本；遺傳算法；高維目標優(yōu)化；柔性流水車間調(diào)度；低碳經(jīng)濟

中圖分類號：TP 18" " " 文獻標志碼：A

隨著柔性作業(yè)車間調(diào)度問題復雜性增加，采用多目標智能優(yōu)化算法求解成為主流。范雅男[1]等人將改進粒子群優(yōu)化算法應用到柔性流水車間調(diào)度問題中。WU[2]等人采用啟發(fā)式算法優(yōu)化帶設備開關(guān)機與調(diào)速2種節(jié)能手段的設備能耗模型。LIU等[3]提出了改進合作粒子群算法，該算法求解規(guī)模比較大的生產(chǎn)調(diào)度問題的收斂速度更快，質(zhì)量更高。楊冬婧[4]等人以總延遲時間最小化為目標，將作業(yè)車間能耗約束轉(zhuǎn)化為最小總能耗，建立車間調(diào)度模型，并設計了一種新型蛙跳算法。李丹[5]等人在遺傳算法中引入一種基于個體斜率的改進精英選擇方法，以求解高維目標柔性作業(yè)車間調(diào)度問題。宋佳容[6]等人使用3種鄰域規(guī)則改進的蟻群算法，求解以最大加工收益和最小碳排放總量為目標的柔性車間調(diào)度問題。盡管上述研究證明優(yōu)化作業(yè)車間調(diào)度與綠色生產(chǎn)具有重要聯(lián)系，但上述研究較多關(guān)注優(yōu)化車間能源消耗與作業(yè)完工時間，如何進一步約束車間碳排放成本仍值得研究。

本文探討碳成本約束下，生產(chǎn)車間總碳排放成本在生產(chǎn)調(diào)度優(yōu)化中的應用前景和挑戰(zhàn)，以進行最佳碳成本控制和資源配置。

1 短期碳排放成本模型

碳排放總成本由預防成本、鑒定成本、有形損失成本和無形損失成本組成。碳排放成本和生產(chǎn)經(jīng)濟效益間相互影響。鑒于碳排放成本的存在，生產(chǎn)企業(yè)會更關(guān)注環(huán)境保護和資源利用效率，并應用清潔、高效的生產(chǎn)技術(shù)來降低碳排放。低碳勢必會提升企業(yè)的競爭力，但也會增加運營成本。生產(chǎn)企業(yè)通常采取節(jié)能減排、資源循環(huán)利用、優(yōu)化產(chǎn)品設計和使用先進管理辦法或環(huán)保設備等措施應對碳排放量和碳排放成本的增加。

根據(jù)文獻[7]中提出的短期碳排放成本決策模型可知，二氧化碳排放總成本為一條“U”形曲線，曲線上存在碳排放成本的最小極值點，該點上的碳排放量即經(jīng)濟碳排放量。在碳排放成本的最優(yōu)點上，生產(chǎn)企業(yè)能夠?qū)崿F(xiàn)碳排放量和成本間的最佳平衡。因此，尋找并實現(xiàn)經(jīng)濟碳排放量是目前作業(yè)車間調(diào)度優(yōu)化的重要目標之一。

2 作業(yè)車間調(diào)度模型

2.1 問題描述

本文研究的高維目標低碳柔性車間調(diào)度問題是將車間生產(chǎn)二氧化碳排放導致的成本、最大完工時間、總拖期時間以及加工設備總負載為目標函數(shù)的綜合優(yōu)化問題，可描述為共有n個需要依次經(jīng)過不同s道工序才能完成的待加工作業(yè)，并且這些作業(yè)的工序可在m臺機器中的多臺上進行；不同工序和機器組合的加工時間是已知的且有差異（徐宜剛、陳勇和王宸等，《改進NSGA-III求解高維多目標綠色柔性作業(yè)車間調(diào)度問題》）。顯然不同組合方案下的機器總負荷、最大完工時間、碳排放總量和碳排放成本有明顯差異。低碳柔性車間調(diào)度優(yōu)化的目標是在保證工件工序順序進行的情況下，每個工件能夠合理分配加工機器，以期找到經(jīng)濟碳排放量，使碳排放成本最低，同時將最大完工時間最小化，使總拖期最短且機器總負荷最低。該問題中有如下8個限制條件：假設1，所有作業(yè)是互相獨立的，不存在先后順序；假設2，任意作業(yè)均需要經(jīng)過完整工序；假設3，任意工件的任意工序在同一時間只能由一個機器執(zhí)行；假設4，一個工序可以在多臺機器上處理；假設5，任意機器在同一時間只能執(zhí)行一個工件的一個工序；假設6，在操作過程中，各作業(yè)不能中斷或取消；假設7，所有作業(yè)加工的開始時間和交貨時間已知；假設8，任意作業(yè)中的任意工序在某臺機器上處理完轉(zhuǎn)向另一臺機器的時間已知。

2.2 優(yōu)化目標分析

目標函數(shù)一，最小作業(yè)車間能源碳排放成本。作業(yè)車間能源碳排放是指由生產(chǎn)車間消耗電能所產(chǎn)生的碳排放成本。生產(chǎn)車間能耗主要包括機器正常加工能耗、怠速空轉(zhuǎn)能耗、其他非調(diào)節(jié)性的固定能耗以及工件轉(zhuǎn)移產(chǎn)生的能耗。采用排放因子法核算碳排放量，由產(chǎn)生碳排放的活動數(shù)據(jù)乘以對應的排放因子（以及深層次因子）來計算排放，分別如公式（1）、公式（2）所示。

Cp=EF電能×E （1）

（2）

式中：Cp為i作業(yè)的j工序在機器k加工時生產(chǎn)車間能耗產(chǎn)生的碳排放量；E、EF電能分別為生產(chǎn)過程中的電能消耗總量和電網(wǎng)平均排放因子；Tijk為i作業(yè)的j工序在機器k上的加工時間；Xijk為決策變量，當作業(yè)i的j工序在機器k上加工時Xijk=1，否則Xijk=0；Ck為機器k的完工時間；Pk和pk分別為機器k加工功率和閑置功率；S為工件轉(zhuǎn)移次數(shù)；Pt工件轉(zhuǎn)移功耗；Ps為加工車間的非調(diào)節(jié)性固定工率。

作業(yè)車間生產(chǎn)碳排放成本總和如公式（3）所示。

C1=α×Cp （3）

式中：C1為碳排放成本；α為單位碳排放成本。

碳捕捉引起的企業(yè)有形損失成本如公式（4）所示。

C2=Cp×pc （4）

式中：C2為二氧化碳治理成本；pc為每單位二氧化碳的碳捕捉價格。

中國二氧化碳捕集利用與封存（CCUS）年度報告（2023）提到電力行業(yè)碳捕集成本為200元/t～600元/t。本文取中間值400元/t來計算碳捕捉成本。

有形損失成本，即碳或有成本為碳排放稅，如公式（5）所示。

C3=Cp×Tax （5）

式中：C3碳或有成本；Tax為單位二氧化碳排放的應征稅額。

預防成本和鑒定成本通常由生產(chǎn)企業(yè)根據(jù)實際經(jīng)營狀況自行決定，對調(diào)度優(yōu)劣不存在影響，因此將作業(yè)車間能源碳排放成本、二氧化碳治理成本和有形損失碳成本進行加總，即可得到本模型的目標函數(shù)一，作業(yè)車間二氧化碳排放成本最低，如公式（6）所示。

minf1=C1+C2+C3 （6）

目標函數(shù)二，最大作業(yè)完工時間最小。最大作業(yè)完工時間指的是從加工開始到加工完最后一個工件所花費的時間?？s短最大完工時間可以顯著提高車間的生產(chǎn)效率，最大完工時間越短代表車間生產(chǎn)效率越高，如公式（7）所示。

（7）

式中：Ti為作業(yè)i的完工時間。

目標函數(shù)三，延期時間最短。延期時間是指作業(yè)工序的實際完成時間超出預定的計劃時間。優(yōu)化總延期時間能幫助訂單式生產(chǎn)企業(yè)如期交貨，并減少產(chǎn)品的囤積現(xiàn)象，如公式（8）所示。

（8）

式中：Li為作業(yè)i的延期時間。

目標函數(shù)四，設備負荷最小。設備總負荷是所有作業(yè)完成后參與加工的設備的總工作時間。設備利用率越高，設備總負荷就越小。設備總負荷如公式（9）所示。

（9）

約束條件分別如公式（10）～公式（13）所示。其中，公式（10）表示任意一個作業(yè)均需要經(jīng)過s道完整工序才算完成；公式（11）表示任意作業(yè)的一道工序只能選定在一個機器上執(zhí)行；公式（12）表示一個工序只有在前面的工序處理完成后才能開始處理下一道工序；公式（13）表示任意機器在加工任意作業(yè)過程中時不能被中斷。

（10）

（11）

TSij+1-TCij≥0，i，j （12）

TSijk +Tijk =TCijk （13）

3 算法設計

3.1 編碼和解碼

本文采用了文獻[8]提出的基于工序排序和機器選擇的雙層個體編碼方式和貪婪解碼算法。

3.2 非支配排序

隨著目標函數(shù)增多，智能算法的求解效率會顯著降低，尋優(yōu)難度也會提升，使用Pareto支配[9]可以大幅提高算法運行效率。

3.3 基于激素調(diào)節(jié)機理的自適應因子

通常在遺傳算法種群進化的前期，較大的交叉概率、較小的變異概率有利于種群快速收斂，不易丟失較優(yōu)解；而在算法進化后期，會使交叉概率逐漸變小、變異概率逐漸增大，有助于搜索精細化和種群多樣化。但傳統(tǒng)遺傳算法的交叉概率和變異概率是固定的，并需要自行設置，參數(shù)的選擇會在一定程度上影響遺傳算法的最終優(yōu)化結(jié)果，但選擇合適的參數(shù)值較難，因此設置自適應交叉變異概率，使種群進化過程中的交叉概率由大變小、變異概率由小變大可解決上述問題。本文將內(nèi)分泌激素調(diào)節(jié)規(guī)律的上升和下降函數(shù)引入NSGA-Ⅲ算法，用于自適應調(diào)節(jié)交叉和變異概率。生物激素調(diào)節(jié)機理的上升規(guī)律函數(shù)Fup（G）、下降規(guī)律函數(shù)Fdown（G）都服從Hill函數(shù)規(guī)律，如公式（14）、公式（15）所示。

（14）

（15）

式中：G為函數(shù)自變量；D為閥值且Dgt;0；n為Hill系數(shù)且n≥1。

按照上述原理，交叉變異概率如公式（16）、公式（17）所示。

Pm=Pm0（α×Fup（G）+Sx0） （16）

Pc=Pc0（α×Fdown（G）+Sx0） （17）

式中：Pm、Pc分別為變異概率、交叉概率；Pc0、Pm0分別為初始變異、交叉概率；a為常量系數(shù)；Sx0為基礎分泌常數(shù)。

上述原理能使算法迭代過程的交叉概率逐漸變小、變異概率逐漸增大，保證算法在前期快速收斂，后期不容易丟失最優(yōu)解和陷入早熟。

3.4 算法流程

引入激素調(diào)節(jié)機理的改進NSGA-Ⅲ算法流程如圖1所示。圖中斜體部分為主要改進之處。

4 試驗仿真

將基于生物激素調(diào)節(jié)機理的改進型NSGA-Ⅲ算法和其他算法進行比較，采用文獻[4]中的8×8實例和文獻[10]中的算例數(shù)據(jù)進行軟件仿真。

車間非調(diào)節(jié)性功率為35kW，工件轉(zhuǎn)移功率為2kW。本文采用的算法程序參數(shù)設置如下：初始交叉概率為0.9，初始變異概率為0.1，G為當前迭代次數(shù)，Hill常數(shù)n=1，閾值D=2，父代個體數(shù)量為100。GA和改進GA算法需要將處理的多目標問題轉(zhuǎn)為單目標問題，權(quán)重設置為[0.2，1×10-7，0.01，0.1]。父代個數(shù)均為100，迭代數(shù)均為200代，每種智能算法獨立試驗20次，求解出的各目標平均值見表1。

表1仿真結(jié)果顯示，在同樣的參數(shù)設置下，本文改進型NSGA-Ⅲ算法所得各目標函數(shù)值平均值均優(yōu)于其他算法。比較每種算法的最優(yōu)結(jié)果可知，在相同參數(shù)設置下，本文使用的改進型NSGA-Ⅲ算法的求解質(zhì)量更優(yōu)，見表2。對應最優(yōu)調(diào)度甘特圖如圖2所示。

不難看出，設備總負載越低，設備碳成本越低，設備利用率越高，最大完工時間也會相應增加。但本文所得方案的總拖期時間仍然是0，說明本文設計的作業(yè)車間調(diào)度模型能夠降低碳排放成本和能耗需求，并能保證生產(chǎn)正常進行，驗證了本文在作業(yè)車間調(diào)度中考慮碳排放成本的可行性。

使用基于激素調(diào)節(jié)機理的自適應因子的改進型NSGA-Ⅲ算法（圓點）與其他算法（星點）的最優(yōu)解空間對比如圖3所示，不難看出改進型NSGA-Ⅲ算法在最優(yōu)解的分布上優(yōu)于傳統(tǒng)算法。

5 結(jié)論

本文針對作業(yè)車間碳排放成本、最大完工時間、總延期時長以及設備總負荷4個目標組成的高維目標低碳柔性車間調(diào)度問題建立綜合優(yōu)化模型，采用基于激素調(diào)節(jié)機理的改進型NSGA-Ⅲ算法求解最優(yōu)調(diào)度方案。實際生產(chǎn)數(shù)據(jù)的模擬仿真表明，本文的改進型NSGA-Ⅲ算法在求解質(zhì)量上優(yōu)于傳統(tǒng)算法，并且所提低碳柔性車間調(diào)度優(yōu)化模型可在降低碳排放成本的同時滿足作業(yè)加工工序的要求。在碳成本日益凸顯的當下，將其作為約束引入生產(chǎn)調(diào)度優(yōu)化具有現(xiàn)實意義。

參考文獻

[1]范雅男，逄煥利.求解柔性流水車間調(diào)度問題的粒子群優(yōu)化算法[J].長春工業(yè)大學學報，2022（3）：258-264.

[2]WU X，SUN Y.A green scheduling algorithm for flexible job shop with Energy-Saving measures[J].Journal of cleaner production，2018，172（3）：3249-3264.

[3]LIU A，YU Y，XING Q，et al.Improved collaborative particle swarm"algorithm for job shop scheduling optimization[J].Journal of computational"amp; theoretical nanoscience，2011，4（合刊）：2180-2183.

[4]楊冬婧，雷德明.新型蛙跳算法求解總能耗約束FJSP[J].中國機械工程，2018，29（22）：2682-2689.

[5]李丹，向鳳紅，毛劍琳.基于INSGA-Ⅱ高維目標柔性作業(yè)車間調(diào)度的優(yōu)化[J].重慶郵電大學學報（自然科學版），2022，34（2）：341-348.

[6]宋佳容，申雪峰，馮悅，等.基于改進蟻群算法的綠色柔性流水車間調(diào)度問題研究[J].遼寧工業(yè)大學學報（自然科學版），2023，43（4）：245-251.

[7]楊蓓，汪方軍，黃侃.適應低碳經(jīng)濟的企業(yè)碳排放成本模型[J].西安交通大學學報（社會科學版），2011，31（1）：44-47.

[8]杜曉亮，張楠，孟凡云，等.改進NSGA2算法求解柔性作業(yè)車間調(diào)度問題[J].組合機床與自動化加工技術(shù)，2022（5）：182-186.

[9]操心慧，許麗娟.基于Pareto支配的高維多目標優(yōu)化算法的分析與研究[J].現(xiàn)代計算機，2023，29（2）：62-67.

[10]王秋蓮，段星皓.基于高維多目標候鳥優(yōu)化算法的柔性作業(yè)車間調(diào)度[J].中國機械工程，2022，33（21）：2601-2612.