基于图禁忌的并行测试任务调度算法

《基于图禁忌的并行测试任务调度算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、航空学报ActaAeronauticaetAstronauticaSinicaSep．252011V01．32No．91669-1677ISSN1000．6893CN11—1929／Vhttp：／／hkxb．buaa．edu．cnhkxb@buaa．edu．CR文章编号：1000—6893(2011)09—1669-09基于图禁忌的并行测试任务调度算法路辉*，陈晓，刘欣，邓小乐北京航空航天大学电子信息与工程学院，北京100191摘要：现有算法处理强约束关系的并行测试任务调度问题具有运算时间长、寻优概率低、收敛性差等缺陷。针对这些问题提出了一种基于图禁忌的调度算法。该算法

2、从测试任务间的约束关系人手，利用图论建立测试任务间的关系图，并结合禁忌算法实现并行测试任务的多目标优化调度。算法中将强约束关系的测试任务调度问题与无约束关系的资源配置问题进行分离，提高了算法的寻优速度。通过仿真实例证明了算法的有效性。与现有并行测试任务调度算法相比，运算时间减少96％、寻优率提高了36．5％。并且具有更好的收敛性。关键词：图论；禁忌搜索；并行测试；任务调度；强约束关系中图分类号：V243；TP202文献标识码：A机载设备、武器装备日益增长的自动测试需求已成为装备维修领域面临的严峻挑战，自动测试系统(AutomaticTestSystem，ATS)已成为现

3、代装备维修的必要手段【1]。并行测试技术是下一代ATS主要特征及关键技术之一【21]。ATS在采用并行测试技术的同时，需要考虑多任务同时并行调度引起的资源冲突、系统死锁以及任务调度最优排列等问题，因此并行任务调度是一个复杂、难以优化的NP(Non-deterministicPolynomial)难题【5J。目前，国内外主要有3类解决并行测试任务调度问题的方法。第1类是基于法则和枚举的方法[6。7]，此类方法在基于一些法则的条件下利用穷举的思想获得满足某种性能指标的调度序列。在测试规模大、约束关系繁多的情况下，该类方法的计算耗时将难以接受。第2类是纯粹采用智能搜索算法的方

4、法¨曲]，此类方法可以获得满足某种性能指标的最优任务调度序列，但缺乏对资源冲突、系统死锁等问题的形式化分析Ll引。第3类方法先采用Petri网建立任务调度模型，再根据模型采用智能搜索算法获得调度优化解L5J引，这类方法容易出现伪解，同时搜索过程繁琐、费时[1⋯，此外这类方法需要建立复杂的Petri网模型，大大增加ATS的开发成本并延长了开发周期【11。12]。3类方法在处理测试任务之间的时序约束、资源冲突等限制条件时，可以将其处理策略分为两种：一种是将不满足限制条件的调度结果作相应的调整，如文献[63的TaskScheduler-T算法，其并行测试调度序列以矩阵的形式表

5、示，该策略在调整过程中会引起其他测试任务时序的调整，降低调度序列的适应性，该弊端是由调度结果的表示形式决定的；另一种是在适应度函数中引入惩罚函数使不符合约束条件的解以非常低的概率进入下一轮迭代中，如文献[83和文献[9]。在限制条件繁多以至于有效解只占整个搜索空间的百万分之一甚至十亿分之一的情况下，第2种策略容易陷入局部最优解甚至不能够找到解，同时算收稿日期：2010．11．23；退修日期：2010·12-27；录用日期：2011-03—01；网络出版时间：2011—03—2411：52网络出版地址：www．cnki．net／kcms／detail／11．1929．V．

6、20110324．1152．005．htmIDOI：CNKI：11-1929／V．20110324．1152．005基金项目：“十一五”国防预研项目(B0520060455)*通讯作者．Tel．：010-82316487E-mail：mluhui@163．tom摹l崩格武I路辉．喙晓．棚欣．等．基子匿禁忌的并行溺试任务调度算法!JI．航空学摄·2011·32(9)：1669·1677，LuHui．ChenXiao。Liux{n．eta1．Agraphtabualgorithmforparalleltesttaskscheduling[JJ．ActaAeronautica

7、etAstronauticaSinica．2011．32‘9)：1669．1677，航空学报SeD．252011V01．32No．9法在惩罚函数上的运算比重较大，所以采用该策略的调度算法的运算效率不高。现有算法处理强约束关系的任务调度问题具有运算时间长、寻优概率低、收敛性差等缺陷，本文从并行测试任务的时序约束关系及测试任务的资源冲突入手，运用图论并结合禁忌搜索算法在组合优化问题中的优势，提出了一种用于解决强约束关系的并行测试任务调度算法——图禁忌算法(GraphTabuAlgorithm)。通过实例仿真分析与比较，证明了该算法的可行性与有