鄭錦燦 邵立珍 雷雪梅

（①北京科技大學(xué)自動化學(xué)院，北京 100083；②北京科技大學(xué)順德創(chuàng)新院，廣東 佛山 528399；③北京科技大學(xué)信息化建設(shè)與管理辦公室，北京 100083）

柔性作業(yè)車間調(diào)度問題（flexible flow job shop scheduling problem，F(xiàn)JSP）是傳統(tǒng)作業(yè)車間調(diào)度問題基礎(chǔ)上的擴展，它是一類經(jīng)典的NP-hard問題。在傳統(tǒng)作業(yè)車間調(diào)度問題中，每個工件由一道或多道具有固定加工順序的工序構(gòu)成，且每道工序的加工機器是唯一的。FJSP允許一道工序有多臺可供選擇的加工機器，且在不同機器上的加工時間可能存在差異，這更符合柔性制造系統(tǒng)的實際情況。傳統(tǒng)的FJSP通常僅考慮單一的目標(biāo)函數(shù)，如最小化最大完工時間或者經(jīng)濟性能指標(biāo)等。但是隨著社會經(jīng)濟的快速發(fā)展和人們的環(huán)保意識不斷的提高，單純的經(jīng)濟指標(biāo)已經(jīng)無法滿足綠色生產(chǎn)的需求，能耗、碳排放等一系列綠色生產(chǎn)指標(biāo)正越來越受到企業(yè)的重視[1]。因此，多目標(biāo)柔性綠色作業(yè)車間調(diào)度問題應(yīng)運而生。

不同于單目標(biāo)FJSP，多目標(biāo)FJSP中多個性能指標(biāo)需要被同時優(yōu)化。許多學(xué)者采用智能優(yōu)化算法求解該問題。Li M等[2]提出了一種兩層帝國競爭算法求解具有目標(biāo)重要性約束的多目標(biāo)優(yōu)化問題。Msc M 等[3]應(yīng)用分布式估計算法求解了多目標(biāo)隨機調(diào)度問題。楊帆[4]提出了一種多種交叉混合的交叉方法和一種基于元胞數(shù)組的解碼方式，提高遺傳算法的全局搜索能力。梁曉磊等[5]構(gòu)建了以機器效率最大和最大完工時間最小為目標(biāo)的調(diào)度模型，并使用改進的遺傳算法求解。Chang H C等[6]提出了一種混合遺傳算法（hybrid genetic algorithm，HGA），使用田口方法來優(yōu)化算法的參數(shù)，還提出了一種新的編碼機制解決了無效工件的分配問題。

在多目標(biāo)調(diào)度問題的求解中，如何防止算法陷入局部最優(yōu)是研究的一個熱點。文笑雨等[7]設(shè)計了N5鄰域結(jié)構(gòu)，并提出了改進NSGA-II求解方法。張國輝等[8]考慮了完工時間，機器負(fù)載以及環(huán)境碳排放的柔性低碳調(diào)度模型，在NSGA-II算法基礎(chǔ)上引入鄰域搜索策略得到了高效可行的調(diào)度解。Frutos M等[9]構(gòu)建了最小化完工時間和總成本的多目標(biāo)模型，在遺傳算法的搜索過程中引入模擬退火算法跳出了局部最優(yōu)。陳輔斌等[10]結(jié)合實際生產(chǎn)過程中加工時間、機器負(fù)載、運行成本等情況，建立了多目標(biāo)調(diào)度模型，引入免疫平衡原理改進NSGAII算法，避免了算法陷入局部最優(yōu)。

雖然上述的研究取得了一定的成果，但是針對多目標(biāo)FJSP的研究，仍存在如下問題：①現(xiàn)有的FJSP模型大都集中于最小化完工時間和機器總負(fù)荷，忽視了能耗指標(biāo)，模型無法滿足實際的綠色生產(chǎn)需求；②在智能優(yōu)化算法中，隨機選擇的初始化策略影響著算法的求解性能，但現(xiàn)有的智能優(yōu)化調(diào)度算法對種群初始化策略關(guān)注較少，且解易于陷入局部最優(yōu)。

基于上述考慮，本文首先建立了一個多目標(biāo)綠色FJSP模型。模型中，除了考慮傳統(tǒng)的經(jīng)濟指標(biāo)，還考慮了能耗指標(biāo)。其次，提出了一種改進的快速非支配排序遺傳算法（improved non-dominated sorting genetic algorithm II，INSGA-II）求解該模型。

