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

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

A Novel Algorithm for Parallel Test Task Scheduling

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 optimi-zation 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.