改進樽海鞘群算法求解柔性作業(yè)車間調(diào)度問題

趙文超，郭鵬,2，王海波,2，雷坤

（1.西南交通大學 機械工程學院,四川 成都 610031;2.軌道交通運維技術(shù)與裝備四川省重點實驗室,四川 成都 610031）

先進的調(diào)度方法能夠提高生產(chǎn)效率和經(jīng)濟效益，其主要任務(wù)是在時間和資源的雙重約束下，合理、科學地對可用共享資源和生產(chǎn)任務(wù)進行分配與管理，盡可能使性能評價指標達到最優(yōu)。柔性作業(yè)車間調(diào)度問題(flexible job shop scheduling problem，F(xiàn)JSP)作為車間作業(yè)調(diào)度的延伸，突破了一道工序只能在一臺設(shè)備加工的局限，引入了設(shè)備指派決策，擴大了可行域的搜索范圍，具有更高的理論計算復雜度。FJSP 廣泛應用于航空航天、交通運輸、智能制造和運籌優(yōu)化等領(lǐng)域，因此針對FJSP 的研究具有重要理論價值和實際應用價值。

針對柔性作業(yè)車間調(diào)度優(yōu)化問題，目前主要的求解算法可以分為兩大類：精確算法和近似算法[1]。由于問題的高度復雜性，研究者大多采用智能優(yōu)化算法求解，諸如模擬退火與禁忌搜索混合算法[2]、遺傳-禁忌搜索混合算法[3]、改進迭代貪婪算法[4]等。近年來隨著計算機科學技術(shù)的不斷進步，許多新的群體智能算法不斷涌現(xiàn)，如人工免疫算法[5]、混合灰狼優(yōu)化算法[6]等。也有使用分派規(guī)則構(gòu)建啟發(fā)式算法的文獻[7]。此外針對FJSP的擴展問題，先后有文獻討論順序相關(guān)調(diào)整時間[8]、能耗約束[9]、動態(tài)事件[10-11]、多時間約束[12]等變種。盡管出現(xiàn)了大量啟發(fā)式求解策略，但求解效率依然有進一步提升的空間和基于群集智能發(fā)展高效調(diào)度框架的必要。

樽海鞘群算法在2017 年由澳大利亞學者Mirjalili等[13]提出，該算法通過模擬自然界中樽海鞘群在海洋中的覓食行為，實現(xiàn)對解空間的探索。該算法具有收斂速度快，魯棒性強且易于實現(xiàn)等顯著特點，已成功地應用于光伏系統(tǒng)優(yōu)化[14]、特征提取[15]、圖像處理[16]和生物醫(yī)學信號處理[17]等問題求解。Jia 等[18]提出了SSACL 算法，使用交叉策略和Lévy 飛行分別改進了樽海鞘群領(lǐng)導者和跟隨者的運動方式，在基準函數(shù)測試中表現(xiàn)出良好的計算性能。然而，該算法在生產(chǎn)調(diào)度領(lǐng)域的研究并不多見，且現(xiàn)有的文獻多集中于并行機調(diào)度問題的研究。Jouhari 等[19]針對不相關(guān)的并行機調(diào)度問題，利用樽海鞘群算法進行局部搜索以增強優(yōu)化器的性能并減少計算時間。Ewees 等[20]提出了一種基于螢火蟲算法的改進樽海鞘群算法來求解帶調(diào)整時間不相關(guān)的并行機調(diào)度問題。Sun 等[21]提出了將樽海鞘群算法應用于車間調(diào)度問題，結(jié)合樽海鞘群算法全局搜索框架，基于關(guān)鍵路徑設(shè)計多個鄰域算子進行局部搜索，對可重入作業(yè)車間調(diào)度問題進行了有效的求解。本文利用Lévy飛行和交叉變異算子對樽海鞘群算法進行改進，并結(jié)合局部鄰域搜索策略來求解柔性作業(yè)車間調(diào)度問題。鑒于樽海鞘群算法的優(yōu)越性，非常有必要研究其在生產(chǎn)調(diào)度領(lǐng)域的應用。