1 多目標(biāo)柔性作業(yè)車間調(diào)度問題

1.1 問題描述

FJSP的數(shù)學(xué)描述[11]為：有n個相互獨立的工件 J ={J1,J2, ··· ,Jn}在m臺不同的機器構(gòu)成的機器集M={M1,M2, ···,Mm}上加工，每個工件包含一定的工序，以工序集 O ={Oi,1,Oi,2, ···,Oi,ni}的形式表示，預(yù)先給定所有工序在可選機器上的加工時間進行加工。

在建立具體的數(shù)學(xué)模型之前，根據(jù)實際的生產(chǎn)加工情況做出如下假設(shè)：

（1）同一時間內(nèi)每個機器只能加工一道工序。

（2）所有工件的工序加工時間是已知的。

（3）同一工件的不同加工工序具有先后優(yōu)先級，不同工件的加工工序沒有先后優(yōu)先級。

（4）一道工序一旦開始加工就不能中止。

（5）每個工件在同一時刻內(nèi)只允許在一道機器上加工。

（6）在0時刻開始所有機器都是可用的，同時機器不會發(fā)生故障。

本文中出現(xiàn)的一些符號定義如表1所示。

表1 符號定義表

1.2 模型建立

FJSP的數(shù)學(xué)模型如下：

式（1）和（2）均是控制約束變量，用來約束指定機器上的加工和工序。式（3）和（4）表示根據(jù)每一工件的工藝路線，工序的先后加工順序約束；式（5）表示每一個工件的完工時間不能超過總的完工時間；式（6）規(guī)定每臺機器某一時刻只能加工一道工序；式（7）是獨占性約束，即規(guī)定某一時刻每道工序僅能在一臺機器上加工；式（8）和（9）中規(guī)定各個參數(shù)的變量必須是正數(shù)。

模型中的優(yōu)化目標(biāo)為：最大完工時間、機器總負(fù)荷、能耗。最大完工時間是使用頻率最高的基本經(jīng)濟指標(biāo)；機器總負(fù)荷指標(biāo)和瓶頸機器負(fù)荷指標(biāo)在延長機器的壽命、合理分配資源以及提高生產(chǎn)效率的方面中有著重要的意義；能耗指標(biāo)作為綠色生產(chǎn)的評價指標(biāo)引入。計算公式如下：

除了上述的3個性能指標(biāo)，在進行算法的性能比較時，通常也會引入機器的瓶頸負(fù)荷指標(biāo)進行測試，其具體計算公式如下。

2 改進的NSGA-II算法

INSGA-II算法的流程圖如圖1所示。該算法基于NSGA-II進行改進，主要包括以下幾個部分：編碼生成初始種群、解碼、快速非支配排序和擁擠度距離計算、交叉變異操作、精英保留策略和學(xué)習(xí)機制。

圖1 改進NSGA-II算法流程圖

2.1 混合種群初始化策略

種群的初始化方式與調(diào)度的初始解具有不可分割的關(guān)系，高效的初始化方式有助于提高算法的收斂速度，通過更少的迭代次數(shù)得到問題的最優(yōu)解。

本文基于機器和工序（machine selection and operation sequence，MSOS)兩層編碼。如圖2，首先隨機生成工序染色體P，然后通過工序染色體P確定機器染色體M，圖中工序染色體[1, 2, 3, 1, 4, 2, 3, 4, 2]依次代表工序 [O11,O21,O31,O12,O41,O22,O32,O42,O23]，機器染色體[5, 1, 2, 4, 3, 3, 1, 2, 5]依次代表機器[M5,M1,M2,M4,M3,M3,M1,M2,M5]。

圖2 MSOS編碼示意圖

在MSOS編碼的基礎(chǔ)上采用一種基于全局、局部、隨機初始化的非支配選擇種群初始化策略。其中，全局選擇通過平衡全局的機器負(fù)載來實現(xiàn)全局負(fù)載最小化；局部選擇注重單一工件的工序最小加工時間，從而保證局部工序的加工時間最短；隨機選擇初始化隨機產(chǎn)生總工序長度的工序集，再通過對應(yīng)工序可選機器集隨機選擇一個機器形成機器集，保證初始種群具有一定的隨機性。具體的初始化方法如下：

步驟1：分別執(zhí)行局部初始化和全局初始化，產(chǎn)生兩個種群數(shù)量均為Np的初始父代種群。

步驟2：合并兩個初始父代種群，使用快速非支配排序的方法對父代種群進行初始排序篩選，刪除父代種群中完全相同的初始個體。

