劉明周 王 強(qiáng) 凌 琳

合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院，合肥，230009

基于分層任務(wù)網(wǎng)絡(luò)的云制造任務(wù)分解方法

劉明周 王 強(qiáng) 凌 琳

合肥工業(yè)大學(xué)機(jī)械與汽車工程學(xué)院，合肥，230009

提出了一種基于順序任務(wù)分解的云制造任務(wù)分解算法。首先給出云制造任務(wù)描述模型以及任務(wù)約束結(jié)構(gòu)的相關(guān)定義，對(duì)制造任務(wù)粒度分析方法、制造任務(wù)內(nèi)聚性度量方法和制造任務(wù)相關(guān)性度量方法進(jìn)行了研究。然后，采用遞歸分解算法對(duì)任務(wù)進(jìn)行優(yōu)化分解，并在分解過(guò)程中考慮任務(wù)的資源匹配問(wèn)題。最后，以某變速箱試制任務(wù)分解為實(shí)例驗(yàn)證了所提方法的可行性和有效性。

云制造；任務(wù)分解；任務(wù)粒度；分層任務(wù)網(wǎng)絡(luò)

0 引言

合理的制造任務(wù)分解與規(guī)劃是云制造服務(wù)平臺(tái)實(shí)現(xiàn)高效資源協(xié)同和共享的關(guān)鍵。目前，國(guó)內(nèi)外學(xué)者對(duì)任務(wù)分解和規(guī)劃方法的研究主要集中在任務(wù)流程建模以及任務(wù)相關(guān)關(guān)系分析兩個(gè)方面。

常見的任務(wù)流程建模方法有圖論法[1-2]、設(shè)計(jì)結(jié)構(gòu)矩陣(design structure matrix, DSM)法[3]和分層任務(wù)網(wǎng)絡(luò)(hierarchical task network, HTN)法[4-5]。任務(wù)流程建模方法很少考慮子任務(wù)的相關(guān)關(guān)系，任務(wù)相關(guān)關(guān)系是任務(wù)分解的重要依據(jù)，通過(guò)合理的分析規(guī)劃能夠有效提高任務(wù)執(zhí)行的效率。安波等[6]通過(guò)構(gòu)建擴(kuò)散任務(wù)相關(guān)性模型，結(jié)合粒子群聚類優(yōu)化分解算法，實(shí)現(xiàn)對(duì)擴(kuò)散任務(wù)的有效分解；包北方等[7]針對(duì)產(chǎn)品定制協(xié)同開發(fā)任務(wù)分解缺乏綜合定量分析的問(wèn)題，提出一種綜合考慮任務(wù)粒度、任務(wù)耦合度、任務(wù)均衡度的任務(wù)分解系統(tǒng)模型；GERASOULIS等[8]在建立任務(wù)相關(guān)性模型的基礎(chǔ)上，運(yùn)用聚類算法得到具有合適粒度大小的任務(wù)分解方案。

上述方法在解決云制造環(huán)境下的制造任務(wù)分解問(wèn)題時(shí)，存在任務(wù)分解與制造資源匹配脫節(jié)的問(wèn)題，另外，云制造任務(wù)的多樣性要求在任務(wù)分解過(guò)程中需要有領(lǐng)域知識(shí)作為支撐。由此，云制造任務(wù)分解過(guò)程中，不僅需要考慮任務(wù)間的平衡性與任務(wù)粒度均衡性，還要考慮資源的匹配性與領(lǐng)域知識(shí)的完備性?；诖?，本文設(shè)計(jì)了一種基于順序任務(wù)分解(ordered task decomposition，OTD)的云制造任務(wù)遞歸分解算法。

1 云制造任務(wù)關(guān)聯(lián)特性分析

1.1 云制造任務(wù)約束結(jié)構(gòu)

云制造任務(wù)執(zhí)行的過(guò)程可以看作是一系列制造服務(wù)按照一定的時(shí)序和邏輯關(guān)系組合完成對(duì)應(yīng)制造任務(wù)活動(dòng)的過(guò)程，是制造服務(wù)與任務(wù)活動(dòng)對(duì)象在時(shí)間、信息和實(shí)物流上的有機(jī)集合。任務(wù)活動(dòng)對(duì)象在不同制造服務(wù)間的信息傳遞、實(shí)物流交互、時(shí)序約束等構(gòu)成了復(fù)雜約束關(guān)系，并以此復(fù)雜關(guān)系為基礎(chǔ)，完成整體制造任務(wù)的執(zhí)行。

