李敬花，閆恒山，楊博歆+，周青驊

(1.哈爾濱工程大學 機電工程學院，黑龍江 哈爾濱 150001；2.哈爾濱工程大學 船舶工程學院，黑龍江 哈爾濱 150001)

0 引言

海洋平臺從零部件加工到組立、搭載，涉及數(shù)以萬計的中間產(chǎn)品和相關裝備，以我國第七代鉆井平臺“藍鯨1號”為例，其鋼板原料重達42 000 t，擁有27 354臺設備及40 000多根管路，建造和進度管理難度較大[1]。制造車間是海工裝備和中間產(chǎn)品的主要加工場所，車間調度的準確性直接影響到中間產(chǎn)品生產(chǎn)節(jié)拍甚至平臺的完工交付時間，若建造進度與預期方案不符，將會給企業(yè)帶來嚴重損失[2]。在實際應用層面，我國海工企業(yè)在車間調度環(huán)節(jié)大量依靠人工進行決策調度，效率和準確性低；在理論研究層面，目前鮮有學者對海工裝備制造車間調度問題進行研究。因此，有必要對海工裝備制造車間調度方法進行研究，采用智能化方法代替或輔助調度人員進行決策，提高車間調度準確性。雖然海工裝備中間產(chǎn)品種類及加工工藝比較復雜，但是以各種型材和管件為代表的工件采取流水線加工形式，工藝流程明確且每道工序中存在若干臺并行加工設備，屬于混合流水車間調度問題(Hybrid Flow Shop Problem, HFSP)，本文主要研究此類構件的加工調度問題。

目前，針對HFSP的研究主要集中在機械、線纜、石化、玩具加工等行業(yè)。如陳超等[3]構建了帶有阻塞重型機械加工車間HFSP模型，并運用遺傳算法(Genetic Algorithm, GA)解決了某電信通信塔制造廠實例問題；汪和平等[4]采用改進初始解的NSGA-Ⅲ對建筑工程項目預制構件的生產(chǎn)調度問題進行了優(yōu)化；王春等[5]針對以某玩具廠工模車間調度問題，引入虛擬工序和虛擬工時概念，并使用混合調度策略進行了實例驗證；賈葉玲等[6]設計了一種改進遺傳算法，解決了某船類零件制造企業(yè)混合流水車間環(huán)境下的成套訂單問題；魯佳俊等[7]提出一種基于果蠅優(yōu)化算法的求解框架，解決了船舶管加工車間多目標生產(chǎn)調度問題。總體而言，目前缺少關于海工裝備制造車間調度問題的研究，其原因主要有兩方面：①海工裝備制造屬于大型結構與設備制造行業(yè)，自動化和標準化程度低，應用場景有限；②與常規(guī)的HFSP相比，海工裝備制造車間調度問題具有約束條件較多且復雜度大的特點，具體表現(xiàn)為：

(1)采取準時制生產(chǎn)方式(Just In Time, JIT)，加工和完工時間具有不確定性；

(2)工件在相鄰工序之間的轉移時間不可忽略；

(3)重點考慮實際完工時間與計劃完工時間的吻合程度而非最早完工時間；

(4)每臺設備對不同工件加工速度不同，屬于不相關并行機；

(5)部分工件需要在特定的設備上完成加工。

文獻研究表明，目前多數(shù)針對HFSP的研究只是部分考慮了上述約束條件。如FATTAHI等[8]在研究中考慮了工件裝配時間影響，但其將加工時間預設為確定值，并未考慮工期不確定性因素；?ZTOP等[9]在建立HFSP模型時考慮了能源消耗和環(huán)境影響，LU等[10]考慮了車間噪聲污染因素，提出一種嵌入了節(jié)能/降噪策略的HFSP模型，但是兩者均未考慮工件轉移時間影響；WANG等[11]研究了考慮設備動態(tài)調整操作的HFSP，但其假定加工設備是完全柔性的，并未考慮特定加工設備約束;袁慶欣等[12]研究了帶有限緩沖區(qū)的HFSP，并考慮了工件運輸時間約束；XING等[13]研究了考慮能耗和設備維護的HFSP，但兩者均以最小化最大完工時間為工期優(yōu)化目標，未考慮提前和拖期影響;NABLI[14]等研究了存在特定設備約束的兩階段HFSP，但并未考慮其他因素影響。與常規(guī)問題不同，海工裝備制造車間調度需要綜合考慮上述所有約束條件進行建模和求解，屬于FHFSP-UPM&SM(fuzzy hybrid flow shop problem with unrelated parallel machine and specific machine)問題，其復雜度和求解難度更大。