本文提出一種融合模擬退火策略的改進樽海鞘群算法求解FJSP。基于設(shè)備負載進行種群初始化，利用交叉和變異遺傳算子對個體進行改進，采用Lévy 飛行對領(lǐng)導者個體位置進行更新。為防止求解陷入局部最優(yōu)，融合模擬退火進行鄰域搜索，提升算法的全局搜索和局部搜索能力。同時，為驗證模型的準確性并為所提算法提供參考依據(jù)，采用Gurobi 數(shù)學求解器進行精確求解混合整數(shù)規(guī)劃模型。運用改進的樽海鞘群算法求解FJSP，并和其他研究文獻進行綜合對比，進一步闡明所提算法的有效性。

1 問題描述與模型構(gòu)建

1.1 問題描述

FJSP 描述如下：給出n個工件的集合J和m臺設(shè)備的集合M。每個工件i的加工工序都是確定的且不盡相同，其中工件i的第j道工序(Oij)可以在兼容設(shè)備子集Mij?M的任何設(shè)備上加工。每道工序的加工時間與所選擇的加工設(shè)備有關(guān)，每個工件都必須嚴格按照預定好的順序進行加工，且每臺設(shè)備在同一時刻只能加工一個工件。調(diào)度的目標是讓每道工序選擇最合適的加工設(shè)備，并確定每臺設(shè)備上的最佳處理順序和加工開始結(jié)束時間。因此，該組合優(yōu)化問題分為兩個子問題：1) 設(shè)備選擇問題，即為工序選擇合適的加工設(shè)備；2)工序排列問題，即確定每臺操作設(shè)備的最佳加工工序序列，以此確定兩個子問題的最優(yōu)值來使得整個調(diào)度系統(tǒng)實現(xiàn)特定的優(yōu)化目標。本文考慮最小化最大完工時間Cmax，即makespan。

此外，在建模過程中還需滿足如下約束條件：

1)工件在到達時間之前不允許加工，所有工件在零時刻都可以被加工；

2)同一工件的工序有加工順序約束，不同的工件沒有加工順序約束；

3)同一臺設(shè)備在同一時刻只能加工一個工件；

4)同一工件的同一道工序在同一時刻只能被一臺設(shè)備加工；

5)工件在某臺設(shè)備上開始加工，不允許中斷；

6)所有加工設(shè)備是連續(xù)可用的，設(shè)備的調(diào)試與設(shè)置時間可以忽略不計。

1.2 模型構(gòu)建

針對柔性作業(yè)車間調(diào)度問題，以最小化最大完工時間Cmax為目標，基于文獻[8]的模型構(gòu)建本問題的整數(shù)規(guī)劃(MIP)模型，各參數(shù)定義見表1。

表1 符號與參數(shù)Table1 Symbols and parameters

目標函數(shù)(1)最小化最大完工時間makespan。式(2)確保每道工序當且僅能指派給可用設(shè)備集中的一臺進行加工。式(3)保證同一工件相鄰工序間的先后關(guān)系。式(4)和式(5)防止在同一設(shè)備k上進行處理的工序作業(yè)時間發(fā)生重疊，當且僅當工序Oij和工序Oi′j′都分配給設(shè)備k(即zijk=zi′j′k=1)時，兩個約束方才起作用。式(4)確保當工序Oi′j′完工后處理工序Oij，則yiji′j′=0。式(5) 表示yiji′j′=1 的情況。對于其他情況，式(4)和式(5)則自動滿足。式(6)確定最大完工時間。式(7)和(8)決定兩組0、1 變量的取值。

2 樽海鞘群算法

樽海鞘群算法模擬樽海鞘的聚集行為，組成樽海鞘鏈在海底進行捕食和移動。在SSA 中，樽海鞘鏈可以分為兩類：領(lǐng)導者和追隨者，鏈的頭部是領(lǐng)導者，其余的都是跟隨者。與其他群體優(yōu)化算法類似，樽海鞘群的位置定義在多維搜索空間內(nèi)，尋找多維空間中食物源F的位置是樽海鞘群追隨的重要指標。領(lǐng)導者根據(jù)F的位置修正自身的位置，追隨者跟隨領(lǐng)導者位置變化更新自身的位置。

在樽海鞘群算法中，定義每個樽海鞘個體的位置向量X用于在N維空間中搜索，其中N為決策變量的數(shù)目。樽海鞘群算法中位置向量X將由維度為D的N個樽海鞘個體組成，其中第i個樽海鞘個體位置表示為樽海鞘個體位置為

因此，種群向量由N×D維矩陣構(gòu)成，即：

矩陣中的第一個向量為領(lǐng)導者，其余向量為追隨者。食物源F的位置是所有樽海鞘個體的目標位置。因此，領(lǐng)導者的位置更新公式為

