基于相似度的總裝作業(yè)集劃分方法研究

陳 剛，顧 丹

(上海航天設(shè)備制造總廠，上海 200245)

航天產(chǎn)品的研制是一項(xiàng)組織嚴(yán)謹(jǐn)、策劃完備、步調(diào)緊湊的工程活動(dòng)，計(jì)劃流程的編排貫穿整個(gè)研制過(guò)程。對(duì)于航天器總裝，在粗粒度層面上，計(jì)劃流程和AIT流程保持一致;在細(xì)粒度層面上，AIT流程中的某些節(jié)點(diǎn)內(nèi)還包含著許多順序無(wú)關(guān)的工作內(nèi)容(以下稱“作業(yè)”)，需進(jìn)一步細(xì)化其計(jì)劃流程。

一個(gè)現(xiàn)實(shí)的問(wèn)題是：在指定的計(jì)劃時(shí)間內(nèi)，針對(duì)指定的作業(yè)集合，在哪個(gè)子時(shí)間段完成哪些作業(yè)(以下稱“作業(yè)集劃分”)才能夠?qū)崿F(xiàn)統(tǒng)籌最優(yōu)?這是一個(gè)類似于背包問(wèn)題的NP難問(wèn)題［1］，理想的解決方案是建立優(yōu)良的智能模型并實(shí)施復(fù)雜的迭代學(xué)習(xí)或迭代演化。

為了尋求簡(jiǎn)單的劃分方法，本文給出一個(gè)基于經(jīng)驗(yàn)的假設(shè)：在相同長(zhǎng)度的子時(shí)間段內(nèi)，作業(yè)的相似度越高，工作的連續(xù)性和繼承性越好，工作效率越高。于是，作業(yè)集劃分要求轉(zhuǎn)變?yōu)閷ふ胰舾山M相似度最高的作業(yè)集合。屬性向量能夠較好地體現(xiàn)事物的內(nèi)在特性，用屬性向量夾角的余弦定義相似度具有非常自然的表現(xiàn)力。然而，余弦法丟失了屬性向量的長(zhǎng)度信息，不能很好地體現(xiàn)對(duì)象間各屬性程度上的差異。鑒于此，本文直接使用屬性向量差的模來(lái)表征相似度，如式(2)所示：

式中：wx=［x1，x2，…，xk］，wy=［y1，y2，…，yk］，分別表示對(duì)象wx與wy在k維屬性空間中的屬性向量;分量 x1，x2，…，xk與 y1，y2，…，yk在向量空間的k個(gè)基上取值，是對(duì)對(duì)象中參與評(píng)價(jià)的各屬性的度量。

由式(2)可知，u(wx，wy)越小，wx與 wy的相似度越高。

定義屬性向量的必要前提是構(gòu)建對(duì)應(yīng)的屬性空間，即定義屬性空間的基。以“設(shè)備安裝”為例，通過(guò)對(duì)“人、機(jī)、料、法、環(huán)”各環(huán)節(jié)進(jìn)行分析，提取出11個(gè)基本屬性作為設(shè)備安裝作業(yè)屬性空間的基，并結(jié)合生產(chǎn)實(shí)際對(duì)這些屬性的賦值方法進(jìn)行指定，見(jiàn)表1。

1 相似度定義

相似度的概念由來(lái)已久，廣泛應(yīng)用于聚類、文本過(guò)濾等領(lǐng)域［2-3］。近年來(lái)，隨著智能推薦系統(tǒng)的盛行，相似度計(jì)算方法由學(xué)術(shù)界向產(chǎn)業(yè)界成功遷移，取得了較好的應(yīng)用效果［4］。

目前，智能推薦系統(tǒng)多采用屬性向量夾角的余弦［5］來(lái)定義兩個(gè)對(duì)象之間的相似度，如式(1)所示：

2 作業(yè)量約束

考慮到負(fù)載均衡要求，必須對(duì)劃分出的作業(yè)集

表1 設(shè)備安裝作業(yè)屬性賦值表

的工作量(作業(yè)量)做出約束。本文給各個(gè)作業(yè)集分配相同的作業(yè)量，因此以各子時(shí)間段內(nèi)作業(yè)量的平均值作為作業(yè)量的約束值R，通過(guò)R可判斷某一個(gè)子時(shí)間段內(nèi)是否分配了超額的工作。

式中：n為待劃分作業(yè)的數(shù)量;Ei為第i個(gè)作業(yè)的工作量;T為子時(shí)間段的數(shù)量。

工作量Ei由經(jīng)驗(yàn)給出，對(duì)其絕對(duì)值沒(méi)有要求，但應(yīng)注意各作業(yè)工作量相對(duì)值的合理性。T由計(jì)劃時(shí)間總量和子時(shí)間段長(zhǎng)度決定，通常以半天(可以連續(xù)工作)為一個(gè)子時(shí)間段，則T=2d(d為上層計(jì)劃安排的完成工作總天數(shù))。

3 作業(yè)集劃分

對(duì)于目標(biāo)作業(yè)集合，在獲取集合中每個(gè)作業(yè)的屬性向量、作業(yè)量及作業(yè)量約束值后，即可實(shí)施作業(yè)集劃分。

作業(yè)集劃分分為兩個(gè)階段進(jìn)行，如圖1所示。

第一階段是在滿足作業(yè)量約束的前提下將各作業(yè)按相似度歸屬到各子時(shí)間段內(nèi)。為了避免難度大的作業(yè)大量聚集，首先將難度最大的作業(yè)歸屬到不同的子時(shí)間段內(nèi)，并以此作為該子時(shí)間段的基準(zhǔn)作業(yè)用于相似度計(jì)算。

由于存在“取整誤差”，第一階段劃分結(jié)束后可能還存在沒(méi)有被劃分到任何子時(shí)間段的作業(yè)，對(duì)于這些作業(yè)，在第二階段進(jìn)行劃分。該階段的劃分只針對(duì)“工作量最不足”的子時(shí)間段，即找出作業(yè)量最小的子時(shí)間段并將剩余作業(yè)中與其相似度最高的作業(yè)加入該子時(shí)間段，重復(fù)操作直到剩余作業(yè)全部劃分結(jié)束。

圖1 作業(yè)集劃分流程

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

以某型號(hào)“3天完成25臺(tái)設(shè)備安裝”的總裝計(jì)劃為例，按以下步驟開(kāi)展作業(yè)集劃分相關(guān)工作。

a．創(chuàng)建屬性向量。

對(duì)所有25臺(tái)設(shè)備在表1所定義的屬性空間中創(chuàng)建屬性向量，其各分量的取值見(jiàn)表2。

表2 設(shè)備安裝屬性向量表

b．計(jì)算相似度。

根據(jù)表2中各設(shè)備安裝操作屬性分量的取值，使用C語(yǔ)言編寫程序，按公式 (2)計(jì)算兩兩設(shè)備之間的相似度，計(jì)算結(jié)果見(jiàn)式 (3)。矩陣中第x行第y列或第x列第y行所對(duì)應(yīng)的取值即為u(wx，wy)。

c．獲取作業(yè)量及作業(yè)量約束值。 經(jīng)過(guò)實(shí)地調(diào)研，得到各設(shè)備安裝操作作業(yè)量的經(jīng)驗(yàn)值(無(wú)量綱，最小作業(yè)量取1)，見(jiàn)表3。

表3 設(shè)備安裝操作作業(yè)量

d．作業(yè)集劃分。

根據(jù)相似度、作業(yè)量及其約束值信息，按圖1所示流程進(jìn)行作業(yè)集劃分，劃分結(jié)果見(jiàn)表4。

結(jié)果顯示，“第一天上午”和“第二天下午”的操作集中使用了升降車和行車;所有7項(xiàng)帶熱控的操作被分配到“第一天上午”、“第二天上午”和“第三天下午”統(tǒng)一實(shí)施;2項(xiàng)具有特殊著裝要求的操作被安排在“第三天下午”連續(xù)開(kāi)展;同時(shí)，分配在每個(gè)子時(shí)間段內(nèi)的操作具有很高的“進(jìn)艙”一致性，除“第一天下午”和“第三天下午”外的其他4個(gè)子時(shí)間段均只有1個(gè)操作與其他操作有不一樣的“進(jìn)艙”屬性。

5 結(jié)束語(yǔ)

基于相似度的作業(yè)集劃分具有邏輯上的合理性。通過(guò)總裝現(xiàn)場(chǎng)應(yīng)用發(fā)現(xiàn)，行車和升降車的使用效率提高，操作一崗轉(zhuǎn)移工位的頻率下降，操作工具及輔助物資擺放混亂或遺失的情況好轉(zhuǎn)，整個(gè)過(guò)程有條不紊。

為了取得更好的劃分效果，可改進(jìn)劃分依據(jù)，采用基于相似度的聚類算法代替本文中的基準(zhǔn)作業(yè)相似度進(jìn)行劃分。但由于高維空間中的聚類算法需要很大的計(jì)算開(kāi)銷，需開(kāi)發(fā)專門的智能系統(tǒng)來(lái)實(shí)現(xiàn)。

表4 設(shè)備安裝作業(yè)集劃分結(jié)果

［1］ 林耿．混合遺傳模擬退火算法求解背包問(wèn)題［J］．河南工程學(xué)院學(xué)報(bào)：自然科學(xué)版，2012，24(3)：66-69．

［2］ 劉明術(shù)，方宏彬，張建，等．屬性相似度在聚類算法中的有效性研究［J］．計(jì)算機(jī)應(yīng)用與軟件，2012，29(9)：146-148．

［3］ 陳天，劉文浩．相似度算法分析與比較研究［J］．現(xiàn)代計(jì)算機(jī)，2012(18)：18-20．

［4］ 李海霞．購(gòu)物網(wǎng)站個(gè)性化推薦系統(tǒng)應(yīng)用分析［J］．產(chǎn)業(yè)經(jīng)濟(jì)，2012(15)：201．

［5］ 宋雅婷，徐天偉．基于用戶興趣的個(gè)性化推薦技術(shù)綜述［J］．云南大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，34(增刊 1)：20-23．