一种面向航天器自动化测试的并行测试任务两阶段调度方法

摘要

本发明是一种面向航天器自动化测试的并行测试任务两阶段调度方法，属于并行测试领域。本方法包括：第一阶段，分析和确定测试任务、任务中指令和被测参数，明确任务间约束关系，建立时序约束矩阵和参数竞争关系矩阵，将任务及其间约束关系转化为无向图，把并行任务调度问题转化为图顶点的顺序最小着色问题，使用基于粒子群和模拟退火结合的方法求解，得到并行度最大的测试任务组；第二阶段，把得到的并行度最大的测试任务组在有限的测试设备上进行分配，获取最优调度方案。本发明快速建立起多个测试任务的约束关系，分析出测试任务之间的独立性，增加了测试任务的并行度，并且在满足约束的条件下实现任务在设备上的最优调度，提高测试的效率。

说明书

技术领域

本发明属于并行测试领域，涉及一种面向航天器自动化测试的先分组后再调度的两阶段 并行测试任务调度方法。

背景技术

航天器系统由若干不同功能的分系统构成，系统复杂且可靠性要求极高，是一种典型的 安全苛刻系统。为了验证航天器组成部件的各项性能和功能是否满足设计要求，大量的测试 工作贯穿整个航天器型号研制过程的各个阶段，是航天器设计制造过程中必不可少的组成部 分。随着航天器研制数量与复杂度的增加，航天器由单一类型扩展到多类型的批产化网络测 试，测试任务的激增极大缩短了测试周期，多任务并行测试的测试模式对测试理论和方法提 出了新的挑战。并行测试成为提高测试效率的重要手段。

并行测试技术属于下一代测试技术范畴，根植于并行处理技术，其表现为，在并行测试 程序的控制下对多个被测对象同时测试。相比于传统顺序测试技术，可以大幅度提高测试效 率和测试资源的利用率，减小测试成本。

在航天器自动化测试中测试任务数量多，每个任务中多个指令会频繁地对飞船参数进行 读写来判断飞船是否正常，并且这多个任务之间存在着执行的时序关系，于是需要在测试设 备上调度测试任务之前对各测试任务的独立性进行分析，使得不存在航天器参数修改竞争关 系的任务才能并行执行。其次，考虑到测试设备有限而且各任务之间的指令以及任务内的指 令之间存在执行时间间隔的约束，将可并行的任务在测试设备上进行执行时需要合理的调度， 使得在测试效率最高的情况下满足各种约束。由上述对航天器自动化测试的分析可知，任务 并行调度约束比较复杂，涉及到测试任务、测试指令、航天器被测参数和测试设备各方面的 约束，并且并行调度存在着明显的层次关系，于是考虑为航天器测试任务并行调度建立两阶 段调度模型，第一阶段计算出可以并行执行的任务，第二阶段将可并行的任务在设备上进行 最优的调度。

计算可并行测试任务的核心是将多个相互之间独立不会引起被测量冲突的测试任务分到 一个组中，一个好的分组结果会使得组内的任务尽可能的多，这样能尽可能得提高测试效率 和资源的利用率。传统的避免并行测试干扰的分组方法是由测试人员凭经验来决定各个测试 任务间的独立性，从而决定哪些测试程序是可并行的，但是在航天器自动化测试中，航天器 功能日益复杂，使得航天器的测试任务也变得复杂，完全由测试人员来确定测试程序间的独 立性已经变得不可行。因此，需要对航天器并行调度的策略进行分析，建立多任务调度模型， 由运行环境自动分析所提交的测试任务间的关系，规划出由各个测试程序组成的无干扰并行 执行序列。目前常用的并行测试任务分组的实现主要是基于算法的，利用智能优化算法，以 一个测试任务整体为粒度来求解出各并行任务组的组成，目标为使得总的测试时间最短。但 是在航天器自动化测试中，每一个任务由多条指令组成，指令之间有一些时间间隔，初始时 并未确定，于是任务的执行时间也不确定，以总测试时间最短作为调度的目标变得不可行； 而且航天器自动化测试中任务中各指令会频繁地对被测对象的参数状态进行修改，如果以一 个任务整体对参数的修改情况来判断各任务是否产生干扰，会使得相互独立的任务非常少； 此外，多个测试任务可能会有测试需求决定一些执行的前后时序关系。以上种种因素决定了 需要设计一种适用于航天器并行测试任务的分组方法。

在设计好分组算法后，如何在测试设备上对组内的任务中各条指令进行调度也是一个需 要考虑的问题。传统的任务在设备上调度的方法一般仅考虑任务对设备的竞争，只要满足任 务对设备的独占关系，通过智能优化算法找到总执行时间最短的调度方式即可。但在航天器 自动化测试中，测试设备有限、不同的任务执行可能会需要不同种类的设备，而且各任务之 间的指令(此处为有相同参数修改需求的指令)以及任务内的指令之间存在执行时间间隔的 约束，因此需要设计一种适用于航天器并行测试任务在设备上的配置方法。

发明内容

本发明提供一种面向航天器自动化测试的并行测试任务两阶段调度方法，用以快速建立 起多个测试任务的约束关系，分析出测试任务之间的独立性，增加了测试任务的并行度，并 且在满足约束的条件下实现任务在设备上的最优调度，提高测试的效率。

本发明给出的一种面向航天器自动化测试的并行测试任务两阶段调度方法，主要包括如 下步骤：

步骤1：确定测试任务、测试任务中的各条指令和被测的状态参数。

步骤2：明确测试任务的约束关系，按照时序关系建立测试任务之间的时序约束矩阵， 按照参数修改竞争关系建立测试任务之间的参数竞争关系矩阵。

步骤3：将各测试任务转化为无向图上的顶点，测试任务之间的参数修改竞争关系转化 为图上的边，若两个测试任务之间有冲突，则无向图上对应的顶点之间有连边。把并行测试 任务调度问题转化为图中顶点顺序最小着色问题。

