基于改進非支配排序遺傳算法的多目標柔性作業車間低碳調度

姜一嘯 吉衛喜，2 何 鑫 蘇 璇

1.江南大學機械工程學院，無錫，214122 2.江蘇省食品制造裝備重點實驗室，無錫，214122

0 引言

隨著生產力的發展、科技水平的不斷提高，制造業發展迅速，但隨之而來的卻是能源消耗的增加以及生態環境的破壞[1]。機械制造業作為國民經濟發展的基礎性行業，是實現綠色發展和科技創新的關鍵領域[2]。車間調度作為制造系統中的關鍵環節，調度方案會對加工效率、成本、碳排放等產生影響，因此，通過生產調度優化實現綠色生產已成為企業節能減排，提高經濟、社會效益的重要途徑。

作業車間調度問題(job shop scheduling problem，JSP)已被證明為NP-hard問題[1]，柔性作業車間調度問題(flexible job shop scheduling problem，FJSP)作為JSP問題的延伸，更符合企業實際生產與社會發展需求，逐漸成為本領域研究的重點[2]。近年來，隨著社會各界對綠色制造、低碳生產的重視，碳達峰與碳中和“雙碳”戰略目標的提出[3]，越來越多的車間調度研究開始將綠色低碳作為優化目標，也取得了較多研究成果。劉彩潔等[4]結合分時電價政策，通過合理安排調度任務避開工業用電高峰，構建了以最小化能耗碳排放、能耗成本與最長完工時間為目標的調度模型，并設計了一種基于動態控制參數的快速非支配排序遺傳算法對該模型進行求解。WU等[5]考慮設備開機、關機與設備調速兩種節能措施，設計了一種能耗模型來計算設備不同狀態下產生的能耗，并提出了一種綠色調度啟發式算法來同時優化完工時間與能耗。ASSIA等[6]將以最小化最長完工時間與能耗為目標的調度問題抽象成一種二元整數線性規劃模型，并通過分支界定算法驗證了該模型的可行性。楊冬婧等[7]針對能耗約束條件下的總延遲最小化問題，將該能耗約束問題轉化為以最小化總能耗和總延遲為目標的雙目標低碳調度問題，并提出了一種新型蛙跳算法進行求解。李明等[8]針對具有準備時間和關鍵目標的柔性作業車間低碳調度問題，設計一種新型帝國競爭算法，在優化關鍵目標的同時兼顧非關鍵目標的改進。綜上，現有研究大多側重于問題本身的模型建立、求解方法的性能優化或是通過不同的節能減排方法來實現低碳調度，而車間作為一個復雜的生產環境，具有多種產生碳排放的途徑，因而考慮不同來源的碳排放對于低碳調度研究有著積極的意義。

由于需要在傳統經濟型指標的基礎上同時考慮綠色指標，低碳調度問題必然是更為復雜的多目標決策問題。針對這類多目標優化問題，傳統的基于經驗的生產規則難以得到優質解，而作為元啟發式方法中運用最為廣泛的進化算法成為了解決該類問題的關鍵。其中，DEB等[9]提出的帶精英策略的非支配排序遺傳算法(non-dominated sorting genetic algorithm，NSGA-Ⅱ)由于采用了快速非支配排序方法、引入了精英保留策略與擁擠度比較算子，因而具有運行速度快、解集收斂性好等優點，被廣泛應用于車間調度問題的求解中。HAN等[10]提出了一種改進的NSGA-Ⅱ對多目標FJSP進行求解，通過采用可變鄰域結構的局部搜索方法來提高NSGA-Ⅱ的搜索能力。LI等[11]在求解具有多排車間布局的FJSP時，在NSGA-Ⅱ中集成了兩種啟發式選擇策略，通過對迭代結果進行優化，進一步提高算法的搜索性能。JIANG[12]采取一種改進的精英策略來動態調整NSGA-Ⅱ的精英解集，并優化了非支配排序算法，然后通過多目標JSP算例驗證了改進算法具有更強的全局搜索能力與求解效率。CHEN等[13]設計了一種具有相對變異性的改進非支配遺傳算法，該算法通過計算兩條染色體之間的血緣關系來確定染色體突變率，從而避免群體早熟，并通過實例對算法性能進行了驗證。宋存立[14]對NSGA-Ⅱ的變異算子與選擇方法進行了改進，提高種群多樣性的同時兼顧了算法的局部搜索能力，并通過實驗案例驗證改進算法的有效性。LIANG等[15]針對NSGA-Ⅱ中的交叉與變異存在盲目定向的問題，設計了一種基于個體擁擠度與種群平均擁擠度的交叉、變異算子，提高了算法的收斂速度，然后提出了一種分層選擇策略以提高后代種群的多樣性，并用該算法對車輛生產調度問題進行求解。可以發現，收斂性優化與多樣性改善是NSGA-Ⅱ在車間調度領域的研究熱點，上述研究通過改進遺傳算子與精英保留策略，或是采用局部搜索與全局改善機制等方法，對NSGA-Ⅱ在收斂性、多樣性等方面的不足進行了優化，取得較優結果。但上述改進算法少有從自適應角度考慮，并且已有的適應性策略往往忽略了不同進化階段對算法性能的需求，同時有關種群初始化的研究相對較少，而初始種群的質量對算法的收斂性有著顯著的影響[16]。