HFSP是一類NP-hard組合優(yōu)化問題，遺傳算法(GA)因其具有的交叉、變異等離散組合操作而廣泛應用于車間調度問題的求解。遺傳算法雖然并行搜索能力好、健壯性強，但也存在局部搜索能力不強、容易陷入局部最優(yōu)的缺陷，因此現(xiàn)有研究大多將其與其他方法相結合以提高求解效果。如ZHAO等[15]設計了一種基于并行順序移動和可變變異概率的改進遺傳算法，用于求解HFSP，提高了算法收斂速度；于蒙等[16]將粒子群算法與GA結合，形成GA-PSO混合算法，提高了算法搜索效率；軒華等[17]針對可重入HFSP，在標準GA基礎上使用NEH啟發(fā)式算法產(chǎn)生工件初始加工順序，提高了解的質量。

和聲搜索(Harmony Search, HS)模擬了樂隊中樂師憑借記憶反復調整樂器音調，最終使音調達到穩(wěn)定諧和狀態(tài)的過程，其利用個體局部信息和群體全局信息指導算法進行搜索，通用性好且與其他算法結合可以有效改善算法整體的收斂性[18]。由于其操作簡單，被應用到多個領域當中[19]。在車間調度領域，包云等[20]提出一種融入了和聲搜索的混合遺傳算法，用于求解阻塞流水車間調度問題；吳龍成等[21]針對硫化車間調度過程中機臺利用率及生產(chǎn)效率低的問題，提出一種改進離散和聲搜索算法，對最大完工時間進行了優(yōu)化；向雙玲等[22]對新和聲產(chǎn)生方式進行了改進，提出了改進和聲搜索算法并應用到柔性作業(yè)車間問題求解過程中。由于本文采用矩陣編碼方式比常規(guī)的實數(shù)串編碼更為復雜，若在GA基礎上融入其他方法，如粒子群算法、變鄰域搜索等，會大幅增加算法復雜度，因此使用和聲搜索算法以避免由算法整體復雜度過大而導致的求解效率低下問題。

綜上，本文主要工作以及創(chuàng)新點包括：

(1)模型方面 同時考慮模糊時間、工件轉移時間、不相關并行機、特定加工設備等多個約束，以交貨期與完工時間吻合度為優(yōu)化目標構建了海工裝備制造車間調度模型。

(2)算法改進方面 使用NSlope啟發(fā)式算法代替隨機方法進行種群初始化，以改善初始種群質量；采用基于線性排序和精英保留策略的選擇算子來克服輪盤賭策略容易早熟的弊端；采用基于工件索引的循環(huán)交叉和基于工序的多點交叉兩種算子進行基因交換，并引入禁忌搜索策略以保證種群基因的充分交流；基于自適應變異概率，使用多點替換變異和單點逆轉變異兩種算子使算法后期跳出局部最優(yōu)，最終形成改進遺傳—和聲搜索算法，用于海工裝備制造車間調度問題求解。

1 帶有模糊時間和特定設備約束的HFSP 模型建立

1.1 模型假設

(1)所有設備在零時刻均處于可用狀態(tài)；

(2)任一工件必須遍歷所有工序；

(3)同一臺設備的兩個相鄰待加工工件之間不存在等待時間；

(4)不考慮阻塞，工件完工后可立即離開當前設備；

(5)不考慮設備損壞、工件插入等干擾事件，視為靜態(tài)調度過程。

1.2 附加條件及約束

1.2.1 模糊加工/轉移/交貨時間

