網絡協同設計過程的任務分解算法模型研究＊

四川大學機械工程學院 成都 610065

0 引言

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

合理的任務分解方法能夠科學分解制造任務，獲得合理的子任務拓撲結構，使云環境下的資源匹配吻合度高，資源利用效率高。相關研究如文獻[3]通過構建擴散任務相關性模型，結合粒子群聚類優化分解算法，實現對擴散任務的有效分解，文獻[4]在制造任務分解的時考慮了任務之間的關聯性，更加適合于云環境下的制造場景，為研究制造任務的分解提供了思路和準則。

根據制造任務分解的三大原則[5]：自下而上的分解原則、能整不分的分解原則以及能分不拆的分解原則。首先研究任務模型的表達，然后基于層次分解的思想，再綜合考慮相關性、內聚性等評價指標，利用改進的順序任務分解方法（OTD）實現云環境下的制造任務分解。

1 云環境下的任務表達方法

1.1 云環境下的任務模型

物元模型[6]是易于計算機存儲、識別和操作的實體對象的表示方法，廣泛應用于目標的模型表達。本文應用物元模型將一項云端制造任務Tk，具體描述了任務本身的各項需求和約束以及用戶的相關期望等，Tk可表示為

式中：Tki為制造任務Tk的第i個子任務，而且每項可分子任務Tki可用三元組描述如式所示；Ta為子任務Tki的屬性集合；To為子任務Tki的狀態集合；Tu為子任務Tki的服務消費集合，依據相關性、內聚性等評價指標，逐級分解到各項子任務均具有不可再分的任務粒度。

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

1.2 任務分解指標構建

任務分解的層級及子任務的數量和粒度控制是云制造任務分解的關鍵，直接影響云制造任務協同完成的質量、執行進度和成本。因此，研究任務分解時子任務之間的關聯關系和內聚性對任務執行的效率和成本至關重要，在學習現有研究的基礎上構建了關聯性度量、內聚性度量和任務粒度評估等指標，對任務分解過程進行控制。

1）任務粒度St

任務粒度層數越深，任務粒度越小，任務個數越多，任務粒度越小，故任務粒度的量化可表示為

式中：St為任務粒度量化指標；La為子任務層數；N為子任務個數，＆為引入的粒度系數。任務層次分解時每一層的任務粒度需要設定閾值、嚴格控制，保證任務的原子性，為次層級的任務分解做好基礎準備。

2）內聚性Pt

內聚性是模塊構建的基本目標，是軟件構建內聯關系的表征。定義為：若M的執行需要調用或等待N的完成或執行，則M調用依賴于N，一個方法M依賴于方法N，則記作M→N。

由于子任務具有較高模塊性，故引入內聚性來度量子任務內部活動單元之間的關聯程度，然后求平均值來綜合評價該項任務的內部關聯程度以判斷其分解效果。由于任務存在較多的約束（時間約束、成本約束和質量約束等），然而這些約束之于任務并不能完全等同于軟件工程中的變量之于方法，故而本文提出以多約束下的模塊內聚度計算方法，即

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

3）相關性Rt

云環境下的制造任務種類多、活動豐富，強約束性（尤其是時序約束）的存在使制造任務的相關性異與軟件構構件中的方法關系，同時一項制造任務的完成依賴于各子任務間的信息交互和物流交通，故任務分解過程需要考慮到任務的獨立性及其相關性，本文應用模糊理論來構建了信息矩陣和理論物流矩陣來描述任務活動間的相關關系。

圖1 半嶺分布型隸屬度函數

考慮到模糊知識的獲取應該去極端化，體現出一般性規律，本文采用半嶺型分布作為專家術語隸屬度函數，再考慮參與評價專家總數和評價術語出現次數（專家評價采用0-9打分法）[7]，建立制造任務關聯關系的量化模型為

式中：N為參與評價的專家人數，Qi為專家對兩個制造任務的關系的第i項評價值，Vi為對該關系做出相同評價值的專家人數，由此計算所得的x可認為是對于兩個制造任務關聯關系的綜合經驗描述，然后將其帶入到半嶺分布當中計算其隸屬度值aij，則aij能基于專家知識和模糊理論量化兩個制造任務i、j之間的關聯程度。以aij為元素，構建如下信息關聯矩陣A，同理獲得物流關聯矩陣L為

考慮到制造任務的多樣性，如設計任務主要以信息交流為主，很少產生實際的物流交互，生產加工類任務則需要信息交互和物流交互雙向溝通，故任務i和任務j的任務關聯度綜合描述為

以rij為元素的三角對稱矩陣R反映了各項任務的關聯關系，其中w1和w2為不同任務類型下關于信息關聯和物流關聯的權值，任務分解時秉承著各子任務內部聚合度高，子任務間關聯弱的原則，故需設定關聯度閾值Rmax＞∞-范數（矩陣R）。

2 改進OTD方法

2.1 OTD方法

傳統的OTD算法是基于分層任務網絡（HTN）規劃方法[8,9]來研究任務分解的方法，一般將一個任務分解問題表示為四元組q＝(s0,w※,Os,Ms)，其中s0為問題的數學模型，w※為初始任務網絡狀態，Os為操作集合，Ms為分解方法集合。該算法的運行流程為：

1）從初始狀態w0※開始，選擇一個可轉換為復合任務的簡單任務ei，任取一個方法mj∈Ms對ei進行分解；

