基于角色復(fù)雜性的損傷修復(fù)方案優(yōu)化模型

曾 慶，尤志鋒，石 全

(陸軍工程大學(xué)石家莊校區(qū) 裝備指揮與管理系，石家莊 050003)

制定出分工的方案后，如何評價其效果有著重要的意義：它既可以對分工方案作出評價，又可以對制定方案的人的水平、能力進(jìn)行評估。便于發(fā)現(xiàn)分工方案存在的問題，既可以用來改進(jìn)方案，提高執(zhí)行的效率，又可以發(fā)現(xiàn)人員能力、水平方面的差距，以便有針對性的進(jìn)行訓(xùn)練，以提高搶修員的搶修能力、水平。對搶修分工方案最直接最準(zhǔn)確的辦法就是對其分工后任務(wù)的執(zhí)行效率和執(zhí)行時間進(jìn)行測度。然而這種方法需要實(shí)際執(zhí)行搶修操作，具有成本高、危險性強(qiáng)的不足，又因?yàn)樵S多場合需要在不執(zhí)行方案的情況下進(jìn)行評估。因此，必須尋找一種更好的辦法來對這種直接的方法進(jìn)行替代。復(fù)雜性是難度和不確定性的度量，能夠反應(yīng)時間、效率等指標(biāo)，因此這里用分工所帶來的搶修員角色復(fù)雜性來對其效果進(jìn)行評估。并用分工所帶來的角色復(fù)雜性與時間進(jìn)行相關(guān)性分析，對該方法進(jìn)行驗(yàn)證。最后結(jié)合第三章的分工復(fù)雜性給出了搶修員角色復(fù)雜性的兩個應(yīng)用。

1 搶修員角色復(fù)雜性分析

文獻(xiàn)[1-2]通過實(shí)驗(yàn)論證了組織結(jié)構(gòu)適應(yīng)性的測度參數(shù)為：工作負(fù)載、交流和個體間的依賴關(guān)系，并用這3個關(guān)系來對組織結(jié)構(gòu)的適應(yīng)性進(jìn)行評價。其實(shí)這里的組織結(jié)構(gòu)的適應(yīng)性也可以看作是組織結(jié)構(gòu)的復(fù)雜性。其中組織可以退化成單個搶修人員，單個搶修人員可以進(jìn)化為搶修組織的一個特例。組織的適應(yīng)性其實(shí)就是搶修人員復(fù)雜性的一種體現(xiàn)。因此搶修人員的角色復(fù)雜性應(yīng)當(dāng)包含負(fù)載、協(xié)作量等。除此之外角色復(fù)雜性還應(yīng)當(dāng)包含角色所負(fù)責(zé)作業(yè)的內(nèi)聚性和所需資源的內(nèi)聚性。因此角色復(fù)雜性主要包含以下5個方面：

1) 搶修人員的內(nèi)部負(fù)載。文獻(xiàn)[2]只考慮了分配到任務(wù)執(zhí)行人員的任務(wù)總數(shù)量。由前面章節(jié)的分析可知，不同的搶修作業(yè)的復(fù)雜性系數(shù)是不同的。因此只考慮數(shù)量，忽略搶修作業(yè)的復(fù)雜性系數(shù)顯然是不精確的。因此這里加入搶修作業(yè)復(fù)雜性系數(shù)，用復(fù)雜性系數(shù)之和來代表搶修員的內(nèi)部工作負(fù)載。設(shè)任務(wù)分工的結(jié)果為

則第j個搶修人員的內(nèi)部總負(fù)載為

其中，w(i)為第i個基本搶修作業(yè)的復(fù)雜性系數(shù)，其具體求法見第6章。n為j搶修員所負(fù)責(zé)的搶修任務(wù)的數(shù)量。則m個搶修員總的角色復(fù)雜性為

其中m為搶修人員的總數(shù)量。

2) 搶修員之間的耦合關(guān)系。搶修員之間的耦合關(guān)系其實(shí)是搶修員的外部負(fù)載。耦合關(guān)系主要有重合關(guān)系和銜接關(guān)系組成。重合關(guān)系：由于損傷的復(fù)雜性，搶修操作往往需要多人協(xié)作才能完成。因此在同一基本搶修作業(yè)上相關(guān)的搶修員之間就構(gòu)成了耦合關(guān)系。搶修作業(yè)銜接關(guān)系是兩個搶修員負(fù)責(zé)的基本搶修任務(wù)在邏輯順序上存在直接的前后銜接關(guān)系，即為緊前作業(yè)或緊后作業(yè)。這兩種關(guān)系越多，搶修員之間的交流、協(xié)同就越多，其執(zhí)行過程就越復(fù)雜。設(shè)m個搶修員之間的協(xié)作矩陣[A]m×m為其中：