本文將設備能耗、刀具磨損及切削液消耗作為車間生產過程中碳排放的來源，考慮包含人工、能耗兩部分組成的加工成本，以最小化碳排放量、最長完工時間和加工成本為目標，建立柔性作業車間低碳調度模型，針對該模型，提出了一種改進NSGA-Ⅱ進行求解。通過經典算例和實際案例來驗證了所提算法的可行性。

1 問題描述與模型的建立

1.1 問題描述

本文研究的多目標柔性作業車間低碳調度問題可以被描述如下：車間有n個待加工工件，記為工件集J={J1，J2，…，Jn}，有m臺加工設備，記為設備集M={M1，M2，…，Mm}，每個工件Ji包含多道工序，每道工序Oij可以在M中的一臺或多臺設備上進行加工，同一道工序在不同設備上的加工時間、加工成本及產生的碳排放量不同，不同的設備可以在同一時刻加工不同的工件。本文研究問題的目標是確定每道工序的加工設備及各個設備上工件的加工順序，從而實現碳排放量、最長完工時間和加工成本的最優組合。

在生產調度中，設備能耗、刀具磨損與切削液消耗產生的碳排放與加工過程相關[17]，同時，由于設備的不同，員工崗位、技能水平的差異，同一個工件的同一道工序在不同的設備上加工的能耗、人工費用也各不相同。因此，本文以設備能耗、刀具磨損與切削液消耗作為碳排放的來源，以設備、人工費用作為加工成本。描述問題與建立模型過程中所需的符號與含義見表1。

表1 模型符號及含義

1.2 模型的建立

本文針對柔性作業車間的特點，以最小化碳排放量FC、最長完工時間FT和加工成本FP為目標函數建立數學模型：

(1)

(2)

(3)

(4)

(5)

(6)

設備k上因切削液消耗而產生的碳排放可表示為

(7)

(8)

(9)

模型的約束條件如下：

(10)

(11)

(12)

(13)

t=0，?kable=1

(14)

(15)

式(10)表示工序的加工過程不能中斷；式(11)表示工件的工序加工存在先后順序，前一道工序完成才能進行后一道工序的加工；式(12)、式(13)表示同一時刻，工件的某道工序只能由其可用設備中的一臺進行加工；式(14)表示所有設備在0時刻均可用。式(15)表示工序分配設備時，所有可用設備都具有相同的優先級。

2 低碳策略下的改進NSGA-Ⅱ

傳統NSGA-Ⅱ在求解多目標問題時，存在初始種群質量、交叉變異率、保留策略等方面的局限性，使得算法搜索效果較差且易陷入局部最優。因此，本文提出了一種改進NSGA-Ⅱ：①設計了一種種群初始化方法，通過Tent混沌映射生成較為均勻、多樣的初始種群，并在傳統貪婪解碼的基礎上結合AHP進一步提高初始種群質量；②設計了考慮種群進化階段及個體質量的遺傳策略；③設計了一種基于外部檔案集的改進精英保留策略，避免了進化后期種群多樣性降低以及可能收斂于非第1支配面的問題，同時保護了優質個體不在遺傳過程中被破壞。改進NSGA-Ⅱ流程如圖1所示。

圖1 改進NSGA-Ⅱ流程圖

2.1 種群初始化

