考慮協(xié)作度的雙人異步并行拆卸序列規(guī)劃

賈寶惠，任 帥，盧 翔

（中國(guó)民航大學(xué)航空工程學(xué)院，天津 300300）

1 引言

后勤保障分析國(guó)際程序規(guī)范（S3000L）明確要求產(chǎn)品在設(shè)計(jì)階段應(yīng)考慮在運(yùn)營(yíng)階段和報(bào)廢階段的拆卸，這要求在技術(shù)出版物中必須有相關(guān)拆卸流程，進(jìn)行拆卸序列規(guī)劃（Disassembly Sequence Planning，簡(jiǎn)稱DSP）設(shè)計(jì)階段有助于提高產(chǎn)品維修性且可對(duì)技術(shù)出版物進(jìn)行有效驗(yàn)證；運(yùn)營(yíng)階段或報(bào)廢階段可有效提高工作人員效率，降低維修成本。

DSP通過(guò)產(chǎn)品零部件的約束關(guān)系得到合理的拆卸順序，以達(dá)到“最佳目標(biāo)”，此目標(biāo)可為拆卸成本最小、拆卸收益最大、對(duì)環(huán)境污染最小等。DSP問(wèn)題隨著產(chǎn)品規(guī)模增長(zhǎng)，拆卸序列將爆炸式增長(zhǎng)，求解難度大。因此，大量學(xué)者開(kāi)展算法研究，提高求解效率，例如蟻群算法［1］，人工蜂群算法［2］、遺傳蝙蝠算法［3］但僅可進(jìn)行單人DSP。工程實(shí)踐中，經(jīng)常會(huì)遇到大型復(fù)雜產(chǎn)品，例如飛機(jī)的拆解，一般需要幾十人甚至幾百人共同進(jìn)行工作，因此多人并行DSP 問(wèn)題日益重要。文獻(xiàn)［4］提出了基于模糊粗糙集的并行DSP，可快速獲得近似最優(yōu)解。文獻(xiàn)［5］探討和確定操作者最佳數(shù)目，并提出異步并行DSP。文獻(xiàn)［6］建立可變序列矩陣搭建了串行與并行拆卸的橋梁。但上研究均是單個(gè)部件只能被單個(gè)執(zhí)行者進(jìn)行拆卸，未考慮執(zhí)行者之間的協(xié)作關(guān)系。文獻(xiàn)［7］提出了多人協(xié)作的并行DSP數(shù)學(xué)模型，但不能實(shí)現(xiàn)異步并行，需約束多人若要協(xié)作完成某操作時(shí)，必須同時(shí)開(kāi)始，同時(shí)結(jié)束，而不能實(shí)現(xiàn)一人先開(kāi)始，另一人中途加入。

綜上，因此，現(xiàn)有的多人DSP并未考慮到協(xié)作效率，且由于優(yōu)先約束關(guān)系的存在，有人員閑置的情況，不能真正實(shí)現(xiàn)異步并行，使得協(xié)作效率較低?；诖?，這里提出協(xié)作度概念，建立數(shù)學(xué)模型，實(shí)現(xiàn)兩人盡量少間歇或無(wú)間歇地異步并行拆卸序列提高拆卸效率，降低人力成本。

2 雙人協(xié)作異步并行DSP

2.1 拆卸優(yōu)先圖

這里所涉及DSP是完全拆卸，其目標(biāo)函數(shù)為拆卸時(shí)間最短，選用較簡(jiǎn)單的拆卸優(yōu)先圖進(jìn)行表達(dá)，如圖1所示。

圖1 拆卸優(yōu)先圖Fig.1 Disassembly Priority Diagram

A、B、C、D、E、F分別表示該產(chǎn)品的組成構(gòu)件，有向箭頭代表約束關(guān)系，表示各部件優(yōu)先約束關(guān)系，如F→A表示在拆卸A之前，必須先拆卸F，F(xiàn)為A的優(yōu)先操作。不同于前人研究的表達(dá)，這里所采用的拆解優(yōu)先圖使用分層表達(dá)，A為第0層，B、C為第一層，D為第二層，E作為第三層，F(xiàn)為第四層，通過(guò)分層表達(dá)便于對(duì)序列的“合規(guī)化處理”“，合規(guī)化處理”即為對(duì)隨機(jī)序列進(jìn)行處理使其滿足優(yōu)先約束。