步驟3：在初始個體被刪除后，如果剩余的總種群數(shù)量少于Np則使用隨機方法初始化父代種群進行補充，直到種群的數(shù)量等于Np。如果剩余的種群數(shù)量等于大于Np，則選擇前Np個個體作為父代的初始種群。

2.2 解碼

解碼操作是指將編碼生成的初始種群染色體轉(zhuǎn)換成為可行的調(diào)度方案。本文中采用一種考慮機器空余時間的插入式貪婪解碼策略[12]，生成主動調(diào)度解，從而最大化的利用機器資源。

2.3 交叉與變異

本文采用改進優(yōu)先工序交叉算子（improved precedence operation crossover, IPOX）和多點保留交叉算子（multipoint preservative crossover, MPX ），以及單點最小加工時間機器突變和倒序變異的混合交叉變異方式來提高算法的尋優(yōu)能力，同時設(shè)置了自適應(yīng)的交叉變異算子。

2.3.1 基于工序的IPOX交叉

步驟1：將所有的工件p隨機分配到兩個數(shù)據(jù)集R1和R2，使得

步驟2：子代C1中復(fù)制父代P1包含在R1中的工序基因，子代C2復(fù)制父代P2包含在R2中的工件，保持復(fù)制前后的工序基因的位置不發(fā)生變化。

步驟3：子代C1之中空余的基因位置用父代P2不包含在R1中的工序基因依次填入，子代C2之中空余的基因位置用父代P1不包含在R2中的工序基因依次填入。

IPOX交叉方式的示意圖如圖3所示。

圖3 IPOX交叉示意圖

2.3.2 基于機器的MPX交叉

步驟1：隨機生成一個長度為總工序數(shù)只包含0和1的數(shù)組R3。

步驟2：隨機選擇兩條父代機器染色體M1和M2，交換M1和M2在R3數(shù)組出現(xiàn)數(shù)字1的相同位置，產(chǎn)生子代的機器集。

MPX交叉方式示意圖如圖4所示。

圖4 MPX交叉示意圖

2.3.3 混合變異策略

本文采用基于工序的倒序變異方式以及基于機器的單點最小加工時間突變的混合變異策略?；诠ば虻牡剐蜃儺?，通過隨機在工序染色體選擇兩個變異位置，然后倒序交換這之間的染色體片段?；跈C器的單點最小加工時間突變，通過隨機選擇一個工序染色體位置，找到其對應(yīng)的機器染色體片段，將對應(yīng)的機器染色體片段替換為該工序在可選機器集中具有最小加工時間的機器。

2.4 自適應(yīng)交叉變異算子

本文中采用基于迭代的自適應(yīng)交叉變異算子來控制交叉和變異的概率。Pc(i)和Pm(i)分別表示每代的交叉和變異的概率，其具體的計算公式如下。

2.5 快速非支配排序與擁擠度算子

多目標(biāo)優(yōu)化問題的多個目標(biāo)函數(shù)之間往往存在沖突，本文采用非支配排序和擁擠度算子對各個解集進行分層排序，從而區(qū)分出解集的優(yōu)劣。

2.6 改進的精英保留策略

傳統(tǒng)NSGA-II采用隱性的精英保留策略，這樣容易導(dǎo)致后代出現(xiàn)大量的解處于第一非支配等級，同時解集之間的相似度也會較高。

本文提出一種動態(tài)調(diào)節(jié)的改進精英保留策略，控制算法迭代產(chǎn)生的后代種群，引入一個分布函數(shù)來限制父代種群中的精英數(shù)量，該分布函數(shù)通過兩種策略進行動態(tài)調(diào)節(jié)。

當(dāng)算法的迭代規(guī)模較小時，子代非支配等級為1的精英數(shù)量較少。此時希望盡可能的保留父代迭代得到的精英解，讓子代繼承這些優(yōu)良特性。而針對第2-N個非支配的等級的種群，則使用比例系數(shù)λ1進行選擇，如果某一支配等級選擇后種群數(shù)之和超過了N，則該非支配等級依據(jù)擁擠比較算子選擇個體數(shù)量，維持種群數(shù)量N保持不變。將這一閾值設(shè)定為子代非支配等級為1的精英數(shù)量小于父代種群規(guī)模的50%， λ1=0.5。此時精英保留策略如圖5，其中Pt和Qt分別表示當(dāng)前代數(shù)的父代種群和子代種群，Pt+1和Qt+1分別表示下一代的父代種群和子代種群。Pt+1的計算公式如下:

