[發(fā)明專利]基于貪婪式分組策略的動態(tài)測試任務調(diào)度方法及調(diào)度平臺

有效

• 申請?zhí)枺?/td>: 201811325860.7
• 申請日: 2018-11-08
• 公開（公告）號: CN109409763B
• 公開（公告）日: 2021-03-12
• 發(fā)明（設計）人: 路輝;石津華;周乾琳;池程芝
• 申請（專利權(quán)）人: 北京航空航天大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/00
• 代理公司: 北京永創(chuàng)新實專利事務所 11121
• 代理人: 冀學軍

1.一種基于貪婪式分組策略的動態(tài)測試任務調(diào)度方法，其特征在于，具體步驟如下：

步驟一、針對自動測試任務調(diào)度場景，從測試實例中獲取測試任務集的信息；

信息包括：測試任務表T＝{t₁,t₂,…,t_j,...,t_N}，t_j為第j個測試任務，N為測試任務總數(shù)；

儀器資源表R＝{r₁,r₂,…,r_i,...,r_M}，r_i為第i個儀器資源，M為儀器資源總數(shù)；

第j個測試任務的方案集表為：k_j表示第j個測試任務的總方案個數(shù)；表示測試任務t_j的第k_j個方案；

動態(tài)任務表D＝{d₁,d₂,...,d_Q}，Q為新任務的總個數(shù)；

故障儀器表B＝{b₁,...,b_S}，S為故障儀器的總個數(shù)；

步驟二：根據(jù)實際需要選擇目標函數(shù)并初始化，選擇粒子群算法為搜索算法進行參數(shù)設置；同時選用實數(shù)編碼方式；

目標函數(shù)為最大完工時間：

其中，表示每組內(nèi)的最后一個測試任務t_j選擇方案時需要完成的時間，即該組內(nèi)所有測試任務選擇方案都完成的時間；

選擇粒子群算法為外層優(yōu)化和內(nèi)層優(yōu)化的搜索算法，并進行調(diào)度方法的參數(shù)設置；

外層優(yōu)化確定當前所有測試任務的分組方式，內(nèi)層優(yōu)化是指確定分組后，每組內(nèi)的測試任務選擇各自方案的調(diào)度順序；

組內(nèi)優(yōu)化目標改進為：

其中，makespan表示組內(nèi)所有任務的最大完工時間；idle_m表示儀器資源m上的總空閑時間；fin_m表示所有任務在儀器資源m上的完工時間；

采用適合于搜索算法與問題描述的實數(shù)編碼方式，由每一位的數(shù)值大小決定分組方式及任務排序；通過選用N個0-1之間的實數(shù)作為N個測試任務，實數(shù)的大小決定了測試任務的排列順序，選擇所有測試任務等間隔分組的方式，則每個測試任務對應的實數(shù)的第一位小數(shù)決定了該測試任務選擇的方案；

步驟三、采用實數(shù)編碼方式隨機選擇N個測試任務，并等分成Gn組依次編號；

Gn組編號為gn＝{1,2,3,....n}；

步驟四、按順序依次選擇等分組編號，并基于搜索算法進行當前組的內(nèi)層優(yōu)化，得到當前組內(nèi)的最優(yōu)解；

初始小組編號gn為1，所有資源的開始可用時間均置為0；

具體步驟為：

步驟401、針對按分組編號選取的當前組，該組中有tn個任務，采用PBSCR分配規(guī)則為每個任務分配資源；

當前組的初始值為編號1的等分組；tn個任務編號為：{t1,t2,t3,....,ti,....tn}；第ti個任務有m_i種資源分配方式；

步驟402、按任務編號依次選取當前任務，并遍歷當前任務的所有可選方案，計算每種方案的完成時間并記錄；

當前任務初始值為t1；第ti個任務的所有可選方案的完成時間為

步驟403、利用每種方案的完成時間，計算各方案的被選擇概率；

針對第ti個任務的第j'種方案，被選擇概率為：

被選擇概率的值越大，該方案被當前任務選擇的可能性越大；

步驟404、根據(jù)概率的大小，采用輪盤賭方法為第ti個任務確定所選方案；

步驟405、為當前組中tn個任務確定各自的方案后，經(jīng)過排序得到當前組的若干解，每個解分別對應一個適應度值；

每個解解碼后，對應當前組內(nèi)所有測試任務的任務排序和方案選擇；

步驟406、對當前任務的所有的適應度值，采用粒子群算法依次進行迭代優(yōu)化，直至達到預定的最大迭代次數(shù)，得到當前組的一個最優(yōu)適應度值f_gn，該值對應當前組的最優(yōu)解；

最優(yōu)適應度值f_gn是當前組中的所有測試任務，按照最優(yōu)排序和最優(yōu)方案選擇調(diào)度后的完成時間；

步驟五、更新資源的當前狀態(tài)，作為下一小組的初始條件，小組編號gn自增1，返回步驟四，直至gn＝n，得到各小組內(nèi)的最優(yōu)適應度值f_gn，進而得到各小組的最優(yōu)解；

步驟六、將各小組的最優(yōu)解進行解碼，得到各組對應的最優(yōu)調(diào)度方案，將所有的最優(yōu)調(diào)度方案首尾相連，得到當前分組方式下的適應度值f_n；

適應度值f_n即當前分組方式中的最后一組完成的時間，也就是當前分組方式下所有組內(nèi)的測試任務都完成的時間；

步驟七、采用實數(shù)編碼方式再次隨機選擇N個測試任務，并等分組依次編號，返回步驟四；得到再次分組方式下的適應度值，直至達到設定的初始種群個數(shù)為止；

步驟八、將所有的分組方式下得到的適應度值，采用粒子群算法進行迭代優(yōu)化，直到達到預定的最大迭代次數(shù)，得到最小的f_n對應的最優(yōu)解；

步驟九、根據(jù)實數(shù)編碼方式對最小的f_n對應的最優(yōu)解進行解碼，得到靜態(tài)調(diào)度方案；

步驟十、利用靜態(tài)調(diào)度方案對動態(tài)事件進行響應；

步驟十一、輸出動態(tài)調(diào)度結(jié)果以及相應的調(diào)度甘特圖；

動態(tài)調(diào)度結(jié)果是動態(tài)事件發(fā)生后新的調(diào)度策略，即新的任務執(zhí)行順序和資源分配方式。