DSP為離散組合優(yōu)化問(wèn)題，基于拆卸優(yōu)先圖模型，可將此問(wèn)題描述為：

產(chǎn)品可拆卸單元為N個(gè)，每次僅能拆卸其中一個(gè)，所求序列應(yīng)該滿足拆卸優(yōu)先關(guān)系，并且每個(gè)頂點(diǎn)都須遍歷且只能遍歷一次。A-F按1～6進(jìn)行排列，拆卸優(yōu)先矩陣R，如式（1）所示。

式中：Rrc—矩陣R的第r行第c列的數(shù)值4 即為拆卸優(yōu)先矩陣層數(shù)。通過(guò)搜索優(yōu)先矩陣可以將隨機(jī)序列進(jìn)行合規(guī)化處理，合規(guī)化處理流程圖，如圖2所示。

圖2 合規(guī)化處理流程圖Fig.2 Flow Chart of Compliance Processing

2.2 建模準(zhǔn)備

DSP中無(wú)法避免出現(xiàn)操作者存在閑置時(shí)間，例如某產(chǎn)品拆卸序列如下：操作者1：123；操作者2：45。若零件4受零件1的優(yōu)先約束，則在操作者2拆卸零件1時(shí)，操作者1將被閑置。若有足夠的空間可容許兩個(gè)人同時(shí)拆卸零件1，既可以節(jié)省二人的體力，也可有效減少工作總時(shí)間。因此下面提出異步并行協(xié)作，解決此問(wèn)題。

協(xié)作是指兩人一起完成操作，可分為同步并行與異步并行，同步并行是指兩操作者同時(shí)開(kāi)始和同時(shí)結(jié)束對(duì)同一零件的操作；異步并行是指在一人開(kāi)始某零件的拆卸工作之后，另一人可以加入此人的拆卸工作中。然而兩人同時(shí)進(jìn)行一個(gè)操作時(shí)其完成時(shí)間不一定為原操作時(shí)間的一半，因此在建立模型時(shí)需考慮二者協(xié)作效率對(duì)模型的影響，在此引入變量“協(xié)作度-εi”，是兩人在同時(shí)進(jìn)行某零部件拆卸時(shí)的協(xié)作效率，影響兩人同時(shí)進(jìn)行同一零部件的拆卸時(shí)間=ti×εi。i為零件號(hào)，ti為零件拆卸時(shí)間，為零件在兩人協(xié)作下的拆卸的時(shí)間。

協(xié)作度主要影響因素有拆卸容納人數(shù)、零件體積、零件質(zhì)量、連接件數(shù)量、是否可用工裝等。其值數(shù)據(jù)，如表1～表3所示。

表1 搬運(yùn)重物受重量影響量化標(biāo)準(zhǔn)Tab.1 Quantitative Criteria for Removal Rod Parts Affected by Weight

其中，m—搬運(yùn)物體質(zhì)量；L—搬運(yùn)桿件的長(zhǎng)度；j—連接件數(shù)量。表1確定了各搬運(yùn)重物受重量影響的量化標(biāo)準(zhǔn)邊界，若兩人同時(shí)進(jìn)行較輕物體的搬運(yùn)工作，則時(shí)間搬運(yùn)時(shí)間不會(huì)變化；若使用工裝，則需要準(zhǔn)備和撤回工裝的操作，因此協(xié)作度會(huì)有所增大；隨著物體重量的提升，單人搬運(yùn)的困難程度繼續(xù)增大，協(xié)作度隨之減小。同理，表2確定了搬運(yùn)桿件的長(zhǎng)度對(duì)協(xié)作度的影響；表3確定了連接件數(shù)量對(duì)協(xié)作度的影響，若連接件僅為1，則協(xié)作度為1，隨著連接件數(shù)量增多，連接件可由兩個(gè)人同時(shí)進(jìn)行連接件的拆卸，協(xié)作度可確定為（0.5～0.6），若使用工裝，協(xié)作度將有所減小。以上3個(gè)表格提出了協(xié)作度的量化方法，根據(jù)工人經(jīng)驗(yàn)進(jìn)行確定。

表2 搬運(yùn)桿件受長(zhǎng)度影響量化標(biāo)準(zhǔn)Tab.2 Quantitative Criteria for Removal Rod Parts Affected by Length

表3 協(xié)作度受緊固件數(shù)量影響量化標(biāo)準(zhǔn)Tab.3 Quantitative Criteria for Number of Fasteners

