[發(fā)明專利]一種基于分組和禁忌搜索的并行測試任務(wù)調(diào)度方法

無效

• 申請?zhí)枺?/td>: 201010513676.2
• 申請日: 2010-10-13
• 公開（公告）號: CN101984412A
• 公開（公告）日: 2011-03-09
• 發(fā)明（設(shè)計）人: 路輝;閆麗琴;李曉白
• 申請（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號: G06F9/46
• 分類號: G06F9/46;G06F9/50
• 代理公司: 北京永創(chuàng)新實專利事務(wù)所 11121
• 代理人: 趙文利

技術(shù)領(lǐng)域

本發(fā)明涉及一種并行測試任務(wù)調(diào)度方法，具體涉及一種基于分組和禁忌搜索的并行測試任務(wù)調(diào)度方法，屬于自動測試測量技術(shù)領(lǐng)域。

背景技術(shù)

隨著高新技術(shù)的快速發(fā)展，自動測試系統(tǒng)(Automatic?Test?System，ATS)在很多行業(yè)得到廣泛應(yīng)用，逐步成為復(fù)雜電子裝備的檢測維護手段，而目前自動測試領(lǐng)域中存在比較突出的問題就是測試系統(tǒng)的測試效率低下，資源利用率較低。對于傳統(tǒng)的通用自動測試系統(tǒng)，大多沿用串行測試的方式，不能同時對多個UUT(Unit?Under?Test，被測設(shè)備)或者單個UUT的多項任務(wù)進行測試，一次僅能完成一個測試任務(wù)，使得整個系統(tǒng)的測試效率很低。隨著現(xiàn)代網(wǎng)絡(luò)化分布式測試應(yīng)用日益增多，串行測試方式已經(jīng)不能滿足現(xiàn)代測試技術(shù)快速發(fā)展的需求，因此研究新的測試技術(shù)，對發(fā)展自動測試系統(tǒng)具有十分重要的理論價值和現(xiàn)實意義。

并行測試技術(shù)的提出是并行處理技術(shù)與現(xiàn)代自動測試技術(shù)的融合，成為自動測試領(lǐng)域的一項重大突破，屬于NxTest?ATS(下一代自動測試系統(tǒng))技術(shù)范疇，也是支撐NxTest?ATS的新技術(shù)之一。并行測試是指ATS在同一時間同時測試多項任務(wù)，通過任務(wù)調(diào)度提高測試系統(tǒng)的吞吐量，減少測試設(shè)備的閑置時間，提高測試資源的利用率，從而提高系統(tǒng)測試效率。其核心之一就是在有限的測試資源的約束條件下，滿足由測試需求決定的測試任務(wù)要求，對多個并發(fā)執(zhí)行的測試任務(wù)進行調(diào)度優(yōu)化，從而達到測試資源利用率最大或總測試時間最短的目標。

目前，并行測試有多種實現(xiàn)方式，如分組測試、交迭并行測試等。分組測試簡單易行，卻不能保證完成所有測試任務(wù)的總時間最短；交迭并行測試通過對任務(wù)的合理安排調(diào)度及優(yōu)化，從而能夠?qū)崿F(xiàn)任務(wù)的總測試時間最短，對提高測試效率具有很直接的現(xiàn)實意義，因此在實際自動測試系統(tǒng)的研究和設(shè)計中也得到了越來越多的關(guān)注。

交迭并行測試技術(shù)的核心和關(guān)鍵是測試任務(wù)的調(diào)度優(yōu)化問題，好的任務(wù)調(diào)度方案能夠顯著提高自動測試系統(tǒng)的測試效率和資源的利用率。目前關(guān)于調(diào)度優(yōu)化問題的實現(xiàn)主要是基于算法的，利用單個算法解決實際問題，往往存在一定的局限性，如蟻群方法主要集中應(yīng)用在車間作業(yè)的調(diào)度方面，而作業(yè)調(diào)度的要求并不完全符合并行測試任務(wù)的需求；Task?Scheduler方法能通過類似枚舉的方法找到問題的最優(yōu)解，因此當(dāng)問題的規(guī)模比較大時，最優(yōu)解的找尋就相對比較費時。針對各種局限情況，調(diào)度問題出現(xiàn)了許多改進的方法，也出現(xiàn)了將兩種或兩種以上的方法融合起來，進而解決實際調(diào)度問題的方法。

禁忌搜索是一種通過自適應(yīng)的記憶結(jié)構(gòu)來引導(dǎo)局部搜索的技術(shù)，通過集中和擴散搜索策略能夠有效避免迂回搜索，但其對初始解的選取具有很強的依賴性。傳統(tǒng)方法通過隨機選擇的方式產(chǎn)生初始解，由于該初始解的隨機性，可能使得方法的尋優(yōu)搜索過程較為復(fù)雜，同時方法在搜索過程中極有可能陷入局部最優(yōu)的情況，從而無法找尋到問題的最優(yōu)解。而一個較好的初始解能夠使得方法避免陷入局部最優(yōu)情況，同時快速收斂到問題的最優(yōu)狀態(tài)，因此可以通過某種規(guī)則方法來獲取問題較好的初始解。將獲取初始解的方法與禁忌搜索方法融合起來，成為求解組合優(yōu)化問題最常用的智能優(yōu)化方法之一，已經(jīng)廣泛應(yīng)用于許多領(lǐng)域，包括機器學(xué)習(xí)，神經(jīng)網(wǎng)絡(luò)，電力通信，車間作業(yè)調(diào)度等。根據(jù)方法特性，可以將其應(yīng)用在自動測試領(lǐng)域的并行測試任務(wù)調(diào)度方面。

發(fā)明內(nèi)容

本發(fā)明的目的在于克服現(xiàn)有技術(shù)解決并行測試任務(wù)調(diào)度問題時的不足，提出一種基于分組和禁忌搜索的并行測試任務(wù)調(diào)度方法，通過圖染色理論中頂點染色方法完成測試任務(wù)的分組，利用分組結(jié)果構(gòu)造符合禁忌搜索過程要求的初始解，不但能夠解決禁忌搜索在完成任務(wù)調(diào)度問題時對初始值選取的不確定性，同時有效避免搜索陷入局部最優(yōu)，提高了測試任務(wù)調(diào)度優(yōu)化找尋最優(yōu)狀態(tài)的速度。

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

步驟1：確定和分析測試任務(wù)

根據(jù)需求明確測試任務(wù)，建立用于描述測試任務(wù)與測試資源之間占用關(guān)系的資源占用模型矩陣TR_n×m，以及表示測試任務(wù)之間約束關(guān)系的任務(wù)相關(guān)模型矩陣RE_n×n，其中，n表示測試任務(wù)總數(shù)，m表示測試資源總數(shù)：