本文將任務(wù)活動(dòng)的約束結(jié)構(gòu)定義為一個(gè)四元組(T，C，D，H)，其中，T表示與該活動(dòng)約束結(jié)構(gòu)相關(guān)的單元集合即任務(wù)活動(dòng)集合；C={(m，rs)∈T×D(T)}表示由多個(gè)單元確定的約束控制結(jié)構(gòu)的集合，(m，rs)表征約束中控制結(jié)構(gòu)內(nèi)各單元的輸入輸出關(guān)系，其中，m為輸出單元即后序制造任務(wù)，rs為輸入單元集合；D表示與該活動(dòng)約束結(jié)構(gòu)相關(guān)的單元集合之間的信息關(guān)聯(lián)矩陣；H表示與該活動(dòng)約束結(jié)構(gòu)相關(guān)的單元集合之間的物流關(guān)聯(lián)矩陣。

常見的任務(wù)活動(dòng)約束結(jié)構(gòu)主要有串行結(jié)構(gòu)、并行結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。

(1)串行結(jié)構(gòu)。表示一組順序執(zhí)行的任務(wù)，如圖1a所示，輸出單元為t2，輸入單元為t1，那么該輸入輸出單元之間的控制約束關(guān)系可表示為(t2，t1)。

(2)并行結(jié)構(gòu)。某一任務(wù)有一個(gè)以上的前序任務(wù)，且前序任務(wù)間相互獨(dú)立，不存在信息依賴關(guān)系，即t2、t3、…、tN之間不存在任何信息交互和實(shí)物流交互。如圖1b所示，輸入單元為t2、t3、…、tN，輸出單元為tN+1，那么該控制約束關(guān)系可表示為(tN+1，{t2，t3，…，tN})。

(3)循環(huán)結(jié)構(gòu)。某任務(wù)活動(dòng)完成后需要返回之前完成的某一活動(dòng)，如圖1c所示，輸入單元為tN，輸出單元為t2，那么該控制約束關(guān)系可表示為(tN，-t2，W)，W為循環(huán)的次數(shù)。

(4)分支結(jié)構(gòu)。依據(jù)一定的條件選擇執(zhí)行的路徑，但任務(wù)完成的路徑不唯一，具體任務(wù)路徑按一定概率選擇，如圖1d所示，輸入單元為t2、t3、…、tN，輸出單元為tN+1，那么該控制約束關(guān)系可表示為(tN+1，{t2‖t3‖…‖tN}，P)，P為各子任務(wù)發(fā)生的概率集合。

(a)串行結(jié)構(gòu)

(b)并行結(jié)構(gòu)

(c)循環(huán)結(jié)構(gòu)

(d)分支結(jié)構(gòu)圖1 任務(wù)約束結(jié)構(gòu)Fig.1 Constraint structure of task

云制造模式下，企業(yè)業(yè)務(wù)需求和制造資源的多樣性、異構(gòu)性以及各業(yè)務(wù)主體信息化水平的差異性，導(dǎo)致對(duì)制造資源服務(wù)和制造任務(wù)需求的描述呈現(xiàn)模糊性和不一致性,因此，對(duì)制造過(guò)程中涉及的活動(dòng)對(duì)象進(jìn)行統(tǒng)一的語(yǔ)義描述是云制造應(yīng)用過(guò)程的關(guān)鍵環(huán)節(jié)。網(wǎng)絡(luò)服務(wù)本體語(yǔ)言(Web ontology language for services，OWL-S)既有較強(qiáng)的語(yǔ)義表達(dá)能力，能提供完備、可判斷的推理機(jī)制，又是一種具有顯式語(yǔ)義、無(wú)歧義的機(jī)器可理解的標(biāo)記語(yǔ)言，可用來(lái)描述Web服務(wù)的屬性和功能。此外，OWL-S過(guò)程模型定義了一組過(guò)程及其執(zhí)行順序，其中包括Sequence、Split、Split+Join、Unordered、Choice、If-Then-Else、Iterate、Repeat-Until等幾種控制流，可以有效實(shí)現(xiàn)對(duì)制造任務(wù)約束結(jié)構(gòu)的表達(dá)，故本文采用OWL-S對(duì)制造任務(wù)進(jìn)行描述。

1.2 制造任務(wù)粒度分析與控制

任務(wù)分解的層級(jí)及子任務(wù)的數(shù)量和粒度控制是云制造任務(wù)分解的關(guān)鍵，直接影響云制造任務(wù)協(xié)同完成的質(zhì)量、執(zhí)行進(jìn)度和成本。子任務(wù)粒度過(guò)小、層級(jí)過(guò)深，任務(wù)間的關(guān)聯(lián)關(guān)系復(fù)雜，勢(shì)必會(huì)增加任務(wù)管理的難度，造成信息交互、物流以及管理成本的大幅攀升。任務(wù)活動(dòng)過(guò)少、粒度過(guò)大，會(huì)導(dǎo)致任務(wù)內(nèi)部復(fù)雜度高，影響整體制造任務(wù)的執(zhí)行效率。因此，任務(wù)粒度控制對(duì)云制造任務(wù)分解來(lái)說(shuō)具有重要的現(xiàn)實(shí)意義。