則第j個搶修員的外部協(xié)作負(fù)載為

則由搶修員之間的耦合關(guān)系引起的外部協(xié)作負(fù)載總和為

3) 基本搶修作業(yè)的內(nèi)聚性。在執(zhí)行搶修任務(wù)分配時需要遵循“盡量將相近的任務(wù)分配給同一搶修員”這一原則。因?yàn)槿蝿?wù)相近時可以相互參考、相互借鑒，這樣可以省去思維、動作、工具的轉(zhuǎn)換帶來的時間浪費(fèi)。由于基本搶修作業(yè)的粒度較大，所以在操作過程圖中距離較近的搶修作業(yè)的相近度較高。因此這里用分配給搶修員的所有基本搶修作業(yè)間在BDR_EPN模型上的距離來表示其內(nèi)聚性：

其中nj=|T(j)|為分配給第j個搶修員的搶修作業(yè)的總數(shù)量。則：

4) 資源的內(nèi)聚性。資源主要指搶修過程所用到的工具、設(shè)備、資料等物質(zhì)資源。資源的內(nèi)聚性是指某個搶修員所負(fù)責(zé)的搶修作業(yè)集中，所有兩兩作業(yè)的相同的資源交集的數(shù)量之和的大小。由于在有些搶修過程中，雖然使用的資源相同，但是其使用的方式大不相同，如標(biāo)準(zhǔn)使用和應(yīng)急他用。這種情況下可以將其看作兩種不同的資源。顯然如果兩個作業(yè)之間的資源內(nèi)聚性較大，就可以省去許多不必要的資源轉(zhuǎn)換時間，也可以利用資源使用的連續(xù)性提高資源的使用效率。設(shè)T(j)為第j個搶修員所分配到的搶修作業(yè)集，|T(j)|為其數(shù)量。則搶修物質(zhì)資源內(nèi)聚性為

其中n(i)為第i個基本搶修作業(yè)和第j個基本搶修作業(yè)所需的物質(zhì)資源的交集中資源的數(shù)量。

由于內(nèi)聚性與復(fù)雜性成反向關(guān)系，所以得資源內(nèi)聚性引發(fā)的搶修員角色復(fù)雜性為

其中n(i)為第個搶修作業(yè)所需的資源總數(shù)量。

5) 搶修員角色復(fù)雜性的綜合。對復(fù)雜性指標(biāo)進(jìn)行綜合，是一個情境選擇問題，要根據(jù)不同的情況，采用不同的方法。其中效果最好的兩個是歐幾里得范式綜合與信息熵綜合。但是一般情況下信息熵所得的復(fù)雜性測度結(jié)果都比較小，一般不便于兩者之間進(jìn)行比較。由于該章所得復(fù)雜性結(jié)果要與前面的進(jìn)行比較以便對分工方案和搶修員的能力進(jìn)行評估，因此這里選用歐幾里德范式進(jìn)行綜合。

由于上述熵指標(biāo)都已經(jīng)是效益型指標(biāo)。即指標(biāo)越大，復(fù)雜性越大，且求取的方法相同，因此無需對原始指標(biāo)進(jìn)行變換，可直接應(yīng)用。經(jīng)過專家組的評判其各個指標(biāo)的權(quán)重為：W=(w1,w2,w3,w4)，第i個指標(biāo)的復(fù)雜性評價值為hf，可得其搶修員的角色復(fù)雜性測度為

2 基于角色復(fù)雜性的方案優(yōu)化[3-4]