由式(9)可知，領(lǐng)導者的位置更新與食物源的位置相關(guān)。系數(shù)c1叫做收斂因子，其定義如下：

式中：t為當前迭代次數(shù)；tmax為 最大迭代次數(shù)。

參數(shù)c2和c3是 [0,1] 區(qū)間內(nèi)均勻生成的隨機數(shù)，c2決定了在第j維空間領(lǐng)導者更新的移動步長，c3決定的是移動的方向的正反。

根據(jù)牛頓運動定律，對跟隨者的位置更新進行公式化：

式中：i≥2，表示第j維空間跟隨者的位置；v0表示初始速度；t0表示時間；a=(vfinal?v0)/t，vfinal=表示第i?1個追隨者在第j維空間跟隨者的位置。

由于時間在優(yōu)化過程中表示為迭代，所以t0=1迭代差值為1，初始速度v0=0，并且追隨者的位置更新只與它前一個樽海鞘個體位置相關(guān)，所以位置更新公式進而可以表示為

式中：i≥2，表示第i個樽海鞘個體在第j維空間的位置。根據(jù)以上個體位置更新方式，可以模擬樽海鞘群的行為機制。

3 改進樽海鞘群算法

自提出以來，SSA 算法在求解連續(xù)優(yōu)化問題得到了廣泛的應用，但在組合優(yōu)化領(lǐng)域的應用較少。因此，針對FJSP 的特點，提出一種基于離散思想的SSA，引入基于設(shè)備負載最小的選擇方案來加快算法收斂；采用交叉變異算子調(diào)整工序與設(shè)備編碼，以此擴大解的搜索空間從而加快算法的搜索效率；防止求解陷入局部最優(yōu)或者無法完全收斂，融合模擬退火策略進行局部領(lǐng)域搜索，進而得到改進離散化樽海鞘群算法(improved discretized salp swarm algorithm，IDSSA)求解FJSP。

3.1 編碼

針對FJSP 的特性，IDSSA 編碼由設(shè)備選擇部分(MS)和工序排序部分(OS)兩個向量組成，每個向量的長度均等于總工序數(shù)之和。設(shè)備選擇部分從第一個工件的第一道加工工序開始直到最后一個工件的最后一道加工工序依次分配加工設(shè)備，數(shù)字k為對應工序可選設(shè)備集內(nèi)的第k臺設(shè)備；工序排序部分中的每一維向量代表待加工工件序號，其出現(xiàn)的次數(shù)代表工件的第幾道工序。(O11,M3),(O21,M4),(O22,M4),(O12,M1),(O23,M3),(O13,M2),(O31,M3),(O32,M1)是利用二維向量編碼的個體。個體的編碼方式如圖1 所示。

圖1 IDSSA 編碼示意Fig.1 IDSSA code representation

3.2 種群初始化

種群初始化是樽海鞘群算法的重要步驟，初始解的質(zhì)量對SSA 的收斂速度和尋優(yōu)效率至關(guān)重要。在生成初始解時，不僅要保證解決方案的多樣性而且還要保證解的質(zhì)量。到目前為止，大多數(shù)文獻采用隨機初始化的方法初始化加工設(shè)備，無法保證最短時間的加工設(shè)備被選擇。因此，最初未選擇的設(shè)備將永遠不會被選擇，這使得算法僅賴于設(shè)備突變操作來選擇這些設(shè)備，但突變操作只有很小的發(fā)生概率，初始解的多樣性也就無法得到保證。FJSP 設(shè)備選擇的難點在于每一道工序選擇加工設(shè)備時，對設(shè)備而言，設(shè)備的負載變化會對加工過程中設(shè)備選擇的結(jié)果產(chǎn)生影響，因此需要考慮加工該工序后的設(shè)備負載變化。使用SSA 進行初始化時，由于沒有任何先驗知識可以參考，本文參考Kacem 等[22]提出的初始種群定位法，該方法在考慮設(shè)備的負載前提下為工序分配設(shè)備，為每一道工序的可選設(shè)備集中尋找時間表中具有最短加工時間的設(shè)備，利用該設(shè)備處理工序。然后對設(shè)備負載進行更新操作，即將前一道工序的加工時間加到同一列的其他項。

3.3 位置更新方式

SSA 中領(lǐng)導者的位置更新方式適用于求解連續(xù)函數(shù)優(yōu)化問題，無法直接用于離散問題，因此需要對更新策略進行離散化改進：