2）總任務網絡N※及子任務網絡集Ns※形成來描述分解目標；

3）對任務網絡進行評價指標分析計算并判斷是否達標，若達標則執行步驟4，否則返回步驟1；

4）輸出分解結果并結束算法。

傳統的OTD算法主要使用分解方法對任務進行分解，判斷其可行性，如若不可行則重新開始分解。然而任務分解的粒度太小、層級太深會使任務間的關系復雜，造成信息交互困難和物流緊張，增加任務執行和管理難度，任務活動太少、粒度太大，直接導致任務內部復雜度高。任務個數和層數不是強相關的兩個變量，能否通過改變任務數量而不增加任務層數，或反之來控制粒度大小和實現分解目標。

2.2 改進的OTD方法

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

式中：Oi為集合Op的第i個元素，Oi的解析式是關于內聚性、任務粒度以及相關性的函數形式，如再在判定當前分解狀態下的St過小，當Pt、Rt均復合條件時，則可選定增大St的算子對當前狀態進行修改，使之成為無違規約束的可行解，傳統OTD與本文改進的OTD之間的流程差異如圖2所示。

圖2 半嶺分布型隸屬度函數

如圖2所示為改進OTD算法，該方法借鑒啟發式算法的思想，根據每次迭代的相關性、內聚性以及任務粒度值來判斷當前解所在狀態距離目標解的距離以及方向，并據此來設定相關算子以形成搜索壓力，使得當前解向著目標解的方向進行搜索。

3 實例應用

為了驗證上述方法的有效性和可行性，本文以固定卷揚式啟閉機的制造任務分解為例，對文中提及的任務分解方法進行驗證，并根據用戶要求設定Pmax-t＝2.5、8＜St＜10、對于每個子任務的Rmax-t＝0.5，對于n個子任務，任務的Rmax-t＝0.5n,進行云環境下的制造任務分解。

啟閉機的制造任務主要包括標準件定制和非標件生產兩個步驟，根據裝配需求，其制造任務的約束主要以時序約束為主，任務分解的方法集合包括時序可分Tm和功能可分Fm，響應的根據相關性、內聚性和粒度的可壓縮值，Os集合包括Rt改進方法Rm、St改進方法Sm以及Pt改進方法Pm。在此，以Pm對固定卷揚式啟閉機的制造進行任務分解，對比傳統的OTD方法，突出本文所論改進的特點所在。

3.1 基于功能的OTD分解實例

基于啟閉機的功能分解方法Fm進行任務分解，啟閉機根據功能分解方法Fm根據OTD算法可將其分解為如圖3所示的制造任務結構。

圖3 基于功能的啟閉機制造任務OTD分解

1）Pt的計算

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

2）St的計算

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

則基于功能分解

即卷筒結構的內聚度值為2。同理，以鋼絲繩、卷筒和軸承座的制造為活動，計算卷揚機構的內聚度，由于鋼絲繩與卷筒相關，軸承座與卷筒相關，鋼絲繩與軸承座無依賴關系，且有根據上述計算M（卷筒）＝2，故在計算卷揚機構聚合度時有

由此可見，Pt(卷筒)＝ 2 ＞Pt(卷揚機構)＝ 1.67。由于卷軸與筒壁兩個活動全相關，而鋼絲繩與軸承座存在不相關關系，也證明了內聚度計算方法的科學性，依次計算的Pt(啟閉機制造)＝ 1.74。

3）Rt的計算

相關性Rt的計算，根據專家經驗和專業知識，對于20個具有執行屬性的子任務，根據專家給予的信息矩陣和物流矩陣，并賦予w1＝0.7和w2＝0.3，獲得相關性關系矩陣R，并計算得R∞-范數＝7。

3.2 基于功能的改進OTD分解實例

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

由于Pt和Rt相比于分解需求，均具距離用戶設定極值有較大的程度，故從Op中選擇MR（即通過增大Rt值使得其他指標滿足要求）對任務分解結構進行改進，以求通過犧牲Rt來增加St使任務分解盡早滿足約束。具體表現為減小任務個數，將耦合度高的子任務合并到一個子任務，運用Op中選擇MR的任務分解結構見圖4。

圖4 基于功能的啟閉機制造任務改進OTD分解

再根據前述的方法計算得St＝9.6，Pt＝1.67，R∞-范數＝8.1，各項指標均滿足分解約束。

3.3 結果分析

將OTD與改進OTD該方法對該任務進行分解后獲得的任務粒度、內聚性和相關性對比如圖5所示。由圖5可知，改進OTD方法通過犧牲空間較大的指標（相關性）來使得降低違反約束的指標值，改變接盡可行解的拓撲結構，獲得可行解。相比于傳統的OTD，改進OTD方面在接近可行解上修改任務的拓撲結構。因此，改進OTD尋找的解更具多樣性，且能避免分解步驟重新開始。

圖5 效果對比

4 結論

1）應用物元模型建立云環境下的制造任務模型，并充分考慮了其屬性、分解狀態和執行狀態，所研究的模型能勝任云制造中的任務表達、存儲和展示；

2）對比傳統OTD方法，本文研究的改進OTD方法能夠在接近可行解上修改任務的拓撲結構，調整分解指標，獲得分解結果。然而，如果分解過程中出現的接盡可行解難以通過算子Op改進獲得可行解，運行算子Op將消費一定的時間；

3）以固定卷揚式啟閉機的云制造任務分解為例，對所提方法進行了驗證。