徐 達(dá)，焦慶龍

（陸軍裝甲兵學(xué)院，北京 100072）

0 引言

在裝備維修性試驗(yàn)過(guò)程中，拆卸是較為重要的環(huán)節(jié)，如何拆卸對(duì)于裝備維修性試驗(yàn)的評(píng)定具有重要影響。尤其是對(duì)裝備維修性定量指標(biāo)驗(yàn)證而言，如何拆卸顯得更為重要，對(duì)維修性定量指標(biāo)試驗(yàn)驗(yàn)證數(shù)據(jù)具有直接的影響。因此，對(duì)裝備的拆卸任務(wù)進(jìn)行合理規(guī)劃是開(kāi)展裝備維修性試驗(yàn)驗(yàn)證之前需要解決的關(guān)鍵問(wèn)題［1］。

在裝備維修性試驗(yàn)驗(yàn)證過(guò)程中，相比串行拆卸方式（即每一時(shí)刻只能拆卸一個(gè)最小拆卸單元），并行拆卸方式（即至少存在某時(shí)刻同時(shí)拆卸兩個(gè)以上最小拆卸單元）是更為普遍的拆卸方式［2］。尤其是復(fù)雜的維修任務(wù)，通常由多個(gè)拆卸任務(wù)組成，如果不對(duì)各拆卸任務(wù)進(jìn)行合理規(guī)劃，會(huì)使所獲取的維修性試驗(yàn)驗(yàn)證數(shù)據(jù)的合理性和可信性存在明顯的不足。

對(duì)于并行拆卸問(wèn)題，張秀芬［2］和張文勝［3］采用“步”的概念對(duì)產(chǎn)品的并行拆卸序列進(jìn)行描述，較好地實(shí)現(xiàn)了對(duì)產(chǎn)品并行拆卸序列規(guī)劃問(wèn)題的求解。但“步”的概念對(duì)產(chǎn)品并行拆卸的效率考慮有所不足，因此，所求取的并行拆卸序列的總的拆卸時(shí)間與工程實(shí)踐的貼合度還有待進(jìn)一步提高。

本文針對(duì)單裝并行拆卸問(wèn)題，鑒于烏鴉搜索算法（Crow Search Algorithm，CSA）在其他領(lǐng)域的成功應(yīng)用［4］，提出了一種基于CSA 的裝備并行拆卸任務(wù)規(guī)劃（Parallel Disassembly Task Planning，PDTP）方法。旨在通過(guò)該方法對(duì)裝備維修性試驗(yàn)驗(yàn)證時(shí)所涉及的拆卸任務(wù)進(jìn)行科學(xué)規(guī)劃，為獲取合理、可信的維修性試驗(yàn)驗(yàn)證數(shù)據(jù)提供一種有效的方法。

1 拆卸任務(wù)流程分析與建模

在裝備拆卸過(guò)程中，各拆卸任務(wù)存在以下流程關(guān)系（以拆卸任務(wù)A 和B 為例）：

1）并行拆卸關(guān)系。拆卸任務(wù)A 和B 之間不存在優(yōu)先關(guān)系，即維修人員先開(kāi)展拆卸任務(wù)A 或B 都可以。

2）串行拆卸關(guān)系。拆卸任務(wù)A 優(yōu)先于B，即維修人員欲想開(kāi)展拆卸任務(wù)B，必須先完成拆卸任務(wù)A。

3）延遲拆卸關(guān)系。拆卸任務(wù)A 雖然優(yōu)先于拆卸任務(wù)B，但并不是維修人員只有在完成拆卸任務(wù)A以后才能開(kāi)展拆卸任務(wù)B。而是在開(kāi)展拆卸任務(wù)A的過(guò)程中的某一時(shí)刻及該時(shí)刻以后，就可以開(kāi)展拆卸任務(wù)B。

上述這3 種拆卸任務(wù)流程關(guān)系，可采用圖形語(yǔ)言進(jìn)行描述，分別如圖1～圖3 所示。

圖1 并行拆卸關(guān)系

圖2 串行拆卸關(guān)系