式中：Fj表示第j維食物源的位置；系數(shù)向量c1是SSA 中最重要的參數(shù)，用于平衡算法的局部搜索和全局探索，隨著迭代次數(shù)的增加逐漸變化，最后趨近于0；r為區(qū)間[0，1]的隨機數(shù)，當r<0.5，樽海鞘群個體xi j向食物源Fj趨近，相反則遠離。L為Lévy 飛行步長，可有效避免陷入局部最優(yōu)，更加快速找到全局最優(yōu)解，Lévy 飛行步長定義為

式中：μ和υ服從正態(tài)分布，其中的 σμ和συ由式(16)計算可得：

式中，Γ是gamma 函數(shù)，參數(shù) β是區(qū)間[0，2]的隨機數(shù)，一般 β=1.5。追隨者的位置更新策略是讓其有針對性的移動，找到更好的適應度位置，從而加快最優(yōu)解的搜索。追隨者的移動是由自身位置和前一個個體的位置綜合決定，對前一個個體位置有較強的依賴性。若追隨者位置陷入局部最優(yōu)，容易造成算法搜索停滯。為了更好地平衡算法的開發(fā)能力和搜索能力，引入線性遞減的慣性權(quán)重，平衡先前個體對當前個體的影響。因此，引入慣性權(quán)重的跟隨者位置更新公式為

式中：ω(s)為初始慣性權(quán)重；ω(e)為最大迭代次數(shù)時的慣性權(quán)重。初始迭代時較大的慣性權(quán)重有助于提升算法的搜索能力，迭代后期慣性權(quán)重較小時，有助于提升算法的開發(fā)能力。

SSA 算法中每個個體經(jīng)過離散化處理后，利用ROV(ranked order value)規(guī)則，分別對每個個體的工序位置向量賦予唯一的ROV 值，然后根據(jù)ROV 值即可構(gòu)造工序編碼。個體位置轉(zhuǎn)換為工序排序過程如圖2 所示，其中相同的工序編號表示同工件的不同工序，出現(xiàn)的次數(shù)代表工件的第幾道工序。

圖2 個體位置轉(zhuǎn)換為工序排序過程Fig.2 Process of converting individual positions into process sequencing

設(shè)備編碼個體的位置向量限制在[1，m] 內(nèi)，其中m為加工設(shè)備數(shù)，若計算得到的向量里元素值超過此區(qū)間，則取邊界值。經(jīng)過位置更新后，設(shè)備位置向量為小數(shù)，對其進行向上取整。位置更新后產(chǎn)生的設(shè)備編碼可能為非可行解，需要對非可行解進行修正：1)設(shè)備向量對應的工序的可選加工設(shè)備集中僅有一臺設(shè)備(即該工序僅能在一臺設(shè)備上加工)，則選擇該工序?qū)脑O(shè)備序號更新設(shè)備位置向量；2)位置更新后的某道工序選擇的設(shè)備不能加工該工序，則在該工序的可選加工集中隨機選擇一臺設(shè)備替換該設(shè)備。

3.4 交叉操作

考慮到遺傳算法有比較強的全局搜索能力[23]，融合交叉和變異算子對標準SSA 算法進行改進，以增加種群的多樣性并加快收斂速度。SSA 算法不依賴遺傳算子進化而是通過個體的位置移動來尋找問題最優(yōu)個體。引入POX 交叉算子(如圖3所示)在OS 部分操作方式如下：

圖3 工序編碼的交叉操作Fig.3 Cross operation of process code

1)生成一個從1 到工件數(shù)的隨機整數(shù)R；

2)父代個體P1將工件序號小于或等于R的工件復制給子代個體C1；父代個體P2將工件序號大于R的工件復制給子代個體C2，保留其位置，并將對應的設(shè)備號復制到相應位置；

3)復制父代P1未出現(xiàn)在子代C2的工件序號到C2，復制父代P2未出現(xiàn)在C1的工件序號到子代C1，并保留其順序，同時復制設(shè)備號到對應位置。

位置更新過程中從子代C1和子代C2中隨機選擇一個作為后代，POX 交叉過程使子代保留父代在每臺設(shè)備的加工次序，并保留部分工件的位置。

交叉算子在MS 部分操作如下：針對設(shè)備選擇部分，采用兩點交叉的方法，對于選定的兩個父代個體，隨機設(shè)置兩個交叉點，交換所設(shè)定的兩個交叉點之間的父代個體都有的工序所對應的設(shè)備序號。

