基于petri網(wǎng)和蟻群算法的并行測試系統(tǒng)任務調(diào)度問題研究.pdf

1、隨著現(xiàn)代科技和工業(yè)的飛速發(fā)展，計算機技術、微電子技術以及通信技術的廣泛應用，自動化測試系統(tǒng)也逐漸向并行化、復雜化和多元化的方向發(fā)展，使得測試系統(tǒng)的規(guī)模不斷擴大，結構越來越復雜，測試系統(tǒng)的任務調(diào)度問題就成為了制約系統(tǒng)性能和發(fā)展的瓶頸。由此，并行測試系統(tǒng)任務調(diào)度策略的研究已經(jīng)成為自動測試領域研究的熱點。基于上述分析，本文主要進行并行測試系統(tǒng)任務調(diào)度過程的建模以及任務調(diào)度算法的研究，通過對并行測試系統(tǒng)任務調(diào)度的過程以及當前任務調(diào)度問題所要關注

2、的問題進行分析，建立了任務調(diào)度的隨機petri網(wǎng)模型，并提出了一種基于petri網(wǎng)建模和蟻群算法結合的任務調(diào)度算法。具體完成的工作如下：
　　1.針對并行測試任務調(diào)度問題的描述、特點以及研究現(xiàn)狀等問題進行了研究和分析，然后介紹了petri網(wǎng)相關理論知識，并給出了建立隨機petri網(wǎng)模型的一般步驟和分析過程。
　　2.針對目前運用 petri網(wǎng)來研究并行測試系統(tǒng)任務調(diào)度問題的不足，文中介紹了并行測試系統(tǒng)的任務劃分原則和方法，并

3、給出了由任務相關圖與petri網(wǎng)模型轉化的算法，最后建立了并行測試系統(tǒng)任務調(diào)度過程的一般petri網(wǎng)模型，并通過實例仿真分析驗證運用petri網(wǎng)解決該問題的可行性。
　　3.針對標準蟻群算法進行任務調(diào)度時算法搜索前期信息素不足而容易陷入局部最優(yōu)解的問題，以及運用petri網(wǎng)理論求解容易導致模型狀態(tài)空間信息爆炸的問題，通過對標準蟻群算法進行改進，提出了一種基于petri網(wǎng)和蟻群算法結合的任務調(diào)度算法—P-ACO算法。具體來說，一是通

4、過改變標準蟻群算法的禁忌表的設置方式，由傳統(tǒng)的禁忌表改為螞蟻共享禁忌表，具體做法是在狀態(tài)轉移概率規(guī)則中加入約束檢驗，對于不符合約束條件的變遷，螞蟻不選擇該條路徑，從而加快算法的搜索速度；二是在算法開始執(zhí)行時，對局部信息素的更新中加入一個衰減因子，從而擴大算法的搜索范圍，避免算法陷入局部最優(yōu)解。
　　最后通過對三種調(diào)度算法的仿真對比分析，實驗結果表明本文所提出的P-ACO算法對并行測試系統(tǒng)的任務調(diào)度在執(zhí)行時間和負載均衡能力上均有很好