[發明專利]支持依賴和時間平衡的云工作流任務聚類方法

在審

• 申請號: 201710202595.2
• 申請日: 2017-03-30
• 公開（公告）號: CN106991006A
• 公開（公告）日: 2017-07-28
• 發明（設計）人: 嚴偉;楊朔;楊威;呂躍華;陶礫;施揚朋
• 申請（專利權）人: 浙江天正信息科技有限公司
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 杭州君度專利代理事務所(特殊普通合伙) 33240
• 代理人: 杜軍

1.支持依賴和時間平衡的云工作流任務聚類方法，其特征在于包括如下步驟：

步驟(1).輸入流程圖中某一層待聚類的任務集taskList；流程圖是工作流W＝(T,E)的圖形化表示，通過有向無環圖來描述；其中T＝{t1,t2,...,tm}是頂點的集合，代表流程中的任務；E是有向邊的集合，代表任務之間的依賴關系；流程圖中從開始任務到某個任務所經過的有向邊的條數稱為該任務所在的層數；

步驟(2).計算該層任務中任意兩個任務之間的關聯度cor(ti,tj)；

關聯度的計算公式如下：

c o r ( t i , t j ) = | c ( t i ) ∩ ( t j ) | | c ( t i ) | · | c ( t j ) | ]]>

其中c(ti)表示任務ti的下一層子任務集合，|c(ti)|表示任務ti的下一層子任務個數；

步驟(3).輸入一個不超過該層任務總數n的聚類個數clusterNum，根據該聚類個數對該層的任務總數進行均分，得出每個聚類Ci需要填充的任務個數；設n/clusterNum的商數為p、余數為q，則前q個聚類需要填充的任務個數為p+1，其余聚類需要填充的任務個數為p；

步驟(4).按聚類C1、C2…CclusterNum的順序，根據聚類Ci需要填充的任務個數對聚類Ci進行任務填充；

特別地，當聚類Ci中所需任務個數為1時，則將剩余未分配的各個任務分別填充至聚類Ci、Ci+1…CclusterNum中，聚類結束，轉至步驟(7)；否則，從剩余任務中找到關聯度最大的兩個任務放到聚類Ci中；

若有多個任務對的關聯度都達到了最大，則選擇任務對中兩任務運行時間之和最接近的任務對填充到聚類Ci中，其中n表示該層包含的任務個數，RT(ti)表示任務ti的執行時間；

步驟(5).若此時聚類Ci中已有的任務個數小于需要填充的任務個數，則計算剩余任務中的每個任務分別加入聚類Ci后Ci中所有任務對的關聯度之和，選擇使得關聯度之和達到最大的那個任務填充到聚類Ci中，如果滿足上述條件的任務有多個，則在這幾個任務中選擇運行時間最接近聚類Ci中剩余平均運行時間leftTaskTime的任務，其中聚類Ci中剩余平均運行時間的計算公式如下：

l e f t T a s k T i m e = Σ i = 1 n R T ( t i ) c l u s t e r N u m - c u r T a s k T i m e ( C i ) n e e d N u m ( C i ) - c u r T a s k N u m ( C i ) ]]>

其中curTaskTime(Ci)表示聚類Ci中已經填充的任務的運行時間之和，curTaskNum(Ci)表示聚類Ci中已經填充的任務數，needNum(Ci)為聚類Ci需要填充的任務個數，n表示該層包含的任務個數；

步驟(6).按步驟(5)繼續向聚類Ci中填充任務，直至填充完畢，然后跳至步驟(4)，繼續下一個聚類的填充，直到所有的聚類都填充完畢；

步驟(7).輸出聚類結果Ci，i＝1,2,...,clusterNum。