胡涛, 马晨辉, 申立群, 梁洁

(1.哈尔滨工业大学 仪器科学与工程学院， 黑龙江 哈尔滨 150001; 2.北京宇航系统工程研究所， 北京 100076)

0 引言

复杂系统测试的时间长、效率低、成本高，提高测试效率、减小仪器闲置已经成为测试系统亟待解决的问题。并行测试技术[1-3]通过提高单位时间内被测对象的数量及在每一个被测对象内部并行进行参数测试，来提高测试仪器的利用率和测试效率，因此并行任务调度算法的设计与实现是关键。

蚁群算法是一种仿生智能算法，应用很广，对于任务调度问题具有很好的适用性。熊婧[4]为蚁群算法应用于调度问题提供了思路，适合于车间作业调度的实际问题；付新华等[5]将蚁群算法与并行测试任务调度相结合，然而算法全局搜索能力仍有待进一步完善；路辉等[6]提出了任务调度方案的详细问题描述，但多目标优化降低了测试效率的要求。上述方法未考虑测试时间最短的任务调度矩阵存在多解的问题，算法体系不完整。

本文针对测试系统测试效率低、资源浪费问题，提出基于蚁群算法的测试任务并行调度优化方法，建立了算法的完整体系。明确了测试任务，分析了可优化空间，应用蚁群算法设计了启发函数和状态转移概率；通过与随机穷举法对比验证了算法的有效性；针对多解问题，提出了资源均衡度的评价标准。仿真结果表明，本文方法是有效的，在实现最短测试时间的同时获得了资源均衡度最高的任务调度序列。

1 并行测试任务调度优化

由于复杂系统测试项目众多，而且严格的约束关系存在于各测试任务之间，有效提取可以并行执行的任务是调度优化的前提，因此需要详细分析并行测试任务及相关约束条件。并行测试任务调度优化的研究框架如图1所示。

图1 测试系统优化总流程Fig.1 Optimization process of test system

由图1可知，测试系统优化流程如下：1)明确测试系统流程及资源任务关系，确定可优化空间；2)将问题进行抽象描述，结合实际蚁群算法、设计算法流程，得到测试时间最短的任务序列；3)对任务序列多解的问题，提出资源均衡度作为评价标准，从而求解出较优的资源、任务调度序列。

2 基于蚁群算法的测试任务调度

复杂系统的测试任务一般可分为单元测试、分系统测试和总检查3部分，各部分之间为串行执行关系，其中单元测试和分系统测试中存在一个任务可由多个资源完成的多方案情况，有可优化的空间。本节将蚁群算法基本原理与并行测试任务调度具体问题结合起来，设计并行测试的蚁群算法启发函数、状态转移概率、信息素更新公式等。

2.1 并行测试任务问题描述

某系统具有x件测试仪器(测试仪器即代表并行任务调度中的资源)、y项待测任务。其中任务占用资源情况为：1)一个任务对应多个资源；2)一个资源对应多种任务；3)一个任务同时需要几个资源。每种方案中的仪器组合具有明确的测试时间。本文研究的最终目标是在任务约束条件下，获取时间最短的测试任务调度序列。

由于测试时序上有严格约束，某些任务具有明确和固定的优先级关系[7]。任务约束[8]主要包括控制相关、资源相关和数据相关3种类型：1)控制相关，即测试任务t1、t2具有优先级关系，例如在t1执行完成后才可执行t2；2)资源相关，即任务t1、t2所需的资源集r1、r2满足r1∩r2≠∅；3)数据相关，即任务t1的测试结果是任务t2的输入，这种约束在本文中并不涉及。根据以上约束关系，对测试任务进行正确合理的优先级设定，优先级高的任务需要先执行完毕才能执行低优先级的任务。

2.2 并行测试的蚁群算法

将蚁群算法基本原理[9-10]与并行测试任务调度具体问题相结合，得到测试时间最短的并行任务调度矩阵TP，该调度矩阵中的行表示资源、列表示资源对任务的测试顺序，内部元素表示任务序号：