任務(wù)粒度是任務(wù)聚合程度的量化水平，反映了整體制造任務(wù)的規(guī)模和層級(jí)，與任務(wù)數(shù)量成反比，其數(shù)學(xué)模型如下：

ST=V/NT

(1)

式中，ST為任務(wù)粒度，ST>0；NT為任務(wù)數(shù)量，NT>0；V為任務(wù)粒度系數(shù)，由任務(wù)內(nèi)聚程度決定，V>0。

1.3 制造任務(wù)內(nèi)聚性度量方法

任務(wù)關(guān)聯(lián)系數(shù)是任務(wù)內(nèi)部各活動(dòng)單元之間的關(guān)聯(lián)程度的量化指標(biāo)。假設(shè)在任務(wù)約束結(jié)構(gòu)(T，C，D，H)中，存在有效約束控制元t。該任務(wù)約束結(jié)構(gòu)的任務(wù)關(guān)聯(lián)系數(shù)λ(t)定義如下：

λ(t)=

(2)

其中，|t|為有效約束控制元的數(shù)量；m、n為輸出活動(dòng)單元；qs為輸入活動(dòng)單元集，({m}∪rs) ∩({n}∪qs)≠?表示不同約束控制元的輸入輸出活動(dòng)單元之間存在非空交集；{m}、{n}表示約束控制元中所有輸入單元的集合；{m}∪rs、{n}∪qs表示約束控制元中所有活動(dòng)單元的集合。任務(wù)關(guān)聯(lián)系數(shù)反映了某約束控制子集與相鄰約束控制元之間活動(dòng)的關(guān)聯(lián)水平。一個(gè)約束控制元中的輸入輸出單元在其他控制元中出現(xiàn)得越多，則約束控制元之間的關(guān)聯(lián)性越強(qiáng)。

任務(wù)重用系數(shù)是指在一個(gè)任務(wù)約束結(jié)構(gòu)中，被重用的活動(dòng)單元數(shù)與該約束控制結(jié)構(gòu)中所有活動(dòng)單元數(shù)的比值，量化反映了該約束結(jié)構(gòu)中活動(dòng)單元被重用的水平，具體定義如下：

(3)

A=|{v∈U|?(m,rs)∈t,(n,qs)∈t,

v∈({m}∪rs)∩({n}∪qs),(m,rs)≠(n,qs)}|

B=|{v∈U|?(m,rs)∈t,v∈({m}∪rs)}|

任務(wù)內(nèi)聚系數(shù)w(t)是任務(wù)關(guān)聯(lián)系數(shù)和任務(wù)重用系數(shù)的乘積，即

w(t)=λ(t)μ(t)

(4)

它綜合表征了任務(wù)約束結(jié)構(gòu)的內(nèi)聚程度。云制造整體任務(wù)Tc的內(nèi)聚系數(shù)V為各個(gè)子任務(wù)內(nèi)聚系數(shù)的均值。

1.4 制造任務(wù)相關(guān)性度量方法

云制造任務(wù)種類繁多，有設(shè)計(jì)任務(wù)、制造加工任務(wù)、物流任務(wù)和測(cè)試任務(wù)等，各任務(wù)活動(dòng)間不可避免地存在信息流和物料流的交互。在任務(wù)分解時(shí)應(yīng)該盡量保持任務(wù)活動(dòng)間的獨(dú)立性，以利于后續(xù)的各個(gè)任務(wù)活動(dòng)能夠相對(duì)獨(dú)立地進(jìn)行。因此，本文引入相關(guān)度的概念，分別從子任務(wù)間信息交互和實(shí)物流傳遞兩方面來(lái)判定任務(wù)活動(dòng)之間相關(guān)性的大小。

信息相關(guān)度用來(lái)反映任務(wù)與任務(wù)之間的信息依賴關(guān)系，本文采用模糊設(shè)計(jì)矩陣法來(lái)構(gòu)建云制造任務(wù)之間的信息關(guān)聯(lián)矩陣，即

(5)

