一種改進(jìn)離散磷蝦群的復(fù)雜產(chǎn)品裝配調(diào)度算法

莊存波， 熊輝， 劉檢華， 唐承統(tǒng)

(北京理工大學(xué) 機(jī)械與車輛學(xué)院， 北京 100081)

0 引言

復(fù)雜產(chǎn)品是指客戶需求復(fù)雜、產(chǎn)品組成復(fù)雜、產(chǎn)品技術(shù)復(fù)雜、制造過程復(fù)雜、項(xiàng)目管理復(fù)雜的一類產(chǎn)品，如導(dǎo)彈、衛(wèi)星、火箭、飛機(jī)等[1]。裝配是復(fù)雜產(chǎn)品生產(chǎn)的最后環(huán)節(jié)，也是最為重要的環(huán)節(jié)之一，其直接關(guān)系到產(chǎn)品的質(zhì)量、壽命、性能和可靠性[2]。生產(chǎn)調(diào)度是指在一定約束條件下，把有限資源在時(shí)間上分配給若干個(gè)任務(wù)，以滿足或優(yōu)化一個(gè)或多個(gè)性能指標(biāo)的過程[3]。生產(chǎn)調(diào)度是產(chǎn)品裝配過程的關(guān)鍵環(huán)節(jié)，也是裝配過程管理與控制的核心問題之一。復(fù)雜產(chǎn)品裝配多以流程為主組織生產(chǎn)，其裝配過程是典型的工作流。在航天器等復(fù)雜產(chǎn)品的裝配過程中，通常包括產(chǎn)品總裝和組件部裝兩個(gè)階段，每個(gè)階段均需繪制總裝工藝流程圖和部裝工藝流程圖?？傃b裝配和部裝裝配多數(shù)是分布在不同的裝配車間，且二者的裝配過程相似，故本文僅研究單個(gè)階段的裝配調(diào)度問題。復(fù)雜產(chǎn)品裝配調(diào)度問題(總裝或部裝)可簡化為一個(gè)以最大完工時(shí)間最小為調(diào)度目標(biāo)、針對(duì)關(guān)鍵路徑進(jìn)行排產(chǎn)的多階段混合流水車間調(diào)度問題(HFSP)。HFSP為流水車間調(diào)度問題(FSP)與并行機(jī)調(diào)度問題的集合，也被稱為柔性FSP(FFSP)。與一般FSP相比， HFSP加大了機(jī)器的可選擇性，擴(kuò)大了可行解的搜索范圍，是更加復(fù)雜的NP-hard問題。傳統(tǒng)HFSP按并行機(jī)類型可分為相同并行機(jī)HFSP[4]、均勻并行機(jī)HFSP[5]及不相關(guān)并行機(jī)HFSP[6]共3種，按階段數(shù)量可分為2階段HFSP、3階段HFSP及多階段HFSP[7].