圖5 第一種條件下的改進精英保留策略

當(dāng)算法迭代到一定的規(guī)模時，子代非支配等級為1的精英數(shù)量已經(jīng)較多，算法的迭代可能陷入停滯。此時使用比例系數(shù) λ2來選擇所有非支配等級的種群，以更多的比例接受一定程度的劣解，提高后代種群的多樣性，防止算法陷入局部最優(yōu)，同時我們也需要控制種群數(shù)量。設(shè)置 λ2的參數(shù)為0.6，此時精英保留策略如圖6，Pt+1的計算公式如下。

圖6 第二種條件下的改進精英保留策略

2.7 學(xué)習(xí)機制

NSGA-II的交叉變異算子在一定程度上可以防止算法陷入局部最優(yōu)。為了提高算法的可靠性，采用一種基于最優(yōu)個體的學(xué)習(xí)機制，針對算法迭代產(chǎn)生的優(yōu)良種群進行鄰域搜索，具體的執(zhí)行過程如下：

步驟1：選擇一條父代迭代后生成解集中支配等級為1的染色體P_1。

步驟2：在染色體上隨機生成兩個位置點A和B，記錄兩點之間的片段做為父代優(yōu)良的基因片段。

步驟3：分別打亂A點左側(cè)的基因片段和B點右側(cè)的基因片段，重新組合生成新的染色體P_2。

步驟4：檢查P_2染色體的調(diào)度的可行性，如果產(chǎn)生了不可行調(diào)度的解，則為其不可行工序在可選機器集中分配一臺機器加工。確保染色體能夠生成可行調(diào)度解后計算P_2目標(biāo)函數(shù)值和非支配等級。

步驟5：比較P_1和P_2的目標(biāo)函數(shù)值和非支配等級，如果P_2優(yōu)于P_1則使用P_2替換P_1來調(diào)整新的父代種群。

學(xué)習(xí)機制的示意圖如圖7所示。

圖7 學(xué)習(xí)機制示意圖

3 算法仿真測試與分析

本文算法基于Matlab R2015a進行編程，并在Windows 10，AMD Ryzen 7-5800H，CPU 3.2 GHz，內(nèi)存16 GB，64位操作系統(tǒng)上運行。設(shè)置算法的初始種群數(shù)量為100，最大迭代代數(shù)為200，交叉算子Pc的范圍為[0.4,0.8]，變異算子Pm的范圍為[0.01,0.1]。

3.1 改進初始化策略的有效性

為了驗證本文所提出的改進初始化策略的有效性，使用隨機初始化的NSGA-II算法和采用非支配選擇策略INSGA-II算法做對比，以Brandimarte基準(zhǔn)算例中的MK04數(shù)據(jù)集為例，設(shè)定目標(biāo)函數(shù)為最小化最大完工時間，最小化瓶頸機器負(fù)荷，最小化總負(fù)荷，其余的所有參數(shù)均保持一致，兩種算法各獨立運行20次，選取最優(yōu)的結(jié)果繪制進化曲線進行對比。

由圖8～10可知使用非支配選擇初始化策略INSGA-II算法在初始解集上均優(yōu)于使用隨機初始化策略的NSGA-II算法，同時其收斂的速度也較NSGA-II有一定的優(yōu)勢。通過對比算法在各個目標(biāo)函數(shù)上的最終解集收斂值，INSGA-II在機器總負(fù)荷以及最大完工時間上均優(yōu)于NSGA-II算法，說明了非支配選擇初始化策略在求解該問題上較優(yōu)。

圖8 INSGA-II和NSGA-II完工時間進化過程

3.2 改進精英保留策略的有效性

為了驗證本文所提出的改進精英保留策略的有效性，選取使用傳統(tǒng)精英保留策略的NSGA-II算法與改進式精英保留策略的INSGA-II算法做對比，其余參數(shù)條件保持一致。選取Brandimarte中MK01的數(shù)據(jù)集進行測試，優(yōu)化目標(biāo)為最小化最大完工時間，最小化瓶頸機器負(fù)荷，最小化總負(fù)荷。兩種算法獨立運行20次，選擇最好的非支配解集個數(shù)進行記錄，如表2所示。

表2 MK01算例對比表

圖9 INSGA-II和NSGA-II瓶頸機器負(fù)荷進化過程

圖10 INSGA-II和NSGA-II總負(fù)荷進化過程

3.3 多目標(biāo)優(yōu)化算法對比實驗