其中，aij(i，j=1，2，…，p) 為第i個(gè)任務(wù)和第j個(gè)任務(wù)之間的信息相關(guān)度，p為所有約束子集中的有效任務(wù)數(shù)量。aij量化表征了任務(wù)之間在溝通協(xié)作、信息傳遞中的頻次和復(fù)雜程度，aij=0表示第i個(gè)任務(wù)和第j個(gè)任務(wù)之間沒有任何信息交互，屬于獨(dú)立不相關(guān)任務(wù)；aij=1表示第i個(gè)任務(wù)和第j個(gè)任務(wù)之間具有較高的信息交互量，這時(shí)應(yīng)將兩個(gè)任務(wù)盡可能地合并以降低信息交互成本。aij的取值范圍為[0，1]，一般采用專家評(píng)價(jià)法確定該值[9]。

物流相關(guān)度是子任務(wù)之間在物流轉(zhuǎn)移頻次、數(shù)量、距離等方面的綜合度量。物流相關(guān)度的判定方式與信息相關(guān)度類似，可表示為

(6)

其中，bij表示任務(wù)i與任務(wù)j之間的物料轉(zhuǎn)移相關(guān)程度，量化表征了任務(wù)之間的實(shí)物流動(dòng)重要程度和密集程度，取值范圍為[0，1]，一般采用專家評(píng)價(jià)法確定[9]。

設(shè)計(jì)類制造任務(wù)中，產(chǎn)品設(shè)計(jì)涉及大量文件傳遞及溝通協(xié)調(diào)工作，但在此過(guò)程中很少有實(shí)體物流產(chǎn)生，故信息相關(guān)度較高，物流相關(guān)度較低。制造加工類、測(cè)試類和物流類制造任務(wù)的物料轉(zhuǎn)移活動(dòng)較多，故物流相關(guān)度較高，可見制造任務(wù)類型的不同對(duì)物流相關(guān)度的影響較大。

任務(wù)相關(guān)度是制造任務(wù)間關(guān)聯(lián)關(guān)系的綜合度量，則任務(wù)活動(dòng)i和j之間的任務(wù)相關(guān)度為

rij=waij+(1-w)bij

(7)

其中，w為信息相關(guān)度在任務(wù)間綜合相關(guān)關(guān)系度量中的權(quán)值，反映了信息相關(guān)度對(duì)綜合相關(guān)度的影響。不同的任務(wù)類型和不同任務(wù)層次中，w的取值也會(huì)有所不同，需要根據(jù)實(shí)際任務(wù)情況判定。在任務(wù)分解過(guò)程中，一般會(huì)設(shè)定相關(guān)度閾值rmax，需要注意的是，rmax的取值與具體任務(wù)類型及任務(wù)層級(jí)有關(guān)，層級(jí)較少時(shí)，為保證任務(wù)能夠順利分解，rmax應(yīng)取較大的值，層級(jí)較多時(shí)，rmax應(yīng)取較小的值，以保證原子任務(wù)能夠有效組合。

2 云制造任務(wù)分解算法

2.1 HTN規(guī)劃方法

HTN規(guī)劃是基于分層抽象和領(lǐng)域知識(shí)的智能規(guī)劃求解方法，其基本步驟是：根據(jù)預(yù)先給定的目標(biāo)任務(wù)，按照遞歸的方式將復(fù)合任務(wù)不斷分解為更小粒度任務(wù)，同時(shí)在分解過(guò)程中進(jìn)行相關(guān)約束和沖突校驗(yàn)，直至形成具有嚴(yán)格時(shí)序關(guān)系和約束關(guān)系的復(fù)雜任務(wù)活動(dòng)網(wǎng)絡(luò)，從而形成任務(wù)規(guī)劃問(wèn)題的可行解。

HTN規(guī)劃問(wèn)題可描述為三元組Q=(s0，w0，D)，其中，s0是規(guī)劃問(wèn)題的初始狀態(tài)；w0是初始任務(wù)網(wǎng)絡(luò)；D是HTN規(guī)劃領(lǐng)域，由操作集和方法集組成。

規(guī)劃領(lǐng)域可表示為D=(O，G)，O代表操作集合，G代表方法集合。原子任務(wù)只存在一個(gè)操作算子，可以描述為o=(op，opre，oeff)，op、opre和oeff分別表示操作對(duì)應(yīng)的原子任務(wù)、操作前提條件和操作執(zhí)行后的效果。分解方法是分解復(fù)合任務(wù)的規(guī)則，可表示為二元組g=f(e，d)，其中，e表示復(fù)合任務(wù)，d表示復(fù)合任務(wù)e分解后的任務(wù)網(wǎng)絡(luò)。

任務(wù)活動(dòng)網(wǎng)絡(luò)tNet=((n1∶e1)，(n2∶e2)，…，(nm∶em)，l)，其中，ni為任務(wù)ei的唯一標(biāo)識(shí)符，ni∈N；l為約束條件，如時(shí)序約束、狀態(tài)約束和值約束等。