圖3 延時(shí)拆卸關(guān)系

假設(shè)拆卸任務(wù)A 和B 的拆卸時(shí)間分別為tA和tB，則這3 種流程關(guān)系的總的維修時(shí)間T 分別為：

1）并行拆卸關(guān)系

2）串行拆卸關(guān)系

3）延時(shí)拆卸關(guān)系

令tAB為開(kāi)展拆卸任務(wù)B 延遲于開(kāi)展拆卸任務(wù)A 的最短時(shí)間，則式（3）中：為開(kāi)展拆卸任務(wù)B 延遲于開(kāi)展拆卸任務(wù)A 的實(shí)際時(shí)間，。

對(duì)此，可采用矩陣來(lái)描述一個(gè)復(fù)雜維修任務(wù)中各拆卸任務(wù)的流程關(guān)系：

則sij的賦值結(jié)果為：

則在得到sij的基礎(chǔ)上，sji的賦值結(jié)果為：

2 適應(yīng)度函數(shù)模型

對(duì)于單裝的維修任務(wù)，應(yīng)以維修時(shí)間最短的拆卸方式作為其在維修性試驗(yàn)驗(yàn)證時(shí)的拆卸方式。這樣根據(jù)這個(gè)拆卸方式所獲取的維修性試驗(yàn)驗(yàn)證數(shù)據(jù)才能科學(xué)地反映裝備的維修性設(shè)計(jì)水平，進(jìn)而作為有效的試驗(yàn)數(shù)據(jù)。與此同時(shí)，在各拆卸任務(wù)進(jìn)行轉(zhuǎn)換時(shí)，對(duì)于復(fù)雜的維修任務(wù)相比各拆卸任務(wù)的拆卸時(shí)間，工具更換和人員換位等時(shí)間通常較為短暫，對(duì)此，本文不予考慮，且不考慮人員的專業(yè)差別。

對(duì)于單裝的維修任務(wù)，令它的拆卸并行度為D［2，5］，即表示在維修過(guò)程中的某個(gè)時(shí)刻，最多可以同時(shí)開(kāi)展D 個(gè)拆卸任務(wù)。則所建立的評(píng)價(jià)拆卸任務(wù)規(guī)劃結(jié)果的適應(yīng)度函數(shù)模型為：

3 面向連續(xù)性時(shí)空優(yōu)化問(wèn)題的CSA

受自然界中烏鴉覓食和生存行為的啟發(fā)，伊朗學(xué)者Alireza［6］提出了CSA。目前，國(guó)內(nèi)學(xué)者發(fā)表的有關(guān)CSA 的文獻(xiàn)資料還比較少，Alireza 給出了CSA的4 個(gè)假設(shè)條件：

1）烏鴉是群居的鳥(niǎo)類。

2）烏鴉能夠記住它們的藏身之所。

3）烏鴉能夠跟蹤同類去完成盜竊。

4）在完成盜竊后，烏鴉能夠以一定的概率去避免它們的藏身之所被發(fā)現(xiàn)。

1）烏鴉c不知曉自己已經(jīng)被同類跟蹤，那么烏鴉i 就會(huì)成功地飛往烏鴉c的藏身之所mtc，則烏鴉i在第t+1 代時(shí)的位置為：

2）烏鴉c已經(jīng)知曉自己被同類跟蹤，則烏鴉c就會(huì)設(shè)法避免同類發(fā)現(xiàn)自己的藏身之所。同時(shí)，烏鴉c也會(huì)以飛往其他位置來(lái)避免自己的藏身之所被發(fā)現(xiàn)，則烏鴉i在第t+1 代時(shí)的位置為：

式中，L 與U 分別為個(gè)體取值的下限與上限。

在個(gè)體比較結(jié)束后，進(jìn)行適應(yīng)度函數(shù)值比較。至此，第t 次迭代計(jì)算即完成，若t＜M，則t=t+1，算法繼續(xù)進(jìn)行迭代計(jì)算，直至滿足終止條件時(shí)退出循環(huán)，并輸出最優(yōu)解及其適應(yīng)度函數(shù)值。

