網(wǎng)絡(luò)協(xié)同設(shè)計(jì)過(guò)程的任務(wù)分解算法模型研究＊

四川大學(xué)機(jī)械工程學(xué)院 成都 610065

0 引言

云制造是一種面向服務(wù)、高效低耗和基于知識(shí)的網(wǎng)絡(luò)化、敏捷化制造新模式和技術(shù)手段，它將促進(jìn)制造的敏捷化、服務(wù)化、綠色化和智能化[1]。一方面用戶可以根據(jù)應(yīng)用需求，隨時(shí)隨地、動(dòng)態(tài)、敏捷地增減制造資源，獲得優(yōu)質(zhì)服務(wù)；另一方面接入云制造的中小規(guī)模企業(yè)形成虛擬聯(lián)盟，統(tǒng)籌協(xié)作，較好地平衡了資源的不足和過(guò)剩并存的沖突[2]，更極大地豐富了成員企業(yè)的制造資源，提高了中小規(guī)模企業(yè)的制造能力，使其能夠分解消化更大型的制造任務(wù)，具備能夠與大型集團(tuán)同臺(tái)競(jìng)技的能力，對(duì)于制造業(yè)升級(jí)轉(zhuǎn)型具有重大意義。

合理的任務(wù)分解方法能夠科學(xué)分解制造任務(wù)，獲得合理的子任務(wù)拓?fù)浣Y(jié)構(gòu)，使云環(huán)境下的資源匹配吻合度高，資源利用效率高。相關(guān)研究如文獻(xiàn)[3]通過(guò)構(gòu)建擴(kuò)散任務(wù)相關(guān)性模型，結(jié)合粒子群聚類優(yōu)化分解算法，實(shí)現(xiàn)對(duì)擴(kuò)散任務(wù)的有效分解，文獻(xiàn)[4]在制造任務(wù)分解的時(shí)考慮了任務(wù)之間的關(guān)聯(lián)性，更加適合于云環(huán)境下的制造場(chǎng)景，為研究制造任務(wù)的分解提供了思路和準(zhǔn)則。

根據(jù)制造任務(wù)分解的三大原則[5]：自下而上的分解原則、能整不分的分解原則以及能分不拆的分解原則。首先研究任務(wù)模型的表達(dá)，然后基于層次分解的思想，再綜合考慮相關(guān)性、內(nèi)聚性等評(píng)價(jià)指標(biāo)，利用改進(jìn)的順序任務(wù)分解方法（OTD）實(shí)現(xiàn)云環(huán)境下的制造任務(wù)分解。

1 云環(huán)境下的任務(wù)表達(dá)方法

1.1 云環(huán)境下的任務(wù)模型

物元模型[6]是易于計(jì)算機(jī)存儲(chǔ)、識(shí)別和操作的實(shí)體對(duì)象的表示方法，廣泛應(yīng)用于目標(biāo)的模型表達(dá)。本文應(yīng)用物元模型將一項(xiàng)云端制造任務(wù)Tk，具體描述了任務(wù)本身的各項(xiàng)需求和約束以及用戶的相關(guān)期望等，Tk可表示為

式中：Tki為制造任務(wù)Tk的第i個(gè)子任務(wù)，而且每項(xiàng)可分子任務(wù)Tki可用三元組描述如式所示；Ta為子任務(wù)Tki的屬性集合；To為子任務(wù)Tki的狀態(tài)集合；Tu為子任務(wù)Tki的服務(wù)消費(fèi)集合，依據(jù)相關(guān)性、內(nèi)聚性等評(píng)價(jià)指標(biāo)，逐級(jí)分解到各項(xiàng)子任務(wù)均具有不可再分的任務(wù)粒度。

