姜一嘯 吉衛(wèi)喜，2 何 鑫 蘇 璇

1.江南大學(xué)機(jī)械工程學(xué)院，無(wú)錫，214122 2.江蘇省食品制造裝備重點(diǎn)實(shí)驗(yàn)室，無(wú)錫，214122

0 引言

隨著生產(chǎn)力的發(fā)展、科技水平的不斷提高，制造業(yè)發(fā)展迅速，但隨之而來(lái)的卻是能源消耗的增加以及生態(tài)環(huán)境的破壞[1]。機(jī)械制造業(yè)作為國(guó)民經(jīng)濟(jì)發(fā)展的基礎(chǔ)性行業(yè)，是實(shí)現(xiàn)綠色發(fā)展和科技創(chuàng)新的關(guān)鍵領(lǐng)域[2]。車間調(diào)度作為制造系統(tǒng)中的關(guān)鍵環(huán)節(jié)，調(diào)度方案會(huì)對(duì)加工效率、成本、碳排放等產(chǎn)生影響，因此，通過(guò)生產(chǎn)調(diào)度優(yōu)化實(shí)現(xiàn)綠色生產(chǎn)已成為企業(yè)節(jié)能減排，提高經(jīng)濟(jì)、社會(huì)效益的重要途徑。

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

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

本文將設(shè)備能耗、刀具磨損及切削液消耗作為車間生產(chǎn)過(guò)程中碳排放的來(lái)源，考慮包含人工、能耗兩部分組成的加工成本，以最小化碳排放量、最長(zhǎng)完工時(shí)間和加工成本為目標(biāo)，建立柔性作業(yè)車間低碳調(diào)度模型，針對(duì)該模型，提出了一種改進(jìn)NSGA-Ⅱ進(jìn)行求解。通過(guò)經(jīng)典算例和實(shí)際案例來(lái)驗(yàn)證了所提算法的可行性。

1 問(wèn)題描述與模型的建立

1.1 問(wèn)題描述

本文研究的多目標(biāo)柔性作業(yè)車間低碳調(diào)度問(wèn)題可以被描述如下：車間有n個(gè)待加工工件，記為工件集J={J1，J2，…，Jn}，有m臺(tái)加工設(shè)備，記為設(shè)備集M={M1，M2，…，Mm}，每個(gè)工件Ji包含多道工序，每道工序Oij可以在M中的一臺(tái)或多臺(tái)設(shè)備上進(jìn)行加工，同一道工序在不同設(shè)備上的加工時(shí)間、加工成本及產(chǎn)生的碳排放量不同，不同的設(shè)備可以在同一時(shí)刻加工不同的工件。本文研究問(wèn)題的目標(biāo)是確定每道工序的加工設(shè)備及各個(gè)設(shè)備上工件的加工順序，從而實(shí)現(xiàn)碳排放量、最長(zhǎng)完工時(shí)間和加工成本的最優(yōu)組合。

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

表1 模型符號(hào)及含義

1.2 模型的建立

本文針對(duì)柔性作業(yè)車間的特點(diǎn)，以最小化碳排放量FC、最長(zhǎng)完工時(shí)間FT和加工成本FP為目標(biāo)函數(shù)建立數(shù)學(xué)模型：

(1)

(2)

(3)

(4)

(5)

(6)

設(shè)備k上因切削液消耗而產(chǎn)生的碳排放可表示為

(7)

(8)

(9)

模型的約束條件如下：

(10)

(11)

(12)

(13)

t=0，?kable=1

(14)

(15)

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

2 低碳策略下的改進(jìn)NSGA-Ⅱ

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

圖1 改進(jìn)NSGA-Ⅱ流程圖

2.1 種群初始化

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

(16)

(17)

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

具體的編碼過(guò)程如下：

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

表2 工序碼編碼示意

(18)

(4)重復(fù)上述操作，直至達(dá)到種群數(shù)量。

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

(1)將通過(guò)Tent混沌映射得到的染色體按順序進(jìn)行解碼操作，在解碼過(guò)程中通過(guò)下式判斷當(dāng)前基因位置對(duì)應(yīng)的工序Oij能否插入該工序可加工設(shè)備中現(xiàn)有的加工間隙中：

(19)

(2)假設(shè)Mini與滿足步驟(1)中條件的待選設(shè)備Mc的總數(shù)量為p，優(yōu)化目標(biāo)數(shù)量為q，對(duì)各優(yōu)化目標(biāo)函數(shù)值進(jìn)行min-max歸一化操作如下：

(20)