自1954年Johnson[8]研究具有兩臺(tái)機(jī)器、工件加工順序已知的HFSP開始，國內(nèi)外學(xué)者對(duì)HFSP進(jìn)行了研究，并取得了顯著成果。目前，HFSP求解算法主要包括精確算法、啟發(fā)式算法和元啟發(fā)式算法。精確算法中分支定界(B&B)算法使用最為廣泛，如Brah等[9]利用B&B算法求解HFSP時(shí)提出了一種對(duì)工件排列和機(jī)器分配進(jìn)行枚舉的分支策略，Neron等[10]為了增強(qiáng)B&B算法搜索效率提出了一種基于推理的全局操作方法。精確算法在理論上能夠獲取問題的最優(yōu)解，但面對(duì)大規(guī)模調(diào)度問題時(shí)，其求解時(shí)間過長，故只適用于求解小規(guī)模調(diào)度問題。Gupta[11]提出了一種簡單的啟發(fā)式算法來求解第1階段含1臺(tái)機(jī)器、第2階段含2臺(tái)相同機(jī)器的2階段HFSP. Riane等[12]提出了2種新的簡單啟發(fā)式算法來求解3階段相同并行機(jī)調(diào)度問題。對(duì)于多階段HFSP，Ruiz等[13]和Pan等[14]在種群初始化階段利用Nawaz-Enscore-Ham(NEH)啟發(fā)式算法[15]生成少數(shù)優(yōu)質(zhì)個(gè)體以提高種群質(zhì)量，從而優(yōu)化算法尋優(yōu)性能。啟發(fā)式算法雖然能在較短時(shí)間內(nèi)獲得可行解，但難以保證解的質(zhì)量。為了獲得更優(yōu)質(zhì)的解，國內(nèi)外許多學(xué)者在近些年更多采用元啟發(fā)式算法來求解HFSP，如遺傳算法(GA)[16-17]、禁忌搜索(TS)[18-19]、模擬退火(SA)[20]、人工免疫系統(tǒng)(AIS)[21-22]、迭代局部搜索(ILS)[23]、粒子群優(yōu)化(PSO)[24-25]、人工蜂群(ABC)算法[26-27]和蟻群優(yōu)化(ACO)[28-29]等群體智能優(yōu)化算法(SIOA)，這些算法多用于求解多階段相同并行機(jī)HFSP. 2012年，Gandomi等[30]通過模擬磷蝦種群覓食行為提出了一種新穎的仿生SIOA，即磷蝦群(KH)算法。在函數(shù)優(yōu)化領(lǐng)域，KH算法及其改進(jìn)算法在許多標(biāo)準(zhǔn)測試問題上被證明比一些熟知的元啟發(fā)式算法更好或非常具有競爭性[31]。KH算法具有較強(qiáng)局部探索能力，且控制參數(shù)少，易于實(shí)現(xiàn)，非常適用于并行計(jì)算。然而，KH算法無法一直很好地實(shí)現(xiàn)全局搜索，易陷入局部最優(yōu)，且KH算法更多依賴于隨機(jī)運(yùn)動(dòng)，易導(dǎo)致收斂速度緩慢[32-33]。目前，KH算法已在特征識(shí)別、人工神經(jīng)網(wǎng)絡(luò)訓(xùn)練、比例—積分—微分(PID)控制、逆幾何設(shè)計(jì)、基于地圖的網(wǎng)絡(luò)路徑優(yōu)化和結(jié)構(gòu)優(yōu)化等問題上得到廣泛研究與應(yīng)用[34]。如Kowalski等[35]將KH算法應(yīng)用于訓(xùn)練人工神經(jīng)網(wǎng)絡(luò)，并通過仿真結(jié)果和算法比較得出KH算法在精度和時(shí)間上比其他元啟發(fā)式算法和傳統(tǒng)方法更有效。Yaghoobi等[36]提出了一種改進(jìn)的混沌KH(ICKH)算法，將其應(yīng)用于PID控制器參數(shù)的確定，通過對(duì)比發(fā)現(xiàn)ICKH算法比其他優(yōu)化算法性能更優(yōu)。KH算法在復(fù)雜產(chǎn)品裝配車間調(diào)度問題和HFSP上的應(yīng)用研究尚無文獻(xiàn)可查。

本文以復(fù)雜產(chǎn)品裝配車間為研究對(duì)象，采用基于排列的編碼方法和基于啟發(fā)式規(guī)則的解碼方法，提出一種改進(jìn)的離散KH(IDKH)算法，通過實(shí)驗(yàn)設(shè)計(jì)方法分析不同參數(shù)設(shè)置對(duì)算法性能的影響，最后通過實(shí)例和算法比較驗(yàn)證所提算法的高效性和魯棒性。

1 復(fù)雜產(chǎn)品裝配調(diào)度模型

1.1 問題描述

1.2 數(shù)學(xué)模型構(gòu)建

基于上述分析，構(gòu)建復(fù)雜產(chǎn)品裝配調(diào)度問題的數(shù)學(xué)模型，具體描述如下：

minCmax，

(1)

(2)

k∈{1,2,…,s-1},

(3)

(4)

zghk+zhgk≤1,g,h∈J,g≠h,

(5)

(6)

xjkm,zghk∈{0,1},

(7)