為了進一步驗證本文INSGA-II算法性能，針對Kacem提出的 8×8，10×10和 15×10這 3個基準(zhǔn)算例進行測試，并與Alzahrani J S[13]提出的搶占式約束規(guī)則（pre-emptive constraint procedure，PCP）算法，Soto C[14]提出的多目標(biāo)分支界定算法 （multiobjective branch and bound，MBB）以及 NSGA-II進行對比。優(yōu)化的目標(biāo)函數(shù)分別為最小化最大完工時間F1，最小化瓶頸機器負(fù)荷F2，最小化總負(fù)荷F3，算例的結(jié)果對比如表3所示。

表3 Kacem算例結(jié)果對比表

由表中的數(shù)據(jù)可知INSGA-II算法在求解8*8的算例時得到的非支配解個數(shù)為4，多于PCP的3個和MBB的3個以及NSGA-II的2個，且分析數(shù)據(jù)可知[15,13,73]，[16,12,75]都比PCP的解集[15,13,76]，[16,12,78]更加好。在10×10的算例上，INSGA-II求得的非支配解數(shù)量均多于PCP以及MBB和NSGA-II，在15×10的算例上INSGA-II求得的非支配解個數(shù)少于PCP的3個，多于MBB和NSGA-II的1個。分析可知，INSGA-II算法能夠有效的求解不同規(guī)模的多目標(biāo)優(yōu)化問題，并得到質(zhì)量較高的解集。

3.4 優(yōu)化調(diào)度方案決策分析

在MK04數(shù)據(jù)集測試，由于該數(shù)據(jù)集不包含能耗信息，故采用計算機隨機生成數(shù)字的方式，添加機器的空載能耗和加工能耗。10個加工機器的空載能耗和機器能耗在[0.1,0.3]和[0.5,2]的范圍內(nèi)自動生成。生成的數(shù)字分別為[0.2,0.1,0.1,0.3,0.2,0.3,0.3,0.2,0.2]，[1.3,0.9,1.7,1.1,1.2,1.9,0.7,0.5]。采用INS-GAII算法優(yōu)化3個目標(biāo)函數(shù)，即最小化最大完工時間f1，最小化總負(fù)荷f2和最小化能耗f3。表3為運行中生成的24個非支配解。

生產(chǎn)決策過程之中，3個指標(biāo)之間的權(quán)重有所差別。由于3個決策目標(biāo)的值具有不同的量綱，需要將其歸一化：

然后歸一化的目標(biāo)函數(shù)乘以相應(yīng)的權(quán)重系數(shù)進行加權(quán)求和得到加權(quán)的目標(biāo)函數(shù)：

假設(shè)決策者對環(huán)境指標(biāo)要求比較高，希望獲得環(huán)境友好型的決策，選取的權(quán)重系數(shù)矩陣W=[0.25,0.25,0.5]，計算得到的最優(yōu)解目標(biāo)函數(shù)如表4第22條所示，其最大完工時間為86，機器總負(fù)載為342，總能耗為390.2，加工信息甘特圖如圖11所示。

圖11 環(huán)境友好型決策調(diào)度甘特圖

表4 MK04算例Pareto最優(yōu)解集表

4 結(jié)語

本文建立了以最小化最大完工時間、最小化機器負(fù)荷、最小化總能耗為優(yōu)化目標(biāo)的綠色柔性作業(yè)車間調(diào)度問題模型。為了有效的求解該問題模型，提出了一種改進的NSGA-II算法，設(shè)計了一種非支配的初始化策略，并采用插入式的貪婪解碼策略進行解碼。采用自適應(yīng)交叉變異算子，結(jié)合IPOX交叉和MPX交叉的混合交叉方式，倒序變異和單點最小加工時間突變的混合變異方式，提高算法的搜索能力。針對傳統(tǒng)NSGA-II解集多樣性差、質(zhì)量低的問題，設(shè)計了基于分布函數(shù)的改進式精英保留策略，并通過引入一種基于最優(yōu)解的學(xué)習(xí)機制來增強算法的局部搜索能力。最后，通過兩個基準(zhǔn)測試算例對算法的性能進行了測試，并進行了決策分析，結(jié)果表明算法求解多目標(biāo)優(yōu)化問題的有效性。

未來研究將考慮不確定環(huán)境下的柔性作業(yè)車間調(diào)度問題，繼續(xù)探索多目標(biāo)優(yōu)化算法的改進策略，提高算法求解的質(zhì)量和效率。