其中，a為設(shè)備序號(hào)，a=1，2，…，p；b為優(yōu)化目標(biāo)序號(hào)，b=1，2，…，q；nab為優(yōu)化目標(biāo)b在設(shè)備a上的取值。進(jìn)而得到在不同設(shè)備上加工的優(yōu)化目標(biāo)決策矩陣m=(mab)p×q。

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

①構(gòu)造判斷矩陣A，表達(dá)式如下：

(21)

其中，fq為各優(yōu)化目標(biāo)，矩陣中的元素代表兩個(gè)優(yōu)化目標(biāo)之間的相對(duì)重要度，用1～9表示，1、3、5、7、9分別表示“同等重要”“稍微重要”“較強(qiáng)重要”“強(qiáng)烈重要”與“極端重要”，2、4、6、8分別表示兩相鄰判斷的中間值。

②計(jì)算判斷矩陣A的最大特征根λ與其對(duì)應(yīng)的經(jīng)歸一化后的特征向量ω。

③對(duì)判斷矩陣A進(jìn)行一致性檢驗(yàn)，一致性指標(biāo)定義如下：

(22)

其中，σ為矩陣階數(shù)。定義一致性比率RC=IC/IR，IR為隨機(jī)一致性指標(biāo)。當(dāng)RC<0.1時(shí)，認(rèn)為該判斷矩陣有滿意的一致性，對(duì)應(yīng)的特征向量ω就作為權(quán)重向量，若不滿足，則需要對(duì)判斷矩陣進(jìn)行進(jìn)行調(diào)整。隨機(jī)一致性指標(biāo)IR的取值見表3。

表3 隨機(jī)一致性指標(biāo)IR標(biāo)準(zhǔn)值

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

(5)當(dāng)發(fā)生插入操作時(shí)，染色體組成需要進(jìn)行動(dòng)態(tài)調(diào)整以保證遺傳信息的準(zhǔn)確。將工序碼與設(shè)備碼中當(dāng)前基因的位置進(jìn)行前移，同時(shí)將設(shè)備碼中對(duì)應(yīng)基因位置的設(shè)備號(hào)替換成插入的加工間隙所在的設(shè)備號(hào)。工序Oij對(duì)應(yīng)的基因在染色體中的新位置pos(Oij)如下：

(23)

2.2 非支配排序與擁擠度計(jì)算

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

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

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

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

得到種群個(gè)體的非支配等級(jí)后，進(jìn)一步計(jì)算各非支配等級(jí)中個(gè)體的擁擠度ld，具體計(jì)算公式如下：

(24)

2.3 選擇操作

采用二元錦標(biāo)賽選擇法選擇進(jìn)行交叉變異的父代種群，具體步驟如下：

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

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

2.4 交叉、變異操作

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

(25)

(26)

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

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

采用模擬二進(jìn)制交叉(simulated binary crossover，SBX)來(lái)交替進(jìn)行工序碼與設(shè)備碼的交叉。

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

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

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

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

采取雙基因變異的方式進(jìn)行設(shè)備碼變異：隨機(jī)選擇父代工序碼P中的兩個(gè)基因，從這兩個(gè)基因?qū)?yīng)的可用設(shè)備集中任選一個(gè)與當(dāng)前不同的設(shè)備進(jìn)行替換生產(chǎn)子代C，如圖3b所示。

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

2.5 改進(jìn)精英保留策略

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

Nd=rdFd

(27)

(28)

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

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

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

(2)從非支配等級(jí)為1的個(gè)體開始，按對(duì)應(yīng)非支配等級(jí)的保留概率判斷是否保留該個(gè)體，當(dāng)保留下來(lái)的個(gè)體數(shù)量達(dá)到N時(shí)停止操作。

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

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

3 仿真實(shí)驗(yàn)

本文分別以經(jīng)典BRdata[25]調(diào)度算例和一個(gè)實(shí)際加工案例為對(duì)象，將改進(jìn)NSGA-Ⅱ與傳統(tǒng)NSGA-Ⅱ和引入?yún)⒖键c(diǎn)選擇的非支配遺傳算法(reference-point-based non-dominated sorting genetic algorithm，NSGA-Ⅲ)[26]進(jìn)行對(duì)比。運(yùn)行環(huán)境為Windows 10操作系統(tǒng)，采用MATLAB R2016a進(jìn)行算法實(shí)現(xiàn)。

3.1 算法性能評(píng)價(jià)指標(biāo)

本文選擇Cov指標(biāo)[27]、Spacing指標(biāo)[28]與HV指標(biāo)[29]從不同方面對(duì)算法性能進(jìn)行評(píng)價(jià)，由于各優(yōu)化目標(biāo)的量綱不同，故計(jì)算指標(biāo)時(shí)需先對(duì)各目標(biāo)進(jìn)行歸一化處理。

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

