[發(fā)明專利]一種工作流的任務(wù)調(diào)度方法、多工作流調(diào)度方法及其系統(tǒng)

在審

• 申請?zhí)枺?/td>: 201410089720.X
• 申請日: 2014-03-12
• 公開（公告）號: CN103914754A
• 公開（公告）日: 2014-07-09
• 發(fā)明（設(shè)計）人: 張鵬;張世鵬;李焱;朱嵬;劉慶云;譚建龍
• 申請（專利權(quán)）人: 中國科學(xué)院信息工程研究所
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 北京輕創(chuàng)知識產(chǎn)權(quán)代理有限公司 11212
• 代理人: 楊立

1.一種工作流的任務(wù)調(diào)度方法，其特征在于，包括：

步驟1，計算工作流中每個任務(wù)的向上權(quán)值，按向上權(quán)值的降序排序?qū)⑷蝿?wù)放入待調(diào)度任務(wù)列表；

其中，任意任務(wù)n_i的向上權(quán)值rank(n_i)被遞歸地定義為：

rank(ni)=w‾i+maxnj∈succ(ni)(ci,j‾+rank(nj));]]>

式中，n_j表示任務(wù)n_i的直接后繼節(jié)點，succ(n_i)表示n_i的直接后續(xù)節(jié)點集合，n_j∈succ(n_i)；表示任務(wù)n_i在所有處理機上的平均預(yù)計執(zhí)行時間；表示n_i和n_j之間數(shù)據(jù)傳遞的平均時間；

步驟2，選擇向上權(quán)值最大的任務(wù)，遍歷并計算該任務(wù)在每個處理機上的最早完成時間，將該任務(wù)部署到最早完成時間最短的處理機上執(zhí)行；

步驟3，按待調(diào)度任務(wù)列表中的任務(wù)順序，采用步驟2的方法為工作流中其余任務(wù)部署相應(yīng)的處理機。

2.根據(jù)權(quán)利要求1所述的任務(wù)調(diào)度方法，其特征在于，所述步驟1中，采用以下公式計算n_i和n_j之間數(shù)據(jù)傳遞的平均時間

Ci,j‾=L‾+datai,j/B‾]]>

式中，為所有處理機數(shù)據(jù)傳輸?shù)膯訒r間的均值，data_i,j表示從任務(wù)n_i到n_j的數(shù)據(jù)傳遞量，表示處理機之間進行數(shù)據(jù)傳輸?shù)钠骄鶄鬟f時間。