式中：Cmax為最大完工時(shí)間；g、h為產(chǎn)品編號(hào)；m∈AT，AT為裝配班組集合，AT={1,2,…,L}，L為裝配班組總數(shù)；pjkm為產(chǎn)品j在工序k、由班組m進(jìn)行裝配操作所需要的時(shí)間；tjk為產(chǎn)品j的第k道工序開工時(shí)間；U為足夠大的正數(shù)；xjkm=1為產(chǎn)品j的第k道工序被分派到裝配班組m上，否則xjkm=0；zghk=1為在第k道工序上產(chǎn)品g先于產(chǎn)品h被裝配，否則zghk=0. (1)式表示調(diào)度性能指標(biāo)，即工期最??；(2)式表示最后一個(gè)產(chǎn)品在最后一道工序s的完工時(shí)間為Cmax；(3)式表示同一個(gè)產(chǎn)品只有在前一道工序裝配完畢后才能開始下一道工序；(4)式表示每個(gè)產(chǎn)品在各個(gè)工序階段只能由一個(gè)裝配班組進(jìn)行裝配操作；(5)式表示產(chǎn)品g和產(chǎn)品h間存在先于、后于、同時(shí)3種順序關(guān)系；(6)式表示同一個(gè)裝配班組在一個(gè)時(shí)刻只能裝配一個(gè)產(chǎn)品，即前一個(gè)產(chǎn)品裝配完成后才能開始下一個(gè)產(chǎn)品的裝配；(7)式表示變量的取值為0或1.

2 標(biāo)準(zhǔn)KH算法介紹

KH算法在優(yōu)化過程中的目標(biāo)是磷蝦與食物之間距離最短及磷蝦種群密度最大[30]。磷蝦個(gè)體i(i∈{1,…,NP}，NP為種群數(shù)量)在t時(shí)刻的位置向量Xi由3個(gè)因素決定：1)受其他磷蝦個(gè)體誘導(dǎo)所產(chǎn)生的運(yùn)動(dòng)向量Ni；2)覓食運(yùn)動(dòng)向量Fi；3)隨機(jī)的物理擴(kuò)散運(yùn)動(dòng)向量Di. 用拉格朗日模型來描述磷蝦個(gè)體的移動(dòng)位置向量：

(8)

1)Ni由局部種群密度(即局部影響)、目標(biāo)種群密度(即目標(biāo)影響)和排斥種群密度(即排斥影響)3個(gè)因素決定。磷蝦個(gè)體i受其他磷蝦個(gè)體誘導(dǎo)所產(chǎn)生的運(yùn)動(dòng)向量可表示為

(9)

2)Fi由食物位置和磷蝦個(gè)體i的過往覓食經(jīng)驗(yàn)2個(gè)因素決定。磷蝦個(gè)體i的覓食運(yùn)動(dòng)向量可表示為

(10)

3)Di為一個(gè)隨機(jī)過程，對(duì)于磷蝦個(gè)體i，有

Di=Dmaxδ,

(11)

式中：Dmax為最大擴(kuò)散速度，取值范圍為[0.002,0.010]，一般取0.005；δ為隨機(jī)方向向量，每項(xiàng)都是位于[-1,1]區(qū)間的隨機(jī)數(shù)。

4)種群位置更新[30]：對(duì)于磷蝦個(gè)體i，第gen+1次迭代后的位置向量可表示為

(12)

式中：Δt為速度向量的比例因子，是非常重要的常數(shù)之一，需根據(jù)優(yōu)化問題仔細(xì)設(shè)定。Δt完全由搜索空間決定，可簡單表示為

(13)

式中：c為一個(gè)常數(shù)，取值范圍為[0，2];UBv和LBv為變量v的上界和下界。

5)遺傳算子：受進(jìn)化算法的啟發(fā)，交叉算子和變異算子兩種遺傳繁殖機(jī)制被加入到KH算法當(dāng)中，經(jīng)過仿真實(shí)驗(yàn)發(fā)現(xiàn)，只將交叉算子應(yīng)用到KH算法中綜合性能最優(yōu)。關(guān)于標(biāo)準(zhǔn)KH算法的詳細(xì)介紹見參考文獻(xiàn)[30].

3 IDKH設(shè)計(jì)

3.1 編碼與解碼

目前，求解HFSP的算法大多采用基于排列的方式對(duì)群體中個(gè)體進(jìn)行編碼，即取所有工件序號(hào)排列作為一個(gè)個(gè)體。群體中的每一個(gè)個(gè)體都對(duì)應(yīng)一個(gè)可行調(diào)度解，個(gè)體長度為工件數(shù)量n，工件號(hào)在排列中位置代表其在第一個(gè)階段加工順序。工件排序和后續(xù)機(jī)器分配由解碼規(guī)則決定[38-39]。