3.5 變異操作

變異操作目的是為了增加種群多樣性，改善算法的尋優(yōu)能力。FJSP 的變異操作后需要保證變異后解的可行性。和交叉操作一樣，分別基于OS 和MS 進行變異操作。設(shè)計變異算子時，引入關(guān)鍵路徑的思想。FJSP 的一個可行解可用有向圖來表示，其中從有向圖起點到終點的最長路徑稱為關(guān)鍵路徑。關(guān)鍵路徑直接影響調(diào)度方案的最大完工時間。關(guān)鍵路徑上的關(guān)鍵工序也稱作關(guān)鍵工序，通過對關(guān)鍵工序進行擾動，有可能會減少最大完工時間。圖4 為圖1 對應的甘特圖，其中陰影部分為關(guān)鍵工序。

圖4 基于關(guān)鍵路徑甘特圖Fig.4 Gantt chart based on the critical path

在滿足加工優(yōu)先級約束前提下，尋找關(guān)鍵路徑上的所有關(guān)鍵塊，隨機選擇關(guān)鍵塊為移動源，選擇不相鄰的工序為移動點，向前或向后插入移動源，其余工序依次向前或向后改變位置，如圖5 所示。

圖5 關(guān)鍵工序鄰域結(jié)構(gòu)示意Fig.5 Diagram of neighborhood structure of key processes

對OS 部分的變異操作引入基于關(guān)鍵路徑的變異算子，將變異位置的選擇縮短到關(guān)鍵路徑上。具體操作過程為隨機選擇一道關(guān)鍵工序，滿足工序加工優(yōu)先級約束的前提下，將它插入到緊鄰的前一道關(guān)鍵工序的某個位置，同時將相應的設(shè)備分配同步前移或者后移。圖6 為選中關(guān)鍵工序O31的情況，并將其插入在另外一道關(guān)鍵工序O22之前。

圖6 工序編碼的關(guān)鍵工序變異操作Fig.6 Key process mutation operation for process coding

對MS 部分的變異操作為隨機選擇一道關(guān)鍵工序，在選擇的關(guān)鍵工序可行加工設(shè)備集中選擇加工時間最少的設(shè)備替換當前加工設(shè)備。這種選擇方式增加種群的多樣性，擴大解的搜索范圍。

3.6 局部鄰域搜索策略

采用上述編碼和位置更新方式，有效地提高算法求解效率和收斂速度，但同時容易陷入局部最優(yōu)解或無法完全收斂。SA 算法具有較強的鄰域搜索能力，將SA 算法與IDSSA 算法相結(jié)合可以有效提升算法的全局搜索和局部搜索能力，進而提升算法性能。本文基于設(shè)備負載的變異方式產(chǎn)生鄰域解，具體流程如下：尋找所有加工設(shè)備中工作負載最大的設(shè)備，并在設(shè)備對應加工工序中隨機選擇一道工序，在考慮工序的優(yōu)先級約束前提下將其分配到可選設(shè)備集中負載最小的設(shè)備。融合SA 算法只對MS 向量進行調(diào)整，讓OS向量匹配到更合適的設(shè)備，從而平衡了設(shè)備工作負載。但同時會增加搜索時間，因此本文在初始種群中隨機選擇部分個體進行局部鄰域搜索，增加種群的多樣性。

3.7 IDSSA 流程

IDSSA 算法流程具體步驟如下：

1)初始化參數(shù)，根據(jù)3.2 節(jié)的初始定位法生成初始解，并隨機化食物源F的位置。

2)計算個體的目標函數(shù)值，將算法最優(yōu)適應值為迭代過程中最佳的計算結(jié)果。

3)根據(jù)改進的位置更新公式分別對樽海鞘領(lǐng)導者和跟隨者的位置進行更新。引入慣性權(quán)重對追隨者個體位置進行優(yōu)化，并記錄當前種群中最優(yōu)食物源的位置。

4)利用交叉、變異算子分別對個體的工序向量和設(shè)備向量進行交叉操作，增加可行解的搜索范圍。

5)更新算法相關(guān)參數(shù)。

6)判斷是否達到最優(yōu)目標值，若新解的目標函數(shù)值優(yōu)于當前解，則更新最優(yōu)解并將其輸出，否則采用SA 算法，隨機選擇部分個體進行局部鄰域搜索。