海工裝備中間產(chǎn)品的加工時間、轉移時間以及交貨期都不是確定值，因此本文采用三角模糊數(shù)(Triangular Fuzzy Number, TFN)對上述3種時間參數(shù)進行描述。另外，為了對加工時間和轉移時間進行運算，需要定義TFN的運算規(guī)則?，F(xiàn)假設有一對TFN:p1=(a1,b1,c1)、p2=(a2,b2,c2)用來表示模糊完工時間，則a,b,c分別表示最早完工時間、期望完工時間以及最晚完工時間，其運算規(guī)則及作用如表1所示。

表1 三角模糊數(shù)運算規(guī)則及其作用

1.2.2 不相關并行機與特定加工設備約束

根據(jù)HFSP每道工序并行機類型的差異，可分為同速并型機(Identical Parallel Machine, IPM)、異速并行機(uniform parallel machine)和不相關并行機(Unrelated Parallel Machine, UPM)三種[23]。本文問題模型中的加工設備均為不相關并行機，即同一臺設備對不同工件的加工時間均不同，因此工件選擇不同的加工設備均會對調度結果產(chǎn)生影響，相比另外兩類問題，解空間和尋優(yōu)難度更大。

在經(jīng)典的HFSP中，工件在某道工序內(nèi)可以任意選擇加工設備，而在海工裝備中間產(chǎn)品制造過程中，會存在部分對加工精度、質量等有特殊要求的工件，此類工件須使用特定設備(Specific Machine, SM)進行加工，因此需要在模型建立階段引入相應的特定加工設備約束條件，使模型符合實際加工要求。盡管特定加工設備約束會使問題的解空間減小，但算法每一步尋優(yōu)操作產(chǎn)生的結果都必須滿足該條件，因此對算法設計和約束處理提出了更高的要求。

1.3 FHFSP-UPM&SM模型

模型相關參數(shù)含義及說明如表2所示。

表2 模型參數(shù)定義及說明

由于海工裝備制造車間調度的目的是使中間產(chǎn)品完工時間和計劃交貨時間吻合度最高，本文以模糊加工時間對模糊交貨期的“一致指數(shù)(Agreement Index, AI)”[24]作為優(yōu)化目標。FHFSP-UPM&SM數(shù)學模型如下：

(1)

s.t.

(2)

j=1,2,…,w,k∈kj;

(3)

lk=1,2,…,hk;

(4)

j=1,2,…,w;

(5)

i1,i2=1,2,…,n,j=1,2,…,w且i1≠i2,

k∈kj,r=l+1,A=+∞;

(6)

j=1,2,…,w-1,r=j+1;

(7)

(8)

2 改進遺傳—和聲搜索算法

基于遺傳算法以及和聲搜索算法的優(yōu)點，本文將兩者結合，利用遺傳算法進行全局尋優(yōu)，利用和聲搜索進行局部強化尋優(yōu)。改進遺傳—和聲搜索算法(Improved GA Harmony Search algorithm, IGA-HS)算法整體流程如圖2所示。

IGA-HS算法具體步驟如下：

步驟1設置參數(shù)。包括種群規(guī)模、交叉概率、變異概率、和聲搜索相關參數(shù)、停止準則等。

步驟2使用NSlope算法生成初始種群。

步驟3計算個體適應度值，根據(jù)適應度值對個體進行升序排列，并對個體逐一編號。

步驟4選擇操作。根據(jù)線性排序策略選出下一代種群。

步驟5交叉操作。根據(jù)交叉概率以及禁忌搜索策略，分別執(zhí)行循環(huán)行交叉和多點列交叉。

步驟6變異操作。根據(jù)變異概率選擇種群中的個體，并隨機選擇工序和機器，分別進行重新生成和列表逆轉操作。

步驟7和聲搜索。對當前種群進行若干次和聲搜索操作，用適應度值更高的個體替換種群中的最劣個體。

步驟8判斷是否滿足算法停止準則，若是則停止，輸出結果；否則，轉步驟3。

下面給出算法詳細設計過程。

2.1 編碼解碼方式

