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

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

0 引言

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

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

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

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

(3)重點(diǎn)考慮實(shí)際完工時(shí)間與計(jì)劃完工時(shí)間的吻合程度而非最早完工時(shí)間；

(4)每臺(tái)設(shè)備對(duì)不同工件加工速度不同，屬于不相關(guān)并行機(jī)；

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

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

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

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

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

(1)模型方面 同時(shí)考慮模糊時(shí)間、工件轉(zhuǎn)移時(shí)間、不相關(guān)并行機(jī)、特定加工設(shè)備等多個(gè)約束，以交貨期與完工時(shí)間吻合度為優(yōu)化目標(biāo)構(gòu)建了海工裝備制造車間調(diào)度模型。

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

1 帶有模糊時(shí)間和特定設(shè)備約束的HFSP 模型建立

1.1 模型假設(shè)

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

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

(3)同一臺(tái)設(shè)備的兩個(gè)相鄰待加工工件之間不存在等待時(shí)間；

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

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

1.2 附加條件及約束

1.2.1 模糊加工/轉(zhuǎn)移/交貨時(shí)間

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

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

1.2.2 不相關(guān)并行機(jī)與特定加工設(shè)備約束

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

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

1.3 FHFSP-UPM&SM模型

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

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

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

(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 改進(jìn)遺傳—和聲搜索算法

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

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

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

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

步驟3計(jì)算個(gè)體適應(yīng)度值，根據(jù)適應(yīng)度值對(duì)個(gè)體進(jìn)行升序排列，并對(duì)個(gè)體逐一編號(hào)。

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

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

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

步驟7和聲搜索。對(duì)當(dāng)前種群進(jìn)行若干次和聲搜索操作，用適應(yīng)度值更高的個(gè)體替換種群中的最劣個(gè)體。

步驟8判斷是否滿足算法停止準(zhǔn)則，若是則停止，輸出結(jié)果；否則，轉(zhuǎn)步驟3。

下面給出算法詳細(xì)設(shè)計(jì)過程。

2.1 編碼解碼方式

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

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

2.2 種群初始化方法

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

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

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

(9)

步驟3在第一道工序中，按照初始工件序列依次為工件隨機(jī)選擇加工設(shè)備；對(duì)于后續(xù)工序，按照工件到達(dá)的先后順序?yàn)楦鱾€(gè)工件隨機(jī)安排加工設(shè)備，最后為存在特定加工設(shè)備約束的工件選擇設(shè)備，直到生成完整個(gè)體。

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

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

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

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

(10)

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

2.4 基于禁忌搜索策略的交叉算子改進(jìn)

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

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

具體步驟為：

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

步驟2在A中隨機(jī)選擇一個(gè)起始點(diǎn)位，然后找到B中對(duì)應(yīng)點(diǎn)位上的索引編號(hào)，再回到A中找到相同編號(hào)的索引的位置。

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

操作方法如圖4所示：

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

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

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

2.5 變異算子改進(jìn)

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

(1)多點(diǎn)替換

多點(diǎn)變異操作首先隨機(jī)選定一個(gè)工序，然后找出所有此工序?qū)?yīng)的列并重新生成該工序內(nèi)的工件和加工設(shè)備組合，替換原有工序，如圖6所示。

(2)單點(diǎn)逆轉(zhuǎn)

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

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

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

(11)

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

2.6 和聲搜索

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

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

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

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

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

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

3 數(shù)值實(shí)驗(yàn)與分析

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

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

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

(3)車間實(shí)例數(shù)據(jù)測(cè)試 采用IGA-HS以及另外三種對(duì)照方法對(duì)車間實(shí)例數(shù)據(jù)進(jìn)行調(diào)度，為評(píng)價(jià)IGA-HS算法的實(shí)用性提供依據(jù)。

3.1 實(shí)驗(yàn)1：NSlope初始化方法測(cè)試

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

表3 NSlope啟發(fā)式算法對(duì)比實(shí)驗(yàn)結(jié)果

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

3.2 實(shí)驗(yàn)2：算法性能對(duì)比測(cè)試

表6 基于n20k4算例的4種算法測(cè)試結(jié)果

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

表7 基于n20k8算例的4種算法測(cè)試結(jié)果

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

表8 基于n50k4算例的4種算法測(cè)試結(jié)果

續(xù)表8

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

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

3.3 實(shí)驗(yàn)3：車間實(shí)例數(shù)據(jù)測(cè)試

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

表4 工件加工時(shí)間表

續(xù)表4

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

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

表6 實(shí)例數(shù)據(jù)測(cè)試結(jié)果

續(xù)表6

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

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

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

4 結(jié)束語

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

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