(29)

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

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

(30)

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

(31)

其中，δ表示Lebesgue測(cè)度，用于測(cè)量體積；N為非支配解集大?。籿l表示參考點(diǎn)與解集中第l個(gè)個(gè)體構(gòu)成的超體積。HV指標(biāo)越大，說(shuō)明算法綜合性能越好。其中，參考點(diǎn)要被非支配解集中的所有個(gè)體支配，本文選擇各優(yōu)化目標(biāo)函數(shù)值中的最大值所對(duì)應(yīng)的點(diǎn)作為HV指標(biāo)中的參考點(diǎn)。

3.2 參數(shù)設(shè)置

改進(jìn)NSGA-Ⅱ中的影響參數(shù)有種群規(guī)模N、遺傳代數(shù)G以及AHP中各目標(biāo)的相對(duì)重要度。本文選擇遺傳算法中幾種常用的N與G設(shè)置，以中等規(guī)模案例MK04為對(duì)象，將算法隨機(jī)運(yùn)算10次，得到各評(píng)價(jià)指標(biāo)均值，見表4?？梢园l(fā)現(xiàn)當(dāng)N=400，G=200時(shí)，Spacing指標(biāo)效果最好；N=200，G=100時(shí)，HV指標(biāo)效果最好。考慮到種群規(guī)模與遺傳代數(shù)過(guò)大時(shí)會(huì)增加運(yùn)算成本，種群規(guī)模與遺傳代數(shù)過(guò)小時(shí)算法性能無(wú)可避免地會(huì)降低，并且隨著遺傳代數(shù)的增加，種群的進(jìn)化會(huì)逐漸放緩，本文取種群規(guī)模N=200，遺傳代數(shù)G=100。

表4 不同種群規(guī)模與遺傳代數(shù)下MK04案例的對(duì)比結(jié)果

根據(jù)文獻(xiàn)[30]及相關(guān)專家意見，針對(duì)本文調(diào)度模型的3個(gè)優(yōu)化目標(biāo)(最長(zhǎng)完工時(shí)間f1、加工成本f2、碳排放量f3)，取對(duì)應(yīng)的相對(duì)重要度f(wàn)12=1/2，f13=3，f23=5，f21=2，f31=1/3，f32=1/5。

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

3.3 算法比較與討論

將3種算法在參數(shù)一致的前提下各隨機(jī)運(yùn)算10次，記錄其中最好的指標(biāo)結(jié)果，見表5，其中Cov1為傳統(tǒng)NSGA-Ⅱ與改進(jìn)NSGA-Ⅱ之間的Cov指標(biāo)，Cov2為NSGA-Ⅲ與改進(jìn)NSGA-Ⅱ之間的Cov指標(biāo)，加粗?jǐn)?shù)值為相同算例中較好的結(jié)果。

表5 BRdata算例的算法性能對(duì)比

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

(a)MK01算例Spacing指標(biāo) (b)MK01算例HV指標(biāo)

從圖4可以看出，本文算法雖然未能同時(shí)在這3個(gè)算例上取得評(píng)價(jià)指標(biāo)的最優(yōu)值，但箱型圖上下限之間的距離更短，整體分布更為集中，也更接近最優(yōu)值，說(shuō)明10次對(duì)比實(shí)驗(yàn)中本文算法求得的解集在Spacing指標(biāo)與HV指標(biāo)方面的差異較小，求解穩(wěn)定性較強(qiáng)，并且解集的各評(píng)價(jià)指標(biāo)都較為優(yōu)秀，進(jìn)而說(shuō)明本文算法在收斂性、均勻性及多樣性方面比對(duì)比算法更優(yōu)。

將3種算法在不同規(guī)模的算例MK01、MK03、MK10上各隨機(jī)運(yùn)行一次后，繪制各優(yōu)化目標(biāo)值的收斂曲線，如圖5～圖7所示?？梢钥闯?，在3個(gè)算例中，本文算法均取得了各優(yōu)化目標(biāo)的最優(yōu)初始值，并且各優(yōu)化目標(biāo)的收斂速度和收斂結(jié)果均優(yōu)于另外兩種對(duì)比算法，結(jié)合HV指標(biāo)的對(duì)比結(jié)果可知本文算法在收斂性方面表現(xiàn)較為優(yōu)秀。分析其主要原因如下：

(a)最長(zhǎng)完工時(shí)間 (b)加工成本 (c)碳排放量

(a)最長(zhǎng)完工時(shí)間 (b)加工成本 (c)碳排放量

(a)最長(zhǎng)完工時(shí)間 (b)加工成本 (c)碳排放量

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