機(jī)器分配部分一般采用最先空閑機(jī)器規(guī)則[40]，但主要面向相同并行機(jī)調(diào)度問題。由于復(fù)雜產(chǎn)品裝配調(diào)度問題屬于不相關(guān)并行機(jī)調(diào)度問題，因此，本文基于該規(guī)則，提出如下改進(jìn)策略：

1)對(duì)于每個(gè)工件j，選擇完工時(shí)間最短的機(jī)器作為工件j的加工機(jī)器，完工時(shí)間為am+pjkm，其中，am為工件j最早允許加工時(shí)間且am=max (rm,Cj,k-1)，rm為機(jī)器m釋放時(shí)間，Cj,k-1為工件j在上一階段的完工時(shí)間；

2)對(duì)于完工時(shí)間相同的機(jī)器，基于效率最大化原則，優(yōu)先選擇加工時(shí)間pjkm最小的機(jī)器；

3)對(duì)于完工時(shí)間和加工時(shí)間都相同的機(jī)器，為了使調(diào)度結(jié)果更加緊湊，選擇am-rm最小的機(jī)器。

工件排序部分采用如下改進(jìn)策略：

1)第一階段按照編碼方式確定工件加工順序，后續(xù)階段基于先到先加工方式進(jìn)行排序；

2)對(duì)于前一階段完成時(shí)間相同的工件，選擇當(dāng)前階段加工時(shí)間短的工件優(yōu)先加工。對(duì)于復(fù)雜產(chǎn)品裝配調(diào)度問題，可用產(chǎn)品序號(hào)代替工件序號(hào)，用裝配代替加工，用裝配班組代替機(jī)器。

3.2 種群初始化

為了保證種群的多樣性以獲得全局最優(yōu)解，采用隨機(jī)方式生成種群個(gè)體的位置向量X=(X1,X2,…,XNP)，個(gè)體i位置向量為Xi，變量數(shù)為工件數(shù)n，上下界范圍可自定義。然而，標(biāo)準(zhǔn)KH算法只適用于連續(xù)優(yōu)化問題的求解，并不適用于離散優(yōu)化問題的求解，因此需將個(gè)體位置向量Xi轉(zhuǎn)化為工件序號(hào)的排列πi后才能夠被解碼。

為此，本文提出轉(zhuǎn)化策略，對(duì)于每一個(gè)磷蝦個(gè)體i，其對(duì)應(yīng)的位置向量為

Xi=(Xi1,Xi2,…,Xin)，

(14)

3.3 局部搜索

針對(duì)標(biāo)準(zhǔn)KH算法收斂速度較為緩慢的問題，本文采用局部搜索策略來加快算法收斂速度，并增強(qiáng)算法局部開采能力。目前，常用的局部搜索策略包括：1)交換策略：從排列編碼中隨機(jī)選擇2個(gè)位置的元素進(jìn)行交換；2)插入策略：從排列編碼中隨機(jī)選擇2個(gè)位置，將第1個(gè)位置中的元素放到第2個(gè)位置上。

為了不影響算法運(yùn)算速度，在每一次迭代過程中，只對(duì)目前出現(xiàn)的最優(yōu)解執(zhí)行局部搜索策略。本文采用一種修改的變鄰域局部搜索策略，具體實(shí)現(xiàn)步驟如下：

1)對(duì)目前已知的最優(yōu)解Xbest執(zhí)行插入操作得到Xbest′.

2)對(duì)Xbest′執(zhí)行混合鄰域局部搜索策略(即在每一次局部搜索過程中，從交換策略和插入策略中隨機(jī)選擇一種，選擇概率均為50%)得到其鄰域X，如果鄰域X適應(yīng)度值比Xbest′適應(yīng)度值低，則用X替代Xbest′進(jìn)行下一次混合鄰域搜索。該步驟迭代次數(shù)為n(n+1).

3)比較Xbest′與Xbest的適應(yīng)度值，即比較f(Xbest′)與f(Xbest)，若f(Xbest′)

3.4 重啟操作