組合任務(wù)可以將搬運(yùn)任務(wù)的協(xié)作度與拆卸任務(wù)協(xié)作度進(jìn)行加權(quán)平均，權(quán)重考慮工作時(shí)間占比。

2.3 模型的數(shù)學(xué)描述

cti：無(wú)協(xié)作的零件拆卸開(kāi)始時(shí)間；

sti：無(wú)協(xié)作的零件拆卸結(jié)束時(shí)間；

cti’：協(xié)作下的零件拆卸開(kāi)始時(shí)間；

sti’：協(xié)作下的零件拆卸結(jié)束時(shí)間；

AS(i)：i的優(yōu)先約束零件，可從拆卸優(yōu)先矩陣中獲?。?/p>

此模型的拆卸目標(biāo)函數(shù)如下：

拆卸優(yōu)先約束如下：

某零件i由單人拆卸，則有：

若零件i的拆卸工作由2人同時(shí)開(kāi)始進(jìn)行，則有：

假設(shè)操作者1操作序列為m1，m3，操作者2的操作序列為m2，m2是m3的拆卸優(yōu)先約束，且stm1

式（2）～式（7）從數(shù)學(xué)上對(duì)模型進(jìn)行了描述。

3 遺傳-粒子群混合優(yōu)化算法

3.1 算子編碼、解碼及適應(yīng)度函數(shù)

將采取雙鏈結(jié)構(gòu)編碼，包含2個(gè)子序列。令v={v1，v2}表示雙鏈拆卸序列。其中v1={s1，…，sj，…，sN}為操作序列，sj表示操作，n=1，2，…，N；v2={q1，…，qn，…，qN}，qn表示v1鏈中的第n個(gè)操作由第qn操作者操作，qn=1，2，…，Q。q1=1，Q為操作者人數(shù)，則表示s1操作由操作者1完成。

首先通過(guò)1.1節(jié)中的方法對(duì)v1序列進(jìn)行“合規(guī)化處理”保證序列滿足優(yōu)先約束。

為計(jì)算適應(yīng)度值，設(shè)計(jì)適用的解碼方案，流程，如圖3所示。

圖3 解碼流程圖Fig.3 Decoding Flowchart

圖中：B—操作分配矩陣，例如B=［1，3，5；2，6，0］，說(shuō)明操作者1進(jìn)行1、3、5操作，操作者2進(jìn)行2、6操作；find函數(shù)功能：找到向量Y中所有大于零元素的位置；ct、st—操作開(kāi)始時(shí)間與結(jié)束時(shí)間矩陣，1*N；t—操作時(shí)間矩陣，1*N，各操作在單人操作下所需時(shí)間；為矩陣B的列數(shù)；F—零件的優(yōu)先約束向量；q—第q個(gè)操作者。

步驟一：根據(jù)雙鏈染色體建立矩陣B；

步驟二：ct=st=0，建立操作時(shí)間矩陣t；

步驟三：判斷操作者q拆卸的第i個(gè)零件是否被約束于別的零件。則比較操作者q的第i-1個(gè)零件的結(jié)束時(shí)間與其所有優(yōu)先零件的結(jié)束時(shí)間，最大者為i的開(kāi)始時(shí)間，i=1則將第i-1個(gè)零件結(jié)束時(shí)間視為0；否，將其開(kāi)始時(shí)間設(shè)定為前一零件的結(jié)束時(shí)間；

步驟四：計(jì)算上述零件拆卸結(jié)束時(shí)間，并更新約束矩陣，使該操作不再作為其他零件的約束零件；

步驟五：q=q+1；

步驟六：當(dāng)q達(dá)到總?cè)藬?shù)時(shí)，i+1；

步驟七：重復(fù)步驟三至步驟六，當(dāng)i>b時(shí)，返回步驟一；

步驟八：重復(fù)步驟三至步驟七N次。

至此，已求出所有零件在不考慮異步并行情況下的拆卸開(kāi)始及結(jié)束時(shí)間。然而，這并沒(méi)實(shí)現(xiàn)異步并行，求解考慮協(xié)作度的異步并行DSP，需對(duì)以上結(jié)果進(jìn)行處理，步驟如下：

步驟一：查找序列中是否存在操作者具有閑置時(shí)間；

步驟二：確定此段閑置時(shí)間另一操作者所拆卸零件；

步驟三：計(jì)算二人協(xié)作下所節(jié)省的實(shí)際。