初始種群的質量對算法的結果及全局收斂性有很大的影響[19]。車間調度問題不僅需要給出工件的加工順序，還要為每道工序分配相應的機器，為此，本文采用Tent混沌映射生成基于工序碼和設備碼的初始種群，相比經典的Logistic混沌映射，Tent混沌映射得到的種群具有更好的隨機性、均勻性與多樣性，具體表達式如下：

(16)

(17)

其中，rand(0，1)為[0，1]之間的隨機數；NT為已有的混沌變量數量。

具體的編碼過程如下：

(2)將第一組混沌變量與原始工序一一對應，按照混沌變量的大小進行降序排列，并將對應的工序進行相應的重排，最終得到的工序序列即為工序碼，見表2。

表2 工序碼編碼示意

(18)

(4)重復上述操作，直至達到種群數量。

解碼是一種將編碼得到的染色體還原成實際加工信息的過程。由于初始種群的質量較差，設備利用率不高、存在的加工間隙較多，在多目標調度問題中，傳統的插入式貪婪解碼只能保證提高設備利用率，縮短完工時間，卻難以保證其他目標的優化，為此本文提出了一種融合層次分析法(analytic hierarchy process，AHP)的貪婪解碼方法，通過引入AHP分析判斷貪婪策略對種群的影響，避免傳統貪婪解碼會影響后續工序安排、難以保證全局優化的問題，從而提高初始種群的質量。具體步驟如下：

(1)將通過Tent混沌映射得到的染色體按順序進行解碼操作，在解碼過程中通過下式判斷當前基因位置對應的工序Oij能否插入該工序可加工設備中現有的加工間隙中：

(19)

(2)假設Mini與滿足步驟(1)中條件的待選設備Mc的總數量為p，優化目標數量為q，對各優化目標函數值進行min-max歸一化操作如下：

(20)

其中，a為設備序號，a=1，2，…，p；b為優化目標序號，b=1，2，…，q；nab為優化目標b在設備a上的取值。進而得到在不同設備上加工的優化目標決策矩陣m=(mab)p×q。

(3)采用AHP計算權重向量，具體步驟如下：

①構造判斷矩陣A，表達式如下：

(21)

其中，fq為各優化目標，矩陣中的元素代表兩個優化目標之間的相對重要度，用1～9表示，1、3、5、7、9分別表示“同等重要”“稍微重要”“較強重要”“強烈重要”與“極端重要”，2、4、6、8分別表示兩相鄰判斷的中間值。

②計算判斷矩陣A的最大特征根λ與其對應的經歸一化后的特征向量ω。

③對判斷矩陣A進行一致性檢驗，一致性指標定義如下：

(22)

其中，σ為矩陣階數。定義一致性比率RC=IC/IR，IR為隨機一致性指標。當RC<0.1時，認為該判斷矩陣有滿意的一致性，對應的特征向量ω就作為權重向量，若不滿足，則需要對判斷矩陣進行進行調整。隨機一致性指標IR的取值見表3。

表3 隨機一致性指標IR標準值

(4)取向量mωT中最小值對應的設備為工序Oij插入的設備，若對應的設備為初始分配設備Mini，且該設備上存在滿足插入條件的間隙，則將工序Oij向前插入，否則仍保留原方案。

(5)當發生插入操作時，染色體組成需要進行動態調整以保證遺傳信息的準確。將工序碼與設備碼中當前基因的位置進行前移，同時將設備碼中對應基因位置的設備號替換成插入的加工間隙所在的設備號。工序Oij對應的基因在染色體中的新位置pos(Oij)如下：

(23)

2.2 非支配排序與擁擠度計算

本文采用一種快速排序方法[21]來進行非支配排序，該方法定義了一種新的支配關系“?d”(超級支配關系)，如果A支配B，或A與B不相關(A、B互不支配)，則A?dB。該方法相較于傳統的NSGA-Ⅱ，平均時間復雜度從O(mN2)降到O(qNlogN)(q為優化目標數量，N為種群規模)，具體步驟如下：

(1)從序列集S(種群所有個體構成的集合)中第1個個體x1開始，將x1與其之后個體進行“?d”比較。一輪比較之后將S分成兩部分，一部分為被x1支配的個體，這部分個體必不為當前種群的非支配個體；另一部分為“超級支配”x1的個體，這部分個體組成新的序列集S′。若x1不被S′中的個體所支配，則x1為當前種群的非支配個體，將其并入非支配解集中。