由上面搶修過程模型可以看出，不同的分工方案對應(yīng)著不同的搶修邏輯模型。因此，不易用一個固定的流程來對所有的方案進(jìn)行優(yōu)化分析。當(dāng)搶修方法和搶修工藝確定后，搶修基本作業(yè)的順序關(guān)系基本上就確定了。尤其是有著緊密連接關(guān)系的基本搶修作業(yè)之間，誰先誰后是必須固定的。但是對于一些沒有緊密連接關(guān)系的搶修作業(yè)，則需根據(jù)總體優(yōu)化的目標(biāo)來進(jìn)行安排，確定他們之間是并行還是串行或是其他關(guān)系[5]。由搶修員的角色復(fù)雜性影響機(jī)制可以看出，當(dāng)分工方案確定后，這些作業(yè)之間的關(guān)系安排將直接影響到搶修員的角色復(fù)雜性。因此利用角色復(fù)雜性可以實(shí)現(xiàn)對搶修作業(yè)的調(diào)度與優(yōu)化，為順利實(shí)現(xiàn)搶修任務(wù)打下基礎(chǔ)。下面基于搶修員角色復(fù)雜性利用分層嵌套遺傳算法對分工方案以及流程邏輯結(jié)構(gòu)設(shè)計方案進(jìn)行優(yōu)化[6]。

2.1 嵌套遺傳算法求解的基本思路

搶修員角色復(fù)雜性主要是由分工方案和搶修流程的邏輯結(jié)構(gòu)兩個因素決定的[7]。因此，需要對兩者展開搜索優(yōu)化，以便找到與最小復(fù)雜性相適應(yīng)的分工方案和邏輯結(jié)構(gòu)。其基本思路為：利用兩步搜索遺傳算法。第一步：對任務(wù)分工方案進(jìn)行搜索。第二部：在某一個分工方案的基礎(chǔ)上對流程結(jié)構(gòu)進(jìn)行搜索，找到使特定方案的角色復(fù)雜性最小的邏輯結(jié)構(gòu)。最后選擇所有的方案中角色復(fù)雜性最小的邏輯結(jié)構(gòu)。并將其對應(yīng)的方案和邏輯結(jié)構(gòu)作為最終結(jié)果進(jìn)行輸出[8]。這其實(shí)是一個嵌套結(jié)構(gòu)，第二部嵌在第一步之中，其基本原理如圖1所示。

2.2 基本步驟

1) 固定方案優(yōu)化結(jié)構(gòu)。為每一個可能的方案找到其使作業(yè)內(nèi)聚性和外部協(xié)作性最小的邏輯結(jié)構(gòu)，其基本模型如下；

min={W(m)+J(m)}

s.t 不同的邏輯結(jié)構(gòu)

搶修作業(yè)的約束

2) 固定邏輯結(jié)構(gòu)優(yōu)化方案。找到一個可能使內(nèi)部負(fù)載和資源內(nèi)聚性最小的分工方案，其基本模型如下；

min={N(m)+T(m)}

s.t 不同的分工方案

3) 第2步所得到的方案及其對應(yīng)的在第一步求出的結(jié)構(gòu)，即為最終結(jié)果。

2.3 邏輯結(jié)構(gòu)優(yōu)化算法設(shè)計

1) 編碼方案。由于緊前作業(yè)和緊后作業(yè)是一對對偶關(guān)系，即若是的緊前作業(yè)，則必然是的緊后作業(yè)。所以只需對其中一個進(jìn)行確定就可以確定搶修作業(yè)過程的邏輯結(jié)構(gòu)圖。這里采用緊后作業(yè)進(jìn)行表示，利用二進(jìn)制矩陣編碼。基因座號的橫縱坐標(biāo)都用基本搶修作業(yè)的編號表示，其編號范圍為[1，n]。基因的值為1或0，1表示所在基因座所表示的基本搶修作業(yè)屬于其緊后作業(yè)，0表示不屬于。這個編碼的前提是需要知道開始作業(yè)。

如圖2所示，Xij表示第i個搶修作業(yè)與第j個搶修作業(yè)的關(guān)系。Xij表明第j個搶修作業(yè)是第i個搶修作業(yè)的緊后作業(yè)，0則表明不是緊后作業(yè)。

如圖3所示的邏輯結(jié)構(gòu)可以用如下編碼表示。

010100|001000|000010|000010|000001|000000

由于在確定結(jié)構(gòu)的過程中，需要用到任務(wù)分配方案，所以需知道第二步的編碼方案。任務(wù)分工的編碼方案仍然采用二進(jìn)制矩陣編碼。基因座編號橫坐標(biāo)為基本搶修作業(yè)的編號，縱坐標(biāo)為搶修單元的編號，基因值為搶修單元與搶修作業(yè)之間的關(guān)系(圖4)。