7)判斷是否滿足終止條件，即是否達到最大迭代次數(shù)。若滿足，則跳轉(zhuǎn)到8)，反之，執(zhí)行2)。

8)算法結(jié)束。

4 計算結(jié)果與分析

為了測試IDSSA 算法在解決全局優(yōu)化問題中的效果，將IDSSA 算法和Jia 等[18]提出的SSACL算法、標準SSA 算法進行計算對比。IDSSA 算法利用Lévy 飛行改進領(lǐng)導者更新方式，在追隨者更新公式上引入自適應慣性權(quán)重，利用交叉、變異策略增加種群多樣性，并加入鄰域搜索進一步改善算法的局部尋優(yōu)能力。

采用CEC2005 的10個基準測試函數(shù)，選取的測試函數(shù)包含單峰和多峰兩種類型函數(shù)，其中單峰函數(shù)在定義上下限區(qū)間內(nèi)只有一個全局最優(yōu)，因此可以測試算法的開拓能力；多峰函數(shù)在定義區(qū)間含有多個全局最優(yōu)和局部最優(yōu)解，可以測試算法的全局搜索能力。函數(shù)的維度、定義域、理論最優(yōu)解和類型如表2 所示。

表2 基準函數(shù)Table2 Benchmark functions

為了對比的公平性，將算法的參數(shù)和SSACL算法設(shè)置一致：種群大小為30，迭代次數(shù)為500。為了避免隨機誤差的影響，每個測試函數(shù)獨立運行30 次。計算對比數(shù)據(jù)如表3 所示，表中每個測試函數(shù)的適應度均值和標準差分別反映了不同算法的收斂精度和穩(wěn)定性。

對于表3 中的測試函數(shù)，SSACL 算法和IDSSA算法比標準SSA 算法尋優(yōu)結(jié)果都要好。在求解精度上，IDSSA 算法有4個基準函數(shù)計算結(jié)果表現(xiàn)最好；就算法測試函數(shù)的平均值和標準差而言，IDSSA 算法也表現(xiàn)出良好的計算優(yōu)勢，表明對標準SSA 算法進行改進有效地提升了算法性能。

表3 基準函數(shù)優(yōu)化結(jié)果對比Table3 Comparison of optimization results of benchmark functions

在驗證IDSSA 求解FJSP 的改進效果和有效性方面，本文采用國際通用的10個Brandimarte基準算例、Fattahi 提出的20個基準算例進行對比分析。Brandimarte 算例中，工件數(shù)量n從10 到20，設(shè)備數(shù)量m從4 到15 進行組合選取，每組算例中的工序數(shù)從5 到15；Fattahi 算例中，工件數(shù)量n從2 到12，設(shè)備數(shù)量m從2 到8 進行組合選取，每組算例中的工序數(shù)從2 到4。使用Python3.6實現(xiàn)算法。計算機硬件配置為英特爾i56400 CPU(2.70 GHz)、8 GB RAM，在Windows 10 的操作系統(tǒng)下運行程序。

4.1 算法參數(shù)選取

參數(shù)設(shè)置對算法性能有很大的影響，參數(shù)選取標準是通過解的質(zhì)量和算法運行時間來衡量，文中利用Brandimate 提出的算例Mk01 結(jié)果來確定算法參數(shù)。以解的平均偏差和平均運行時間為基準，經(jīng)過多次計算從而確定相關(guān)參數(shù)。本文所提的IDSSA 主要包括 β、T0、μ、ω(s)、ω(e)和Tlim等6個參數(shù)。基于計算結(jié)果，參數(shù) β設(shè)置為1.5；初始溫度T0和冷卻系數(shù) μ分別被設(shè)置為100 和0.95；利用Gurobi 求解限制時間為Tlim=1 200 s；經(jīng)過正交實驗后確定 ω(s)=0.9，ω(e)=0.4 時算法具有最佳性能。

4.2 結(jié)果分析

為了更好評估融合交叉與變異算子的IDSSA算法的有效性和穩(wěn)定性，選取Brandimate 提出的算例Mk01 進行測算。收斂曲線如圖7(a)所示，通過觀察IDSSA 算法與不含交叉變異操作的改進SSA 算法的收斂曲線，發(fā)現(xiàn)引入交叉與變異算子的I D S S A 算法收斂曲線下降更快。較之SSA 算法，IDSSA 算法收斂速度和穩(wěn)定性得到進一步改善。同時，為驗證局部鄰域搜索策略的有效性，同樣選取算例Mk01 進行測算。收斂曲線如圖7(b)所示，將IDSSA 算法與不含局部搜索策略的改進SSA 算法進行對比發(fā)現(xiàn)，IDSSA 算法表現(xiàn)出了更高的搜索精度。