(2)在新的序列集S′中重復步驟(1)中的操作，直至S′中只有1個個體。

(3)將S中屬于當前非支配解集的個體刪除，重復上述操作，直至所有個體的非支配等級都分配完畢。

得到種群個體的非支配等級后，進一步計算各非支配等級中個體的擁擠度ld，具體計算公式如下：

(24)

2.3 選擇操作

采用二元錦標賽選擇法選擇進行交叉變異的父代種群，具體步驟如下：

(1)從初始種群中任選兩個個體進行比較，優先選擇非支配等級高的個體；若兩者非支配等級相同，則優先選擇擁擠度較高的個體；若兩者擁擠度相同，則從中任選一個。

(2)重復步驟(1)，直至選出N個個體作為父代種群。

2.4 交叉、變異操作

交叉率、變異率對算法全局收斂性有很大的影響[22]，已有的自適應遺傳策略大多只模擬了交叉個體對環境的反應，而沒有考慮不同進化階段對交叉率、變異率的要求。在算法初期，種群質量較差，應賦予相對較高的交叉率和變異率以提高種群質量；在算法后期，種群質量相對優秀并且較為穩定，應逐漸減小交叉率和變異率，保護優秀的基因不被破壞，并避免算法搜索停滯。由于多目標優化問題中各目標之間存在耦合，同時為避免算法搜索過程變成隨機搜索，變異率不宜超過0.1[22]，交叉率的范圍應為[0.9，1][23]。因此，本文在已有自適應策略[24]的基礎上，設計了一種基于遺傳參數的自適應遺傳策略，根據種群進化階段以及種群個體的支配情況動態調整交叉率Pj和變異率Pb，具體表達式如下：

(25)

(26)

當交叉、變異對象的非支配等級較高，即染色體質量較差時，以最大交叉率和變異率促進個體進化；當交叉、變異對象的非支配等級較低，即染色體質量較好時，根據種群進化階段適當降低交叉、變異率，同時，若當前種群非支配層數R較大，即種群整體收斂性較差時，可適當提高交叉率、變異率來加快種群收斂。特殊地，若當前種群所有個體都互不支配，即所有個體非支配等級均為1，以最大交叉率和變異率來提高種群多樣性。

交叉操作通過交換種群個體之間部分基因片段生成新的個體，變異操作通過改變種群個體自身基因片段來豐富種群多樣性。由于工序碼與設備碼的編碼規則不一致，故兩者的交叉、變異操作也有所不同，分別進行說明如下。

采用模擬二進制交叉(simulated binary crossover，SBX)來交替進行工序碼與設備碼的交叉。

工序碼的交叉過程(圖2a)如下：從父代種群中隨機選擇兩個個體，將其工序碼作為父代P1和P2，隨機生成一個工件列表J，J中記錄將要進行交叉的工件號。將P1中屬于J中工件的信息與P2中不屬于J中工件的信息保留下來，生成子代C1，將P1中不屬于J中工件的信息與P2中屬于J中工件的信息保留下來，生成子代C2。

設備碼的交叉過程(圖2b)如下：從父代種群中隨機選擇兩個個體，將其工序碼和設備碼作為父代P1和P2，隨機生成一個位置列表J，確定P1工序碼中屬于J中位置的工序，將其對應的設備與P2中對應工序的設備相交換，生成對應的子代設備碼C1和C2。

(a)工序碼交叉 (b)設備碼交叉

采取互換基因的方式進行工序碼變異：隨機選擇父代工序碼P中的兩個基因進行位置交換，生產子代C，如圖3a所示。

采取雙基因變異的方式進行設備碼變異：隨機選擇父代工序碼P中的兩個基因，從這兩個基因對應的可用設備集中任選一個與當前不同的設備進行替換生產子代C，如圖3b所示。

(a)工序碼變異 (b)設備碼變異

2.5 改進精英保留策略