(2)自適應(yīng)的遺傳算子使得算法在迭代初期能夠以較大交叉率、變異率加快種群進(jìn)化，并在迭代后期通過(guò)減小交叉、變異率以減少對(duì)優(yōu)質(zhì)個(gè)體的破壞，加快算法的收斂。

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

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

從圖8可以看出，在同一個(gè)算例中，隨著算法的迭代，個(gè)體重復(fù)率逐漸增加，并且在較大規(guī)模的算例中，出現(xiàn)重復(fù)個(gè)體的概率也相對(duì)較低，而本文算法求得解集中的個(gè)體重復(fù)率及個(gè)體重復(fù)率的增長(zhǎng)速度要明顯低于對(duì)比算法。結(jié)合Spacing指標(biāo)與HV指標(biāo)的對(duì)比結(jié)果可知，本文算法求解的多樣性與分布性更好。其主要原因如下：

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

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

(2)自適應(yīng)的遺傳策略在進(jìn)化初期及種群非支配等級(jí)數(shù)量較少時(shí)提高了交叉、變異率，在促進(jìn)新個(gè)體的產(chǎn)生同時(shí)減少了重復(fù)個(gè)體的產(chǎn)生。

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

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

表6 簡(jiǎn)化整理后的8×6柔性作業(yè)車間調(diào)度任務(wù)實(shí)例

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

由表7可以發(fā)現(xiàn)，本文算法在3個(gè)優(yōu)化目標(biāo)上均取得了最優(yōu)值與均值，說(shuō)明其尋優(yōu)能力要優(yōu)于傳統(tǒng)NSGA-Ⅱ與NSGA-Ⅲ。圖9a與圖9b中箱型圖分布范圍相較于傳統(tǒng)NSGA-Ⅱ與NSGA-Ⅲ而言優(yōu)勢(shì)不夠明顯，圖9c中箱型圖分布范圍比另外兩種算法更小，說(shuō)明本文算法在優(yōu)化最長(zhǎng)完工時(shí)間與加工成本的穩(wěn)定性與收斂性上優(yōu)勢(shì)不夠明顯，在求解碳排放量時(shí)的穩(wěn)定性與收斂性較強(qiáng)。除此之外，Cov指標(biāo)、Spacing指標(biāo)及HV指標(biāo)相對(duì)另外兩種算法而言更優(yōu)。

表7 實(shí)際算例算法性能比較

為了更直觀地分析三種算法在求解本文調(diào)度問(wèn)題結(jié)果上的差異，各隨機(jī)運(yùn)算1次后得到在最長(zhǎng)完工時(shí)間、加工成本與碳排放量3個(gè)目標(biāo)維度上的Pareto前沿面分布圖，如圖10所示。

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

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

4 結(jié)語(yǔ)

(1)本文考慮設(shè)備能耗、刀具磨損及切削液消耗在生產(chǎn)過(guò)程中造成的碳排放以及加工過(guò)程中產(chǎn)生的能耗、人工費(fèi)用，建立了以最小化碳排放量、最長(zhǎng)完工時(shí)間和加工成本為目標(biāo)的低碳調(diào)度模型。

(2)針對(duì)研究問(wèn)題的特點(diǎn)，設(shè)計(jì)了一種改進(jìn)NSGA-Ⅱ進(jìn)行求解，通過(guò)Tent混沌映射與融合AHP的貪婪解碼的策略形成質(zhì)量較高的初始種群；設(shè)計(jì)了一種自適應(yīng)遺傳策略，根據(jù)進(jìn)化階段與種群非支配狀態(tài)動(dòng)態(tài)調(diào)整交叉率、變異率；對(duì)傳統(tǒng)精英保留策略進(jìn)行改進(jìn)，提高了種群多樣性，并通過(guò)外部存檔策略保留優(yōu)質(zhì)個(gè)體。

(3)基于經(jīng)典調(diào)度算例BRdata進(jìn)行了擴(kuò)展，與傳統(tǒng)NSGA-Ⅱ與NSGA-Ⅲ的對(duì)比證明了本文算法在種群初始化與收斂性等方面的優(yōu)勢(shì)，并通過(guò)一個(gè)實(shí)際案例驗(yàn)證了本文算法求解多目標(biāo)柔性作業(yè)車間低碳調(diào)度問(wèn)題的有效性。

后續(xù)研究考慮把低碳調(diào)度問(wèn)題擴(kuò)展到更為復(fù)雜的生產(chǎn)系統(tǒng)中，如動(dòng)態(tài)生產(chǎn)環(huán)境等，并添加更多的實(shí)際約束，更貼近實(shí)際生產(chǎn)，同時(shí)進(jìn)一步提高算法的通用性。