車間調度問題通常采用實數(shù)串編碼、矩陣編碼等形式。實數(shù)串編碼雖然易于理解，但是其將加工信息分解為若干實數(shù)串，導致信息密度較低且操作繁瑣。為了精確操控工件和加工機器的對應關系，本文采用矩陣編碼形式。其中，矩陣行表示工件編號，列表示加工設備，用矩陣元素是否為空來表示工件是否在某一設備上加工，矩陣元素大小表示其在該設備上的加工順位。以3道工序，每道工序3臺設備，共5個工件的加工過程為例，個體編碼如圖3所示。

由上述規(guī)則可知，在第一道工序中，工件2和工件5使用1號設備加工，工件5加工順位排在工件2之后；工件1和工件3使用2號設備加工，工件3加工順位排在工件1之后；工件4使用3號設備加工。當矩陣元素相等時，可按照工件序號大小排序，由此可得到工件加工計劃。

2.2 種群初始化方法

使用GA求解車間調度問題時，種群初始化操作主要有兩種方式：隨機生成和啟發(fā)式方法[25]。目前，在車間調度算法研究中常用NEH(Nawaz, Enscore, Ham)算法來產(chǎn)生初始種群，以提高初始解的質量，本文使用Slope算法[26]進行種群初始化操作。Slope算法是解決置換流水作業(yè)問題的一種重要的啟發(fā)式算法，該算法通過計算工件的傾斜值來為工件排序，主要原理為：若某工件在上游設備上的加工時間較短，而在下游設備上的加工時間較長，則其加工順序應當靠前，反之加工順序靠后。因此，當工件在上游設備上的加工時間較短而在下游設備上的加工時間較長，其傾斜值應該較大，反之傾斜值較小。本文基于上述原理，考慮交貨時間因素，提出一種新的Slope算法(New Slope, NSlope)用來生成初始種群，具體步驟如下：

步驟1設定種群規(guī)模N。

步驟2從每道工序中隨機選擇一臺設備，形成加工設備序列。根據(jù)序列中的m′臺加工設備，計算工件的傾斜值來為工件降序排序，產(chǎn)生初始工件序列，一個工件i的傾斜值Ai定義為：

(9)

步驟3在第一道工序中，按照初始工件序列依次為工件隨機選擇加工設備；對于后續(xù)工序，按照工件到達的先后順序為各個工件隨機安排加工設備，最后為存在特定加工設備約束的工件選擇設備，直到生成完整個體。

步驟4判斷種群規(guī)模是否達到N，若是則結束；否則重復步驟2和步驟3，直到產(chǎn)生完整的初始種群NP。

2.3 基于線性排序和精英保留策略的選擇算子改進

傳統(tǒng)的輪盤賭選擇策略存在個體適應度為零時不會被選擇到下一代的缺陷，且當個體適應度值較大時容易被多次重復選擇，進而導致種群多樣性降低、算法快速早熟。因此，本文采用基于線性排序策略的選擇算子來改善上述缺陷。具體選擇方法為：首先根據(jù)適應度值進行升序排序，然后賦予個體相應的序號，最佳個體序號為N，其被選概率為Pmax；最差個體序號為1，被選概率為Pmin，則個體i被選概率

Pi=Pmin+(Pmax-Pmin)(i-1/N-1)。

(10)

另外，為防止種群中的精英個體在后續(xù)遺傳操作中被破壞，采取精英保留策略對每代適應度值最大的個體進行保留，不參與后續(xù)遺傳操作。

2.4 基于禁忌搜索策略的交叉算子改進

本文采用的矩陣編碼存在行、列兩個維度，因此需要分別進行行交叉和列交叉操作。

(1)基于工件索引的循環(huán)交叉(CX)

具體步驟為：

步驟1對于兩個交叉?zhèn)€體工件索引A和B，A保持不變，將B亂序排列。

步驟2在A中隨機選擇一個起始點位，然后找到B中對應點位上的索引編號，再回到A中找到相同編號的索引的位置。

步驟3重復步驟2中的點位尋找方式，直到形成一個閉環(huán)，環(huán)中所有位置即為選中的交叉點位，最后將對應點位的基因互換。

操作方法如圖4所示：