步骤4：使用基于粒子群算法和模拟退火算法结合的方法迭代求解图中顶点顺序最小着 色问题，得出并行度最大的测试任务组。

步骤5：对步骤4得到的测试任务组，把测试任务之间有修改相同参数的指令时间间隔 约束、测试任务内各指令的执行时间最大间隔约束以及总的调度时间最短作为目标，把测试 任务在测试设备上的最优调度问题转化为多目标优化问题。

步骤6：使用NSGA-II算法求解步骤5的多目标优化问题，获取测试任务在测试设备上 的最优调度。

所述的步骤1中，读取周期内的测试任务文件，按行提取出测试任务中的测试指令，分析 测试指令获取航天器被测的状态参数，被测的状态参数为指令修改的航天器参数，根据指令 的类型估算出指令的执行时间。用数学定义的方法将每个测试任务中的指令条数、各指令的 执行时间、各指令之间的最大执行时间间隔、各指令修改的航天器状态参数表示如下：设P_α表示航天器被测的第α个状态参数，P＝{P₁,P₂,...,P_m}为航天器被测状态参数集合，m是状态 参数个数，α＝1,2,…,m；设T_i表示一个周期内第i个测试任务，T＝{T₁,T₂,...,T_n}表示一个周期 内的测试任务集合，n为任务个数，i＝1,2,…,n；设表示第i个任务的第k条指令，表示指令的种类，指令的种类决定指令的执行时间；为指令将修改的航 天器状态参数，其中

任务T_i表示为$\{{\mathrm{ins}}_i^1,{\mathrm{mxspan}}_i^1,{\mathrm{ins}}_i^2,{\mathrm{mxspan}}_i^2,...,{\mathrm{mxspan}}_i^{\mathrm{ic}\left(i\right)-1},{\mathrm{ins}}_i^{\mathrm{ic}\left(i\right)}\};$的形式，其中是 任务T_i中第k条指令与第k+1条指令之间的最大时间间隔，ic(i)是任务T_i中的指令条数。用偏序 符号来表示任务间的时序约束关系，如任务T_i必须先于任务T_j执行，记做T_i＞T_j。

所述的步骤2先分析测试任务之间的时序关系，按照时序关系建立测试任务之间的时序约 束矩阵A^n×n，如果T_i＞T_j，则A^n×n[i][j]＝1，否则A^n×n[i][j]＝0；根据航天器自动化测试的特 点，建立测试任务对于参数修改的时间间隔不等式。读取各测试任务中各指令对于航天器参 数状态改变情况，如两个测试任务中有指令对相同的参数进行修改，将任务中各指令信息代 入时间间隔不等式中，如满足不等式，那么两个任务不冲突。按照任务之间的参数竞争关系 建立任务参数冲突矩阵B^n×n，如果T_i和T_j由时间间隔不等式计算出有冲突，则B^n×n[i][j]＝1， 否则B^n×n[i][j]＝0。设测试任务T_i的指令与测试任务T_j的指令对相同的参数进行修改， 根据下面时间间隔不等式判断T_i和T_j是否冲突：

$\left(\begin{array}{c}|(\underset{p=1}{\overset{t-1}{\Sigma }}\mathrm{exe}\left({\mathrm{ins}}_j^p\right)-\underset{p=1}{\overset{k-1}{\Sigma }}\mathrm{exe}\left({\mathrm{ins}}_i^p\right))+\mathrm{begin}\left(T_i\right)+[\max \left(\mathrm{exe}\left(T_i\right)\right)-(\max \left(\mathrm{exe}\left(T_j\right)\right)]/2+\\ (\underset{p=1}{\overset{k-1}{\Sigma }}{\mathrm{mxspan}}_j^p-\underset{p=1}{\overset{t-1}{\Sigma }}{\mathrm{mxspan}}_i^p)/2|>\max (\mathrm{exe}\left({\mathrm{ins}}_i^k\right),\mathrm{exe}\left({\mathrm{ins}}_j^t\right))\end{array}\right)$

若满足不等式则T_i和T_j不冲突，否则，T_i和T_j有冲突；exe(x)表示任务x或者指令x的 执行时长；begin(x)表示任务x或者指令x的开始执行时间；max(exe(T_i))是任务T_i中各条指 令之间的间隔时间都为最大值时任务T_i的总的执行时间；是指令与指令的执行时长的较大值。

步骤3将各测试任务转化为无向图G中的顶点，读取参数竞争关系矩阵B^n×n，如两个任务 有冲突，矩阵中元素B^n×n[i][j]＝1，那么无向图G中的测试任务T_i和T_j对应的顶点之间有连边。

综上所述，本发明的并行测试任务两阶段调度方法的优点和积极效果在于：

(1)易用性，本发明第一阶段航天器自动化测试系统中的测试任务、测试指令和被测 航天器状态参数以及任务之间的约束关系使用统一的数学方法进行表述，简单易用；第二阶 段考虑到约束复杂计算量太大，将多约束问题转化为多目标优化问题，方便进行处理。本发 明方法接口调用易用性强，方便与现有其它模块集成；

(2)通用性，本发明提出的一种面向航天器自动化测试的并行测试任务两阶段调度方 法，在实际应用中针对特定领域工程，通过对方法接口进行适当修改即可满足本领域需求；

(3)实用性，本发明通过以上六个步骤实现航天器自动化测试并行任务合理调度方 法，可以满足工程实际需求，具有一定的实用性；本发明可快速建立起多个测试任务的约束 关系，分析出测试任务之间的独立性，增加了测试任务的并行度，并且在满足约束的条件下 实现任务在设备上的最优调度，提高测试的效率；

(4)高效性，本发明第一阶段考虑到单种智能优化算法存在各种缺陷，组合了两种智 能优化算法，能在有效提高全局搜索能力的基础上加快算法收敛速度，以提高测试的效率。

附图说明

图1为本发明一种面向航天器自动化测试的并行测试任务两阶段调度方法的流程图；

图2为本发明一种面向航天器自动化测试的并行测试任务两阶段调度方法的软件功能结 构图；

图3为本发明混合粒子群模拟退火初始化种群的方法伪代码示意图；

图4为本发明使用粒子群算法迭代过程中粒子位置越界的两种处理策略示意图；

图5为本发明使用改进的NSGA-II算法中使用交叉算子的一个示例图。

具体实施方法

下文中将参考附图并结合实施来详细说明本发明。

本发明提供的面向航天器自动化测试的并行测试任务两阶段调度方法，在第一阶段通过 抽取出各个任务的航天器参数修改需求和任务的时序关系，建立适用于航天器自动化测试的 任务约束关系，使用粒子群和模拟退火结合的思想，生成相互之间无冲突的可并行测试的任 务组；在第二阶段把第一阶段分组得到的测试任务在有限的测试设备上进行分配，将多约束 优化问题转化为多目标优化问题，使用改进的多目标优化NSGA-II算法(带有精英策略的非 支配排序遗传算法)生成满足各种时间间隔约束并且总执行时间最短的调度方案。

本发明提供的一种面向航天器自动化测试并行测试任务两阶段调度方法所其软件结构图 如图2所示，包含测试任务读取模块，测试任务约束生成模块，并行任务生成模块和并行任务 调度模块。

测试任务读取模块主要功能包括测试任务预处理及测试任务分析。

测试任务预处理：读取周期内的测试任务文件，按行提取出测试任务中的测试指令。指 令对航天器状态的操作分为修改和只读，一些数据操作类的指令只是从航天器获取某些状态 参数的值并进行相应的判别，这些指令不会对状态参数进行改变，不会引起状态参数的竞争， 因此只需要考虑修改类指令即可。分析任务中的指令，得到任务中各指令修改航天器参数的 情况。在航天器自动化测试中，测试指令耗时的主要原因是它涉及到的网络通讯以及一定的 测试业务逻辑过程，网络通讯时间由特定的网络环境决定，不同类型的指令由于其完成的测 试业务不同，网络通信及需要交互次数都不同，可以根据指令的类型估算出指令的执行时间。

测试任务分析：定义航天器自动化测试并行调度模型中的变量。将测试任务、任务中的 各条指令(指令的执行时间、指令之间最大间隔时间、指令修改参数情况)、任务执行的时序 关系和航天器的参数均使用模型中的变量表示。

测试任务约束生成模块主要功能包括任务时序约束矩阵生成、有相同参数修改的任务时 间间隔计算、以及任务参数竞争关系矩阵生成。

任务时序约束矩阵生成：通过读取任务之间的时序关系，建立矩阵A。

相同参数修改的任务时间间隔计算：为任务参数竞争约束关系提供依据。考虑到航天器 自动化测试中每个任务都有多条指令，一个任务修改的参数是其中指令修改参数的并集，则 不同任务修改的参数很可能有重叠。如果以一个任务整体对于参数的修改情况来作为区分任 务是否有参数冲突的依据，那么任务出现冲突的情况会很多，使得能够并行测试的任务很少 甚至不存在，所以需要设计一种适用于航天器自动化测试的冲突判断方法。对于任务T_i和T_j， 将其带入定义好的时间间隔不等式中，如果任务满足此不等式，则可以说明两个任务在一定 程度上不会引起冲突，否则，认为此两个任务会引起冲突。

任务参数竞争关系矩阵生成：读取由相同参数修改的任务时间间隔计算功能得到的任务 冲突情况，建立矩阵B。

并行任务生成模块主要功能包括任务及其约束关系到图的转化和并行任务方法调用。

任务及其约束关系到图的转化：将任务以及任务对于航天器参数修改竞争关系转化为无 向图上的顶点和边，把并行任务调度问题转化为图节点顺序最小着色问题。

并行调度方法调用主要功能是使用基于粒子群算法和模拟退火算法结合的算法思想来解 决图顶点的着色问题，目标为使得任务调度的并行度尽可能大。

并行任务调度模块主要功能包括任务在设备上调度的约束分析和并行任务调度方法调 用。

任务在设备上调度的约束分析：在调度算法使用之前对任务在设备上的调度需要满足的 各项约束进行分析，包括任务之间有修改参数竞争关系的指令执行时间间隔约束、任务内各 指令的执行时间最大间隔约束、各指令对于设备的独占约束。

并行任务调度方法调用：使用针对航天器自动化测试改进的NSGA-II算法来解决测试任 务在测试设备上的合理调度，目标是使得总的调度时间尽可能短并且满足任务在测试设备上 执行的多个约束。

一种面向航天器自动化测试并行测试任务两阶段调度方法，如图1所示，包括如下6步。

步骤1：确定和分析测试任务，明确自动化测试系统中的被测状态参数。

读取周期内的测试任务文件，按行提取出测试任务中的测试指令。分析任务中的指令， 获取测试任务中各指令修改航天器状态参数的情况，根据指令的类型估算出指令的执行时间。 用数学定义的方法将每个测试任务中的指令条数、各指令的执行时间、各指令之间的最大执 行时间间隔、各指令修改的航天器参数对象表示出来，方便下面步骤的求解。

设P_α表示航天器被测的第α个状态参数，P＝{P₁,P₂,...,P_m}为航天器被测状态参数集合， m是状态参数个数，α＝1,2,…,m；Ti表示周期内第i个测试任务，T＝{T₁,T₂,...,T_n}表示一个周 期内的测试任务集合，n为任务个数，i＝1,2,…,n；表示第i个任务T_i的第k条指令， 表示指令的种类，指令的种类决定指令的执行时间；为指令将会修改的航天器状态参数，其中任务T_i表示为$\{{\mathrm{ins}}_i^1,{\mathrm{mxspan}}_i^1,{\mathrm{ins}}_i^2,{\mathrm{mxspan}}_i^2,...,{\mathrm{mxspan}}_i^{\mathrm{ic}\left(i\right)-1},{\mathrm{ins}}_i^{\mathrm{ic}\left(i\right)}\}$的形式，其中是任务 T_i中第k条指令与第k+1条指令之间的最大时间间隔，ic(i)是任务T_i中的指令条数。用偏序 符号来表示任务间的时序约束关系，如任务T_i必须先于任务T_j执行，记做T_i＞T_j。

步骤2：使用航天器自动化测试任务参数修改的竞争关系确定方法和时序关系抽取方法， 明确任务的约束关系，建立测试任务之间的时序约束矩阵和参数竞争关系矩阵，为下一步分 析任务的独立性做准备。

步骤2先分析任务之间的时序关系，按照时序关系建立任务时序约束矩阵A^n×n；然后根 据航天器自动化测试的特点，建立任务对于参数修改的时间间隔不等式。读取各任务中各指 令对于航天器参数状态改变情况，如两个任务中有指令对相同的参数进行修改，将任务中各 指令信息代入时间间隔不等式中，如满足不等式，那么两个任务不冲突。按照任务之间的参 数竞争关系建立任务之间的参数竞争关系矩阵B^n×n。

步骤2.1：读取n个任务之间的时序关系，建立一个n×n的时序约束矩阵A^n×n，如果T_i＞T_j， 则A^n×n[i][j]＝1，否则A^n×n[i][j]＝0。

步骤2.2：生成任务之间的参数竞争关系矩阵。

假设begin(x)表示任务x或者指令x的开始执行时间，exe(x)表示任务x或者指令x的执 行时长，表示的是在实际在测试设备上调度时指令与其后一条的指令的 真正间隔时间，由定义可知对于任意两个任务T_i和T_j，如果任务中有 指令修改了相同的航天器状态参数，即下面对如 何判断任务T_i和T_j是否冲突进行阐述。考虑任务在测试设备上实际调度的情况，如果任务T_j的 指令先于任务T_i的指令被执行，则$\mathrm{begin}\left({\mathrm{ins}}_i^k\right)-\mathrm{begin}\left({\mathrm{ins}}_j^t\right)>\mathrm{exe}\left({\mathrm{ins}}_j^t\right),$相反则应该有为了更大限度地避免冲突认为两条指令的 开始执行时间必须满足式(1)。

$|\mathrm{begin}\left({\mathrm{ins}}_i^t\right)-\mathrm{begin}\left({\mathrm{ins}}_j^k\right)|>\max (\mathrm{exe}\left({\mathrm{ins}}_i^k\right),\mathrm{exe}\left({\mathrm{ins}}_j^t\right))---\left(1\right)$

由于$\mathrm{begin}\left({\mathrm{ins}}_i^k\right)=\mathrm{begin}\left(T_i\right)+\underset{p=1}{\overset{k-1}{\Sigma }}(\mathrm{exe}\left({\mathrm{ins}}_i^p\right)+\mathrm{span}\left({\mathrm{ins}}_i^p\right)),$令$\max (\mathrm{exe}\left({\mathrm{ins}}_i^k\right),\mathrm{exe}\left({\mathrm{ins}}_j^t\right))=M,$ 则式(1)可以写为式(2)的形式：

$|\mathrm{begin}\left(T_j\right)+\underset{p=1}{\overset{t-1}{\Sigma }}(\mathrm{exe}\left({\mathrm{ins}}_j^p\right)+\mathrm{span}\left({\mathrm{ins}}_j^p\right))-(\mathrm{begin}\left(T_i\right)+\underset{p=1}{\overset{k-1}{\Sigma }}(\mathrm{exe}\left({\mathrm{ins}}_i^p\right)+\mathrm{span}\left({\mathrm{ins}}_i^p\right)))|>M---\left(2\right)$

由于在并行任务序列生成阶段并不知道测试设备的情况，所以测试任务在测试设备上具 体的开始时间以及任务中各指令的间隔时间并不能明确，假设任务T_j和任务T_i执行时间间隔 为t(此处t可以为正也可为负)，则begin(T_j)-begin(T_i)＝t，带入式(2)得到：

$|(\underset{p=1}{\overset{t-1}{\Sigma }}\mathrm{exe}\left({\mathrm{ins}}_j^p\right)-\underset{p=1}{\overset{k-1}{\Sigma }}\mathrm{exe}\left({\mathrm{ins}}_t^p\right))+t+(\underset{p=1}{\overset{t-1}{\Sigma }}\mathrm{span}\left({\mathrm{ins}}_j^p\right)-\underset{p=1}{\overset{k-1}{\Sigma }}\mathrm{span}\left({\mathrm{ins}}_i^p\right))|>M---\left(3\right)$

对于式(3)中左边：

第一部分为固定的值，因为任务中各指令的执行时间是已知的；

第二部分为两个任务的开始执行时间间隔t，考虑到在任务调度过程中，t在区间 $[-\underset{p=1}{\overset{p<n\&p\ne i}{\Sigma }}\max \left(\mathrm{exe}\left(T_p\right)\right),\underset{p=1}{\overset{p<n\&p\ne j}{\Sigma }}\max \left(\mathrm{exe}\left(T_p\right)\right)]$上满足均匀分布，其中max(exe(T_p)是一个任务T_p中各条指令之间的间隔时间都为最大值时这个任务T_p的总的执行时间，则t的数学期望为 [max(exe(T_i))-(max(exe(T_j))]/2；

第三部分为任务在测试设备上实际调度时指令之间的间隔，

设$y=\underset{p=1}{\overset{t-1}{\Sigma }}\mathrm{span}\left({\mathrm{ins}}_j^p\right)-\underset{p=1}{\overset{k-1}{\Sigma }}\mathrm{span}\left({\mathrm{ins}}_i^p\right)\in [-\underset{p=1}{\overset{k-1}{\Sigma }}{\mathrm{mxspan}}_i^p,\underset{p=1}{\overset{t-1}{\Sigma }}{\mathrm{mxspan}}_j^p],$与两个任务开始的时间 间隔相同，实际调度时指令的间隔也没有特定的规律，可认为y在区间上满足均匀分布，数 学期望为$(\underset{p=1}{\overset{k-1}{\Sigma }}{\mathrm{mxspan}}_i^p,\underset{p=1}{\overset{t-1}{\Sigma }}{\mathrm{mxspan}}_j^p)/2.$

将第二、三部分的数学期望带入到式(3)中，则有：

$\left(\begin{array}{c}|(\underset{p=1}{\overset{t-1}{\Sigma }}\mathrm{exe}\left({\mathrm{ins}}_j^p\right)-\underset{p=1}{\overset{k-1}{\Sigma }}\mathrm{exe}\left({\mathrm{ins}}_i^p\right))+\mathrm{begin}\left(T_i\right)+[\max \left(\mathrm{exe}\left(T_i\right)\right)-(\max \left(\mathrm{exe}\left(T_j\right)\right)]/2+\\ (\underset{p=1}{\overset{k-1}{\Sigma }}{\mathrm{mxspan}}_j^p-\underset{p=1}{\overset{t-1}{\Sigma }}{\mathrm{mxspan}}_i^p)/2|>\max (\mathrm{exe}\left({\mathrm{ins}}_i^k\right),\mathrm{exe}\left({\mathrm{ins}}_j^t\right))\end{array}\right)---\left(4\right)$

设begin(T_i)＝0，式(4)中所有的值都为已知。如两个任务T_i和T_j中有修改相同参数的指令 与把任务中各个值带入式(4)，如果能满足不等式，则认为这两个任务T_i和T_j不会 引起冲突，否则认为这两个任务会引起冲突。

建立一个n×n的参数竞争关系矩阵B^n×n，如果T_i和T_j由式(4)计算出有冲突，则 B^n×n[i][j]＝1，否则，B^n×n[i][j]＝0。

步骤3：将各测试任务转化为无向图上的顶点，测试任务之间的参数竞争关系转化为图 上的边，把问题转化为图的染色问题。

建立一个无向图G＝(V,E)，来描述各个任务之间对于参数修改的竞争冲突关系，其中 V＝{v₁,v₂,...,v_n}表示图G的顶点集，步骤3.1用每一个顶点代表一个测试任务，测试任务T_i 对应顶点v_i；步骤3.2生成图G的边集E，E＝{e_ij|B^n×n[i][j]＝1}，通过读取矩阵B^n×n，若两 个测试任务之间有冲突关系，则G中代表任务的顶点之间有连边。

通过生成的无向图G，可把并行任务调度问题转化为图的顺序最小着色问题。图的顺序 最小着色问题要求按照一定的着色顺序对各个顶点进行着色，使得有边连接的相邻顶点之间 不能有相同的颜色，目标是求得对图进行正常顶点着色所需要的最小颜色数。

步骤4：使用基于粒子群算法和模拟退火算法结合的方法迭代求解出并行度最大的测试 任务组。步骤1～步骤4为本发明并行测试任务第一阶段。

步骤4.1：确定编码和适应度函数。

使用智能优化算法解决图顺序最小着色问题首先需要确定编码，编码即把实际问题的解 描述为一种便于算法操作的形式。将图中各顶点也就是各测试任务的着色数作为编码，着色 数为正整数。着色数的大小表示着色的先后顺序，也表示顶点对应的测试任务执行的先后顺 序，着色数越小的测试任务代表越先被着色，着色数相同的测试任务表示可以并行执行。如 当前周期中有5个任务，一个编码为(1,2,3,2,1)，代表的着色序列为{T₁,T₅}→{T₂,T₄}→{T₃}， 对应并行调度则为任务T₁和T₅并行执行，执行完毕后T₂和T₄并行执行，最后再执行任务T₃。

适应度函数用来评价智能算法中一个解的优劣，方便对解进行比较。如果相邻顶点v_i和v_j着色数相同，表示为q(i,j)＝1，用即可表示一个解中违反着色约束的次数；如时序 约束规定T_i＞T_j，但是任务T_i对应顶点v_i的着色数比T_j对应顶点v_j的着色数大，表示为 g(i,j)＝1，用可以表示解中违反时序约束的次数。问题的目标为着色数最小，假 设在一个解中使用了b种颜色来对图进行着色。

于是构造适应度函数$f_c=\mathrm{AC}\times (\underset{e_{\mathrm{ij}}\in E}{\Sigma }q(i,j)+\underset{i=1}{\overset{n}{\Sigma }}\underset{j=i+1}{\overset{n}{\Sigma }}g(i,j))+b.$对于此适应度函数，取值 越小表示此解越优。适应度函数括号内的部分为惩罚项，AC为惩罚系数，通过增大AC值可 以使得违反约束的解的适应度算出来特别大，则可以在迭代的过程中将此解剔除。

步骤4.2：确定使用的粒子群算法和模拟退火算法所需要的参数和各个变量。

在并行任务调度中，给定一个实例，可用n(n表示测试任务的个数)维空间表示搜索空 间，第i维代表第i个测试任务T_i对应顶点v_i的着色；设着色的数目为b，有b≤n，b＝n时 表示最差的情况，即所有任务串行执行，第i维的有效取值集为D_i＝{1,2,...,n-1}，事实上本 问题中每一个维度的有效取值范围相同。每个粒子有n维，对应n个顶点，即每个粒子为n 个测试任务的一个执行顺序。设第r次迭代时粒子a的位置为X_a(r)＝(x_a1(r),x_a2(r),...,x_an(r))， 速度为V_a(r)＝(v_a1(r),v_a2(r),...,v_an(r))，x_ai(r)对应第r次迭代时粒子a中第i个顶点(测试任务) 的着色(执行顺序)，v_ai(r)对应第r次迭代时粒子a中第i个顶点(测试任务)的速度。pBest 表示粒子本身迄今搜索到的最优解，称为个体极值；gBest表示整个粒子群到目前为止找到 的最优解，称为全局极值。基于粒子群算法和模拟退火算法结合的并行测试任务调度方法的 参数包括：迭代次数MI，种群规模MP，粒子群算法中的惯性权重ω，学习因子c₁和c₂，惩 罚系数AC，模拟退火算法的降火初温ε₀，降温系数μ。通过参考相关文献和实际效果，本发 明设置参数值如表1所示：

表1 参数设置

步骤4.3：产生初始种群，进化代数记为1。

种群初始化方法的伪代码如图3所示，为了尽快的找到最优解并且保证群体中粒子的质 量，采用一种改进的随机初始化方法，具体是：(a)从未着色顶点集中随机选择一个顶点， 着一个颜色，然后再对与该顶点不邻接的各个顶点着相同的颜色；(b)重复上述(a)过程， 直到所有的顶点被染色。(c)重复上述(a)和(b)MP次生成规模为MP的初始种群。

如图3所示，该方法使用的变量和方法如下：

UC是还没有被染色的顶点集合；c是一个一维数组，用来保存各个顶点的颜色；color 表示当前着色使用的颜色。方法PutToUC(UC,i)表示将顶点i放入UC集中；方法Random(UC) 从UC集中随机选择一个顶点并将其返回，方法DeleteFromUC(UC,v)表示把UC集中的顶点 v删除。使用改进的初始化方法可以在初始时保证个体的质量，能够更快地找到满意的解， 并且不影响个体的多样性。

步骤4.4：计算每个粒子的适应度值，得到局部最优位置和全局最优位置。

把种群中每个粒子带入适应度函数中计算出适应值，粒子的局部最优位置为粒子迭代过 程中适应度值最优的位置，设第r次迭代时得到第a个粒子的局部最优位置为pBest_a(r)。全 局最优位置为种群迭代过程中适应度值最优的粒子所在的位置，设第r次迭代时得到的全局 最优位置为gBest(r)。

步骤4.5：根据局部最优位置和全局最优位置更新粒子位置。

在每次迭代中，使用如下规则来更新粒子的速度和位置：

v_ai(r+1)＝ωv_ai(r)+c₁rand₁(pBest_ai(r)-x_ai(r))+c₂rand₂(gBest_i(r)-x_ai(r))

x_ai(r+1)＝x_ai(r)+v_ai(r+1)

其中，v_ai(r)表示在第r次迭代中第a个粒子在第i维的速度，x_ai(r)表示在第r次迭代中 第a个粒子在第i维的位置坐标。ω是在一个取值范围内随着迭代次数线性减小的值，ωv_ai(r) 代表的是粒子先前的速度或惯性；c₁和c₂表示学习因子，用于决定局部最优位置和全局最优 位置对于解的影响的比例；rand₁和rand₂是两个随机值；pBest_ai(r)-x_ai(r)可以看作是粒子的 “认知”行为，表示粒子本身的思考能力；而gBest_i(r)-x_ai(r)可看作是粒子的“社会”行为， 表示粒子之间的信息共享与相互合作。gBest_i(r)表示第r次迭代中全局最优位置的第i维， pBest_ai(r)为第r次迭代中第a个粒子的局部最优位置的第i维。

需要注意的是，并行任务调度问题属于离散优化问题，于是本发明中对于每次迭代计算 出的v_ai(r)的值进行四舍五入取整并且限定在[1,n-1]的范围内，如果v_ai(r)<1，则v_ai(r)＝1； 如果v_ai(r)>n-1，则v_ai(r)＝n-1。另外，如果计算出的x_ai(r)飞出了搜索空间范围，如图4的(a) 和(b)所示，可以采用吸收和反射两种策略来处理。

吸收策略：当粒子的位置超出某一边界时，粒子被吸收到相应的边界上，如x_ai(r)<1，则 x_ai'(r)＝1；如x_ai(r)>n-1，则x_ai'(r)＝n-1；x_ai'(r)为重新设置的位置。

反射策略：当粒子的位置超出某一边界时，粒子被反射到相应的边界内，如x_ai(r)<1，则 重新设置的位置x_ai'(r)＝1+(1-x_ai(r))＝2-x_ai(r)；如x_ai(r)>n-1，则重新设置的位置x_ai'(r)＝ n-1-[x_ai(r)-(n-1)]＝2(n-1)-x_ai(r)。

在实际的应用过程中，可以根据情况选择这两种策略中较优的一个。

步骤4.6：比较粒子新旧位置适应度值的变化，以一定概率接受较差的新值。

计算出粒子新位置的适应度值，得出新旧两个位置的适应度值的变化量▽f，如▽f＜0， 则新位置的适应度值小，则说明新的解是一个更优的解。

降温操作为ε_r+1＝με_r，对于概率pc＝min(1,exp(-▽f/ε_r))，如pc≥random(0,1)，则接受 新的位置，否则拒绝新的位置，保持原来位置不变。以一定的概率接受劣解能够避免陷入局 部最优，随着ε不断变小，接受劣解的概率也不断减小，最终ε趋于0，不再接受劣解，得到 全局最优解。ε₁＝με₀，ε₀为降火初温。

步骤4.7：判断是否满足终止条件？即判断进化代数是否大于50、或最优解是否连续M 代未发生变化，如果是，则执行步骤4.9，如果不是，则执行步骤4.8。本发明实施例中M取 值10。

步骤4.8：进化代数+1，进入步骤4.4开始下一次迭代。

步骤4.9：迭代结束，输出全局最优解。

步骤5：把任务之间有修改参数竞争关系的指令时间间隔约束、任务内各指令的执行时 间最大间隔约束以及总的调度时间最短作为目标，把任务在设备上的最优调度问题转化为多 目标优化问题。

设DevType_q表示第q个测试设备类型，DevType＝{DevType₁,DevType₂,...,DevType_H}为航 天器自动化测试系统中测试设备类型集合，H是测试设备类型个数；设dnum_q表示第q个测 试设备类型下的测试设备个数，DevNum＝{dnum₁,dnum₂,...,dnum_H}描述了各测试设备类型下 的测试设备个数，属于相同测试设备类型的测试设备可以看作是等同的。与第一阶段相同，T_i表示一个代表具体功能的测试任务，T＝{T₁,T₂,...,T_n}表示一个周期内的测试任务集合，n为周 期内任务个数，由第一阶段的分析可知组内的测试任务可以并行执行；每个任务执行时都需 要一种特定种类的测试设备，TaskDev_i表示第i个测试任务执行所需要的测试设备类型， TaskDev_i∈DevType。

本步骤将各测试任务修改相同参数的指令之间的时间间隔约束、测试任务内各指令的最 大执行时间间隔约束和总的调度时间最短，一起作为多目标优化问题的目标，问题转化为求 满足这些目标的在有限测试设备上的合理调度。

第二阶段问题的可以用数学方式表示如下：

目标函数F＝min(time)，其中$\mathrm{time}={\max }_{i=1}^n(\mathrm{begin}\left(T_i\right)+\mathrm{exe}\left(T_i\right));$

min表示求取最小值，max表示求取最大值；

约束条件：

1如果存在测试任务Ti的指令和测试任务Tj的指令修改了相同的航天器状态参 数，即则$|\mathrm{begin}\left({\mathrm{ins}}_i^k\right)-\mathrm{begin}\left({\mathrm{ins}}_j^t\right)|>\max (\mathrm{exe}\left({\mathrm{ins}}_i^k\right),$$\mathrm{exe}\left({\mathrm{ins}}_j^t\right));$

$2\forall k\in [1,\mathrm{ic}\left(i\right)],\mathrm{begin}\left({\mathrm{ins}}_i^{k+1}\right)-\mathrm{begin}\left({\mathrm{ins}}_i^k\right)\le {\mathrm{mxspan}}_i^k;$

$3\mu \in [0,\mathrm{time}],\left|\right\{{\mathrm{ins}}_i^k|i=\mathrm{1,2},...,n,k=1,2,...,\mathrm{ic}\left(i\right),\mathrm{gc}(\mu ,{\mathrm{ins}}_i^k)=1\}|<{\mathrm{dnum}}_{{\mathrm{TaskDev}}_i}\text{;gc}(\mu ,{\mathrm{ins}}_i^k)=1$表示指令在时刻μ时正在执行。

目标函数表示总的调度时间最短，约束1表示如果周期内的两个测试任务中有修改相同 参数的指令，则二个指令的开始执行时间必须至少间隔两条指令执行时间的最大值，约束2 表示对于周期内的每一个侧任务，每条指令与其上一条指令的执行间隔时间必须小于规定好 的最大间隔时间，约束3表示任一时刻占用一类测试设备的指令条数不大于该类测试设备的 总数，为测试任务中指令对于测试设备的独占约束。

由于约束比较复杂，本发明将约束优化问题转化为多目标优化问题，把目标函数和约束 当作并列的多个目标来进行处理。计算每个解违反约束的程度，并把该程度作为一个目标进 行优化，随着使用步骤6算法的迭代，该程度越来越小并且趋近于0，即产生了满足约束的 最优目标解。

步骤6，使用算法NSGA-II来求解出满足各项时间间隔约束的任务在设备上的最优调度。 第二阶段结束，得到目标解。

步骤6.1：确定算法NSGA-II编码和所需的参数。

把系统周期中的指令按照所属测试任务进行从小到大的编号，如测试任务T_i的第k个指 令的编号为由前面定义可知，ic(s)为任务T_s中的指令条数，并定义一个从 编号到指令互相映射的函数f。编码定义为系统中每个测试设备上执行的指令编号的矩阵 Dispatch^h×L，其中，h为所有测试设备类型下的测试设备总个数，L为此编码 代表的调度方式各测试设备上执行指令的最大条数。

对于一个编码，使用一种方法将所有测试任务中的所有指令分配到各个测试设备上，形 成可行的调度并且计算各个目标值的过程成为解码。定义一种解码规则：

1)对于矩阵Dispatch^h×L中第一列中的各指令，开始执行时间为0；

2)对于矩阵中第二列及以后的各指令，假设如k＝1，则此指令 的开始执行时间为begin(f(Dispatch[c][l-1]))+exe(f(Dispatch[c][l-1]))，即第c台设备上一条 执行指令的结束时间；如k>1，此条指令的开始执行时间为 $\max (\mathrm{begin}\left(f\left(\mathrm{Dispatch}\right[c\left]\right[l-1\left]\right)\right)+\mathrm{exe}\left(f\left(\mathrm{Dispatch}\right[c\left]\right[l-1\left]\right)\right),\mathrm{begin}\left({\mathrm{ins}}_i^{k-1}\right)+\mathrm{exe}\left({\mathrm{ins}}_i^{k-1}\right)),$即取第 c台设备上一条指令的结束时间和相同测试任务中上一条指令的结束时间中较大的值。

Dispatch[c][l]表示矩阵Dispatch^h×L的第c行第l列元素，f(Dispatch[c][l])表示第c行第 l列元素对应的指令。

使用此编码规则，默认满足同一时刻资源独占的约束。给定一个确定的解，也即设备上 指令调度矩阵，就可以得到多个测试任务中多条测试指令在测试设备上的唯一的调度。

对于NSGA-II算法，参考相关文献和实际效果，设置种群大小N为20，遗传代数R_max为100，变异概率为0.2。

步骤6.2：初始进化代数R＝1，随机生成初始种群X_R。

采用特殊的随机方法来初始化生成初始种群X₁。在初始化确定矩阵Dispatch^h×L的每一列 时使用一个当前可以选择的指令集合UE，UE中是各测试任务中当前还未执行的编号最小的 指令集合。最开始为每一个测试任务的第一条指令。矩阵生成过程如 下：

(1)设l＝1；

(2)随机选择一个UE中的指令再随机选择相应测试设备类型下的一个设备，设 所选择的是第c台设备，令即使得第c台设备上第l个执行的指令 为

(3)更新UE，把从UE中删除，将放入UE中。

(4)如Dispatch矩阵中第l列每一行都已经有元素，l＝l+1，然后转(2)继续执行； 如果UE已经为空，结束。

执行上面的矩阵生成过程N次，即可得到初始化的N个个体。本发明实施例N为20。

步骤6.3：对当前种群X_R进行快速非支配排序生成非支配集Z。

对种群中的每一个个体按照解码规则可以得到一个各测试设备上执行的每条指令的开始 时间。按照第二阶段问题的目标函数和约束，可以把种群中个体的总调度时间和对约束1、2 的违反情况三个目标(因为约束3已经通过解码方法得到了满足)的值进行计算。对于个体u₁， 如果存在个体u₂，u₂的每个目标函数F的值都优于u₁，则称个体u₂支配个体u₁。

(1)找到种群中所有不被其他个体支配的个体，将它们存入当前集合Z₁，并将这些个 体从种群中删除，可知Z₁集合中个体为种群中最优的；

(2)对于当前集合Z₁中的每个个体u2，将u2对于其他个体的支配关系解除，目前种群中 不被任何其他个体所支配的个体放入集合Z₂，并将这些个体从种群中删除；

(3)重复上面的操作生成Z_w直到种群为空。设最终将种群分为W个集合，Z＝{Z₁,Z₂,…, Z_W}，W为正整数，Z_w表示非支配集Z中的第w个集合，w＝1,2,…,W。

步骤6.4：Z中集合按照等级高低依次加入新的父代种群Y_R+1中，对于同一个集合Z_w中 的个体，比较拥挤度，拥挤度高的进入Y_R+1。

对于Z中的集合，按等级从高到底依次将Z_w(w＝1,2,…,W)放入新的父代种群Y_R+1中， w值越小Z_w等级越高，如果Y_R+1的数量还未达到规定的种群大小N，则依次加入Z_w+1,Z_w+2,…， 如果最后还需加入种群的个数小于当前的集合Z_w中的个体个数，则对集合Z_w中的个体按照 拥挤度排序，按照拥挤度从高到低依次加入种群Y_R+1中，直到种群Y_R+1个数达到N。拥挤度 表示原种群中给定点的周围个体的密度。

步骤6.5：对当前种群X_R进行交叉和变异操作，生成新的子代种群Q_R+₁。

对于前面提到的编码方式，一般的交叉变异算子不适用，于是需要设计特殊的算子，需 要保证交叉变异后解的可行性。

交叉算子：首先，对于每一个设备类型，随机选择一个测试设备，交换两个个体相同行 号的元素，也即相同测试设备上执行的指令的序列进行交换。其次，对交换元素后的个体， 将个体中与交换后的行中元素相同的元素删除。交换后可能发现其他行有重复的指令，删掉 其他行的重复指令。然后，对每个个体，生成UE集合，根据步骤6.2中生成个体的方法将指 令随机放到测试设备上。对删除元素后的个体重新计算当前UE集合，按照步骤6.2初始化构 造矩阵的方法来将指令随机放到设备上执行。最后，调整同一设备上的指令，使得同一测试 任务的指令执行顺序正确。在调用初始化构造方法生成了新的矩阵后，可能会出现一个设备 上同一测试任务后面的指令在前面指令之前执行，这个时候需要将这种顺序错位的指令交换， 一个交叉的例子如图5所示。如图5所示，对于某两个个体，交换第二行元素，交叉后，将 其他行与第二行相同的元素删除，然后针对每个个体，生成对应的UE集合，根据步骤6.2 中生成矩阵的方法，将指令随机放到测试设备上，最后，调整同一设备上的指令，使得同一 测试任务的指令执行顺序正确。

变异算子：交换一个个体同一行的两个元素，并调整同一行上的指令，使得同一测试任 务的指令执行顺序正确。对于每一个设备类型，随机选择一个测试设备，找到此行中随机的 两个位置，判断这两个位置上的指令，如果不是属于同一个测试任务，则将两个指令位置交 换。需要注意变异后也可能会出现一个测试设备上同一测试任务后面的指令在前面指令之前 执行的情况，此时需要将这种顺序错位的指令交换。

步骤6.6：将前面生成的父代种群Y_R+₁与交叉编译后生成的子代种群Q_R+₁合并形成大小 为种群大小两倍的新种群X_R+1，此步的作用是为了使得父子两代共同竞争产生下一代种群， 有利于保持父代中的优良个体进入下一代，保证某些优良的种群个体在进化过程中不会被丢 弃，从而提高了优化结果的精度。

步骤6.7：更新迭代次数，R＝R+1，判断当前R是否大于规定的最大值R_max，如果不是， 转入步骤6.3，否则，转入步骤6.8。

步骤6.8：迭代结束，输出当前种群中的最优个体。最优个体是根据步骤5的目标函数计 算得到，是测试任务在测试设备上的最优调度方案。

本发明结合航天器自动化测试的实际问题，给出了并行任务的两阶段调度方法，避免了 传统的并行测试任务调度方法的局限性，在第一阶段采用粒子群算法和模拟退火两种算法结 合的方法，避免了单一智能算法可能存在的容易陷入局部最优或者收敛速度过慢的缺点；在 第二阶段把复杂的约束求解问题转化为多目标优化问题，并且针对航天器测试的特点对 NSGA-II算法进行改进，能够有效提高航天器自动化测试任务调度方法的效率。