規(guī)劃解是HTN規(guī)劃問(wèn)題的可行解，可表示為π=〈o1，o2，…，on〉，其中，o1、o2、…、on是完成初始任務(wù)w0的操作。

常規(guī)HTN規(guī)劃方法具有領(lǐng)域無(wú)關(guān)性，因此，在解決特定的領(lǐng)域規(guī)劃問(wèn)題時(shí)需要引入領(lǐng)域知識(shí)，如產(chǎn)品設(shè)計(jì)任務(wù)需要考慮產(chǎn)品結(jié)構(gòu)要求、功能要求等知識(shí)，制造加工任務(wù)則需要考慮工藝要求、資源約束等知識(shí)。領(lǐng)域知識(shí)在引入HTN規(guī)劃方法時(shí)，通常以操作集合和方法集合表現(xiàn)，通過(guò)拓展操作和方法的內(nèi)涵，實(shí)現(xiàn)制造領(lǐng)域知識(shí)的引入。

操作是描述任務(wù)執(zhí)行的過(guò)程，在操作算子中引入k元素，將領(lǐng)域知識(shí)的描述加入到opre和oeff，通過(guò)k完成領(lǐng)域知識(shí)的調(diào)用，如調(diào)用領(lǐng)域知識(shí)庫(kù)、集成領(lǐng)域算法等，從而能夠有效地將領(lǐng)域知識(shí)引入到HTN規(guī)劃中，新操作算子可表示為o*=(op，opre，k，oeff)。

方法g的作用是將復(fù)合任務(wù)分解為多個(gè)子任務(wù)。復(fù)合任務(wù)在分解時(shí)可能有多種分解模式，因此在構(gòu)建方法g時(shí)需要融入領(lǐng)域知識(shí)。將d改寫為((p1，d1)，(p2，d2)，…，(pn，dn))的序?qū)π问?，新的方法可表示為g*=f(e，(p1，d1)，(p2，d2)，…，(pn，dn))，(pi，di)，表示在前提條件(領(lǐng)域知識(shí)的載體)pi下，通過(guò)方法g將復(fù)合任務(wù)e分解為di。

云制造任務(wù)分解中，任務(wù)類型多樣，涉及多領(lǐng)域知識(shí)，且任務(wù)活動(dòng)間約束結(jié)構(gòu)較為復(fù)雜，存在并行、選擇和循環(huán)等復(fù)雜約束結(jié)構(gòu)關(guān)系，通過(guò)在操作中引入k元素，以及在方法g中引入(oprei，di)，在di中定義序?qū)χg的約束結(jié)構(gòu)關(guān)系，將領(lǐng)域知識(shí)引入方法g，從而實(shí)現(xiàn)不同類型云制造任務(wù)的分解。

2.2 基于HTN的云制造任務(wù)分解算法

HTN的任務(wù)分解方式可分為三類：順序任務(wù)分解、無(wú)序任務(wù)分解(unordered task decomposition，UTD)和部分有序任務(wù)分解算法(partially ordered task decomposition，POTD)。由于云制造任務(wù)一般按照層次性原則自頂而下進(jìn)行分解，故本文采用OTD算法對(duì)任務(wù)進(jìn)行分解。經(jīng)典OTD算法[10]首先以初始任務(wù)網(wǎng)絡(luò)為起點(diǎn)，運(yùn)用任務(wù)分解方法g*，按照先后順序?qū)θ蝿?wù)網(wǎng)絡(luò)中的各任務(wù)活動(dòng)(子任務(wù))進(jìn)行遞歸分解。分解完成后，判定當(dāng)前任務(wù)規(guī)劃能否滿足任務(wù)執(zhí)行的需求，若滿足任務(wù)執(zhí)行的條件，則生成一個(gè)可執(zhí)行計(jì)劃。相比傳統(tǒng)的任務(wù)分解方法而言，OTD算法降低了任務(wù)分解的難度及不確定性，從而極大提高了任務(wù)分解的效率，具體的算法求解過(guò)程如圖2所示，其中q(s0,w0，Os,Ms)表示某一制造任務(wù)分解問(wèn)題，Os為操作集合，Ms為分解方法的集合。

圖2 基于OTD的任務(wù)分解算法解算流程Fig.2 Decomposition algorithm of cloud manufacturing task based on OTD

3 實(shí)例驗(yàn)證

以國(guó)內(nèi)某變速箱制造企業(yè)DTF630自動(dòng)變速箱樣機(jī)試制任務(wù)為例，對(duì)本文提出的基于HTN的云制造任務(wù)分解算法進(jìn)行應(yīng)用。自動(dòng)變速箱結(jié)構(gòu)復(fù)雜，其樣機(jī)試制涉及226種零件的外協(xié)加工任務(wù)，需要由多個(gè)企業(yè)協(xié)同完成。變速箱樣機(jī)試制與批量生產(chǎn)不同。樣機(jī)試制階段，零部件外形尺寸以及工藝參數(shù)需要與其他零件進(jìn)行匹配，因此樣機(jī)試制過(guò)程中的各項(xiàng)子任務(wù)有嚴(yán)格的時(shí)序關(guān)系。另外，負(fù)責(zé)零件試制的外協(xié)廠家需要滿足一定QoS約束條件(服務(wù)質(zhì)量、服務(wù)成本、服務(wù)時(shí)間、服務(wù)延時(shí)率、服務(wù)匹配度、服務(wù)糾紛率和服務(wù)信譽(yù)度等)，表1所示為部分試制任務(wù)的QoS約束條件。因此，根據(jù)所提方法對(duì)該制造任務(wù)進(jìn)行分解。

表1 部分試制任務(wù)QoS約束條件

初始任務(wù)網(wǎng)絡(luò)w0=({u0}，L)，u0為初始任務(wù)節(jié)點(diǎn)，u0中只包含一個(gè)任務(wù)活動(dòng)t01，即DTF630樣機(jī)試制任務(wù)，L為該任務(wù)的相關(guān)約束條件集，如任務(wù)完成成本、周期、價(jià)格以及執(zhí)行任務(wù)的制造服務(wù)QoS等約束條件。假設(shè)分解后的子任務(wù)均有與之匹配的制造服務(wù)，另外根據(jù)專家經(jīng)驗(yàn)，設(shè)定最大任務(wù)粒度系數(shù)不超過(guò)0.02，為簡(jiǎn)明起見，省略了參數(shù)項(xiàng)，采用OTD算法遞歸分解該任務(wù)的實(shí)施過(guò)程如下：

(1)變速箱試制任務(wù)并不能由單個(gè)制造服務(wù)提供商獨(dú)立完成。因此，基于層次原則，按照產(chǎn)品BOM結(jié)構(gòu)對(duì)自動(dòng)變速箱樣機(jī)試制初始任務(wù)w0進(jìn)行分解，得到任務(wù)分網(wǎng)絡(luò)w1=((n11∶e11)，(n12∶e12)，…，(n18∶e18)，L1)，子任務(wù)t分別是：①殼體及附件試制任務(wù)e11；②齒輪傳動(dòng)裝置試制任務(wù)e12；③差速器總成試制任務(wù)e13；④同步器裝置試制任務(wù)e14；⑤換擋執(zhí)行裝置試制任務(wù)e15；⑥駐車制動(dòng)裝置試制任務(wù)e16；⑦液壓模塊總成試制任務(wù)e17；⑧電控單元試制任務(wù)e18。

(2)對(duì)新任務(wù)網(wǎng)絡(luò)w1進(jìn)行相關(guān)性分析、內(nèi)聚性分析以及粒度分析，由于任務(wù)網(wǎng)絡(luò)w1的任務(wù)粒度過(guò)大，需要對(duì)w1進(jìn)行進(jìn)一步的細(xì)化分解。以e17為例，液壓模塊總成試制任務(wù)e17由閥體、開關(guān)電磁閥、壓力控制閥、流量傳感器和隔板等組成零件的試制組成，零件結(jié)構(gòu)、功能以及制造工藝差別較大，需要進(jìn)一步細(xì)化。

(3)選擇一個(gè)可轉(zhuǎn)化為復(fù)合任務(wù)的簡(jiǎn)單任務(wù)ec，任取一個(gè)方法g*∈θ(θ為tc的分解方法集合)對(duì)ec進(jìn)行分解，這里選擇液壓模塊總成試制任務(wù)e17進(jìn)行分解，得到對(duì)應(yīng)的子任務(wù)網(wǎng)絡(luò)d21=((n21∶e21)，(n22∶e22)，…，(n28∶e28)，L21)，分解方法g*采用按BOM結(jié)構(gòu)分解的方法，其中，閥體試制任務(wù)為e21，電磁閥試制任務(wù)為e22，流量傳感器試制任務(wù)為e23，蓄能器、開關(guān)閥彈簧試制任務(wù)為e24，泄壓閥堵頭、冷卻滑閥堵頭總成試制任務(wù)為e25，隔板試制任務(wù)為e26，從而形成新任務(wù)網(wǎng)絡(luò)w2。由于在w2中依然存在e11、e12等大粒度任務(wù)，故不滿足相關(guān)性及粒度約束，需要進(jìn)行進(jìn)一步分解。

(4)重復(fù)步驟(2)和步驟(3)，由于篇幅所限，本文給出最終完成分解的任務(wù)網(wǎng)絡(luò)圖，如圖3所示，圖中數(shù)字代表分解后的子任務(wù)序號(hào)。

圖3 分解后的任務(wù)網(wǎng)絡(luò)圖Fig.3 Network of decomposed task

可以得出8個(gè)有效子任務(wù)，其活動(dòng)約束結(jié)構(gòu)為Ta={1，2，…，5}，Ca={(4，{1，2，3})，(5，{4})}，Tb={5，11，12，13}，Cb={(11，{5})，(12，{5})，(13，{5})}，Tc={4，6，7，8}，Cc={(8，{4，6，7})}，Td={12，14，15，16，17}，Cd={(14，{12})，(17，{14，15，16})}，Te={8，9，10，18}，Ce={(18，{8，9，10})}，Tf={18，19，20，21，22}，Cf={(20，{18})，(21，{18})，(22，{19，20})}，Tg={22，23，24，26}，Cg={(26，{22，23，24})}，Th={17，25，26，27}，Ch={(26，{17})，(27，{25，26})}，各子任務(wù)的分解圖見圖4。

(5)根據(jù)式(2)～式(4)，分別計(jì)算相應(yīng)任務(wù)集的內(nèi)聚系數(shù)，如表2所示。

由式(1)可計(jì)算出任務(wù)粒度：

該分解方案的任務(wù)粒度在任務(wù)內(nèi)聚度閾值范圍之內(nèi)，因此，進(jìn)入制造服務(wù)匹配階段，篩選候選制造服務(wù)集。若此時(shí)的任務(wù)粒度不在任務(wù)內(nèi)聚度閾值范圍之內(nèi)，則需要對(duì)任務(wù)網(wǎng)絡(luò)進(jìn)行相關(guān)性分析，根據(jù)任務(wù)活動(dòng)之間信息交互、物流交互以及功能相似度分別構(gòu)造信息關(guān)聯(lián)矩陣D和物流關(guān)聯(lián)矩陣H，將信息交互以及物流交互較多的任務(wù)活動(dòng)進(jìn)行合并，從而增大任務(wù)集的內(nèi)聚系數(shù)，降低任務(wù)集之間的相關(guān)性，提高任務(wù)執(zhí)行效率。

(a) (b)

(c) (d)

(e) (f)

(g) (h)圖4 合適任務(wù)粒度分解集Fig.4 Suitable task granularity decomposition set

任務(wù)序號(hào)活動(dòng)關(guān)聯(lián)系數(shù)λ(t)活動(dòng)重用系數(shù)μ(t)任務(wù)內(nèi)聚系數(shù)w(t)a1．0000．200．200b1．0000．250．250c000d1．0000．200．200e000f0．3330．200．066g000h0．5000．250．125

任務(wù)活動(dòng)網(wǎng)絡(luò)符合任務(wù)粒度約束條件后，需要為任務(wù)活動(dòng)網(wǎng)絡(luò)中各子任務(wù)匹配符合要求的制造服務(wù)。在匹配過(guò)程中主要考慮服務(wù)延時(shí)率、服務(wù)中標(biāo)率、服務(wù)完成率、服務(wù)匹配度、服務(wù)糾紛率和服務(wù)信譽(yù)度等QoS約束條件，用戶可根據(jù)實(shí)際需求來(lái)調(diào)整篩選的參數(shù)，以擴(kuò)大或縮小候選制造服務(wù)的規(guī)模，最終形成候選制造服務(wù)集，為云制造資源優(yōu)化配置提供數(shù)據(jù)支撐。

4 結(jié)語(yǔ)

任務(wù)分解的目標(biāo)在于將復(fù)雜的多層次、多粒度制造任務(wù)細(xì)化為粒度合適、便于協(xié)同執(zhí)行的子任務(wù)。本文給出了云制造任務(wù)描述模型及任務(wù)約束結(jié)構(gòu)的相關(guān)定義，設(shè)計(jì)了基于分層任務(wù)網(wǎng)絡(luò)的云制造任務(wù)遞歸分解算法，并給出了制造任務(wù)粒度分析方法、制造任務(wù)內(nèi)聚性度量方法以及制造任務(wù)相關(guān)性度量方法。該方法不但考慮了任務(wù)相關(guān)性和內(nèi)聚性，還將制造任務(wù)與制造資源的匹配性以及任務(wù)分解的領(lǐng)域知識(shí)引入任務(wù)分解過(guò)程，從任務(wù)流程建模與規(guī)劃、任務(wù)相關(guān)關(guān)系分析以及制造資源匹配等方面對(duì)任務(wù)分解方法進(jìn)行優(yōu)化，有效提高了任務(wù)分解效率，降低后序制造資源優(yōu)化配置問(wèn)題的復(fù)雜性。