4 面向PDTP 問(wèn)題的CSA

PDTP 問(wèn)題是一個(gè)NP-hard 問(wèn)題，基本的CSA并不適用，這就需要對(duì)CSA 進(jìn)行離散化處理。在將各拆卸任務(wù)進(jìn)行編號(hào)后，即可令種群中的每個(gè)個(gè)體為各拆卸任務(wù)的合理排列。CSA 的任務(wù)即是結(jié)合所建立的適應(yīng)度函數(shù)模型，搜索最優(yōu)的拆卸任務(wù)規(guī)劃結(jié)果。對(duì)此，引入遺傳算法（Genetic Algorithm，GA）的交叉、變異操作方式［7-8］，實(shí)現(xiàn)CSA 的離散化處理。

4.1 交叉操作

交叉操作是GA 重要的個(gè)體更新方式，通過(guò)交叉操作能夠使不同的個(gè)體間進(jìn)行有效地“互動(dòng)”，進(jìn)而增加產(chǎn)生優(yōu)秀個(gè)體的機(jī)會(huì)。本文所采用的交叉操作方式為在拆卸優(yōu)先關(guān)系算子指導(dǎo)下的兩個(gè)個(gè)體間交叉操作。假設(shè)拆卸優(yōu)先關(guān)系算子J1為12 211，兩個(gè)參與交叉操作的個(gè)體I1和I2分別為53 241 和21 543，令拆卸任務(wù)5 和3 為串行拆卸關(guān)系，并記I1與I2交叉操作后產(chǎn)生的個(gè)體為I1。則在拆卸優(yōu)先關(guān)系算子的指導(dǎo)下，I1的前3 個(gè)拆卸任務(wù)的產(chǎn)生方式如圖4 所示。

圖4 個(gè)體交叉操作過(guò)程示意圖

繼續(xù)完成圖4 中的交叉操作可產(chǎn)生I1為52 134，并記這種交叉操作方式的函數(shù)表達(dá)式為：

4.2 變異操作

變異操作是GA 的另一種個(gè)體更新方式，通過(guò)變異操作能夠使種群中的個(gè)體在不需要其他個(gè)體的幫助下就可產(chǎn)生新的個(gè)體。本文采用的變異操作方式為在不影響其他拆卸任務(wù)間流程關(guān)系的條件下，選取個(gè)體中流程關(guān)系為并行拆卸的兩個(gè)拆卸任務(wù)，將這兩個(gè)拆卸任務(wù)的位置進(jìn)行互換。假設(shè)I1為53 241，拆卸任務(wù)2 和1 為并行拆卸關(guān)系，且拆卸任務(wù)2 和1 無(wú)論誰(shuí)先拆卸，都不影響I1內(nèi)部的流程關(guān)系，則I1經(jīng)變異操作后產(chǎn)生的個(gè)體I?1為53 142，并記這種變異操作方式的函數(shù)表達(dá)式為：

式中，a 和b 為位置互換的兩個(gè)拆卸任務(wù)。

4.3 CSA 離散化處理

至此，在建立交叉、變異操作函數(shù)的基礎(chǔ)上，則當(dāng)r1＞P 時(shí)，式（8）的離散化處理方法為：

式中，B 為閾值。

當(dāng)r1≤P 時(shí)，式（9）的離散化處理方法為：

式（11）的離散化處理方法為：

至此，面向PDTP 問(wèn)題的CSA 的迭代計(jì)算流程如圖5 所示。

圖5 面向PDTP 問(wèn)題的CSA

5 應(yīng)用實(shí)例

以維修任務(wù)“某型裝備動(dòng)力艙吊艙”為例，該維修任務(wù)共包含22 項(xiàng)拆卸任務(wù)，各拆卸任務(wù)的拆卸時(shí)間如表1 所示。

表1 各拆卸任務(wù)的拆卸時(shí)間（單位：min）