(2)基于工序的多點列交叉(MPX)

由于單列交叉在操作前后可能會出現(xiàn)同道工序內(nèi)多臺設備加工同一工件或者加工設備缺失的情況，需要頻繁進行約束操作。因此本文采用多列交叉形式，對某道工序對應的所有列進行整體交叉，在保證交叉操作的同時減少約束處理步驟，提高算法執(zhí)行效率，如圖5所示。

同時，為了避免個體重復交叉以提高搜索效率，這里引入禁忌表。首先將種群中的個體進行編號，假設有兩個個體A、B，A的禁忌表為listA，在完成交叉操作后將B的個體編號計入禁忌表listA=[B]，短期內(nèi)使A與B不再進行交叉操作，禁忌表的長度可視種群規(guī)模而定，如NP/4。

2.5 變異算子改進

針對本文所使用的矩陣編碼，算法在執(zhí)行過程中隨機采用以下兩種變異算子，分別為：

(1)多點替換

多點變異操作首先隨機選定一個工序，然后找出所有此工序對應的列并重新生成該工序內(nèi)的工件和加工設備組合，替換原有工序，如圖6所示。

(2)單點逆轉

單點逆轉變異操作包括行變異和列變異。首先確定變異位置，將該行(列)非空值按照編號順序依次取出存入一個列表，并將列表內(nèi)元素順序逆序排列，最后按現(xiàn)有順序依次放回矩陣對應位置，單點逆轉操作如圖7所示。

為了使算法后期能夠跳出局部最優(yōu)，采用一種自適應變異概率。首先設定最大變異概率Pmax及最小變異概率Pmin，并使變異概率隨著遺傳代數(shù)gen的變化逐漸遞增，則個體i的變異概率Pi計算公式如下：

Pi=Pmin+(Pmax-Pmin)(gen/GEN+1)。

(11)

式中GEN為遺傳總代數(shù)。

2.6 和聲搜索

為增強算法的局部搜索能力，避免算法過早收斂，在選擇、交叉、變異操作后進行和聲搜索，對種群進行局部更新，和聲搜索的具體步驟如下：

步驟1確定參數(shù)，包括記憶庫選擇概率(Harmony Memory Considering Rate, HMCR)、調整概率(Pitch Adjusting Size, PAR)和最大搜索次數(shù)Tmax。

步驟2以當前種群為和聲記憶庫，產(chǎn)生0～1間的隨機數(shù)rand_1，若rand_1

步驟3產(chǎn)生0～1間的隨機數(shù)rand_2，若rand_2

步驟4比較新個體適應度值fitness_new和種群中最差個體的適應度值fitness_bad，若fitness_new>fitness_bad，則用新個體代替種群最差個體，執(zhí)行步驟5。隨著遺傳代數(shù)的增加，種群內(nèi)個體會逐漸趨于一致。當所有個體都相同時，fitness_new可能會恒小于fitness_bad，進而陷入死循環(huán)。為避免這種情況，設置最大執(zhí)行次數(shù)Lmax，當fitness_new連續(xù)Lmax次不大于fitness_bad時，直接用新個體代替種群最差個體，否則返回步驟2。

步驟5判斷是否達到最大搜索次數(shù)Tmax，若是則結束，否則返回步驟2。

3 數(shù)值實驗與分析

為驗證所提算法的實用性及性能，依次進行以下3組數(shù)值實驗：

(1)NSlope初始化方法測試 分別采用隨機方法與NSlope啟發(fā)式方法生成初始種群，并比較兩種方法產(chǎn)生的初始種群的質量，進而驗證NSlope啟發(fā)式方法的有效性。

(2)算法性能對比測試 選用相同的車間調度測試算例，將IGA-HS算法與改進遺傳變鄰域搜索算法、混合粒子群遺傳算法以及改進候鳥優(yōu)化算法進行比較，進而評價IGA-HS算法的性能。

(3)車間實例數(shù)據(jù)測試 采用IGA-HS以及另外三種對照方法對車間實例數(shù)據(jù)進行調度，為評價IGA-HS算法的實用性提供依據(jù)。