針對(duì)KH算法全局搜索性能有限而導(dǎo)致的容易陷入局部最優(yōu)問題，本文提出了一種重啟策略。具體運(yùn)行流程為：1)當(dāng)種群最優(yōu)解不更新代數(shù)Age達(dá)到設(shè)定常數(shù)Limit時(shí)，算法將執(zhí)行重啟操作；2)保留百分比為η的最優(yōu)個(gè)體，剩下(1-η)·NP個(gè)個(gè)體則被隨機(jī)生成的種群個(gè)體替代。重啟操作偽代碼如圖2所示。

3.5 IDKH算法流程

基于上述分析，構(gòu)建如圖3所示的求解復(fù)雜產(chǎn)品裝配調(diào)度問題的IDKH算法運(yùn)算流程。

4 仿真結(jié)果與算法比較

4.1 參數(shù)討論

采用MATLAB 2013平臺(tái)對(duì)IDKH算法進(jìn)行編程，并在性能為Inter(R) Core(TM) i7-3770 CPU 和3.40 GHz RAM的計(jì)算機(jī)上運(yùn)行IDKH算法，操作系

SetLimit,η;

IfAge>=Limit

Keep the current bestXbest

Randomly generate the left (1-η)*NPindividuals

While not termination

Repeat

Evaluate the fitness of the krill

Perform the three motions

Implement the crossover operator

Update the krill position

一切都和過往的經(jīng)驗(yàn)不一樣了。在國家隊(duì)時(shí)，鄒習(xí)慣謹(jǐn)慎地談?wù)撃繕?biāo)。第一場職業(yè)賽前新聞發(fā)布會(huì)，一個(gè)泰國記者看到他笑瞇瞇的，感到吃驚。而現(xiàn)在，他會(huì)訓(xùn)練自己不怒自威的樣子，擺一張臭臉，不光給媒體看，更多給對(duì)手看。

Evaluate the krill based on its new position

Until a number ofNPreplications

Sort all the krill and find the current bestXbest′

Iff(Xbest′)

Xbest=Xbest′

END If

END while

END If

END

圖2 重啟操作的偽代碼

Fig.2 Pseudo code of restart operation

統(tǒng)為Windows 7.

IDKH算法中，種群個(gè)數(shù)NP、控制時(shí)間間隔C、重啟操作常數(shù)Limit和最優(yōu)種群保留比例η等4個(gè)參數(shù)會(huì)對(duì)其性能產(chǎn)生影響。各參數(shù)水平取值如表1所示。

為了測試IDKH算法的性能，本文隨機(jī)生成一系列計(jì)算實(shí)例，產(chǎn)品(工件)數(shù)量J∈{10,15,20}，

表1 IDKH算法參數(shù)水平表Tab.1 Combinations of parameter values of IDKH

工序(階段)數(shù)S=5，裝配(加工)工時(shí)為取值范圍[3, 40]的離散隨機(jī)整數(shù)分布，每階段的并行機(jī)數(shù)均為3. 每種組合隨機(jī)生成3個(gè)實(shí)例，共計(jì)NI=3×3=9個(gè)實(shí)例。為每個(gè)實(shí)例選擇規(guī)模為L16(44)的正交實(shí)驗(yàn)，IDKH算法在每種參數(shù)組合下均獨(dú)立運(yùn)行20次，設(shè)定終止條件為最大迭代次數(shù)200，同時(shí)限制每次運(yùn)行時(shí)間不超過20 s. 計(jì)算得到每個(gè)實(shí)例正交結(jié)果如表2所示。

表2 IDKH算法正交表Tab.2 Orthogonal array and response values

由表2可知，組合[3 2 4 1]的不同參數(shù)組合的平均值最小，是較為穩(wěn)定的、獲得最優(yōu)參數(shù)值的組合，此時(shí)NP=80，C=1.0，Limit=100，η=0.1. 根據(jù)表2，種群個(gè)數(shù)NP、控制時(shí)間間隔C、重啟操作常數(shù)Limit和最優(yōu)種群保留比例η的極差和重要程度如表3所示。

表3 IDKH算法各參數(shù)極差表Tab.3 Statistics of response values

由表3可知，Limit和η極差最大，其次為NP，C最小，這表明重啟操作對(duì)IDKH算法的性能影響最大。從數(shù)值上看，4個(gè)參數(shù)極差均不超過0.50%，說明IDKH算法魯棒性較強(qiáng)。不同參數(shù)在不同水平下對(duì)算法性能的影響趨勢圖如圖4所示。