圖7 IDSSA 與SSA 的收斂曲線比較Fig.7 Comparison of IDSSA and SSA convergence curves

為驗證所提MIP 模型的正確性并給所提算法運算結(jié)果提供對比參考，采用Brandimarte 基準算例[24]進行測試，運用Gurobi 8.1.1 進行精確求解。為了達到性能評價的目的，在本文所提算法和HGWO 算法[6]、Heuristic 算法[7]以及后續(xù)對比算法的參數(shù)設(shè)置上選擇了最佳的、相同的參數(shù)配置以保證了算法的可比性。由于問題的難求解性，處理MIP 模型時將Gurobi 時間限定為1 200 s，若求解時間未超過1 200 s，則輸出解為最優(yōu)解。除此之外，還采用Fattahi 基準算例進行對比，并與文獻中的算法進行對比，包括HTS/SA 算法[2]、MIG算法[4]、AIA 算法[5]。

比較本文提出算法與其他文獻算法相較當前最優(yōu)解的相對百分偏差RPD(relative percent deviation)，計算公式為

其中對于每個算例，UB表示當前算例目前最佳目標函數(shù)值，Cmax表示當前算例求解的最大完工時間。

表4 為Brandimarte 基準算例測試結(jié)果。表4中n×m表示對應算例的工件數(shù)和設(shè)備數(shù)。ARPD表示當前算法的相對百分偏差平均值(%)。CPU表示算法運行時間，s。為了排除誤差的影響，更加準確地對比所提算法的可行性和有效性，將每個算例運行10 次。可以看出所提出的MIP 在求解較小規(guī)模算例得到了令人滿意的解，在求解較大規(guī)模算例陷入局部最優(yōu)，不能在有效的時間內(nèi)得到較優(yōu)解。本文所提出的IDSSA 和其他參考文獻提出的算法相比，計算結(jié)果中9個算例優(yōu)于Heuristic，相比HGWO 存在較大的優(yōu)勢。相較當前最優(yōu)解的平均偏差來看，IDSSA 和其他算法相比偏差值最小，即從整體上來看，所提出的IDSSA 優(yōu)于MIP 和參考文獻[6-7]所提出的其他兩種算法。

表4 Brandimate 算例計算結(jié)果對比Table4 Comparison of calculation results of Brandimate instances

續(xù)表4

表5 給出了本文算法在Fattahi 測試集上的性能，對比方法有HTS/SA[2]、AIA[4]、MIG[5]等。在較小規(guī)模算例上，表中列舉算法求解性能差異不大，而在較大規(guī)模算例(即MFJS9 和MFJS10)上，本文算法顯示出良好的求解性能。圖8 為IDSSA算法求解問題MFJS9 輸出結(jié)果的甘特圖。

圖8 MFJS9 調(diào)度甘特圖Fig.8 MFJS9 scheduling Gantt chart

表5 Fattahi 算例計算結(jié)果對比Table5 Comparison of calculation results of Fattahi instances

5 結(jié)束語

本文在標準樽海鞘群算法的基礎(chǔ)上，提出了一種融合模擬退火算法的改進樽海鞘群算法。基于Lévy 飛行對領(lǐng)導者的位置更新方式進行離散化改進，引入自適應慣性權(quán)重對追隨者的位置進行移動，平衡算法的開發(fā)能力和搜索能力。建立問題的混合整數(shù)規(guī)劃模型并利用標準算例檢驗算法的性能，結(jié)果表明：改進的樽海鞘群算法在求解單目標柔性業(yè)車間問題取得了比較好的結(jié)果，算法的魯棒性和有效性得到了驗證。同時，本文為連續(xù)化SSA 算法進行離散化求解工程實際問題提供了一種可行的改進方式。

下一步還將開展算法的計算時間復雜度理論分析及算法的收斂特性理論證明相關(guān)工作。同時，深入分析FJSP 的問題特征，在實際的生產(chǎn)作業(yè)中，存在著物料組成、工人技能、設(shè)備資源受限等諸多約束條件，考慮將改進的樽海鞘群算法應用到更加復雜的工程實踐問題當中，進一步驗證算法的性能。