3.1 實驗1：NSlope初始化方法測試

為測試NSlope啟發(fā)式算法對初始種群質量的影響，進行種群初始化對比實驗。實驗1以NADERIA等[27]提出的“n20k4m3422”為基準，生成不相關并行機算例進行實驗，另外設置交貨期窗口以保證與本文FHFSP-UPM&SM模型的一致性。其中n表示工件數(shù)量，k表示表示工序數(shù)量，m表示每道工序的加工設備數(shù)量，“n20k4m3244”表示該問題為20個工件，共4道工序，每道工序的設備數(shù)依次為3、2、4、4。將NSlope啟發(fā)式算法和隨機方法兩種初始化方法進行對比，進行20次種群生成實驗，結果如表3所示。

表3 NSlope啟發(fā)式算法對比實驗結果

表3中：R表示隨機方法，N表示NSlope啟發(fā)式方法；ave表示種群加權AI平均值，best表示種群加權AI最佳值的平均值。由實驗1結果可知，在20次實驗中，R_ave的平均值為0.022，N_ave的平均值為0.032，則NSlope啟發(fā)式算法產(chǎn)生的初始解平均值的整體質量更高；R_best的平均值為0.275，N_best的平均值為0.331，則NSlope啟發(fā)式算法產(chǎn)生的初始解最佳值的整體質量更高。因此，相比隨機策略，NSlope啟發(fā)式算法在初始種群初始化方面更有優(yōu)勢。

3.2 實驗2：算法性能對比測試

表6 基于n20k4算例的4種算法測試結果

在表6的10組算例中，IGA-HS求得了5組最好解，3項指標在10組算例下的平均值分別為：0.19、27.5%、27.9%；IGA-VNS求得了2組最好解，3項指標在10組算例下的平均值分別為：0.14、33.4%、35.5%；IPSO-GA求得了1組最好解，3項指標在10組算例下的平均值分別為：0.12、40.5%、35.2%，MBO求得了2組最好解，3項指標在10組算例下的平均值分別為：0.14、41.0%、29.6%。因此,在該組算例下，IGA-HS算法的性能表現(xiàn)優(yōu)于其余3種算法。

表7 基于n20k8算例的4種算法測試結果

在表7的10組算例中，IGA-HS求得了7組最好解，3項指標在10組算例下的平均值分別為：0.20、26.5%、28.8%；IGA-VNS求得了2組最好解，3項指標在10組算例下的平均值分別為：0.14、26.8%、41.2%；IPSO-GA求得了0組最好解，3項指標在10組算例下的平均值分別為：0.09、36.3%、42.1%，MBO求得了1組最好解，3項指標在10組算例下的平均值分別為：0.12、36.7%、33.2%。因此,在該組算例下，IGA-HS算法的性能表現(xiàn)優(yōu)于其余3種算法。

表8 基于n50k4算例的4種算法測試結果

續(xù)表8

在表8的10組算例中，IGA-HS求得了10組最好解，3項指標在10組算例下的平均值分別為：0.15、32.5%、30.4%；IGA-VNS求得了0組最好解，3項指標在10組算例下的平均值分別為：0.07、30.4%、53.1%；IPSO-GA求得了0組最好解，3項指標在10組算例下的平均值分別為：0.07、58.3%、20.2%；MBO求得了0組最好解，3項指標在10組算例下的平均值分別為：0.08、44.5%、33.5%。因此,在該組算例下，IGA-HS算法的性能表現(xiàn)高于其余3種算法。

若用工序數(shù)與工件數(shù)的乘積表示3組算例的復雜程度，則4種方法求得的加權AI、提前率adv與延誤率del之和隨算例復雜程度的變化情況如圖8所示。由圖8可知，4種方法得到的加權AI(實線部分)總體上呈現(xiàn)遞減趨勢，提前率adv與延誤率del之和(虛線部分)總體上呈現(xiàn)遞增趨勢，表明隨著算例復雜程度的增加，算法求解效果有不同程度的降低；GA-VNS、IPS-GA和MBO曲線較為接近，三者求解效果相當；而IGA-HS對應曲線與另外3種方法有明顯區(qū)分且結果更優(yōu)，因此求解效果最好。