對(duì)于具體任務(wù)Tki，用七元組描述一項(xiàng)不可再分的子任務(wù)的屬性集合Ta＝(ID，Na，Co，Ti，Qu，Eq，Re)。其中ID為任務(wù)編碼，Na為任務(wù)名稱，Co為任務(wù)成本約束，Ti為任務(wù)時(shí)間約束，Qu為任務(wù)的質(zhì)量要求，Eq為任務(wù)特殊裝備要求以及Re為用戶的其他要求。用二元組表達(dá)子任務(wù)Tki的屬性狀態(tài)集合To＝(TL，TS)，TL為該子任務(wù)的次級(jí)子任務(wù)ID列表，TS為其執(zhí)行狀態(tài)列表，若該級(jí)子任務(wù)不再包含子任務(wù)，則其已擁有了原子性（不可再分的任務(wù)粒度），用二元組表達(dá)子任務(wù)Tki的服務(wù)消費(fèi)集合Tu＝(Re，Po),其中Re是累計(jì)成本，Po是累計(jì)消費(fèi)時(shí)間。

1.2 任務(wù)分解指標(biāo)構(gòu)建

任務(wù)分解的層級(jí)及子任務(wù)的數(shù)量和粒度控制是云制造任務(wù)分解的關(guān)鍵，直接影響云制造任務(wù)協(xié)同完成的質(zhì)量、執(zhí)行進(jìn)度和成本。因此，研究任務(wù)分解時(shí)子任務(wù)之間的關(guān)聯(lián)關(guān)系和內(nèi)聚性對(duì)任務(wù)執(zhí)行的效率和成本至關(guān)重要，在學(xué)習(xí)現(xiàn)有研究的基礎(chǔ)上構(gòu)建了關(guān)聯(lián)性度量、內(nèi)聚性度量和任務(wù)粒度評(píng)估等指標(biāo)，對(duì)任務(wù)分解過(guò)程進(jìn)行控制。

1）任務(wù)粒度St

任務(wù)粒度層數(shù)越深，任務(wù)粒度越小，任務(wù)個(gè)數(shù)越多，任務(wù)粒度越小，故任務(wù)粒度的量化可表示為

式中：St為任務(wù)粒度量化指標(biāo)；La為子任務(wù)層數(shù)；N為子任務(wù)個(gè)數(shù)，＆為引入的粒度系數(shù)。任務(wù)層次分解時(shí)每一層的任務(wù)粒度需要設(shè)定閾值、嚴(yán)格控制，保證任務(wù)的原子性，為次層級(jí)的任務(wù)分解做好基礎(chǔ)準(zhǔn)備。

2）內(nèi)聚性Pt

內(nèi)聚性是模塊構(gòu)建的基本目標(biāo)，是軟件構(gòu)建內(nèi)聯(lián)關(guān)系的表征。定義為：若M的執(zhí)行需要調(diào)用或等待N的完成或執(zhí)行，則M調(diào)用依賴于N，一個(gè)方法M依賴于方法N，則記作M→N。

由于子任務(wù)具有較高模塊性，故引入內(nèi)聚性來(lái)度量子任務(wù)內(nèi)部活動(dòng)單元之間的關(guān)聯(lián)程度，然后求平均值來(lái)綜合評(píng)價(jià)該項(xiàng)任務(wù)的內(nèi)部關(guān)聯(lián)程度以判斷其分解效果。由于任務(wù)存在較多的約束（時(shí)間約束、成本約束和質(zhì)量約束等），然而這些約束之于任務(wù)并不能完全等同于軟件工程中的變量之于方法，故而本文提出以多約束下的模塊內(nèi)聚度計(jì)算方法，即

式中：f(n)為在約束k下的第q個(gè)子任務(wù)的內(nèi)聚度量化指標(biāo)；n為第q個(gè)子任務(wù)內(nèi)部的活動(dòng)數(shù)量；f(i)為第q個(gè)子任務(wù)的第i個(gè)活動(dòng)與其相關(guān)活動(dòng)的內(nèi)聚度指標(biāo)，是f(n)中f(i)的具體量化形式；f(k)為與活動(dòng)i相關(guān)的第k個(gè)活動(dòng)；M為活動(dòng)k的內(nèi)聚度，如果k為不可再分的活動(dòng)，則其M=1，否則M的值按照式（3）進(jìn)行遞歸計(jì)算；Pt為內(nèi)聚度指標(biāo)；Q為某任務(wù)分解過(guò)程中的約束個(gè)數(shù)。