由圖4(a)可知，NP越大，算法性能越優(yōu)，原因在于NP決定了群體在搜索空間的覆蓋范圍。當(dāng)NP較小時(shí)，算法全局探索性能較差，易早熟收斂而陷入局部最優(yōu)；當(dāng)NP較大時(shí)，群體能夠覆蓋更多搜索空間，更易獲得高質(zhì)量的解。NP較大時(shí)，計(jì)算量大、耗時(shí)長，同時(shí)變優(yōu)幅度隨著NP增加不斷變小(水平3和水平4差距不大，僅為0.03)，故NP不宜過大，NP=80為最佳。C決定了算法尋優(yōu)過程中在整個(gè)搜索空間的移動(dòng)幅度，C過大易導(dǎo)致收斂速度過快而陷入局部最優(yōu)，C過小易導(dǎo)致收斂速度緩慢從而影響IDKH算法性能，由圖4(b)可知，C=1.0時(shí)IDKH算法整體性能最優(yōu)。對(duì)于重啟操作，Limit決定了重啟時(shí)機(jī)。當(dāng)Limit較小時(shí)，IDKH算法還未達(dá)到局部最優(yōu)就被迫重啟，不僅重啟效果一般，且會(huì)影響IDKH算法性能。η決定了重啟時(shí)保留最佳個(gè)體比例，當(dāng)保留比例較大時(shí)，IDKH算法易再次陷入局部最優(yōu)，導(dǎo)致重啟效果不明顯。由圖4(c)和圖4(d)可知，當(dāng)Limit=100，η=0.1時(shí)，重啟效果最佳。綜上所述，組合[3 2 4 1]為最佳參數(shù)組合，即NP=80，C=1.0，Limit=100，η=0.1.

4.2 初始實(shí)驗(yàn)

與離散KH(DKH)算法相比，IDKH算法主要是在局部搜索和重啟操作兩個(gè)方面進(jìn)行了改進(jìn)。

本文實(shí)驗(yàn)中，考慮對(duì)比IDKH算法及其3種變型：DKH算法、包含重啟操作的DKH(DKH-RS)算法、包含局部搜索的DKH(DKH-LS)算法。為了驗(yàn)證DKH算法、DKH-RS算法、DKH-LS算法和IDKH算法求解HFSP的性能，采用4.1節(jié)中的9個(gè)實(shí)例對(duì)算法性能進(jìn)行比較，選擇最優(yōu)參數(shù)組合NP=80，C=1.0，Limit=100，η=0.1，每個(gè)實(shí)例均運(yùn)行20次，每次運(yùn)行時(shí)間不超過20 s. 如圖5所示為IDKH算法不同變型下的平均值、最優(yōu)值和標(biāo)準(zhǔn)差變化趨勢圖。

通過DKH算法和DKH-LS算法對(duì)比以及DKH-RS算法和IDKH算法對(duì)比發(fā)現(xiàn)，加入局部搜索操作后，算法的平均值、最小值和標(biāo)準(zhǔn)差都會(huì)得到優(yōu)化，說明局部搜索策略能夠全面提高算法尋優(yōu)性能和魯棒性。通過DKH算法和DKH-RS算法對(duì)比以及DKH-LS算法和IDKH算法對(duì)比發(fā)現(xiàn)，加入重啟操作后，算法的平均值和標(biāo)準(zhǔn)差得到了優(yōu)化，即算法平均尋優(yōu)性能和魯棒性得到了增強(qiáng) 但最小值略有下降，原因在于算法還未達(dá)到局部最優(yōu)就被迫重啟了，然而大多數(shù)情況下并不會(huì)出現(xiàn)這種情況，如DKH-LS算法僅在一個(gè)實(shí)例上比IDKH算法獲得的最小值小，其他均一致。綜合來看，IDKH算法性能最優(yōu)。

4.3 計(jì)算結(jié)果

4.3.1 文獻(xiàn)實(shí)例驗(yàn)證