步驟四：更新，并重復(fù)以上步驟。

在算法中實(shí)現(xiàn)，流程參照?qǐng)D，如圖4所示。

圖4 考慮協(xié)作處理流程圖Fig.4 Processing Flowchart Considered Collaboration

所求st中最大值即為最后一個(gè)拆卸零件的結(jié)束時(shí)間，也是適應(yīng)度函數(shù)。圖中：Q—人數(shù)為2；k、l—操作者的第k、l個(gè)操作；K、L—各操作者的操作個(gè)數(shù)；ts—協(xié)作操作節(jié)省的時(shí)間；Ts—協(xié)作操作節(jié)省的總時(shí)間；ε—協(xié)作度；ct、st—操作開(kāi)始時(shí)間與結(jié)束時(shí)間矩陣；ct’、st’—協(xié)作下操作開(kāi)始時(shí)間與結(jié)束時(shí)間矩陣，1*N。

3.2 遺傳-粒子群混合算法

粒子群算法（PSO）：

粒子群算法多適用于連續(xù)組合優(yōu)化問(wèn)題［8］，通過(guò)PSO 求解DSP這種離散問(wèn)題，需通過(guò)以下方法將其進(jìn)行對(duì)應(yīng)。

在產(chǎn)品模型基礎(chǔ)上，產(chǎn)生多個(gè)粒子，每個(gè)粒子由1-N的自然數(shù)組成，N為可拆卸零件個(gè)數(shù)，即可構(gòu)成一個(gè)粒子群。

前人將速度取值空間定為0，1來(lái)代表至下一代粒子元素是否發(fā)生變動(dòng)。但是通過(guò)此方式進(jìn)行粒子的移動(dòng)會(huì)導(dǎo)致產(chǎn)生不合規(guī)的粒子，需要再對(duì)粒子進(jìn)行合規(guī)劃處理，這里取消粒子群中速度概念。但是粒子群算法是將粒子的方向朝著更優(yōu)的粒子移動(dòng)，取消速度概念，但在宏觀上依然是粒子群算法行為。

遺傳算法（GA）：

遺傳交叉算子和變異算子是遺傳算法的重要操作［9-11］。在此問(wèn)題的求解中若對(duì)v1鏈進(jìn)行變異操作，則序列則需重新進(jìn)行合規(guī)化處理，可能導(dǎo)致變異操作無(wú)效，所以對(duì)v1鏈只進(jìn)行交叉操作。傳統(tǒng)的交叉變異算子會(huì)導(dǎo)致原本合規(guī)的父代染色體得到不合規(guī)的子代染色體。因此傳統(tǒng)的交叉算子將不適用。

（1）交叉是GA更新和探索解空間的關(guān)鍵操作。傳統(tǒng)的交叉算子可能會(huì)導(dǎo)致序列錯(cuò)誤，比如父代1：FEDBAC 與父代2：FECDBA在第3個(gè)點(diǎn)交叉則產(chǎn)生FECBAC與FEDDBA。

為保證基因的完整性，將使用優(yōu)先選擇交叉方式進(jìn)行交叉［12］：生成子代掩碼C1，為1-2的隨機(jī)排列，②C1中第一個(gè)數(shù)字是1，子代C2第一個(gè)基因從F1的第一個(gè)基因提取，并刪除F1與F2 中的該基因。③第二個(gè)數(shù)字是2，C2 提取父代2 的第一個(gè)基因，并刪除F1與F2的該基因。④重復(fù)步驟可得出新染色體C2。

（2）變異算子針對(duì)v2進(jìn)行，這能使在同樣的v1序列下，得到不同的人員工作規(guī)劃。

混合算法：

粒子群中若產(chǎn)生相對(duì)較優(yōu)的粒子，粒子都會(huì)朝其進(jìn)化，若此粒子并非全局最優(yōu)，且全局最優(yōu)的方向與此粒子的方向相反，則無(wú)法找到全局最優(yōu)解，使得局部搜索能力較強(qiáng)，對(duì)求解質(zhì)量要求不高時(shí)，該算法可高效求得高質(zhì)量的解，但非最優(yōu)解。

另外DSP是離散型數(shù)值尋優(yōu)問(wèn)題，且其序列有所約束，這容易導(dǎo)致初始種群本身就很有可能已散落在局部最優(yōu)解的而導(dǎo)致無(wú)法尋找到全局最優(yōu)解，從而得不出最優(yōu)序列。

