[發明專利]一種基于分組和禁忌搜索的并行測試任務調度方法

無效

• 申請號: 201010513676.2
• 申請日: 2010-10-13
• 公開（公告）號: CN101984412A
• 公開（公告）日: 2011-03-09
• 發明（設計）人: 路輝;閆麗琴;李曉白
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G06F9/46
• 分類號: G06F9/46;G06F9/50
• 代理公司: 北京永創新實專利事務所 11121
• 代理人: 趙文利

1.一種基于分組和禁忌搜索的并行測試任務調度方法，其特征在于，包括以下幾個步驟：

步驟1：確定和分析測試任務

建立用于描述測試任務與測試資源之間占用關系的資源占用模型矩陣TR_n×m，以及表示測試任務之間約束關系的任務相關模型矩陣RE_n×n，其中，n表示測試任務總數，m表示測試資源總數：

TRn×m=tr11tr12···tr1mtr12r22···tr2m············trn1trn2···trnm,REn×n=re11re12···re1nre12re22···re2n············ren1ren2···renn]]>

其中，資源占用模型矩陣TR_n×m的行表示測試任務T_i，1≤i≤n，列表示測試資源R_j，1≤j≤m，若TR_n×m中某元素tr_ij＝0，表示任務T_i在測試過程中不占用資源R_j；反之，若tr_ij≠0，則tr_ij＝t_i，表示任務Ti在測試過程中占用資源R_j，且占用時間為任務T_i的測試時間t_i；任務相關模型矩陣的行和列均代表測試任務，如果任務T_l和T_k在測試過程中需要占用相同的測試資源，其中1≤l≤n，1≤k≤n，那么任務相關模型矩陣RE_n×n中的元素re_lk＝1，即T_l和T_k任務相關，否則re_lk＝0，即T_l和T_k任務不相關；

步驟2：測試任務分組

根據步驟1建立的測試任務資源占用模型和任務相關模型，確立測試任務的圖論模型，利用最大度優先的Welsh-Powell方法對任務頂點進行染色，根據任務頂點顏色劃分結果完成測試任務的分組；

步驟3：構造任務調度優化的初始調度方案

由步驟2所得任務分組結果構造待測任務調度序列表示調度序列中第i個要安排調度的任務，根據序列依次確定每一個測試任務的最早開始測試時間、測試完成時間以及完成所有測試任務所需時間，得到初始任務調度方案；

步驟4：禁忌搜索優化調度方案

具體的實施步驟如下：

步驟4.1輸入步驟3所得的初始調度序列以及由該調度序列所確定的時間目標函數值f；

步驟4.2確定鄰域的生成規則，構造出禁忌搜索方法的鄰域，采用λ交換法，將λ值取為2，即交換調度序列中兩個任務的調度順序，具體構造過程如下：

(a)依次交換初始調度序列中最后一個任務與前面各個任務的次序，構造鄰域N1，鄰域規模為(n-1)，n為測試任務總數，對當前解序列進行集中搜索；

(b)交換初始調度序列中任意兩個任務的次序，構造鄰域N2，規模為n為測試任務總數，擴大搜索的空間；

步驟4.3構造方法的禁忌表，根據鄰域生成規則，將交換測序的兩個任務序號作為禁忌對象，并確定禁忌表的大小，即禁忌長度L，使得一個禁忌對象加入禁忌表后，經過L次的迭代運算，實現對該禁忌對象的解禁；

步驟4.4根據步驟4.2確定的鄰域生成規則構造當前調度序列的鄰域；

步驟4.5從鄰域中選擇序列作為新的當前調度序列，具體實現過程如下：

(1)確定擇優規則，從鄰域中選擇一個好解作為下一次迭代初始解，采用第一個改進解優先策略；

(2)確定搜索規則，結合N1和N2鄰域進行動態變鄰域搜索，根據確定的擇優規則，從當前解序列的N1鄰域中選擇第一個改進目標值的解序列，若N1鄰域中沒有滿足條件的解，則進入N2鄰域進行更大范圍搜索，如果仍然沒有滿足擇優規則的解序列，則從N2鄰域中選擇一個最好的解作為當前解序列；

(3)按照任務的排列次序，依次計算鄰域中的各序列進行調度的測試完成總時間，選擇出滿足搜索規則和擇優規則的解序列作為新的當前解序列；

步驟4.6判斷是否滿足禁忌搜索優化調度的搜索停止條件，搜索停止條件為給定一個最大的方法迭代次數；若不滿足，則對步驟4.4和步驟4.5進行迭代，不斷選擇新的解序列，同時生成新的鄰域逐步尋優；否則，轉下步；

步驟4.7輸出最后的任務調度方案，包括：滿足搜索停止條件前最后得到的當前調度序列、序列中各個任務的開始測試時間規劃和并行調度完成所有測試任務的總時間。