傳統的精英保留策略通過非支配關系與擁擠度保留父代與子代合并種群中的前N個個體作為新一代種群，但隨著種群的進化，大量的個體聚集于第1非支配等級，種群多樣性降低，并且前期得到的優質個體可能在進化中被破壞，難以在整個遺傳過程中被保留。因此，本文提出了一種基于外部檔案集的改進精英保留策略，通過設計一種概率分布函數代替傳統按非支配等級與擁擠度大小確定的保留策略，該概率分布函數根據種群進化狀況為不同非支配等級的個體添加相應的保留概率。算法初期種群質量較差，優質個體應有較大的概率被保留，加快種群的進化，算法后期第1非支配等級個體大量增加，提高了其他非支配等級的個體被保留的概率，保證了種群多樣性，避免陷入局部最優。同時，建立一個大小為N的外部檔案集，用于存放保留下來的非支配個體，并通過非支配關系對其進行更新。具體分布函數如下：

Nd=rdFd

(27)

(28)

式中，d為非支配等級(d≥1)；Nd為第d級非支配等級上保留的個體的集合；Fd為第d級非支配等級所有個體的集合；rd為第d級非支配等級上個體被保留的概率；nd為第d級非支配等級上的個體數。

基于外部檔案集的改進精英保留策略的步驟如下：

(1)將父代與子代合并成大小為2N的新種群，重新進行非支配等級與擁擠度計算。

(2)從非支配等級為1的個體開始，按對應非支配等級的保留概率判斷是否保留該個體，當保留下來的個體數量達到N時停止操作。

(3)若遍歷完所有非支配等級后保留的個體數量小于N，則對剩余個體繼續進行上述操作，直至找出N個個體作為新一代種群。

(4)將新一代種群中的個體并入外部檔案集，并重新進行非支配排序與擁擠度計算，保留其中最優秀的前N個個體。

3 仿真實驗

本文分別以經典BRdata[25]調度算例和一個實際加工案例為對象，將改進NSGA-Ⅱ與傳統NSGA-Ⅱ和引入參考點選擇的非支配遺傳算法(reference-point-based non-dominated sorting genetic algorithm，NSGA-Ⅲ)[26]進行對比。運行環境為Windows 10操作系統，采用MATLAB R2016a進行算法實現。

3.1 算法性能評價指標

本文選擇Cov指標[27]、Spacing指標[28]與HV指標[29]從不同方面對算法性能進行評價，由于各優化目標的量綱不同，故計算指標時需先對各目標進行歸一化處理。

Cov指標可以反映兩個非支配解集間的互相支配程度，其具體定義如下：

(29)

其中，X、Y為兩個待比較的非支配解集；x、y為X、Y中的個體；“x?y||x=y”表示x支配y或x與y相等；Cov(X，Y)表示解集Y中被解集X中至少一個解支配或等同的個體在Y中的占比。當Cov(X，Y)=1時，表明Y中的所有個體都能在X中找到支配或等于它的個體；反之，當Cov(X，Y)=0時，表明Y中的所有個體都不被X中的個體支配。由于Cov(X，Y)與Cov(Y，X)之間不存在必然的聯系，故必須同時考慮。若Cov(X，Y)>Cov(Y，X)，則說明解集X對解集Y中個體的支配程度強于解集Y對解集X中個體的支配程度，若Cov(X，Y)

Spacing指標可以反映非支配解集中個體分布的均勻性，其具體定義如下：

(30)

HV指標可以綜合反映算法的收斂性與多樣性，其具體定義如下：

(31)

其中，δ表示Lebesgue測度，用于測量體積；N為非支配解集大小；vl表示參考點與解集中第l個個體構成的超體積。HV指標越大，說明算法綜合性能越好。其中，參考點要被非支配解集中的所有個體支配，本文選擇各優化目標函數值中的最大值所對應的點作為HV指標中的參考點。

3.2 參數設置

改進NSGA-Ⅱ中的影響參數有種群規模N、遺傳代數G以及AHP中各目標的相對重要度。本文選擇遺傳算法中幾種常用的N與G設置，以中等規模案例MK04為對象，將算法隨機運算10次，得到各評價指標均值，見表4。可以發現當N=400，G=200時，Spacing指標效果最好；N=200，G=100時，HV指標效果最好。考慮到種群規模與遺傳代數過大時會增加運算成本，種群規模與遺傳代數過小時算法性能無可避免地會降低，并且隨著遺傳代數的增加，種群的進化會逐漸放緩，本文取種群規模N=200，遺傳代數G=100。

表4 不同種群規模與遺傳代數下MK04案例的對比結果

根據文獻[30]及相關專家意見，針對本文調度模型的3個優化目標(最長完工時間f1、加工成本f2、碳排放量f3)，取對應的相對重要度f12=1/2，f13=3，f23=5，f21=2，f31=1/3，f32=1/5。

