[發明專利]一種分布式計算任務的協同調度方法及裝置

有效

• 申請號: 201710078384.2
• 申請日: 2017-02-14
• 公開（公告）號: CN108427602B
• 公開（公告）日: 2021-10-29
• 發明（設計）人: 朱力鵬;胡斌;饒瑋;黃太貴;李端超;王松;靳丹;馬志程
• 申請（專利權）人: 全球能源互聯網研究院有限公司;國網安徽省電力有限公司;國網甘肅省電力公司;國家電網有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06N3/12
• 代理公司: 北京安博達知識產權代理有限公司 11271
• 代理人: 徐國文

1.一種分布式計算任務的協同調度方法，其特征在于，所述方法包括：

確定各任務在各資源上的期望完成時間，并建立期望完成時間矩陣；

利用基因表達式編程算法確定各資源需處理任務個數；

根據各任務的緊迫度和重要度確定各任務的評估值，并按各任務的評估值從大到小排序，獲取任務序列；

根據所述期望完成時間矩陣和各資源需處理任務個數利用Min-Min算法依次將任務序列中的任務分配到各資源上；

所述根據各任務的緊迫度和重要度確定各任務的評估值，并按各任務的評估值從大到小排序，獲取任務序列，包括：

按下式確定任務i在當前時刻t的評估值G_i(t)：

G_i(t)＝p₁U_i(t)+p₂I_i

上式中，U_i(t)為任務i在當前時刻t的緊迫度，I_i為任務i的重要度，p₁為緊迫度權重，p₂為重要度權重，p₁+p₂＝1；

按下式確定任務i在當前時刻t的緊迫度U_i(t)：

U_i(t)＝t_i1/(t_i2+t_i3-t)

上式中，t_i1為任務估計完成時間，t_i2為任務被允許的完成時間；t_i3為任務被允許的超時時間；

按下式確定任務i的重要度I_i：

I_i＝m₁H_i+m₂N_i

上式中，H_i為任務i的關系重要度，N_i為任務i的時間重要度，m₁為關系重要度權重，m₂為時間重要度權重，m₁+m₂＝1；

其中，按下式確定任務i的關系重要度H_i：

上式中，M_ik為任務i與任務k的關系依賴度，若M_ik＝0，則任務i與任務k無關，若M_ik＝1，則任務i的執行過程與任務k的執行過程相互依賴，n為任務總數；

按下式確定任務i的時間重要度N_i：

上式中，t_i1為任務i的估計完成時間，t_k1為任務k的估計完成時間；

所述利用基因表達式編程算法確定各資源需處理任務個數，包括：

a.初始化種群，所述種群由m個資源和每個資源要處理的任務個數組成，其中，種群中染色體的頭長為p，尾長d＝p(l-1)+1，l為最大操作數；

b.根據種群個體的適應度函數值選擇種群中最優個體，保留最優個體并對當前子種群個體進行基因交叉、基因突變和重組，獲取新種群，其中，按下式確定種群個體的適應度函數：

上式中，M為資源選擇任務個數的范圍值，C_(i,j)為任務i對資源j的適應度返回值，T_j為資源j選擇任務個數的目標值，f_i為任務i調度到資源j上的適應度值；

c.若遺傳代數t滿足tT，則輸出所述新種群，并對該新種群進行解碼，獲取目標函數值最小時各資源需處理任務個數，若遺傳代數t不滿足tT，則令t＝t+1并返回步驟b，其中，所述目標函數為：

上式中，h_j為資源j需處理任務的個數，e_ij為第i個任務在第j個資源上的期望完成時間，n為任務總數，m為資源總數。

2.如權利要求1所述的方法，其特征在于，所述確定各任務在各資源上的期望完成時間，并建立期望完成時間矩陣，包括：

記任務數為n，資源數為m，按下式構建n×m的期望完成時間矩陣E_n×m：

上式中，e_ij為第i個任務在第j個資源上的期望完成時間。