2. 中国电子设备系统工程公司研究所, 北京 100141
现代高科技战争对装备的快速响应提出了较高的要求。传统的串行测试方法和维护保障手段，其操作复杂且耗时较长，已经无法满足现代化综合航电系统的测试保障要求。并行测试在综合航空电子系统测试中的应用，能够大幅缩短战斗机的测试、维修和保障时间，对于部队的快速反应具有很强的现实意义[1]。并行测试技术作为下一代自动测试系统的支撑技术之一，相比传统的串行测试，可以大幅度提高综合航电系统的测试效率和测试准确性，提高测试资源的利用率。文献[2]分析了并行测试的优点，提出了并行测试的可并行性概念以及可并行度指标，提出了并行测试在提高测试资源利用率方面的优势；文献[3]依据有色Petri网理论，基于实例建立了的并行测试系统有色Petri网模型，并用可达树方法分析验证了所建立模型的有界性、活性、公平性，提出了一种新的对复杂系统的建模方法；文献[4]中提出了一种基于图染色理论的任务分组方法，将资源不相关的测试任务分为一组，最大限度地提高测试并行度。但是这种方法在测试任务较少，模型较为简单的情况下，较容易实现，随着测试任务的增多，势必对于求解任务分组带来一定的困难，而且求取测试资源的配置方案也极为不便。
本文主要利用时间Petri网进行建模，给出计算完成所有测试任务的最短测试时间的方法，再根据Petri的可达标识图分析方法，提出了最短测试时间的基础上的测试资源配置方案。
1 Petri网建模和可达标识图 1.1 时间Petri网时间Petri网(timed petri net, TPN)是一个五元组：∑=(S, T; F, M, DI), 其中(S, T; F, M)是一个原型Petri网, DI是定义在库所S上的时间函数。其中S和T是2个不相交的集合。S的元素称之为库所(place), T的元素称为变迁(transition), F是网N的流关系(flow relation)。对于x, y∈S∪T, 若(x, y)∈F, 则从x到y画1条有向边, 且有向边只存在于库所和变迁之间, 任意2个库所和2个变迁之间都没有有向边连接。而用图形来表示一个标识网时, 对s∈S, 若M(s)=k, 则表示库所s内有k个标志或标记, 也称为托肯(token)。而对于t∈T, DI(t)=a表示变迁t的发生需要a个时间单位来完成。即当一个标识M满足M[>t时, 变迁t发生以后, 需要经过a个时间单位, t的发生才结束[3]。
现用2个变迁和1个库所的连接来表示1个测试任务i, 如图 1所示。其中, 变迁ti1表示该测试任务的开始, 变迁ti2表示测试任务的结束, 库所si中有一个标识(也称作托肯)时, 表示该测试任务正在进行。对库所所赋予的时间值ai表示该测试任务从开始到结束需要经过ai个时间单位。
|
| 图 1 一个测试任务的时间Petri网模型 |
对于所有测试任务, 可通过下列步骤构造出其时间Petri网(TPN)模型。
1) 如果任务i是任务j的先决测试任务, 那么在ti2和tj1之间加入一个库所sij, 使得·sij={ti2}, sij·={tj1}, 并对其赋予时间权值为0。
2) 对于没有先决测试任务的任务, 把代表它们各自开始的变迁合并成一个, 记为t0, 并引入一个初始状态库所s0, 使得·s0=Φ, s0·={t0}, ·t0={s0}, {sk|测试任务集合k无前提任务}, 并对s0赋予时间权值0。
3) 对于没有后续测试任务的任务, 把代表它们各自结束的变迁合并为一个, 记为te, 并引入一个结束状态库所se, 使得·se={te}, se·=Φ, 并对se赋予时间权值0。
4) 设置初始标识M0, 使得M0(s0)=1, 表示测试还未开始; M0(s)=0, s≠s0且s≠I。
1.3 可达标识图对于一个有界的Petri网, 由于其可达标识集R(M0)是一个有限集, 因此以R(M0)作为顶点集, 将标识之间的直接可达关系作为弧集, 用顶点集和弧集构成一个有向图, 即为Petri网的可达标识图(reachable marking graph)。此时, 一个网系统的状态变化和变迁发生序列的情况便可以通过这个网的可达标识图来进行分析。
在标识图中, 将每个顶点所对应的标识表示成一个向量。假设Petri网的库所集有m个元素, S={s1, s2, …, sm}, 则这个网的一个标识M可以表示成一个m维向量:M=[M(s1), M(s2), …, M(sm)], 也可以用一个库所集合来表示:M={M(si)×si|si∈S∧M(si)≠0}。
2 最短测试时间和测试主路径定义1 假设用E(Si)表示测试任务Si的最早可以开始时间, 用TE表示完成所有测试任务的最短测试时间, 用L(Si)表示保证所有测试任务在TE时间完成的某测试任务最晚必须开始时间。则有[3]:
|
(1) |
|
(2) |
|
(3) |
式中, ·(·Si)表示的是在测试任务库所Si的前一任务库所, (Si·)·表示的是测试任务库所Si的后一任务库所, 而W(Si)则为在测试任务库所Si上的时间权值, 即为完成该项测试任务所需要的时间。
测试主路径是指由于测试任务的时序关系制约而必须进行串行测试的任务。不在测试主路径上的测试任务均可并行于这条主路径测试。
定理1 设∑一个网模型, 那么在∑中, 必然存在一条从S0至Se的有向通路, 对于在该有向通路上的每个库所Si, 都有L(Si)=E(Si)。
证明 由定义1可知, E(Se)=TE=L(SE); 假设存在一个库所Sx∈·(·Se), 且满足E(Se)=E(Sx)+W(Sx), 则L(Sx)=min{E(Se)}-W(Sx)=E(Se)-W(Sx), 可得E(Sx)=L(Sx)。依次逆向类推, 最终可以得到E(S0)=L(S0)。这样可以找到一条由初始状态库所S0至结束状态库所Se的有向通路, 对于在该有向通路上的每个库所Si, 都有E(Si)=L(Si)。
由定义1和定理1可以得到从S0到Se的一条有向通路, 这条有向通路即为测试主路径。测试主路径有可能并不唯一。
3 最小测试资源集定义2 对于一个标识M∈R(M0), 如果E(M)表示标识M最早可能出现的时间, L(M)为保证整个测试流程在TE时间内完成, 标识M的最晚存在时间, 则有:
|
(4) |
|
(5) |
定理2 设∑一个网模型, 则在该网模型的可达标识图RMG(∑)中, 必然存在一条从初始标识M0到结束标识Me的有向通路, 在这条有向通路上的每个可达标识M都满足E(M)≤L(M)。
证明 对于初始标识M0, 显然有E(M0)≤L(M0)。假设存在一个变迁ti, 使得M0[ti>M1, 由公式(5)可知, 存在S0∈M0, 使得L(S0)+W(S0)=L(M), 且满足S0·={ti}→M0[ti>。对于∀Si∈·ti, 有
|
而对于∀Sj∈t·, 有
|
由于∀S∈M0, 总有E(S)≤E(M0)≤L(M0)≤L(M1), 因此有E(M1)≤L(M1)。依此类推, 直至Me, 这样就必然存在一条有向通路, 对于在这条有向通路上的每个可达标识M, 都有E(M)≤L(M)。显然, 这种有向通路并不唯一。
定理3 如果一个网模型∑的可达标识图RMG(∑), 在满足定理2的条件下存在一条有向通路(oriented path):OP=M0→M1→…→Me, 为保证完成整个测试流程的时间最短, 在该条有向通路上所需要的最小测试资源集为:
|
(6) |
(6) 式中, minRS(Mi)表示在标识Mi下, 同时并行处理的所有测试任务所需要的最小测试资源集; 求和∑表示多重集扩展加和。
定义3 设N=(S, T; F)为一个出现网, 如果对于∀x∈S∪T, 使得在网N中删去x后, 该网会出现多个连通的分支, 则称x为网N的一个割点。如果∀x1, x2∈T是网N的2个割点, 且从x1到x2存在不少于1条的有向通路, 则认为从x1到x2的部分网结构为原网的一个并发段, 记为P(x1, x2)[3]。
定义4 设P(x1, x2)为网∑=(S, T; F, W)的一个并发段, MTL(∑)是网∑的一条测试主路径, 为保证完成在该并发段内的测试任务的时间最短, 则该并发段需要的测试设备(TEN)的最小需求量为[3]:
|
(7) |
(7) 式中, SP(x1, x2)表示的为在并发段P(x1, x2)内的库所集合, W(Si)为某一库所的测试时间权值, TENmin(P(x1, x2))取值为不小于其本身实际值的整数。
如果在某一测试流程中, 存在多个并发段, 则完成整个测试任务所需测试设备的最小需求量为各个并发段所需测试设备的最小需求量的最大值。
4 实例分析假设有14项测试任务T={a, b, c, d, e, f, g, h, i, j, k, l, m, n}, 完成测试任务所需要的测试仪器资源为r1, r2, r3, r4。各子测试任务之间的测试优先级, 占用测试仪器资源和测试时间关系。如表 1所示。
| 测试任务 | 测试时间 | 先决任务 | 占用资源 |
| a | 3 | 无 | r1 |
| b | 2 | 无 | r2 |
| c | 4 | a | r3 |
| d | 1 | a | r2 |
| e | 2 | a | r4 |
| f | 2 | b | r2 |
| g | 3 | c, f | r1 |
| h | 5 | c, d | r2, r3 |
| i | 4 | c, d | r3 |
| j | 1 | e | r1 |
| k | 3 | i | r2 |
| l | 2 | g, k | r3 |
| m | 3 | h | r4 |
| n | 3 | h, j | r1, r3 |
单套测试设备的最小测试资源集, 是指整合在一套测试设备中用于完成对被测设备(UUT)的测试所需要的所有资源的集合。当设备封装之后, 测试资源集中的测试仪器不可添加或更改。
|
| 图 2 测试任务集T的TPN模型∑ |
现根据图 2所示的Petri网模型和公式(1)、公式(2)和公式(3), 计算各测试任务的最早可以开始时间和最晚必须开始时间, 时间单位为秒(s), 如表 2所示。
| 测试任务 | W(Si) | E(Si) | L(Si) |
| S0 | 0 | 0 | 0 |
| a | 3 | 0 | 0 |
| b | 2 | 0 | 7 |
| c | 4 | 3 | 3 |
| d | 1 | 3 | 6 |
| e | 2 | 3 | 10 |
| f | 2 | 2 | 9 |
| Schi | 0 | 7 | 7 |
| Scg | 0 | 7 | 11 |
| g | 3 | 7 | 11 |
| h | 5 | 7 | 8 |
| i | 4 | 7 | 7 |
| j | 1 | 5 | 12 |
| k | 3 | 11 | 11 |
| Shn | 0 | 12 | 13 |
| l | 2 | 14 | 14 |
| m | 3 | 12 | 13 |
| n | 3 | 12 | 13 |
| Se | 0 | 16 | 16 |
由表 2可以看出, 结束状态库所的最早开始时间和最晚必须开始时间都为16 s, 即整个测试任务完成的最短时间为16 s。根据定理1, 在表 2中寻找满足条件E(Si)=L(Si)的测试任务集合, 这样, 可以得出该测试网模型的测试主路径为:S0→a→c→Schi→i→k→l→Se。
现根据图 2的网模型∑, 绘制其可达标识图RMG(∑), 如图 3所示。
|
| 图 3 网模型∑2的可达标识图RMG（∑） |
各可达标识所包含的库所集合如表 3所示:
| 可达标识 | 库所集合 |
| M0 | S0 |
| M1 | a, b |
| M2 | b, c, d, e |
| M3 | a, f |
| M4 | c, d, e, f |
| M5 | b, c, d, j |
| M6 | c, d, f, j |
| M7 | Schi, Scg, d, e, f |
| M8 | Schi, Scg, d, f, j |
| M9 | h, i, j, Scg, f |
| M10 | Schi, d, g, j |
| M11 | h, i, j, g |
| M12 | j, Shn, m, i, g |
| M13 | h, j, k, g |
| M14 | n, m, i, g |
| M15 | j, Shn, m, k, g |
| M16 | h, j, l |
| M17 | n, m, k, g |
| M18 | Shn, m, j, l |
| M19 | n, m, l |
| Me | Se |
根据定义2, 求出各可达标识Mi的最早出现时间和最晚存在时间, 如表 4所示。
| 可达标识 | E(Mi) | L(Mi) |
| M0 | 0 | 0 |
| M1 | 0 | 3 |
| M2 | 3 | 7 |
| M3 | 2 | 3 |
| M4 | 3 | 7 |
| M5 | 5 | 7 |
| M6 | 5 | 7 |
| M7 | 7 | 7 |
| M8 | 7 | 7 |
| M9 | 7 | 11 |
| M10 | 7 | 7 |
| M11 | 7 | 11 |
| M12 | 12 | 11 |
| M13 | 11 | 13 |
| M14 | 12 | 11 |
| M15 | 12 | 13 |
| M16 | 14 | 13 |
| M17 | 12 | 14 |
| M18 | 14 | 13 |
| M19 | 14 | 16 |
| Me | 16 | 16 |
根据定理2, 满足E(M)≤L(M)条件的有向通路存在不只一条, 现选取其中一条有向通路进行分析:
|
在该有向通路中, 标识M1存在的时间区间为[0, 3], 其包含的库所集合为{a, b}, 表示在该状态下, a, b 2个测试任务被同时启动且并行执行; 同理, 标识M3表示在t=2时刻, 任务b完成测试, 任务f启动并执行; 标识M4表示在t=3时刻, 任务a完成测试, 任务c, d, e被启动且并行执行; 标识M6表示在t=5时刻, 任务e完成测试, 任务j被启动执行; 标识序列M8→M10→M11的完整含义为:在t=7时刻, 任务c完成测试, 任务h, i, g被同时启动且并行执行。标识M13表示t=11时刻任务i完成测试, 任务k启动并执行; 标识序列M15→M17的完整含义为:在t=12时刻, 任务h完成测试, 任务m, n被同时启动且并行执行。标识M19表示t=14时刻, 任务k完成测试, 任务l启动并执行; 标识Me表示在t=16时刻, 所有任务完成测试, 整个测试流程结束。
因此, 根据定理3, 对于可达标识图RMG(∑)有:
|
上述各式表示了测试流程中8个并行处理的阶段所需要的最小资源集。可得完成整个测试流程所需要的最小测试资源集为:
|
现将表 1中测试任务集的并行测试流程及对应的资源配置方案绘制在甘特图中, 如图 4所示。
|
| 图 4 测试任务集T的测试任务流程甘特图 |
由图 4可知, 在最小测试资源集{r1, 2r2, 2r3, r4}的条件下, 采用这种测试流程方案可以使整个测试任务在最短时间16 s内完成, 相比于串行测试(38 s)测试时间缩短了22 s, 测试效率提高了(38-16)/38×100%=57.9%。
4.2 最小资源集求解测试设备的可重构性, 是指单套测试设备中的测试资源固定不变, 在有空余测试设备的条件下, 通过多套测试设备的联合调度使用, 在完成某项测试任务时达到测试时间最短的目的。
在这里设每套测试设备均可单独完成各任务的测试工作, 通过定义3可知, 图 2所示网模型∑中, t0, t10和te是该网的4个割点, 从t0到te、t0到t10部分网结构分别构成原网的2个并发段, 即P(t0, te), P(t0, t10)。而该网模型只有一条测试主路径MTL(∑):S0→a→c→Schi→i→k→l→Se, 因此有:
|
整个原网模型测试设备的最小需求量为:
|
所以, 为使网模型∑2中的整个测试流程在最短时间内完成, 只需要3套测试设备即可。而根据图 4的测试流程甘特图可知, 在时间区间[3, 4]内, 有4个测试任务c, d, e, f在同时进行。因此, 现对网模型∑进行修改, 使任务d安排在任务e和j之间串行处理。这种处理并不是修改了测试任务的先后制约关系, 而是根据需要人为做出的测试顺序修改。修改后的Petri网模型∑2如图 5所示。
|
| 图 5 修改测试顺序后的Petri网模型∑2 |
根据定义1, 所求得的模型∑2中最短测试时间TE的值为16 s, 因此可以认为这种改动是合理的。
根据可达标识图分析方法, 可以得出网模型∑2在最小可重构测试设备条件下的并行测试流程如图 6所示。
|
| 图 6 最小可重构测试设备的并行测试任务流程甘特图 |
本文主要通过实例模型，以测试任务的先后时序关系为基础，在完成整个测试任务最短测试时间的基础上，利用Petri网的可达标识图分析方法介绍了综合航电系统并行测试的2种资源优化配置方案，并得出了并行测试任务流程甘特图。通过分析可以看出，这2种资源配置方案可以使整个测试流程在最短测试时间的前提下完成测试任务，大幅提高测试效率。
| [1] | Zhang G Q, Shi G Q, Zhao H G, Et Al. A Parallel Test Task Scheduling of Integrated Avionics System Based on the Ant Colony Algorithm[J]. Applied Mechanics & Materials, 2015, 713/715: 2069-2072. |
| [2] |
吴勇, 王雪, 赵焕义. 基于图染色理论和遗传蜂群算法的并行测试任务调度[J]. 计算机应用, 2015, 35(5): 1280-1283.
Wu Yong, Wang Xue, Zhao Huanyi. Parallel Test Task Scheduling Based on Graph Coloring Theory and Genetic-Bee Colony Algorithm[J]. Journal of Computer Applications, 2015, 35(5): 1280-1283. DOI:10.11772/j.issn.1001-9081.2015.05.1280 (in Chinese) |
| [3] | Mironescu I D, VinAn L. Coloured Petri Net Modelling of Task Scheduling on a Heterogeneous Computational Node[C]//IEEE International Conference on Intelligent Computer Communication and Processing, 2014:323-330 |
| [4] | Sotskov Y N, Gholami O. Mixed Graph Model and Algorithms for Parallel-Machine Job-Shop Scheduling Problems[J]. International Journal of Production Research, 2015, 55(6): 1549-1564. |
| [5] | Lill R, Saglietti F. Model-Based Testing of Autonomous Systems Based on Coloured Petri Nets[C]//Arcs Workshops, 2012:1-5 |
| [6] |
刘云周, 吴勇, 邓雪杰. 基于时延Petri网和人工蜂群算法的航电系统并行测试研究[J]. 测控技术, 2014, 33(11): 37-41.
Liu Yunzhou, Wu Yong, Deng Xuejie. Parellel Test of Advanced Avionics System Based on Timed Petri Net and Artificial Bee Colony Algorithm[J]. Measurement & Control Technology, 2014, 33(11): 37-41. DOI:10.3969/j.issn.1000-8829.2014.11.011 (in Chinese) |
| [7] | Kim D K, Lee T E, Kim H J. Optimal Scheduling of Transient Cycles for Single-Armed Cluster Tools with Parallel Chambers[J]. IEEE Trans on Automation Science & Engineering, 2013, 13(2): 1165-1175. |
| [8] | Wang X, Li Z, Wonham W M. Optimal Priority-Free Conditionally-Preemptive Real-Time Scheduling of Periodic Tasks Based on Des Supervisory Control[J]. IEEE Trans on Systems Man & Cybernetics Systems, 2017, 47(7): 1082-1098. |
| [9] | Guo Z, Zhang Y, Zhao X, et al. A Timed Colored Petri Net Simulation-Based Self-Adaptive Collaboration Method for Production-Logistics Systems[J]. Applied Sciences, 2017, 7(3): 235. DOI:10.3390/app7030235 |
| [10] | Kim D K, Lee T E, Kim H J. Optimal Scheduling of Transient Cycles for Single-Armed Cluster Tools with Parallel Chambers[J]. IEEE Trans on Automation Science & Engineering, 2013, 13(2): 1165-1175. |
| [11] | Tonke D, Lee T E. Modeling, Analysis, and Scheduling of Cluster Tools with Two Independent Arms[J]. IEEE Trans on Automation Science & Engineering, 2016, 13(2): 1176-1188. |
| [12] | Jiang J M, Zhu H, Li Q, et al. Analyzing Event-Based Scheduling in Concurrent Reactive Systems[J]. ACM Trans on Embedded Computing Systems, 2015, 14(4): 86. |
2. Chinese Electronic Equipment System Corporation Institute, Beijing 100141, China