傳統NSGA-Ⅱ算法與NSGA-Ⅲ算法的初始種群均采用隨機生成，取交叉率0.9，變異率0.1，NSGA-Ⅲ算法所需的參考點由Deb and Jain方法[31]生成。

3.3 算法比較與討論

將3種算法在參數一致的前提下各隨機運算10次，記錄其中最好的指標結果，見表5，其中Cov1為傳統NSGA-Ⅱ與改進NSGA-Ⅱ之間的Cov指標，Cov2為NSGA-Ⅲ與改進NSGA-Ⅱ之間的Cov指標，加粗數值為相同算例中較好的結果。

表5 BRdata算例的算法性能對比

由對比結果可知，在COV指標方面，改進NSGA-Ⅱ在10個算例上均大幅優于另外兩種算法，說明本文算法求得解集中幾乎所有個體都不會被對比算法求得的解支配，解的質量更優，算法的尋優能力較強；在Spacing指標方面，改進NSGA-Ⅱ在算例MK06和MK09上略劣于另外兩種算法取得的最優值，但在其余算例上均優于對比算法；在HV指標方面，改進NSGA-Ⅱ僅在算例MK01上略劣于NSGA-Ⅲ所取得的最優值，但在另外9個算例上均表現更好。以MK01、MK06和MK09算例為對象，繪制HV指標和Spacing指標的對比箱型圖，對比結果如圖4所示。

(a)MK01算例Spacing指標 (b)MK01算例HV指標

從圖4可以看出，本文算法雖然未能同時在這3個算例上取得評價指標的最優值，但箱型圖上下限之間的距離更短，整體分布更為集中，也更接近最優值，說明10次對比實驗中本文算法求得的解集在Spacing指標與HV指標方面的差異較小，求解穩定性較強，并且解集的各評價指標都較為優秀，進而說明本文算法在收斂性、均勻性及多樣性方面比對比算法更優。

將3種算法在不同規模的算例MK01、MK03、MK10上各隨機運行一次后，繪制各優化目標值的收斂曲線，如圖5～圖7所示。可以看出，在3個算例中，本文算法均取得了各優化目標的最優初始值，并且各優化目標的收斂速度和收斂結果均優于另外兩種對比算法，結合HV指標的對比結果可知本文算法在收斂性方面表現較為優秀。分析其主要原因如下：

(a)最長完工時間 (b)加工成本 (c)碳排放量

(a)最長完工時間 (b)加工成本 (c)碳排放量

(a)最長完工時間 (b)加工成本 (c)碳排放量

(1)基于AHP的貪婪解碼策略對初始種群的多個目標進行了協同優化，避免了種群質量朝著某一個目標方向偏移，從而使得初始種群在各目標維度上都優于對比算法，在一定程度上加快了算法收斂。

(2)自適應的遺傳算子使得算法在迭代初期能夠以較大交叉率、變異率加快種群進化，并在迭代后期通過減小交叉、變異率以減少對優質個體的破壞，加快算法的收斂。

(3)改進的精英保留策略通過提高算法后期被支配個體被保留的概率，為種群添加了多樣的基因，降低了算法收斂于局部最優的可能性。

記錄迭代過程中種群的個體重復率，即重復個體在種群中的占比，包括決策向量重復(個體之間的基因組成相同)和目標向量重復(個體之間的基因組成不同但表現形式相同)，并繪制圖8所示的重復率迭代折線圖。

從圖8可以看出，在同一個算例中，隨著算法的迭代，個體重復率逐漸增加，并且在較大規模的算例中，出現重復個體的概率也相對較低，而本文算法求得解集中的個體重復率及個體重復率的增長速度要明顯低于對比算法。結合Spacing指標與HV指標的對比結果可知，本文算法求解的多樣性與分布性更好。其主要原因如下：

(a)MK01算例 (b)MK03算例 (c)MK09算例

(1)種群初始化中通過Tent混沌映射來進行個體的生成，減少了個體之間的相似性，使種群盡可能均勻的分布到解空間，進而提高了種群的多樣性。

(2)自適應的遺傳策略在進化初期及種群非支配等級數量較少時提高了交叉、變異率，在促進新個體的產生同時減少了重復個體的產生。