(1)

式中：tri j中的ri为资源序号(i=1,2,…,x)；j为任务序号(j=1,2,…,y)。若任务tl(l∈{1,2,…,y})在第j步被ri测试，则tri j=tl，否则tri j=0表示空任务，此时资源空闲，可以被其他任务选择。

结合并行测试任务调度问题特点，蚁群算法设计如下：

1) 启发函数ηij[11-12]。启发函数ηij表示任务tj被资源ri选择的期望程度，

(2)

启发函数数值表示先验客观因素的影响情况，依据贪心规则进行计算，即基于当前一步，测试时间越短的路径其启发函数数值越大、转移概率越高，但是有时会发生早熟现象[13-14]。因此，任务选择还需要利用信息素的影响，以免陷入局部最优解。

(3)

式中：α表示信息素的重要程度[15]，其值越大，搜索的随机性越弱，蚂蚁越容易汇聚到一个可行解；τij表示资源选择任务的信息素浓度；β=1-α反映了启发式信息的重要程度，β越大，先验知识越重要；tabuk(i)表示蚂蚁k在资源ri的禁忌表，即已执行过的任务；s表示未执行的任务号。任务的选择概率即转移概率主要受到信息素和启发函数的影响。为使算法具有良好的搜索能力，需要合理设置α、β的值。

(4)

3) 全局信息素更新规则τij. 信息素的更新在一次完整迭代后，根据所有蚂蚁为任一仪器的任务选择进行计算：

(5)

(6)

利用(2)式～(6)式，通过蚁群算法得到最短测试时间的任务调度矩阵。但其中存在多种满足测试需求的可执行测试方案，方案多解的原因如下：某些测试任务的测试顺序发生变化，测试顺序不影响测试时间；测试资源在不同时间被使用；测试资源的可测任务集发生变化。虽然总测试时间相同，但还需要依据实际情况从其他方面综合考虑具体配置方案。

下面引用云计算领域的负载均衡度概念[16]，提出并行测试任务调度中的资源均衡度定义，来解决任务矩阵的多解问题。

具体解决方式为：在最短测试时间的测试方案中选取资源均衡度最大的资源、任务调度方案。用资源均衡度σ表示同种资源测试任务时间的平均程度，σ越大，仪器的工作时间越均衡，对每个仪器的损耗越小。σ的定义如下：

(7)

(8)

式中：s表示第c种资源的数量；Trv、Tru表示对应资源的任务时间。

2.3 算法流程设计

测试需求与蚁群算法相结合，对并行任务优化调度问题建立蚁群算法流程如图2所示，其中迭代序数和蚂蚁序数分别用Nc和k表示，可并行任务的提取通过遍历所有仪器实现。

图2 蚁群算法并行调度流程Fig.2 Parallel scheduling process of ant colony algorithm

3 实例仿真分析

在仿真实例中选取测试任务50项、资源节点10个，来源为公开资料的典型测试流程，资源情况[17]如表1所示。

表1 测试资源情况

测试流程为：首先进行单元测试，然后进行分系统测试，最后进行总检查。具体约束情况如图3所示。

图3 测试约束限定Fig.3 Testing constraints

由图3可见，若任务ti优先于任务tj，则用ti≻tj表示，即ti的测试要先于tj的测试。单元测试任务约束关系为：t1≻(t2,t3,…,t19)，t8≻t9,t10≻t11，t12≻t13≻t14.

同理，分系统测试任务约束关系为(t20,t21,…,t26)≻(t27,t28,…,t46)，t37≻t38，(t27,t28,…,t31)≻(t35,t36,…,t46)，(t43,t44,t45)≻t46，(t32,t33,t34)≻(t35,t36,t37,t38)，t35≻t36，t39≻t40≻t41；总检查测试任务约束关系为t47≻t48≻t49≻t50.