遺傳算法通過(guò)變異可提高其全局搜索性，因此將遺傳算法與其進(jìn)行結(jié)合，可以增強(qiáng)其全局搜索能力，提出了GA-PSO混合的優(yōu)化算法。

GA-PSO優(yōu)化算法流程，如圖5所示。所提的混合算法是從用遺傳算法來(lái)模擬粒子群算法的角度出發(fā)，重構(gòu)遺傳算法交叉及變異算子。從宏觀上來(lái)看，其行為是粒子群算法；從微觀來(lái)看，其行為是遺傳算法，從而構(gòu)成GA-PSO混合算法。

圖5 GA-PSO算法求解流程Fig.5 GA-PSO Algorithm Solution Process

4 實(shí)例驗(yàn)證及分析

以文獻(xiàn)［13］的飛機(jī)起落架為例，以文中方法求解最優(yōu)拆卸序列。飛機(jī)起落架結(jié)構(gòu)復(fù)雜，包含15個(gè)零件，其伴隨著大量的緊固件，在拆卸優(yōu)先圖中可將緊固件和其作用對(duì)象綁定，從而簡(jiǎn)化拆卸優(yōu)先圖，如圖6所示。

圖6 起落架拆卸優(yōu)先圖Fig.6 Priority Diagram for Landing Gear Disassembly

借鑒文獻(xiàn)的研究成果，對(duì)各個(gè)零件的拆卸時(shí)間進(jìn)行估計(jì)［14］，并根據(jù)專家經(jīng)驗(yàn)給出各零件的拆卸協(xié)作度，零件拆卸時(shí)間及協(xié)作度，如表4所示。

表4 各零部件拆卸時(shí)間（單位：秒）Tab.4 Disassembly Time of Each Part（Unit：s）

分別通過(guò)現(xiàn)有方法和考慮協(xié)作度的雙人異步并行DSP對(duì)起落架拆卸序列進(jìn)行求解，求解結(jié)果，如表5所示。為便于觀察，將結(jié)果繪制為甘特圖，如圖7所示。

表5 起落架拆卸方案Tab.5 Landing Gear Disassembly Scheme

圖7 拆卸序列規(guī)劃Fig.7 Disassembly Sequence Planning

易看出在未考慮協(xié)作度情況下，兩操作者分別操作各自劃分的序列，并無(wú)交叉；在考慮考慮協(xié)作度的雙人異步并行拆卸序列中，對(duì)零件37和零件82進(jìn)行異步并行拆卸，對(duì)零件58進(jìn)行同步并行拆卸。

在操作者2完成零件22的拆卸之后，由于37零件對(duì)38零件有優(yōu)先約束，因此操作者2本應(yīng)在操作者1完成37零件的拆卸后再開(kāi)始工作，時(shí)間閑置?？紤]異步并行，操作者2加入與操作者1共同拆卸37零件。節(jié)省了操作者2的閑置時(shí)間，提高了效率。

飛機(jī)維修最主要的成本就是人力成本，對(duì)比得，前者拆卸時(shí)間為2412s，而這里所用方法拆卸時(shí)間為2349.6s，節(jié)省2.5%，這對(duì)于民航業(yè)大量的維修任務(wù)量來(lái)說(shuō)，可有效地減少拆卸工作損耗時(shí)間，提高拆卸效率，降低人力成本。

另外，算法訓(xùn)練過(guò)程，如圖8所示。種群規(guī)模為10，算法可以在15代以內(nèi)收斂至最優(yōu)。

圖8 算法訓(xùn)練過(guò)程Fig.8 Algorithm Training Process

5 結(jié)論

（1）通過(guò)協(xié)作度概念的提出，建立了考慮協(xié)作度的雙人異步并行DSP，模型允許操作者異步并行拆卸零件，提高了拆卸工作的靈活性，使拆卸工作更加高效。

（2）建立了適用的算法編碼與解碼方案，并結(jié)合遺傳與粒子群算法，設(shè)計(jì)了高效的求解算法。

（3）實(shí)例驗(yàn)證了這里所提出雙人協(xié)作異步并行DSP更加節(jié)省時(shí)間，可以為雙人拆卸問(wèn)題提供更加高效的方案，并且為將來(lái)實(shí)現(xiàn)考慮協(xié)作的多人異步并行拆卸打下了基礎(chǔ)，對(duì)維修人員進(jìn)行大型部件拆卸提供了理論依據(jù)。