這種編碼方案既可以表示一個作業(yè)由多人同時完成，也可以表示一個人在不同的時段可以完成多個作業(yè)。

2) 初始種群生成。為了對流程的邏輯結(jié)構(gòu)進(jìn)行表示，這里用一個二元組來表示搶修作業(yè)，即(xi,xi·)，其中xi·表示搶修作業(yè)xi的緊后作業(yè)集合。這樣所有搶修作業(yè)的二元組表示即可以確定一個唯一的搶修流程結(jié)構(gòu)。流程結(jié)構(gòu)的選擇就是選擇每個搶修作業(yè)的緊后作業(yè)集合。由編碼方案可以看出基因的長度較長為：n×n。如果不對其中部分基因座的基因值進(jìn)行限制，則搜索的空間太大，當(dāng)n的值較大時，搜索的速度很慢，也容易陷入局部最優(yōu)。這個集合的大小決定了搜索空間的大小。按照搶修方法確定的搶修工藝對某個作業(yè)的兩個集合進(jìn)行限定，以縮小搜索的空間，提高搜索的效率和準(zhǔn)確性。搶修作業(yè)的緊后作業(yè)集不具有傳遞性，這樣可以保證對循環(huán)結(jié)構(gòu)仍然有效。

根據(jù)搶修方法和搶修工藝所確定的搶修作業(yè)約束對部分基因座的值進(jìn)行限制。如某些作業(yè)只能在另一個作業(yè)的緊后面發(fā)生，或流程中不存在循環(huán)等。當(dāng)限制確定后，在可以選擇的基因座處，用隨機(jī)數(shù)產(chǎn)生器產(chǎn)生0或1的值，作為一個個體，假設(shè)共有n′個基因座可以選擇，則共產(chǎn)生2n′個個體。根據(jù)其大小按照輪盤賭選擇地方法從中選出20、40、100個個體作為初始種群。

3) 適應(yīng)度函數(shù)。從角色復(fù)雜性的影響因素可以看出，邏輯結(jié)構(gòu)只對基本作業(yè)的內(nèi)聚性、角色的耦合性產(chǎn)生影響。角色耦合性越大復(fù)雜性越大；作業(yè)的內(nèi)聚性越大，復(fù)雜性越小，然而在求取角色內(nèi)聚性對復(fù)雜性的影響時，已經(jīng)對其做了一定的變換，與復(fù)雜性成正相關(guān)關(guān)系，所以W(m),J(m)與復(fù)雜性是一致正相關(guān)的關(guān)系，因此這里用兩者之和作為邏輯結(jié)構(gòu)優(yōu)化的適應(yīng)度函數(shù)：

f=W(m)+J(m)

其具體的計算公式已在2中給出。只需將公式轉(zhuǎn)換成代碼即可。

4) 交叉算子。矩陣編碼，在遺傳操作的過程中將整個矩陣作為遺傳個體進(jìn)行操作。隨機(jī)產(chǎn)生一個區(qū)間[1,n]的服從均勻分布的隨機(jī)數(shù)，將兩個矩陣染色體中隨機(jī)數(shù)所代表的兩個行(或列)照一定的概率pc進(jìn)行交換。這樣雖然是對位交換，可以保證交換后的染色體仍滿足原來的約束。但是卻可以改變各個作業(yè)節(jié)點(diǎn)之間的關(guān)系使其出現(xiàn)以下兩種情況：

一個節(jié)點(diǎn)的今后節(jié)點(diǎn)集中的兩個節(jié)點(diǎn)之間出現(xiàn)今后關(guān)系(圖5)；編碼當(dāng)中除第一列(起始節(jié)點(diǎn))和最后一行(結(jié)束節(jié)點(diǎn))外，出現(xiàn)列中全部為零或行全部為零的現(xiàn)象(圖)。這兩種情況都與搶修作業(yè)流的定義不符(DBR-EPN)，需要排除。因此，當(dāng)交叉后若出現(xiàn)上述兩種情況之一，則需要將其中不符合要求的基因值進(jìn)行改變使上述兩種情況不再出現(xiàn)。