目前，求解HFSP比較常用的智能算法為GA[13,41]，近幾年涌現(xiàn)出了一些新穎算法，如萬有引力搜索算法(GSA)[42]、差分進(jìn)化(DE)算法[43]、分布式估計(jì)算法(EDA)[38,44-45]。本文利用參考文獻(xiàn)[38,46]所提3個(gè)HFSP實(shí)例L1、L2、L3，對(duì)比IDKH算法和DKH算法與GA、GSA、DE算法、EDA在求解實(shí)例時(shí)的性能差異。其中：DE算法數(shù)據(jù)來源于參考文獻(xiàn)[43]，評(píng)價(jià)次數(shù)為10 000；GA、GSA、EDA數(shù)據(jù)均來源于參考文獻(xiàn)[45]，采用運(yùn)行時(shí)間10 s為終止條件。對(duì)于IDKH算法，同樣設(shè)定終止條件為10 s，參數(shù)組合為NP=80，C=1.0，Limit=100，η=0.1，運(yùn)算結(jié)果如表4所示。另外，由于智能算法均存在一些隨機(jī)因子， 運(yùn)行10次的結(jié)果有時(shí)并不能準(zhǔn)確反映出算法性能(如算法穩(wěn)定性)。因此，為了能夠更加準(zhǔn)確地驗(yàn)證所提算法性能，本文對(duì)DKH算法和IDKH算法運(yùn)行70次，根據(jù)70次運(yùn)行結(jié)果及其平均值得出10次運(yùn)行結(jié)果。對(duì)于GA、GSA、DE算法、EDA(包括EDA_W算法[38]和EDA_I算法[45])，則采用參考文獻(xiàn)[45]所提供的10次運(yùn)算結(jié)果，得出其平均值。

表4 3個(gè)實(shí)例在不同智能算法中的結(jié)果對(duì)比

由表4可知， IDKH算法和EDA_I算法結(jié)果要明顯好于其他算法，且都很穩(wěn)定。二者求解性能相差不大，但I(xiàn)DKH算法略優(yōu)于EDA_I算法，基本上每次都能獲得目前已知的最優(yōu)解，如：對(duì)于L2和L3，每次都能獲得目前已知的最優(yōu)解297和13；對(duì)于L2，在運(yùn)行70次過程中，僅有一次沒有獲得已知的最優(yōu)解21，運(yùn)行70次得到的平均值為21.014 3. 其次為GSA和DKH算法，再次為GA和EDA_W算法，最后為DE算法，從而可知IDKH算法在求解HFSP時(shí)是高效且穩(wěn)定的。

4.3.2 工程實(shí)例驗(yàn)證

以某航天器裝配為例，在調(diào)度開始時(shí)刻，需要完成10個(gè)產(chǎn)品的裝配，其裝配工藝流程如圖6所示。裝配總工序數(shù)為7，關(guān)鍵路徑上的工序數(shù)為4，分別標(biāo)記為S1、S2、S3、S4. 關(guān)鍵路徑上的每道工序均有3個(gè)裝配班組,分別標(biāo)記為M1～M12，及5個(gè)裝配工位(滿足裝配工位數(shù)量大于等于裝配班組數(shù)量的前提)可供分配，不同裝配班組完成不同裝配工序所需要的裝配時(shí)間如表5所示。

基于該實(shí)例，分別用IDKH算法、DKH算法、EDA_W算法進(jìn)行求解，每種算法均運(yùn)行70次，每次最大運(yùn)行時(shí)間仍為10 s.求解發(fā)現(xiàn)只有IDKH算法每次都能獲得目前已知的最優(yōu)解Cmax=195，其調(diào)度甘特圖如圖7所示。圖7中，矩形框的數(shù)字表示產(chǎn)品序號(hào)j.

表5 某航天器的裝配時(shí)間表Tab.5 Assembly time of a spacecraft h

5 結(jié)論

針對(duì)復(fù)雜產(chǎn)品裝配調(diào)度問題，引入了一種高效的群體智能優(yōu)化算法—KH算法，并采用局部搜索和重啟策略增強(qiáng)了KH算法的局部尋優(yōu)能力和全局搜索能力。針對(duì)已有參考文獻(xiàn)[38,46]中3個(gè)不同實(shí)例和1個(gè)工程實(shí)例，IDKH算法求解結(jié)果明顯比GSA、DKH算法、GA、EDA_W算法、DE算法等算法好，略優(yōu)于EDA_I算法，且基本上每次都能獲得目前已知的最優(yōu)解，反映出IDKH算法在求解HFSP和復(fù)雜產(chǎn)品裝配調(diào)度問題時(shí)是高效且穩(wěn)定的。