测试任务、测试方案、仪器资源以及时间的对应关系[17]如表2所示，其中tj表示测试任务，ri表示资源(在资源项中，以逗号相隔的ri表示方案中任意一个资源都不能缺少，以顿号相隔的ri表示一个方案中只需要任意一个资源)，方案号为1～6，表示一个任务最多有6个方案，时间为对应的任务完成时间。

表2 测试任务、方案、资源及时间

使用MATLAB 2016对算法进行编程实现，运行平台为：Intel Core i5 CPU，2.13 GHz，内存4.0 GB. 算法参数设置依据多次仿真结果选取，具体参数如表3所示。算法的最大迭代次数为100次，达到迭代次数后算法终止。

表3 仿真测试参数设置

3.1 仿真结果及分析

仿真实验结果如图4所示。图4中3条曲线分别为每次迭代的多种测试方案测试时间最大值、平均测试时间，以及测试时间最小值即每次迭代的最优解。

图4 蚁群算法迭代曲线Fig.4 Iterative curves of ant colony algorithm

由图4可见，最短时间收敛到74 min，大约经过了12次迭代。虽然时间最大值在迭代过程中仍然存在波动，这是由于蚂蚁的随机性引起，但其峰值具有减小趋势，平均测试时间同时趋向于最小值而最小值已保持稳定，因此可以认为测试任务调度的最优解已成功找到。

在最短测试时间为74 min的多种任务矩阵中，资源均衡度最大值maxσ为0.885 min-2的最优任务调度矩阵对应的Gantt图如图5所示，其中数字为任务序号。

图5 并行任务调度方案Fig.5 Parallel task scheduling scheme

3.2 与随机穷举法对比

在同种约束限定下，将随机穷举法与本文算法进行对比，验证本文算法的有效性。以本文优化出的流程为参考，结合型号的实际情况如人员操作、子系统协调等无法量化为约束的情况，设计人员可以设计出比传统流程更优秀的结果。

在满足约束条件下，用随机方式产生并行任务序列，4 000种随机序列的用时情况如图6所示。

图6 4 000次随机序列用时Fig.6 Time consumption of 4 000 random sequences

由图6可见，在满足约束条件下，最大测试时间为94 min，大多数测试时间集中于84 min左右，最短时间为76 min. 由此可见，任务调度的最优解并没有被随机穷举方法找到，虽然通过增加搜索次数可能找到最优解，但对于复杂测试系统，随机穷举法并不是一个很好的选择，其搜索效率相对于蚁群算法低很多。

相比随机穷举法，蚁群算法显然具有较好的效率，具体的比较情况如表3所示。

表3 仿真效果比较

对比蚁群算法与随机穷举法可知，用蚁群算法进行测试任务并行优化调度在寻优速度上表现更好，具有较大的优势。

3.3 与半串行测试方式对比

目前，本文的测试实例在实际工作中多以半串行方式进行测试，即大测试项目间串行，测试项目内分解任务并行，在一定程度上使得测试时间减小，但仍然存在较大的优化空间，半串行的总测试时间为130 min. 改变大项目之间的任务约束，可以更充分地进行并行分解，其测试效率的提升率由(9)式可得：

(9)

式中：Ts为半串行测试总时间；Tp为并行测试总时间。根据(9)式，经蚁群算法优化后，并行测试较半串行测试，测试效率提升了43.07%.

4 结论

本文分析了测试任务调度优化问题，将蚁群算法应用于并行测试的任务调度优化，并针对最短时间任务调度序列多解的问题，用资源均衡度的概念寻找资源均衡度最好的最短时间任务调度序列。仿真结果表明，与随机穷举法对比，本文算法能有效地找到最短时间任务调度序列，大大改善了测试系统的测试效率，与现有的半串行测试方法相比，节约了测试时间，提升了测试效率；提出了资源均衡度的概念作为评价标准，解决了最短时间任务调度序列多解的问题。如果在特定情况下资源均衡度比较重要，则可以将接近于最短时间的测试方案也包括进来，以选取资源均衡度较好的测试序列。