3）相關(guān)性Rt

云環(huán)境下的制造任務(wù)種類多、活動(dòng)豐富，強(qiáng)約束性（尤其是時(shí)序約束）的存在使制造任務(wù)的相關(guān)性異與軟件構(gòu)構(gòu)件中的方法關(guān)系，同時(shí)一項(xiàng)制造任務(wù)的完成依賴于各子任務(wù)間的信息交互和物流交通，故任務(wù)分解過(guò)程需要考慮到任務(wù)的獨(dú)立性及其相關(guān)性，本文應(yīng)用模糊理論來(lái)構(gòu)建了信息矩陣和理論物流矩陣來(lái)描述任務(wù)活動(dòng)間的相關(guān)關(guān)系。

圖1 半嶺分布型隸屬度函數(shù)

考慮到模糊知識(shí)的獲取應(yīng)該去極端化，體現(xiàn)出一般性規(guī)律，本文采用半嶺型分布作為專家術(shù)語(yǔ)隸屬度函數(shù)，再考慮參與評(píng)價(jià)專家總數(shù)和評(píng)價(jià)術(shù)語(yǔ)出現(xiàn)次數(shù)（專家評(píng)價(jià)采用0-9打分法）[7]，建立制造任務(wù)關(guān)聯(lián)關(guān)系的量化模型為

式中：N為參與評(píng)價(jià)的專家人數(shù)，Qi為專家對(duì)兩個(gè)制造任務(wù)的關(guān)系的第i項(xiàng)評(píng)價(jià)值，Vi為對(duì)該關(guān)系做出相同評(píng)價(jià)值的專家人數(shù)，由此計(jì)算所得的x可認(rèn)為是對(duì)于兩個(gè)制造任務(wù)關(guān)聯(lián)關(guān)系的綜合經(jīng)驗(yàn)描述，然后將其帶入到半嶺分布當(dāng)中計(jì)算其隸屬度值aij，則aij能基于專家知識(shí)和模糊理論量化兩個(gè)制造任務(wù)i、j之間的關(guān)聯(lián)程度。以aij為元素，構(gòu)建如下信息關(guān)聯(lián)矩陣A，同理獲得物流關(guān)聯(lián)矩陣L為

考慮到制造任務(wù)的多樣性，如設(shè)計(jì)任務(wù)主要以信息交流為主，很少產(chǎn)生實(shí)際的物流交互，生產(chǎn)加工類任務(wù)則需要信息交互和物流交互雙向溝通，故任務(wù)i和任務(wù)j的任務(wù)關(guān)聯(lián)度綜合描述為

以rij為元素的三角對(duì)稱矩陣R反映了各項(xiàng)任務(wù)的關(guān)聯(lián)關(guān)系，其中w1和w2為不同任務(wù)類型下關(guān)于信息關(guān)聯(lián)和物流關(guān)聯(lián)的權(quán)值，任務(wù)分解時(shí)秉承著各子任務(wù)內(nèi)部聚合度高，子任務(wù)間關(guān)聯(lián)弱的原則，故需設(shè)定關(guān)聯(lián)度閾值Rmax＞∞-范數(shù)（矩陣R）。

2 改進(jìn)OTD方法

2.1 OTD方法

傳統(tǒng)的OTD算法是基于分層任務(wù)網(wǎng)絡(luò)（HTN）規(guī)劃方法[8,9]來(lái)研究任務(wù)分解的方法，一般將一個(gè)任務(wù)分解問(wèn)題表示為四元組q＝(s0,w※,Os,Ms)，其中s0為問(wèn)題的數(shù)學(xué)模型，w※為初始任務(wù)網(wǎng)絡(luò)狀態(tài)，Os為操作集合，Ms為分解方法集合。該算法的運(yùn)行流程為：

