一种新的并行测试任务调度算法  

A Novel Algorithm for Parallel Test Task Scheduling

作　　者：付新华[1] 肖明清[2] 刘万俊[2] 周越文[2] 

机构地区：[1]桂林空军学院航空兵参谋系,广西桂林541003 [2]空军工程大学工程学院,陕西西安710038

出　　处：《航空学报》2009年第12期2363-2370,共8页Acta Aeronautica et Astronautica Sinica

基　　金：总装"十一五"国防预研项目(51317030103)

摘　　要：并行测试的任务优化调度是并行测试技术的核心问题。为了解决现有调度方法耗时、实际应用范围有限以及缺少对资源冲突和系统死锁的形式化分析等问题,采用赋时有色Petri网(TCPN)建立并行测试任务调度的TCPN模型,基于TCPN模型的可达标识图利用改进蚁群算法求解最优任务调度序列。算法搜索过程中,采用多目标优化,目标函数综合了测试时间、仪器成本和负载平衡度,使得算法更符合工程应用。采用动态标注方法在搜索过程中加大可行解间的信息素差别,避免算法早熟。仿真实例证明该算法是有效的。Optimized parallel test task scheduling is key to parallel test technology.To solve the following problems of common task scheduling algorithms： taking up much time,limited practical application area,lack of formalization analysis on resource conflict and system deadlock,timed coloured Petri-net（TCPN） is used to build the TCPN model of parallel test task scheduling.Base on the reachable marking graph of TCPN model,a novel ant colony algorithm is proposed to obtain the optimized task scheduling sequence. Multi-target optimization is used during the search process to satisfy engineering requirements, and the target function integrates total test time, instrument price, and load balance. An approach of dynamic labeling to increase the pheromone difference between feasible solutions is adopted to avoid earliness of algorithm. A simulation example is given. The practical application shows that this algorithm is valid.

关 键 词：并行测试 建模任务调度 多目标优化 PETRI网 蚁群算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TN407[自动化与计算机技术—计算机科学与技术]