基于分層任務網絡的云制造任務分解方法

劉明周 王 強 凌 琳

合肥工業大學機械與汽車工程學院，合肥，230009

基于分層任務網絡的云制造任務分解方法

劉明周 王 強 凌 琳

合肥工業大學機械與汽車工程學院，合肥，230009

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

云制造；任務分解；任務粒度；分層任務網絡

0 引言

合理的制造任務分解與規劃是云制造服務平臺實現高效資源協同和共享的關鍵。目前，國內外學者對任務分解和規劃方法的研究主要集中在任務流程建模以及任務相關關系分析兩個方面。

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

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

1 云制造任務關聯特性分析

1.1 云制造任務約束結構

云制造任務執行的過程可以看作是一系列制造服務按照一定的時序和邏輯關系組合完成對應制造任務活動的過程，是制造服務與任務活動對象在時間、信息和實物流上的有機集合。任務活動對象在不同制造服務間的信息傳遞、實物流交互、時序約束等構成了復雜約束關系，并以此復雜關系為基礎，完成整體制造任務的執行。

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

常見的任務活動約束結構主要有串行結構、并行結構、選擇結構和循環結構。

(1)串行結構。表示一組順序執行的任務，如圖1a所示，輸出單元為t2，輸入單元為t1，那么該輸入輸出單元之間的控制約束關系可表示為(t2，t1)。

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

(3)循環結構。某任務活動完成后需要返回之前完成的某一活動，如圖1c所示，輸入單元為tN，輸出單元為t2，那么該控制約束關系可表示為(tN，-t2，W)，W為循環的次數。

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

(a)串行結構

(b)并行結構

(c)循環結構

(d)分支結構圖1 任務約束結構Fig.1 Constraint structure of task

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

1.2 制造任務粒度分析與控制

任務分解的層級及子任務的數量和粒度控制是云制造任務分解的關鍵，直接影響云制造任務協同完成的質量、執行進度和成本。子任務粒度過小、層級過深，任務間的關聯關系復雜，勢必會增加任務管理的難度，造成信息交互、物流以及管理成本的大幅攀升。任務活動過少、粒度過大，會導致任務內部復雜度高，影響整體制造任務的執行效率。因此，任務粒度控制對云制造任務分解來說具有重要的現實意義。

任務粒度是任務聚合程度的量化水平，反映了整體制造任務的規模和層級，與任務數量成反比，其數學模型如下：

ST=V/NT

(1)

式中，ST為任務粒度，ST>0；NT為任務數量，NT>0；V為任務粒度系數，由任務內聚程度決定，V>0。

1.3 制造任務內聚性度量方法

任務關聯系數是任務內部各活動單元之間的關聯程度的量化指標。假設在任務約束結構(T，C，D，H)中，存在有效約束控制元t。該任務約束結構的任務關聯系數λ(t)定義如下：

λ(t)=

(2)

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

任務重用系數是指在一個任務約束結構中，被重用的活動單元數與該約束控制結構中所有活動單元數的比值，量化反映了該約束結構中活動單元被重用的水平，具體定義如下：

(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(t)是任務關聯系數和任務重用系數的乘積，即

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

(4)

它綜合表征了任務約束結構的內聚程度。云制造整體任務Tc的內聚系數V為各個子任務內聚系數的均值。

1.4 制造任務相關性度量方法

云制造任務種類繁多，有設計任務、制造加工任務、物流任務和測試任務等，各任務活動間不可避免地存在信息流和物料流的交互。在任務分解時應該盡量保持任務活動間的獨立性，以利于后續的各個任務活動能夠相對獨立地進行。因此，本文引入相關度的概念，分別從子任務間信息交互和實物流傳遞兩方面來判定任務活動之間相關性的大小。

信息相關度用來反映任務與任務之間的信息依賴關系，本文采用模糊設計矩陣法來構建云制造任務之間的信息關聯矩陣，即

(5)

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

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

(6)

其中，bij表示任務i與任務j之間的物料轉移相關程度，量化表征了任務之間的實物流動重要程度和密集程度，取值范圍為[0，1]，一般采用專家評價法確定[9]。

設計類制造任務中，產品設計涉及大量文件傳遞及溝通協調工作，但在此過程中很少有實體物流產生，故信息相關度較高，物流相關度較低。制造加工類、測試類和物流類制造任務的物料轉移活動較多，故物流相關度較高，可見制造任務類型的不同對物流相關度的影響較大。

任務相關度是制造任務間關聯關系的綜合度量，則任務活動i和j之間的任務相關度為

rij=waij+(1-w)bij

(7)

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

2 云制造任務分解算法

2.1 HTN規劃方法

HTN規劃是基于分層抽象和領域知識的智能規劃求解方法，其基本步驟是：根據預先給定的目標任務，按照遞歸的方式將復合任務不斷分解為更小粒度任務，同時在分解過程中進行相關約束和沖突校驗，直至形成具有嚴格時序關系和約束關系的復雜任務活動網絡，從而形成任務規劃問題的可行解。

HTN規劃問題可描述為三元組Q=(s0，w0，D)，其中，s0是規劃問題的初始狀態；w0是初始任務網絡；D是HTN規劃領域，由操作集和方法集組成。

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

任務活動網絡tNet=((n1∶e1)，(n2∶e2)，…，(nm∶em)，l)，其中，ni為任務ei的唯一標識符，ni∈N；l為約束條件，如時序約束、狀態約束和值約束等。

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

常規HTN規劃方法具有領域無關性，因此，在解決特定的領域規劃問題時需要引入領域知識，如產品設計任務需要考慮產品結構要求、功能要求等知識，制造加工任務則需要考慮工藝要求、資源約束等知識。領域知識在引入HTN規劃方法時，通常以操作集合和方法集合表現，通過拓展操作和方法的內涵，實現制造領域知識的引入。

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

方法g的作用是將復合任務分解為多個子任務。復合任務在分解時可能有多種分解模式，因此在構建方法g時需要融入領域知識。將d改寫為((p1，d1)，(p2，d2)，…，(pn，dn))的序對形式，新的方法可表示為g*=f(e，(p1，d1)，(p2，d2)，…，(pn，dn))，(pi，di)，表示在前提條件(領域知識的載體)pi下，通過方法g將復合任務e分解為di。

云制造任務分解中，任務類型多樣，涉及多領域知識，且任務活動間約束結構較為復雜，存在并行、選擇和循環等復雜約束結構關系，通過在操作中引入k元素，以及在方法g中引入(oprei，di)，在di中定義序對之間的約束結構關系，將領域知識引入方法g，從而實現不同類型云制造任務的分解。

2.2 基于HTN的云制造任務分解算法

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

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

3 實例驗證

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

表1 部分試制任務QoS約束條件

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

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

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

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

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

圖3 分解后的任務網絡圖Fig.3 Network of decomposed task

可以得出8個有效子任務，其活動約束結構為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})}，各子任務的分解圖見圖4。

(5)根據式(2)～式(4)，分別計算相應任務集的內聚系數，如表2所示。

由式(1)可計算出任務粒度：

該分解方案的任務粒度在任務內聚度閾值范圍之內，因此，進入制造服務匹配階段，篩選候選制造服務集。若此時的任務粒度不在任務內聚度閾值范圍之內，則需要對任務網絡進行相關性分析，根據任務活動之間信息交互、物流交互以及功能相似度分別構造信息關聯矩陣D和物流關聯矩陣H，將信息交互以及物流交互較多的任務活動進行合并，從而增大任務集的內聚系數，降低任務集之間的相關性，提高任務執行效率。

(a) (b)

(c) (d)

(e) (f)

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

任務序號活動關聯系數λ(t)活動重用系數μ(t)任務內聚系數w(t)a1．0000．200．200b1．0000．250．250c000d1．0000．200．200e000f0．3330．200．066g000h0．5000．250．125

任務活動網絡符合任務粒度約束條件后，需要為任務活動網絡中各子任務匹配符合要求的制造服務。在匹配過程中主要考慮服務延時率、服務中標率、服務完成率、服務匹配度、服務糾紛率和服務信譽度等QoS約束條件，用戶可根據實際需求來調整篩選的參數，以擴大或縮小候選制造服務的規模，最終形成候選制造服務集，為云制造資源優化配置提供數據支撐。

4 結語

任務分解的目標在于將復雜的多層次、多粒度制造任務細化為粒度合適、便于協同執行的子任務。本文給出了云制造任務描述模型及任務約束結構的相關定義，設計了基于分層任務網絡的云制造任務遞歸分解算法，并給出了制造任務粒度分析方法、制造任務內聚性度量方法以及制造任務相關性度量方法。該方法不但考慮了任務相關性和內聚性，還將制造任務與制造資源的匹配性以及任務分解的領域知識引入任務分解過程，從任務流程建模與規劃、任務相關關系分析以及制造資源匹配等方面對任務分解方法進行優化，有效提高了任務分解效率，降低后序制造資源優化配置問題的復雜性。

[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] 安波，廖文和，郭宇，等.基于相關性的擴散制造任務規劃方法研究[J].中國機械工程，2011，22(23)：2839-2844.ANBo，LIAOWenhe，GUOYu，etal.StudyonExtendedManufacturingTaskPlanningMethodBasedonCorrelation[J].ChinaMechanicalEngineering，2011，22(23)：2839-2844.

[7] 包北方，楊育，李斐，等.產品定制協同開發任務分解模型[J].計算機集成制造系統，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] 秦壽康. 綜合評價原理與應用[M]. 北京:電子工業出版社, 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年生。南京理工大學機械工程學院博士研究生。主要研究方向為農業機械裝備。發表論文3篇。E-mail:jiangqinghai101@126.com。武 凱，男，1972年生。南京理工大學機械工程學院教授。孫 宇，男，1964年生。南京理工大學機械工程學院教授、博士研究生導師。楊 棟，男，1991年生。南京理工大學機械工程學院博士研究生。

2016-04-27

TH166

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