1）從初始狀態(tài)w0※開(kāi)始，選擇一個(gè)可轉(zhuǎn)換為復(fù)合任務(wù)的簡(jiǎn)單任務(wù)ei，任取一個(gè)方法mj∈Ms對(duì)ei進(jìn)行分解；

2）總?cè)蝿?wù)網(wǎng)絡(luò)N※及子任務(wù)網(wǎng)絡(luò)集Ns※形成來(lái)描述分解目標(biāo)；

3）對(duì)任務(wù)網(wǎng)絡(luò)進(jìn)行評(píng)價(jià)指標(biāo)分析計(jì)算并判斷是否達(dá)標(biāo)，若達(dá)標(biāo)則執(zhí)行步驟4，否則返回步驟1；

4）輸出分解結(jié)果并結(jié)束算法。

傳統(tǒng)的OTD算法主要使用分解方法對(duì)任務(wù)進(jìn)行分解，判斷其可行性，如若不可行則重新開(kāi)始分解。然而任務(wù)分解的粒度太小、層級(jí)太深會(huì)使任務(wù)間的關(guān)系復(fù)雜，造成信息交互困難和物流緊張，增加任務(wù)執(zhí)行和管理難度，任務(wù)活動(dòng)太少、粒度太大，直接導(dǎo)致任務(wù)內(nèi)部復(fù)雜度高。任務(wù)個(gè)數(shù)和層數(shù)不是強(qiáng)相關(guān)的兩個(gè)變量，能否通過(guò)改變?nèi)蝿?wù)數(shù)量而不增加任務(wù)層數(shù)，或反之來(lái)控制粒度大小和實(shí)現(xiàn)分解目標(biāo)。

2.2 改進(jìn)的OTD方法

傳統(tǒng)的OTD方法并未考慮到任務(wù)分解到某一解狀態(tài)S距離目標(biāo)解的距離，也未考慮到變異分解狀態(tài)來(lái)獲得其他形式的解以保證解空間的多樣型，為了解決上述問(wèn)題，本文研究了改進(jìn)OTD算法，在計(jì)算評(píng)價(jià)指標(biāo)、判斷可行性之后根據(jù)指標(biāo)更改變換N※和Ns※尋找實(shí)現(xiàn)目標(biāo)任務(wù)網(wǎng)絡(luò)的狀態(tài)，對(duì)于改進(jìn)的OTD算法詳述為：任務(wù)分解問(wèn)題表示為四元組q＝(s0,w※,Os,Ms)，其中s0、w※、Ms的含義與傳統(tǒng)OTD方法無(wú)異，引進(jìn)操作方法集合Os來(lái)描述變換N※和N※s的啟發(fā)式操作算子。Os為一個(gè)算子集合，相比于傳統(tǒng)的OTD操作。本文提出了搜索壓力算子集OP來(lái)描述當(dāng)前解所在狀態(tài)距離目標(biāo)解的距離及其搜索方向，OP的具體內(nèi)涵可表示為

式中：Oi為集合Op的第i個(gè)元素，Oi的解析式是關(guān)于內(nèi)聚性、任務(wù)粒度以及相關(guān)性的函數(shù)形式，如再在判定當(dāng)前分解狀態(tài)下的St過(guò)小，當(dāng)Pt、Rt均復(fù)合條件時(shí)，則可選定增大St的算子對(duì)當(dāng)前狀態(tài)進(jìn)行修改，使之成為無(wú)違規(guī)約束的可行解，傳統(tǒng)OTD與本文改進(jìn)的OTD之間的流程差異如圖2所示。

圖2 半嶺分布型隸屬度函數(shù)

如圖2所示為改進(jìn)OTD算法，該方法借鑒啟發(fā)式算法的思想，根據(jù)每次迭代的相關(guān)性、內(nèi)聚性以及任務(wù)粒度值來(lái)判斷當(dāng)前解所在狀態(tài)距離目標(biāo)解的距離以及方向，并據(jù)此來(lái)設(shè)定相關(guān)算子以形成搜索壓力，使得當(dāng)前解向著目標(biāo)解的方向進(jìn)行搜索。

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