(3)改進的精英保留策略為每個個體分配了自適應的被保留概率，從而為種群添加了不同非支配等級的個體，在很大程度上增加了種群多樣性。重復個體由于互不支配而具有了相同的非支配等級，而傳統NSGA-Ⅱ與NSGA-Ⅲ都是先按照非支配等級來保留個體，容易保留非支配等級較低的重復個體，雖然NSGA-Ⅲ引入了基于參考點的方式來增加種群多樣性，但僅用于選擇最后一個非支配等級(即保留了該非支配等級的個體后，種群個體數不小于N)，一般適用于收斂困難的高維和超高維空間，在本文研究的問題中優勢并不明顯。同時外部存檔策略又能有效避免多樣化的個體對種群整體質量的影響，較好地平衡了算法收斂與多樣化的能力。

為進一步驗證本文算法在實際問題中的有效性，以某電梯零部件制造企業金工車間的一個加工任務為例，將其數據整理簡化成一個8×6(8個工件，6臺設備)的生成調度問題，具體的加工數據見表6，其余數據與BRdata算例中一致，將每種算法各隨機運算10次，圖9為各優化目標函數值的箱型圖，相應的指標對比結果見表7，其中Cov1表示傳統NSGA-Ⅱ與改進NSGA-Ⅱ的解集之間的支配關系，Cov2表示NSGA-Ⅲ與改進NSGA-Ⅱ的解集之間的支配關系。

表6 簡化整理后的8×6柔性作業車間調度任務實例

(a)最長完工時間箱型圖 (b)加工成本箱型圖 (c)碳排放量箱型圖

由表7可以發現，本文算法在3個優化目標上均取得了最優值與均值，說明其尋優能力要優于傳統NSGA-Ⅱ與NSGA-Ⅲ。圖9a與圖9b中箱型圖分布范圍相較于傳統NSGA-Ⅱ與NSGA-Ⅲ而言優勢不夠明顯，圖9c中箱型圖分布范圍比另外兩種算法更小，說明本文算法在優化最長完工時間與加工成本的穩定性與收斂性上優勢不夠明顯，在求解碳排放量時的穩定性與收斂性較強。除此之外，Cov指標、Spacing指標及HV指標相對另外兩種算法而言更優。

表7 實際算例算法性能比較

為了更直觀地分析三種算法在求解本文調度問題結果上的差異，各隨機運算1次后得到在最長完工時間、加工成本與碳排放量3個目標維度上的Pareto前沿面分布圖，如圖10所示。

(a)原始視圖 (b)完工時間-加工成本視圖

由圖10a可以看出，本文調度問題的解集是由一系列分布在Pareto最優面周圍的離散解組成的，改進NSGA-Ⅱ求得各優化目標函數值在整體上要優于對比算法。由圖10b和圖10d可以看出，在相同的完工時間下，相比傳統NSGA-Ⅱ和NSGA-Ⅲ，本文算法得到解的加工成本和碳排放量更低也更收斂，并且整體上隨著完工時間的增加而減少。由圖10c可以看出，隨著加工成本的增加，碳排放量呈增長趨勢，但在相同加工成本下本文算法求得解的碳排放量更低。綜上所述，在相同的運算條件下，本文算法得到的解在各目標維度上的質量更優。

4 結語

(1)本文考慮設備能耗、刀具磨損及切削液消耗在生產過程中造成的碳排放以及加工過程中產生的能耗、人工費用，建立了以最小化碳排放量、最長完工時間和加工成本為目標的低碳調度模型。

(2)針對研究問題的特點，設計了一種改進NSGA-Ⅱ進行求解，通過Tent混沌映射與融合AHP的貪婪解碼的策略形成質量較高的初始種群；設計了一種自適應遺傳策略，根據進化階段與種群非支配狀態動態調整交叉率、變異率；對傳統精英保留策略進行改進，提高了種群多樣性，并通過外部存檔策略保留優質個體。

(3)基于經典調度算例BRdata進行了擴展，與傳統NSGA-Ⅱ與NSGA-Ⅲ的對比證明了本文算法在種群初始化與收斂性等方面的優勢，并通過一個實際案例驗證了本文算法求解多目標柔性作業車間低碳調度問題的有效性。

后續研究考慮把低碳調度問題擴展到更為復雜的生產系統中，如動態生產環境等，并添加更多的實際約束，更貼近實際生產，同時進一步提高算法的通用性。