篇幅所限，本文不再給出流程關(guān)系矩陣S，僅給出維修任務(wù)的流程關(guān)系圖，如圖6 所示。圖6 中虛線框1 和2 中的拆卸任務(wù)對(duì)于各自虛線框外的拆卸任務(wù)具有相同的流程關(guān)系，如拆卸任務(wù)A 同虛線框1 中所有的拆卸任務(wù)為串行拆卸關(guān)系。

圖6 動(dòng)力艙吊艙流程關(guān)系圖

由圖6 可以看出，拆卸任務(wù)間的并行拆卸關(guān)系較多，合理規(guī)劃拆卸任務(wù)的空間較大。令D=4 和5，J1為動(dòng)態(tài)算子，a=J，b=K，N=10，M=100，P=0.1，fl=2，B=1。則CSA 求取的適應(yīng)度函數(shù)值變化情況分別如圖7 和下頁(yè)圖8 所示。

圖7 D=4 時(shí)，適應(yīng)度函數(shù)值收斂曲線

圖8 D=5 時(shí)，適應(yīng)度函數(shù)值收斂曲線

由圖7 和圖8 可以看出，隨著迭代次數(shù)的增加，CSA 的最優(yōu)適應(yīng)度函數(shù)值逐漸減小，并很快收斂。平均適應(yīng)度函數(shù)值也隨著迭代次數(shù)的增加和最優(yōu)適應(yīng)度函數(shù)值的減小而呈現(xiàn)減小的趨勢(shì)。表明CSA 的尋優(yōu)能力和搜索能力良好，實(shí)現(xiàn)了對(duì)裝備并行拆卸任務(wù)進(jìn)行有效規(guī)劃的目的。

值得說(shuō)明的是，拆卸任務(wù)U 和V 嚴(yán)格意義來(lái)講為延時(shí)拆卸關(guān)系，但由于拆卸任務(wù)U 的拆卸時(shí)間較短，且出于安全等因素的考慮，維修人員在實(shí)際拆卸時(shí)，通常是完成拆卸任務(wù)U 以后再開(kāi)展拆卸任務(wù)V，故將其定義為串行拆卸關(guān)系。當(dāng)D=4時(shí)，CSA 求取的最優(yōu)并行拆卸任務(wù)規(guī)劃結(jié)果如圖9 所示。

圖9 D=4 時(shí)，CSA 求取的最優(yōu)并行拆卸任務(wù)規(guī)劃結(jié)果

鑒于本文采用GA 的交叉、變異操作方式實(shí)現(xiàn)了CSA 的離散化處理，故選取GA 同CSA 進(jìn)行比較。令GA 的交叉、變異操作方式同CSA，交叉概率為0.95，變異概率為0.05。選擇輪盤(pán)賭策略作為GA的個(gè)體選擇策略，令N=10，M=100，分別對(duì)CSA 和GA 獨(dú)立計(jì)算30 次［9］，則兩種算法求取的最優(yōu)適應(yīng)度函數(shù)值的質(zhì)量如表2 所示。

表2 CSA 與GA 求取的最優(yōu)適應(yīng)度函數(shù)值質(zhì)量

由表2 可以看出，在相同的種群規(guī)模和迭代次數(shù)等條件下，對(duì)本文給出的最優(yōu)適應(yīng)度函數(shù)值的4項(xiàng)指標(biāo)進(jìn)行逐項(xiàng)比較，CSA 皆小于GA，即表明CSA優(yōu)于GA，驗(yàn)證了CSA 的優(yōu)越性。

6 結(jié)論

針對(duì)裝備并行拆卸任務(wù)規(guī)劃問(wèn)題，在采用GA個(gè)體更新方式的基礎(chǔ)上，本文提出了一種離散CSA，有效解決了裝備PDTP 問(wèn)題。并將CSA 同GA進(jìn)行了比較，驗(yàn)證了CSA 離散方式的可行性和優(yōu)越性。本文所提出的面向PDTP 問(wèn)題的CSA，具有收斂速度快和尋優(yōu)效果好的優(yōu)點(diǎn)，為有效開(kāi)展裝備維修性試驗(yàn)驗(yàn)證工作提供了有效的決策方法。