為了驗(yàn)證上述方法的有效性和可行性，本文以固定卷?yè)P(yáng)式啟閉機(jī)的制造任務(wù)分解為例，對(duì)文中提及的任務(wù)分解方法進(jìn)行驗(yàn)證，并根據(jù)用戶要求設(shè)定Pmax-t＝2.5、8＜St＜10、對(duì)于每個(gè)子任務(wù)的Rmax-t＝0.5，對(duì)于n個(gè)子任務(wù)，任務(wù)的Rmax-t＝0.5n,進(jìn)行云環(huán)境下的制造任務(wù)分解。

啟閉機(jī)的制造任務(wù)主要包括標(biāo)準(zhǔn)件定制和非標(biāo)件生產(chǎn)兩個(gè)步驟，根據(jù)裝配需求，其制造任務(wù)的約束主要以時(shí)序約束為主，任務(wù)分解的方法集合包括時(shí)序可分Tm和功能可分Fm，響應(yīng)的根據(jù)相關(guān)性、內(nèi)聚性和粒度的可壓縮值，Os集合包括Rt改進(jìn)方法Rm、St改進(jìn)方法Sm以及Pt改進(jìn)方法Pm。在此，以Pm對(duì)固定卷?yè)P(yáng)式啟閉機(jī)的制造進(jìn)行任務(wù)分解，對(duì)比傳統(tǒng)的OTD方法，突出本文所論改進(jìn)的特點(diǎn)所在。

3.1 基于功能的OTD分解實(shí)例

基于啟閉機(jī)的功能分解方法Fm進(jìn)行任務(wù)分解，啟閉機(jī)根據(jù)功能分解方法Fm根據(jù)OTD算法可將其分解為如圖3所示的制造任務(wù)結(jié)構(gòu)。

圖3 基于功能的啟閉機(jī)制造任務(wù)OTD分解

1）Pt的計(jì)算

根據(jù)任務(wù)分解結(jié)果進(jìn)行Pt、St、Rt值計(jì)算，并驗(yàn)證是否滿足要求，對(duì)于St根據(jù)式（5）進(jìn)行計(jì)算有St＝（1+0.2）×3+20÷3＝10.23，系數(shù)1.2為用戶在任務(wù)注冊(cè)時(shí)，希望得到的任務(wù)分解層數(shù)系數(shù)（用0～1量化用戶對(duì)任務(wù)層數(shù)的期望，0.5表示用戶對(duì)層數(shù)深度沒(méi)有必要的要求,1是任務(wù)層數(shù)對(duì)任務(wù)粒度影響的固有系數(shù)）。

2）St的計(jì)算

St的量化方法如式（6）所示，在卷筒制造任務(wù)中，筒壁要根據(jù)卷筒軸的實(shí)際形狀尺寸進(jìn)行裝配形成卷筒部件，筒壁制造依賴于卷軸，故以卷軸、筒壁為活動(dòng)，計(jì)算卷筒制造子任務(wù)T1的內(nèi)聚度有

則基于功能分解

即卷筒結(jié)構(gòu)的內(nèi)聚度值為2。同理，以鋼絲繩、卷筒和軸承座的制造為活動(dòng)，計(jì)算卷?yè)P(yáng)機(jī)構(gòu)的內(nèi)聚度，由于鋼絲繩與卷筒相關(guān)，軸承座與卷筒相關(guān)，鋼絲繩與軸承座無(wú)依賴關(guān)系，且有根據(jù)上述計(jì)算M（卷筒）＝2，故在計(jì)算卷?yè)P(yáng)機(jī)構(gòu)聚合度時(shí)有

由此可見(jiàn)，Pt(卷筒)＝ 2 ＞Pt(卷?yè)P(yáng)機(jī)構(gòu))＝ 1.67。由于卷軸與筒壁兩個(gè)活動(dòng)全相關(guān)，而鋼絲繩與軸承座存在不相關(guān)關(guān)系，也證明了內(nèi)聚度計(jì)算方法的科學(xué)性，依次計(jì)算的Pt(啟閉機(jī)制造)＝ 1.74。