[1]BORENSTEIND.ADirectedAcyclicGraphRepresentationofRoutingManufacturingFlexibility[J].EuropeanJournalofOperationalResearch，2000，127(1)：78-93.

[2]BRIR.ParallelSimulationAlgorithmforMaintenanceOptimizationBasedonDirectedAcyclicGraph[J].ReliabilityEngineering&SystemSafety，2008，93(6)：874-884.

[3]BROWNINGTR.ApplyingtheDesignStructureMatrixtoSystemDecompositionandIntegrationProblems:aReviewandNewDirections[J].IEEETransactionsonEngineeringManagement，2001，48(3)：292-306.

[4]GEORGIEVSKII，AIELLOM.HTNPlanning:Overview,Comparison,andBeyond[J].ArtificialIntelligence，2015，222：124-156.

[5]RAHMANMMH，HORIGUCHIS.HTN:aNewHierarchicalInterconnectionNetworkforMassivelyParallelComputers[J].IEEETransactionsonInformationandSystems，2003，86(9)：1479-1486.

[6] 安波，廖文和，郭宇，等.基于相關(guān)性的擴(kuò)散制造任務(wù)規(guī)劃方法研究[J].中國(guó)機(jī)械工程，2011，22(23)：2839-2844.ANBo，LIAOWenhe，GUOYu，etal.StudyonExtendedManufacturingTaskPlanningMethodBasedonCorrelation[J].ChinaMechanicalEngineering，2011，22(23)：2839-2844.

[7] 包北方，楊育，李斐，等.產(chǎn)品定制協(xié)同開發(fā)任務(wù)分解模型[J].計(jì)算機(jī)集成制造系統(tǒng)，2014，20(7)：1537-1545.BAOBeifang，YANGYu，LIFei，etal.DecompositionModelinProductCustomizationCollaborativeDevelopmentTask[J].ComputerIntegratedManufacturingSystems，2014，20(7)：1537-1545.

[8]GERASOULISA，YANGT.OntheGranularityand

ClusteringofDirectedAcyclicTaskGraphs[J].IEEETransactionsonParallel&DistributedSystems，1993，4(6)：686-701.

[9] 秦壽康. 綜合評(píng)價(jià)原理與應(yīng)用[M]. 北京:電子工業(yè)出版社, 2003:24-45.QINKangshou.PrincipleandApplicationofComprehensiveEvaluationMethods[M].Beijing:PublishingHouseofElectronicsIndustry，2003:24-45.

[10]MUC,LIY.AnIntrusionResponseDecision-makingModelBasedonHierarchicalTaskNetworkPlanning[J].ExpertSystemswithApplications, 2010, 37(3):2465-2472.

(編輯 張 洋)

Cloud Manufacturing Task Decomposition Method Based on HTN

LIU Mingzhou WANG Qiang LING Lin

School of Machinery and Automobile Engineering,Hefei University of Technology,Hefei，230009

A cloud manufacturing task decomposition algorithm was proposed herein on the basis of sequential task decomposition. Firstly, a descriptive model of manufacturing tasks and the related definitions of task constraint structures were provided were carried out. Then the researches of manufacturing task granularity analysis method, cohesion measurement method were carried out, and correlation measuring method. Then, recursive decomposition algorithm was adopted to carry out the tasks of optimization decomposition consistently, considering the task resource matching problem during the decomposition processes. Finally, feasibility and effectiveness of the proposed method was verified by an example of a gearbox test-manufacturing task decomposition.

cloud manufacturing； task decomposition； task granularity； hierarchical task network(HTN)

蔣清海，男，1986年生。南京理工大學(xué)機(jī)械工程學(xué)院博士研究生。主要研究方向?yàn)檗r(nóng)業(yè)機(jī)械裝備。發(fā)表論文3篇。E-mail:jiangqinghai101@126.com。武 凱，男，1972年生。南京理工大學(xué)機(jī)械工程學(xué)院教授。孫 宇，男，1964年生。南京理工大學(xué)機(jī)械工程學(xué)院教授、博士研究生導(dǎo)師。楊 棟，男，1991年生。南京理工大學(xué)機(jī)械工程學(xué)院博士研究生。

2016-04-27

TH166

10.3969/j.issn.1004-132X.2017.08.008