航空学报 > 2009, Vol. 30 Issue (12): 2363-2370

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

付新滑1, 肖明清2, 刘万俊2, 周越文2

  

  1. 1.桂林空军学院 航空兵参谋系 2.空军工程大学 工程学院
  • 收稿日期:2008-10-14 修回日期:2009-01-21 出版日期:2009-12-25 发布日期:2009-12-25
  • 通讯作者: 付新华

A Novel Algorithm for Parallel Test Task Scheduling

Fu Xinhua1, Xiao Mingqing2, Liu Wanjun2, Zhou Yuewen2

  

  1. 1. Aviation Staff Department, Guilin Air Force Academy 2. Engineering College, Air Force Engineering University
  • Received:2008-10-14 Revised:2009-01-21 Online:2009-12-25 Published:2009-12-25
  • Contact: Fu Xinhua

摘要: 并行测试的任务优化调度是并行测试技术的核心问题。为了解决现有调度方法耗时、实际应用范围有限以及缺少对资源冲突和系统死锁的形式化分析等问题,采用赋时有色Petri网(TCPN)建立并行测试任务调度的TCPN模型,基于TCPN模型的可达标识图利用改进蚁群算法求解最优任务调度序列。算法搜索过程中,采用多目标优化,目标函数综合了测试时间、仪器成本和负载平衡度,使得算法更符合工程应用。采用动态标注方法在搜索过程中加大可行解间的信息素差别,避免算法早熟。仿真实例证明该算法是有效的。

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

Abstract: 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.

Key words: parallel test, modeling task scheduling, multi-target optimization, Petri nets, ant colony algorithm

中图分类号: