并行测试是指测试系统在同一时刻能够开展多项测试任务，也可以是在同一时间内完成对多个被测设备的测试，其主要是通过增加单位时间内被测任务的数量，提高测试效率[1]。并行测试可有效解决大规模生产测试过程中存在的测试时间长、资源利用率低、设备成本高问题。
文献[2-5]均提出了较好的并行测试调度方法，有效提高了测试并行度，但无法适应测试任务较多、测试资源有限情况；文献[6-9]使用遗传算法对并行测试任务进行求解，取得了较好的效果，但由于遗传算法存在陷入早熟情况而可能无法得到最优解；文献[10-11]中均从非时间最短角度求解任务调度序列，存在一定优化空间。
本文通过采用蚁群算法，以求得最短测试时间为目标，基于有限测试资源，获得了最短测试时间的任务调度序列，有效提高了测试效率。
1 任务调度模型
任务调度的目标是实现完成各个任务时间最短，影响目标实现的因素主要包括：资源、任务、过程及三者之间的约束关系。
资源是完成任务的条件，任务是占用资源的时间，过程是完成任务的环节，资源数量、过程环节制约着任务完成。
现将任务调度过程各因素用数学模型描述为：
测试资源集：R={r1，r2，r3，…，rn}。
测试任务集：T={t1，t2，t3，…，tm}。
资源任务时间矩阵：RTUn×m。该矩阵行表示测试资源，列表示测试任务，各列表示该测试资源可以测试的任务。对于任一测试任务tj，需占用测试资源ri在kij时间内完成测试，则有RTUn×m(i， j)=kij，否则RTUn×m(i， j)=0。
测试任务资源约束集Rtj：由矩阵RTUn×m中的列向量t:j中所有大于0的分量所对应的资源所组成的集合。该集合反映了完成测试任务t:j的测试资源约束关系。
先决任务集Cm×m：表示进行测试任务之前必须完成的测试任务集合，若完成测试任务ti的先决条件是tj，则有Cm×m(i， j)=1，否则Cm×m(i， j)=0。
为满足并行测试需求，结合实际特点进行抽象后，任务模型具备以下3个条件：
1) 任一被测设备占用任一测试资源的时间固定且等于该被测设备的测试时间和测试该被测设备状态准备时间；
2) 在任意时刻，任何一测试资源只能供一个被测设备/测试项目使用；
3) 不考虑测试过程中出现问题情况和任一测试设备撤收时间。
任务调度模型
表示完成任务所需时间，是资源任务时间矩阵中各列最长时间之和。
并行测试任务调度序列TP：该序列为n×y维矩阵，其中n表示测试资源，y表示在必须进行串行测试与分配其中并行测试项目之和，其中的元素为满足测试任务约束关系且测试资源不冲突的测试任务。
2 算法设计与实现
2.1 目标函数的确定
基于有限资源并行测试任务调度的目标是得到测试时间最短的并行测试任务序列，即在有限资源和达到测试目标的条件下，使得总测试时间最短。因此，需通过设计算法求得必须进行串行测试最短时间，并以该测试时间为基础得到并行测试任务调度方案，因此算法的目标函数为：
(1)
式中： Time表示并行测试的最短测试时间；m表示需要进行测试的任务数； j表示某一测试任务；
表示考虑前提条件后测试任务j的测试时间，为各测试任务测试时间之和。此最短时间即为必须进行串行测试任务的测试时间之和，且该串行测试任务序列必须是建立在完成所有测试任务的基础之上。
2.2 算法设计与分析
算法设计的思路是根据测试任务先后顺序和测试资源约束条件的需求，求得最短串行测试时间，然后将可并行测试任务分配至串行测试区间内，得到并行测试任务调度序列。
本文采用蚁群算法[]求取并行测试任务调度序列，蚁群算法是一种模拟蚂蚁群体觅食行为的仿生启发式优化算法，采用正反馈并行自催化机制，当蚂蚁觅食行进到一个从未经过的路口时，便会随机选择其中一条路径前行并释放信息素，信息素释放量的大小和路径长度成反比。随后行进到这个路口的蚂蚁，便会选择信息素较大路径，这样便形成了正反馈机制。信息量在最优路径上会不断积累，越来越大，非最优路径上的信息量随着时间越长，该路径上存有的信息素将会逐渐减少，最终通过整个蚁群的运动，便会寻找出最优路径，蚁群算法基于如下假设：
1) 蚂蚁之间通过信息素进行通信。每只蚂蚁仅根据其周围的局部环境做出反应，也只对其周围的局部环境产生影响；
2) 蚂蚁由其内部模式决定对环境的反应；
3) 在个体水平上，每只蚂蚁仅根据环境独立做出选择，在群体水平上，每只蚂蚁选择路径的行为是随机的，但整个蚁群可通过自组织过程形成高度有序的群体行为。
因此，本文主要思路是用蚂蚁遍历所有测试任务，在蚂蚁移动的过程中，随着测试任务之间信息素的不断变化，最优解始终朝着测试总时间最短的方向变化。每只蚂蚁到达终点之后，在测试资源的约束和测试任务之间的制约关系条件下，计算出该只蚂蚁的测试总时间，确定主要的串行测试任务序列。通过初始设定的蚂蚁数量和迭代次数，根据之前确定的启发函数，状态转移概率和信息素更新规则，反复计算，最终得出测试总时间最短的串行测试任务序列，并在此基础上将可并行测试任务安排在最短测试总时间的时间区间内，即为并行测试任务调度的最优解。
1) 启发函数。
启发函数ηcj即局部搜索函数，反映了蚂蚁从当前测试任务结束后选择第c步执行的测试任务tj的期望程度[12]。现取启发函数ηcj为：
(2)
式中：Q表示期望程度的强度值，由初始状态时人为设定；kij表示用测试资源ri完成测试任务tj的测试时间；tj属于测试任务集T。
2) 状态转移概率。
状态转移概率是蚂蚁寻找下一测试任务的一种抽象概念，即为蚂蚁选择下一测试任务的概率。在这里，用
表示在t时刻，蚂蚁l完成当前测试任务i，选择下一测试任务j的概率[12]。即：
(3)
式中：optionl表示蚂蚁l下一步的可选测试任务集optionl={s|s∈{T-abul}∧Ps∈abul}，abul为蚂蚁l的禁忌表，用来记录蚂蚁l已经完成的测试任务，随着蚂蚁的搜索过程而动态调整，直到遍历所有测试任务，Ps为可选测试任务s的先决任务集，在进行下一步测试任务的选择之前，首先要明确可选测试任务的先决任务已经完成测试，即在蚂蚁l的禁忌表中；α为信息启发式因子，表示的是蚂蚁运动轨迹的相对重要性，反映了蚂蚁在测试任务选择的过程中所积累的信息素在蚂蚁搜索时所起的作用，其值越大，则表明该蚂蚁越倾向于选择其他蚂蚁所选择过的测试任务，蚂蚁之间的相互协作性越强；β为期望启发式因子，反映了蚂蚁在测试任务选择的过程中，启发函数在蚂蚁对测试任务选择时的受重视程度，其值越大，则该状态转移概率越接近于贪心规则0。
3) 信息素更新规则。
(4)
式(4)中：
表示第l只蚂蚁由测试任务i选择测试任务j时留下的信息量；τ0表示初始时刻各测试任务之间的信息量；F表示由当前蚂蚁l选择的测试任务路径的测试时间；SP为当前迭代循环中所有蚂蚁选择测试任务路径最短测试时间；
表示所有测试时间的平均值；l∈i→j表示第l只蚂蚁由任务i选择任务j。通过动态标记的方法可在搜索过程中加大可行解间的信息素的差别，避免算法早熟[13]。
由此，可以将信息素更新的策略表示为：
(5)
τij(t+n)=(1-ρ)τij(t)+Δτij
(6)
式(6)中：τij(t+n)表示在所有蚂蚁遍历所有测试任务n之后，由测试任务i转移到测试任务j上信息素的变化情况； ρ表示信息素挥发系数，(1-ρ)则表示信息素残留因子，为了防止信息的无限积累， ρ的取值范围为ρ⊂(0，1)0；Δτij表示本次循环中由测试任务i转移到测试任务j上信息素的增量。
4) 算法流程。
根据以上规则，基于蚁群算法的并行测试任务调度流程如图1所示。
图1 基于蚁群算法的并行测试任务调度流程框图
3 并行测试任务调度实例
文献[15]中使用自适应混沌免疫算法，求得任务调度序列，本文以此为例进行仿真分析，求解任务调度序列，文献[15]中测试任务为2部雷达8项测试任务，因此可等效为16项测试任务集，t1A，t2A，t3A，t4A，t5A，t6A，t7A，t8A，t1B，t2B，t3B，t4B，t5B，t6B，t7B，t8B，完成测试任务所需要的测试仪器资源集R={r1，r2，r3，r4，r5，r6，r7}。各测试任务之间的测试优先级、占用测试仪器资源和测试时间关系如表1所示。
表1 测试任务资源集
待测参数占用资源测试时间/s待测参数占用资源测试时间/st1r1,r25t5r3,r520t2r1,r312t6r1,r64t3r43t7r740t4r1,r42t8r315
根据表1和测试仪器资源集R可得：
根据上述方法及结果，对表1中的数据模型进行求解。蚁群算法的初始参数设置为：信息启发式因子α=1，期望启发式因子β=2，信息素挥发系数ρ=0.2，期望程度强度值Q=300，初始信息量τ0=1，蚂蚁数目M=6，迭代次数 K=20。
根据算法运算结果，得出该数据模型必须串行测试序列为：t5B→t5A→t2B→t2A→t8A→t8B，其余测试任务均为可并行测试任务。并行测试任务调度序列TP为：
其中，该矩阵的行代表测试资源，由下至上分别为r1，r2，r3，r4，r5，r6，r7。该实例模型的仿真测试流程如图2所示，图1中1～16代表任务集t1A～t8B，据此可得2部雷达测试流程如图3所示。
图2 并行测试流程示意图
图3 2部雷达测试流程示意图
根据蚁群算法仿真结果可以看出，在固定测试资源集R={r1，r2，r3，r4，r5，r6，r7}的约束下，完成整个测试流程的最短测试时间为94 s，比文献[15]测试时间短7 s，比完全串行测试短108 s。
4 结论
本文提出的基于有限资源并行任务调度，使用蚁群算法进行调度，在寻找最优路径过程中，只考虑测试任务的时序关系，遍历所有测试任务之后，再通过测试资源的约束关系确定并行任务调度方案和必须串行测试序列，信息素的更新仅针对该串行序列，在所有蚂蚁遍历测试任务和完成迭代次数之后，得出最优测试序列。通过实例仿真可知，使用蚁群算法对基于有限资源的并行测试任务进行调度，可以很好地求解出最短测试时间和任务调度方案，效率有了明显的提高。
[1] 肖明清，朱小平，夏锐.并行测试技术综述[J].空军工程大学学报(自然科学版)，2005，6(03)：22-25.
[2] SOTSKOV Y N，GHOLAMI O.Mixed Graph Model and Algorithms for Parallel-Machine Job-Shop Scheduling Problems[J].Internation Journal of Production Research，2015，55(06):1549-1564.
[3] 王正元，刘卫东，景慧丽，等.一种并行测试任务调度优化方法[J].兵工学报，2018，39(02):399-404.
[4] 周强，司丰炜，修言彬.Petri网结合Dijkstra算法的并行测试任务调度方法研究[J].电子测量与仪器学报，2015，29(06):920-927.
[5] 姚静波，辛朝军，蔡远文.一种基于多测试资源的并行测试任务调度算法[J].兵工自动化，2014，23(04):22-24，36.
[6] 方甲永，肖明清，谢娟.基于遗传蚁群算法的并行测试任务调度与资源配置[J].兵工学报，2009，23(04):343-349.
[7] 王伟斌，秦红磊.基于自然数编码遗传算法的并行测试技术[J].系统工程与电子技术，2010，32(06):1343-1348.
[8] 梁旭，李行善，于劲松.基于遗传算法的并行测试调度算法研究[J].电子测量与仪器学报，2009，23(02):19-24.
[9] 秦勇，梁旭.基于混合遗传算法的并行测试任务调度研究[J].国外电子测量技术，2016，35(09):72-75.
[10] 胡涛，马晨辉，申立群，等.基于蚁群算法的测试任务调度优化方法[J].兵工学报，2019，40(06):1310-1316.
[11] 丁超，唐力伟，邓士杰.基于动态优先级的测试任务抢占调度算法[J].系统工程与电子技术，2016，38(09):2080-2085.
[12] 段海滨.蚁群算法原理及其应用[M].北京:科学出版社，2005.
[13] 付新华，肖明清，夏锐.基于蚁群算法的并行测试任务调度[J].系统仿真学报，2008，20(16):4352-4356.
[14] 曾梦凡，陈思洋,张文茜，等.利用蚁群算法生成覆盖表：探索与挖掘[J].软件学报，2016，27(04):855-878.
[15] 李文海，管晗.求解并行测试任务调度问题的ACIA[J].兵器装备工程学报，2018，39(03):116-120.