[發(fā)明專利]一種任務(wù)調(diào)度方法及裝置

在審

• 申請?zhí)枺?/td>: 201610715089.9
• 申請日: 2016-08-24
• 公開（公告）號: CN107783831A
• 公開（公告）日: 2018-03-09
• 發(fā)明（設(shè)計）人: 李航
• 申請（專利權(quán)）人: 深圳市中興微電子技術(shù)有限公司
• 主分類號: G06F9/50
• 分類號: G06F9/50
• 代理公司: 北京派特恩知識產(chǎn)權(quán)代理有限公司11270
• 代理人: 張穎玲,蔣雅潔

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

重復(fù)執(zhí)行任務(wù)隨機分配操作，獲得包含有Q種任務(wù)分配方式的初始處理器分配方案；所述任務(wù)隨機分配操作為將所有N個任務(wù)隨機分配于M個處理器中；M、N、Q為自然數(shù)且M<N；

重復(fù)執(zhí)行下述操作，直至找到最終任務(wù)分配方式：

基于局部搜索和全局搜索更新處理器分配方案，計算更新后的處理器分配方案中每種任務(wù)分配方式下所有N個任務(wù)在M個處理器中完成所需的時間；

當(dāng)所需時間最短的任務(wù)分配方式滿足要求時，將所述所需時間最短的任務(wù)分配方式作為任務(wù)調(diào)度的最終任務(wù)分配方式。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述方法還包括：

當(dāng)所需時間最短的任務(wù)分配方式不滿足要求時，對所述更新后的處理器分配方案中的任務(wù)分配方式執(zhí)行變異操作。

3.根據(jù)權(quán)利要求1或2所述的方法，其特征在于，所述將所有N個任務(wù)隨機分配于M個處理器中，包括：

隨機選擇[1,M]之間的一個整數(shù)隨機數(shù)m₁，并從所有N個任務(wù)中隨機選擇一個任務(wù)分配給第m₁個處理器；隨機選擇[1,M]之間的一個整數(shù)隨機數(shù)m₂，并從剩余的N-1個任務(wù)中隨機選擇一個任務(wù)分配給第m₂個處理器；以此循環(huán)，直至所有N個任務(wù)都被分配給M個處理器，獲得一種任務(wù)分配方式。

4.根據(jù)權(quán)利要求1或2所述的方法，其特征在于，所述基于局部搜索和全局搜索更新處理器分配方案，包括：

利用粒子群算法對當(dāng)前的處理器分配方案進行局部搜索，獲取所述當(dāng)前的處理器分配方案中的局部最優(yōu)任務(wù)分配方式；

將所述當(dāng)前的處理器分配方案中的局部最優(yōu)任務(wù)分配方式下所有N個任務(wù)在M個處理器中完成所需的時間作為第一時間；所述當(dāng)前的處理器分配方案中的全局最優(yōu)任務(wù)分配方式下所有N個任務(wù)在M個處理器中完成所需的時間作為第二時間；

確定所述第一時間小于或等于所述第二時間時，將所述當(dāng)前的處理器分配方案中的全局最優(yōu)任務(wù)分配方式替換為所述當(dāng)前的處理器分配方案中的局部最優(yōu)任務(wù)分配方式；

對所述當(dāng)前的處理器分配方案中的任務(wù)分配方式執(zhí)行交叉操作，獲得更新后的處理器分配方案。

5.根據(jù)權(quán)利要求4所述的方法，其特征在于，所述利用粒子群算法對當(dāng)前的處理器分配方案進行局部搜索，獲取所述當(dāng)前的處理器分配方案中的局部最優(yōu)任務(wù)分配方式，包括：

隨機生成一個包含有I個粒子且每個粒子為一種任務(wù)分配方式的初始粒子群，并將所述當(dāng)前的處理器分配方案中的全局最優(yōu)任務(wù)分配方式作為所述初始粒子群的初始最優(yōu)粒子加入到所述初始粒子群中；

根據(jù)更新在第k+1次迭代時粒子i的速度V_i(k+1)，1≤i≤I+1，0≤k≤K-1；其中，X_gbest(k)表示在第k+1次迭代之前所述粒子群中最優(yōu)粒子的位置，X_ibest(k)表示在第k+1次迭代之前粒子i的最優(yōu)位置，表示交叉操作,K為設(shè)置的最大迭代次數(shù)；所述最優(yōu)粒子為粒子群中具有最小適應(yīng)度值的粒子；所述適應(yīng)度值為粒子在所對應(yīng)的任務(wù)分配方式下所有N個任務(wù)在M個處理器中完成所需的時間；

根據(jù)更新在第k+1次迭代時粒子i的位置X_i(k+1)；

計算粒子i在第k+1次迭代時的適應(yīng)度值，并根據(jù)粒子i在第k+1次迭代時的適應(yīng)度值更新所述粒子i在第k+1次迭代后的最優(yōu)位置X_ibest(k+1)、以及更新在第k+1次迭代后所述粒子群中的最優(yōu)粒子和所述粒子群中更新后的最優(yōu)粒子的位置X_gbest(k+1)；

當(dāng)檢測出所述迭代次數(shù)k+1小于K且所述粒子群中最優(yōu)粒子的適應(yīng)度值小于設(shè)置的第一閾值或所述迭代次數(shù)k+1等于K時，將所述粒子群中的最優(yōu)粒子所對應(yīng)的任務(wù)分配方式作為所述當(dāng)前的處理器分配方案中的局部最優(yōu)任務(wù)分配方式；

當(dāng)檢測出所述迭代次數(shù)k+1小于K且所述粒子群中最優(yōu)粒子的適應(yīng)度值大于或等于設(shè)置的第一閾值時，計算第k+1次迭代后所述粒子群中粒子之間的相似度值，若所述相似度值大于或等于設(shè)置的第二閾值，則對所述粒子的位置執(zhí)行變異操作。