徐 達(dá)，焦慶龍

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1）烏鴉是群居的鳥類。

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

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

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

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

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

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

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

4 面向PDTP 問題的CSA

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

4.1 交叉操作

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

圖4 個體交叉操作過程示意圖

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

4.2 變異操作

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

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

4.3 CSA 離散化處理

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

式中，B 為閾值。

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

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

至此，面向PDTP 問題的CSA 的迭代計算流程如圖5 所示。

圖5 面向PDTP 問題的CSA

5 應(yīng)用實例

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

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