3）Rt的計(jì)算

相關(guān)性Rt的計(jì)算，根據(jù)專家經(jīng)驗(yàn)和專業(yè)知識(shí)，對(duì)于20個(gè)具有執(zhí)行屬性的子任務(wù)，根據(jù)專家給予的信息矩陣和物流矩陣，并賦予w1＝0.7和w2＝0.3，獲得相關(guān)性關(guān)系矩陣R，并計(jì)算得R∞-范數(shù)＝7。

3.2 基于功能的改進(jìn)OTD分解實(shí)例

為了不增加任務(wù)層數(shù)，構(gòu)建方法集合OP改進(jìn)分解結(jié)果，由前所述Pt＝1.74、St＝10.23、Rt＝7，對(duì)比與用戶需求明顯只有Smax-t＝10＜St＝10.23，違反了粒度值的約束，故從構(gòu)建的方法集合Op中選擇一個(gè)方法來(lái)對(duì)已有的任務(wù)結(jié)構(gòu)進(jìn)行變換。

由于Pt和Rt相比于分解需求，均具距離用戶設(shè)定極值有較大的程度，故從Op中選擇MR（即通過(guò)增大Rt值使得其他指標(biāo)滿足要求）對(duì)任務(wù)分解結(jié)構(gòu)進(jìn)行改進(jìn)，以求通過(guò)犧牲Rt來(lái)增加St使任務(wù)分解盡早滿足約束。具體表現(xiàn)為減小任務(wù)個(gè)數(shù)，將耦合度高的子任務(wù)合并到一個(gè)子任務(wù)，運(yùn)用Op中選擇MR的任務(wù)分解結(jié)構(gòu)見(jiàn)圖4。

圖4 基于功能的啟閉機(jī)制造任務(wù)改進(jìn)OTD分解

再根據(jù)前述的方法計(jì)算得St＝9.6，Pt＝1.67，R∞-范數(shù)＝8.1，各項(xiàng)指標(biāo)均滿足分解約束。

3.3 結(jié)果分析

將OTD與改進(jìn)OTD該方法對(duì)該任務(wù)進(jìn)行分解后獲得的任務(wù)粒度、內(nèi)聚性和相關(guān)性對(duì)比如圖5所示。由圖5可知，改進(jìn)OTD方法通過(guò)犧牲空間較大的指標(biāo)（相關(guān)性）來(lái)使得降低違反約束的指標(biāo)值，改變接盡可行解的拓?fù)浣Y(jié)構(gòu)，獲得可行解。相比于傳統(tǒng)的OTD，改進(jìn)OTD方面在接近可行解上修改任務(wù)的拓?fù)浣Y(jié)構(gòu)。因此，改進(jìn)OTD尋找的解更具多樣性，且能避免分解步驟重新開(kāi)始。

圖5 效果對(duì)比

4 結(jié)論

1）應(yīng)用物元模型建立云環(huán)境下的制造任務(wù)模型，并充分考慮了其屬性、分解狀態(tài)和執(zhí)行狀態(tài)，所研究的模型能勝任云制造中的任務(wù)表達(dá)、存儲(chǔ)和展示；

2）對(duì)比傳統(tǒng)OTD方法，本文研究的改進(jìn)OTD方法能夠在接近可行解上修改任務(wù)的拓?fù)浣Y(jié)構(gòu)，調(diào)整分解指標(biāo)，獲得分解結(jié)果。然而，如果分解過(guò)程中出現(xiàn)的接盡可行解難以通過(guò)算子Op改進(jìn)獲得可行解，運(yùn)行算子Op將消費(fèi)一定的時(shí)間；

3）以固定卷?yè)P(yáng)式啟閉機(jī)的云制造任務(wù)分解為例，對(duì)所提方法進(jìn)行了驗(yàn)證。