5) 變異算子.隨機(jī)產(chǎn)生兩個區(qū)間[1,n]的服從均勻分布的隨機(jī)數(shù)，將產(chǎn)生的這兩個數(shù)作為坐標(biāo)值，來定位染色體矩陣中基因的位置。若該該基因位置由于約束的設(shè)定而不能改變，或變異后出現(xiàn)上述兩種情況，則重新生成隨機(jī)數(shù)，直到找到?jīng)]有約束限制可以改變?yōu)橹埂Ｒ砸欢ǖ母怕蕄m將該基因值與1相減后去絕對值。

6) 終止條件。如果連續(xù)3次迭代所得到的種群中適應(yīng)度最大的值之間差的絕對值都小于某一個制定的值，則增大選擇和變異的概率，重新迭代。若所得種群的最大值仍然與沒有改變之前的最大值之間差值的絕對值仍然小于給定的值ξ，則停止迭代，否則繼續(xù)，直到滿足上述條件為止。

分工方案優(yōu)化算法設(shè)計與邏輯結(jié)構(gòu)優(yōu)化的算法設(shè)計基本相同，這里就不在重復(fù)，只說明一下初始種群的限制：根據(jù)搶修員的能力水平及專業(yè)限制結(jié)合搶修作業(yè)本身的特征進(jìn)行人工初步分配。其原則經(jīng)過初步分析是只要搶修員不能完成或不適合完成該項(xiàng)搶修作業(yè)，則將該搶修作業(yè)基因座對應(yīng)的搶修員設(shè)置為0。

3 實(shí)例分析與應(yīng)用[6]

這里以火炮身管拆卸為例對算法的運(yùn)行情況進(jìn)行測試。火炮身管拆拼是戰(zhàn)場上經(jīng)常遇到的搶修操作，其拆卸的快于否，直接影響著搶修操作的成敗，因此合理優(yōu)化身管拆卸作業(yè)步驟，對提高身管搶修效率具有十分重要的意義。火炮身管拆卸分為以下6步：① 打平炮身；② 抽出駐退機(jī)；③ 抽出復(fù)進(jìn)機(jī)；④ 卸下后座沖鐵；⑤ 后退炮身并固定；⑥ 用吊車抽出炮身。為了更加清楚的說明問題，以前五步為例進(jìn)行說明。共有2名中級修理工任何一名修理工可以勝任全部五項(xiàng)工作。打平炮身必須作為起始，后退炮身并固定必須作為結(jié)束。因此，該優(yōu)化內(nèi)容就變?yōu)榱藢?2)(3)(4)步的邏輯優(yōu)化，及兩名修理工的分工。按照上述嵌套遺傳算法模型，設(shè)置交叉概率為0.85，變異概率為0.05，最大進(jìn)化代數(shù)為200，初始種群數(shù)量為50。其遺傳進(jìn)化過程如圖6(左)所示。

經(jīng)過優(yōu)化得最優(yōu)方案為：1，2，3由搶修人員1完成，4，5由搶修人員2完成。(如圖7右所示)。其對應(yīng)的最優(yōu)邏輯結(jié)構(gòu)的編碼矩陣及最優(yōu)邏輯結(jié)構(gòu)圖分別如圖7(左和右)所示。最優(yōu)邏輯結(jié)構(gòu)所對應(yīng)的搶修人員角色復(fù)雜性為：8.843 0。算法運(yùn)行時間為0.13 ms。雖然該實(shí)例較為簡單但是與運(yùn)行同等簡單實(shí)例的普通遺傳算法(文獻(xiàn)[9])相比(3 ms)仍然具有較高的效率。

圖7 最優(yōu)邏輯結(jié)構(gòu)矩陣及流程

4 結(jié)論

提出了搶修員角色復(fù)雜性的概念及其計算模型。角色復(fù)雜性由分工方案和流程的邏輯結(jié)構(gòu)共同決定。與第三章任務(wù)分工本身的復(fù)雜性與搶修員角色復(fù)雜性相結(jié)合可以實(shí)現(xiàn)對搶修方案的評估，進(jìn)而評估搶修員的能力水平；同時基于搶修員角色復(fù)雜性，利用嵌套遺傳算法可以同時對分工和搶修邏輯結(jié)構(gòu)進(jìn)行優(yōu)化，為合理的安排基本搶修作業(yè)的順序、充分利用已有資源提供了更加科學(xué)的依據(jù)。