3.3 實驗3：車間實例數(shù)據(jù)測試

為進一步測試算法對實際調度案例的求解效果，實驗3使用某海工企業(yè)管件加工車間實例數(shù)據(jù)進行測試，共包含10個工件，5道工序，16臺加工設備。工件在不同設備上的加工時間信息如表4所示(單位：min)，表中空缺部分表示該工件存在特定加工設備約束。工件在相鄰工序之間的轉移時間如圖9所示，圓內(nèi)包含3個數(shù)字，分別對應三角模糊數(shù)的3個分量，表示工件從行所在設備向列所在設備轉移時所消耗的時間(單位：min)，轉移方向用箭頭標出。

表4 工件加工時間表

續(xù)表4

對照方法仍然采用實驗2中的3種方法，分別運行20次，統(tǒng)計加權AI、提前數(shù)、延誤數(shù)3項指標的最佳值、最差值和平均值。IGA-HS主要參數(shù)設置如表5所示，實驗結果如表6所示。

表5 算法主要參數(shù)設置

表6 實例數(shù)據(jù)測試結果

續(xù)表6

由實驗結果可知，IGA-HS產(chǎn)生的加權AI值在最佳、最差和平均值3項指標上的表現(xiàn)優(yōu)于另外3種對照方法。將4種方法的20次尋優(yōu)曲線進行平均，結果如圖10所示。

由尋優(yōu)曲線變化情況可知，在初始階段IGA-HS生成的解的質量更高，這是因為IGA-HS使用NSlope算法生成初始解，可以避免產(chǎn)生大量劣質個體；IGA-VNS與IPS-GA尋優(yōu)曲線在160代左右不再繼續(xù)遞增，曲線平穩(wěn)后適應度值接近，因此兩者表現(xiàn)相當；MBO在前期收斂速度較快，但是在50代后，其曲線遞增趨勢明顯減緩，達到平穩(wěn)后的適應度值低于另外3種方法，因此表現(xiàn)最差；在160代以后，IGA-HS的適應度值則仍保持遞增趨勢，并在180代左右出現(xiàn)明顯遞增，原因是IGA-HS使用自適應變異概率，結合HS進行局部強化搜索，增強了算法跳出局部最優(yōu)解的能力，因此能夠搜索到適應度更高的解。如圖11所示為實例數(shù)據(jù)調度方案的模糊甘特圖。

綜上可知，本文提出的IGA-HS算法在求解海工裝備制造車間調度問題上具有良好的效果，IGA-HS算法的整體求解效果優(yōu)于另外3種對照算法。首先，NSlope啟發(fā)式算法產(chǎn)生了高質量的初始種群；其次，對選擇、交叉、變異算子的改進提高了算法的收斂性質；最后，使用和聲搜索算法進行局部強化搜索，使IGA-HS具備良好的局部搜索能力，提高了算法的整體性能。

4 結束語

本文主要研究了帶有工件轉移時間、特定加工設備約束、模糊加工時間和模糊交貨期的海工裝備制造車間調度問題。以最大加權平均一致指數(shù)為目標函數(shù)，建立了FHFSP-UPM&SM模型，并設計了一種改進遺傳和聲搜索算法。算法初始階段采用NSlope啟發(fā)式算法生成具有較高質量的初始種群；算法選擇階段采用線性排序策略和精英保留策略，用以改善算法收斂性質，提高算法搜索效率；算法交叉階段針對矩陣編碼的兩個維度，采用兩種交叉算子提高交叉性能，禁忌搜索策略能夠保證個體交叉更為充分；算法變異階段設計了兩種變異算子，結合自適應變異概率，增強了算法跳出局部最優(yōu)的能力。通過數(shù)值實驗對算法性能進行了測試，驗證了本文所提方法在求解海工裝備制造車間調度問題上的有效性。

在后續(xù)研究過程中，擬考慮將工件轉移時間視作廣義的物流配送時間，將物流配送問題與車間調度問題相結合，進一步提高研究的實用性。