论文研究-基于赋时有色Petri网的测试系统资源优化方法.pdf

所需积分/C币:10 2019-09-19 17:53:14 656KB .PDF
收藏 收藏
举报

论文研究-基于赋时有色Petri网的测试系统资源优化方法.pdf,  提出采用赋时有色Petri网(TCP-net)对测试流程进行建模,用来优化自动测试系统的资源配置.给出了测试流程TCP-net模型的构建步骤; 基于模型,给出了寻求测试流程最短测试用时的方法,并设计了求解最短测试用时下最小资源集的算法:基于空闲区匹配的最小资源集算法;通过给出一个应用实例, 证明了上述方法的有效性和实用性.
1674 系统工程理论与实践 第30卷 实现库所S的物理意义为:当S中不包含托肯时,表示其前集测试任务讠还未开始测试;当S中包含 托肯时:表示其前集测试任务讠已经开始测试或测试完成,是处在测试状态还是已测试完状态可以根据S 中托肯的时间属性值(即时间邮票)和系统全局时间的比较米判断 2)若测试任务k没有前提测试任务则引入一个准备状态库所Sk,并使得Sk={k} 3)若测试任务h没有后续测试任务,则引入一个完成状态库所Sh,并使得Sh={h} 4)在2)的基础上,再引入一个开始测试标志库所S和一个开始测试变迁T0,使得S0=更,S={T0}, 10={50},T={Sk无前提测试任务的k的准条状态库所} 5)在3)的基础上再引入一个测试完成标志库所S和一个结束测试变迁T,使得T={Sh无后续测 试任务的h的完成状态库所},T={S},S={T},Se=更. 6)根据测试任务占用资源情况,连接好仪器资源库所Ⅰ与各测试任务之间的双向弧 7)设置初始标识Mo,使得:M0(S0)=1;M0(D)=ATS仪器资源集;Mo(s)=0,8≠S08≠Ⅰ. 从上述网模型的构造过程可以看出,一个测试流程的 TCP-net模型具有以下特点: 1)开始测试变迁T和结束测试变迁Te为两个虚拟测试任务,由于其测试用时均为0,因此不影响整个 系统的性能 2)Vs∈S-{}:|s|≤1,|sl|≤1 3),v∈SUT-{7},若(x,y)gF+,则()F.其中F+=FUF·FU…=F2, FCSXTUT×S 为流关系.dom(F)cod(F)-SuT,dom(F)-{x|y:(x,y)∈F},cod(F)-{v|x:(x,y)∈F}. 4)x∈SuT-{S0,Se}-{l}:(S0,x)∈F+且(x,S)∈F+,即每个测试任务(变迁)及其状态(库所) 都位于从S0到S的一条有向通道上 性质2)和3)说明:在不考虑仪器资源的情况下,一个测试流程的 TCP-net模型其基网是一个出现网 为论述方便,记测试流程的 TCP-net模型为∑,不考虑仪器资源时的TCP-net模型为∑ 4最短测试时间 定义2E()表示测试过程中任务i的最早可以开始测试时间,E()满足: E(i)=max{E()+t()∈i的前提测试任务集} (1) 其中t()表示测试任务j的测试用时.若测试任务无前提测试任务,则E()=0.记TE表示整个测试过程 所用的最短时间,显然有T=E() 定义3L(i)表示为保证幣个测试过程在最短测试时间T内完成,测试任务i的最晚(最迟)必须开始 测试时问,L()满足 L(i)=min{L(j)j∈I的后续测试任务集}-t(i) 显然L(T)=TE.从T开始,逐个向后回溯,可以求出为保证整个测试过程在最短测试时间内完成,各 测试仟务最晚必须开始测试的时间 定理1∑中存在一条从T到T的有向测试通路,对该有向测试通路上的每个测试任务i(包括两个 虚拟测试任务),都有L(2)=E(i 证明由式(1)和(2)有,L(Te)=E(1e)=Tb 根据式(1)可知存在任务k∈{TT为测试任务T的前提测试任务},便得TE=E(le)=E(k)+t(k E(k)=Tet(h) (3) 又根据式(2)有,L(k)=min{L()∈k的后续测试任务集}-t(k),而显然min{L()∈k的后续测试 任务集}=TE.所以 L(k)=TE-t(h 综合(3)、(4)式可知E(k)=L(k) 同理对于测试任务k,存在测试任务h∈{TT为测试任务k的前提测试任务},使得E(b)=L(h),依 此类推逆向追溯最终可以推出E(T)=L(T) 第9期 付新华,等:基于赋时有色Ptri网的测试系统资源优化方法 1675 这样,就找到了一条从T0到Te的有向测试通路,对该有向测试通路上的每个测试任务(包括两个虚拟 测试任务),都有L()=E().把满足定理1的有向测试通路称为主测试任务序列线ML( Main list),显然 ML可能不唯 5基于空闲区匹配的最小资源集求解算法 定义4设N={S,T;F}为一个连通的现网,x∈SUT.如果从N中删去x就会变成多个连通分 支,那么称:为N的一个割点 定义5已知∑’t,t∈T是其基网的两个割点.如果从t到t有多于一条有向路,那么称t;到t 的部分网结构(不包括割点本身即t1和t)为∑的一个并发段,记为P(t,t) 设P(t2,t)为∑的一个并发段,ML∑)是∑的一条主测试任务序列线,记TP(t,t)表示并发段 P(t,t)中所有变迁测试任务)的集合,TP(t,t)∩ML∑)表示既在并发段P(t1,t)之内在主测试任 务序列线ML(∑)上的变迁集合则并发段P(t2t)的最短测试时间 minT(P(t,+)=∑1(th)∈rP(1tmM), 式中t(tk)表示测试任务tk的测试用时 为保证并发段P(43)测试时间最短、记其所需的资源最小集为 InlIERs(P(2,13). ImINEs(P(,))可 通过以下方法得到 1)寻找该并发段内的所有主测试任务序列线ML1,ML2,…,MLk,k为主测试任务序列线总数,显然 k>1 2)任取一条主测试任务序列线ML(1≤x≤k).不失一般性,记MLx为:MLx=71→T2→ → T. ML所需要的最小资源集 min RS(MLx)=∑RS(T 式中求和∑采用多重集扩展加法⊕:RS(t1)为一个多重集,表示测试任务T占用的资源集 3)不妨记 minRS(Mx)={m(A)A,m(B),…,m(N)N},其中A、B、…N为资源代号.构造M/ 的测试任务在资源上分配的甘特图G,如图3所示 m(N) T=(2) 试B1 资A 时间轴 图3测试任务在资源上分配的甘特图G 记Q=TP(t,t;)「MIa=MJ,表示并发段P(t,t)之内位于主测试任务序列线Ma上的测试 任务的集合.Q=TP(t;,t)-ML表示并发段P(t2,t)之内不属于ML上的所有测试任务的集合.Q 中的测试任务又可以分成两类,一类是该测试任务位于ML之外的其它主测试任务序列线之上,即H= {∈TP(t2,t;)∧T∈ML2(1≤x≤k且z≠x)};另一类是该测试任务不属于任何主测试任务序列线 即H=Q-H={1∈TP(t1,t1)∧TgML2(1≤≤k)}.后者称为弹性测试任务,表示在保证最短测 试时旬条件下该任务的启动测试时刻有一定的活动区间.前者则称为非弹性测试任务,表示在保证最短测试 时间条件下该任务的启动测试时刻固定 至此,寻找并发段P(t;,t)所需资源最小集问题转化为将Q中的测试任务在增加最少资源的前提下合 理地安排在图3所示的资源空闲区间上.具体过程如下 1)将H中的测试任务按所需要占用资源的数量从多到少依次排序,得到有序集合H.不妨设H′={V1, V2,…,V},显然vV∈H(1≤j<q),有|RS(V)>|RS(V+1) 1676 系统工程理论与实践 第30卷 2)计算ⅵ的合理执行时间区间tb,tel=E(v1)、E(ⅵ)+t(Ⅵ)根据所占资源及执行区间匹配图G中 的资源空闲区,若未能完仝匹配则逐渐増加新资源使得刚好能完全匹配成功.填充空闲区,并修改图G为 3)计算V2的合理执行时间区间,并在图G1的基 问题描述效输入 础上匹配空闲区,填充空闲区,修改(1为(2,依此类 构建流程的模型∑和∑ 推,直到V最后得到新甘特图Gq 找到所有一发段( 4)将H中的测试任务按所需要占用资源的数量从 多到少依次排序,得到有序集合不妨没豆′={W,|班的和 是否存 并发段 W2,…,Wm},显然VW;∈H(1≤j<m),有 ARS(W)≥|RS(W+1) 找到并发段的所有土测试任务序列线 5)计算W1的合理执行时间区间{h,ta]=[E(W1) L(W1)+t(W1),根据所占资源及执行区间前后滑动匹 计算其最小资源集开构造日特图 配图Gφ中的资源空闲区.若未能完全匹配,则逐渐增 计算弹性测试任务集和非弹性测试任务集 加新资源使得刚好能完全匹配成功.填充空闲区,并修 [将按占月资源数量排序,得到有序 改图Gn为G1 6)计算W2的合理执行时间区间,并在图G1的基 算的合执行区根所与额及执行区同四配 础上匹配空闲区.填充空闲区,修改(1为(2.依此类 矧中的资源空闲区。若未能完仝匹配,则逐渐增加新资源 使得刚好能完全匹配戍功。填充空闲区,并修改图为 推,直到Wm最后得到新甘特图Gm 7)图Gm中的资源集即为所求最小资源集min RS(P(ti, t,) 将按口用资源数量排序,得到序樊 若测试流程包含若干并发段,为保让总的测试时间 最短,其所需最小资源集 计算的合理执行时间区间,根柘所占资源及扶行区间前后滑动 minRS(∑) ∑RS(T)∑ minRS(P) 匹配图中的资源空困区。若未能完全匹配,则逐渐增加紡资源 使得刚好能完全匹配成功、填充空闲区,并修改图为′ Ta2∈T P 否 式中:T为整个流程的测试任务集;P为∑的并发段, n为并发段总数,TP2为并发段P中所有变迁即测试任 算‘的资源得到的最小资源集 务的集合:求和∑均为多重集扩展加⊕ 综上所述,可归纳出基于空闲区匹配的最小资源集 求解算法流程,如图4所示 按⊕计算所有变迁不在并发段上的资源和 并与所有并发段所求最小资源集求⊕ 6算例分析和仿真 结果输出 已知测试流程的测试任务集T={a,b,C,d,C,f,图4基于空闲区匹配的最小资源集求解算法流程 g,h,i,j,k},任务的优先级关系、使用仪器和测试所用时问(单位:秒)如表1所示.仪器编号与实际仪器的 对应关系为:I1数字万用表(DVM);I2函数发生器(DA;I3一逻辑分析仪(TA);I4数字化仪(AD 表1测试任务的优先级关系、使用仪器和测试所用时间 测试任务 d k 测试用时2 前提任务 无 b. c c d 使用仪器 4 I3+I4 根据表1及测试流程TCP-net模型的构建步骤可画出该流程的 TCP-net模型∑1:如图5所示.其不 考虑仪器资源时的 TCP-net模型∑1,如图6所示 对于图6模型∑1,根据式(1)、(2),容易得出各测试任务T的E()和L(T)值,如表2所示.从表 中可以看出最短测试时间TE=12,其主测试任务序列线ML=T0→a→b→→i→k→T 第9期 付新华,等:基于赋时有色Ptri网的测试系统资源优化方法 1677 9+(S0)49+2sd)e Sfh @2 @+2 ▲TA++AD a+1 DVM TATa+3(Sce)e DⅤM TA@+2 ey Sab DVM INSTRUMENT INSTRUMENT.alKo) 图5测试流程的 TCP-net模型 @ I'e @ o)四(sas°s下 +3 a+2 +2 X Sab be 图6测试流程的TCP-net模型(不考虑仪器资源) 表2∑中各测试任务T的E(T)和L(T)值 h F(2) ∫46 L(T2) 4 4 10 10 12 采用基于空闲区匹配的最小资源集求解算法对实例进行分析,经软件计算得到其最小资源集为{1'DVM 2’AD,1TA,1'DA}.各测试任务在资源上分配的甘特图如图7所示(重复任务表示该任务需占用多个资源) 显然,图7只是合理调度过程的一种 为验证求最小资源集算法和软件的正确性,采用有色 Petri网建模、仿真和分析工具 CPn Tools进行仿 真12-13.给资源集赋初值{1DVM,2AD,1TA,1DA},仿真结果如图8所示.从仿真结果可以看出,测 试流程在依据求最小资源集算法获得的最小资源集下可以在最短测试时间内完成整个测试,从而验证了求最 小资源集算法和软件的正确性和有效性. 试 资 时间轴 图7测试任务在资源上分配的甘特图 fg 'AD DA DVM AD 5IDVM++2'AD++ITA++I'DA 图8测试流程在最小资源集下的调度过程仿真 1678 系统工程理论与实践 第30卷 7结束语 提出釆用赋时有色 Petri网来进行测试系统资源的优化配置.通过建立测试流程的TCP-nct模型,可以 得到测试流程的最短测试用时,以及最短测试用时下的最小资源集,从而达到优化测试系统资源配置的目的 论文只是针对测试用时为常量的情况进行讨论,但此方法可以拓展到测试用时为区间或服从某种函数分布的 情况 参考文献 门]孙宝江,秦红磊,胡文明,等.自动测试系统适配器自动设计技术J.航空学报,2007,28(3):703-707 Sun b, Qin H L, Hu w m, et al. Automatic design for general purpose test unit adapter of automatic test system. Acta Aeronautica Et Astronautica Sinica, 2007, 28(3: 703-707. 2 Sun B J, Qin H L, Shen S T. An automatic design technique for hardware system of ats[C// Autotestcon Proceedings ieee. 2006: 386-396 3]詹惠琴.测试系统的 Petri网建模和性熊分析研究[D].电子科技大博土学位论文,2005 Zhan H Q. Study on the Petri net modeling and performance analysis of a testing system D. University of Electrical Science and Technology. 2005 4]胡瑜.基于有色 Petri网理论的并行自动测试系统建模研究[].电子科技大博上学位论文,2003 HU Y. Colored Petri net based modeling of parallel automatic test systems]. University of Electrical Science and Technology, 2003 ]李巍,杨锁昌,郑新燎,等.基于赋时 Petri网的自动测斌系统建模J].军械工程学院学报,2005,17⑥):68-70 Li W, Yang S C, Zheng X L, et al. Modeling research of automated test system based on timed petri net[J. Journal of Ordnance Engineering College. 2005, 17(6):68-70 l6]李爱萍,工家礼,段利国.基于UML的自动测试系统建模方法研究J.宇航学报,2006,27(6):1382-1385. Li A P, Wang J L, Duan L G. The study on automatic test system modeling method based on UMLJ. Journal of astronautic,2006,27(6):1382-1385 7]张信一,黎燕.基于Ptri网的工作流建模J.微机发展,2003,13(6):91-93 ng XY. Li Y. Method of workflow modeling based on Petri net[J. Microcomputer Development, 2003, 13(6) 9193 8 Jense K. An introduction to the theoretical aspects of colored Petri nets[C// Lecture Notes in Computer Science New York: Springer-Verlag, 1994: 230-272 9 Jense K. An introduction to the the practice use of colored Petri nets[Cl//Reisig W, Rozenberg g Petri Nets Il. LNCS1492, Berlin, Heidelberg, New York: Springer-Verlag. 1998: 237-292 10]吴哲辉. Petri网导论[M].北京:机械工业出版社,2006 Wu Z H. Petri Net Introduction[M. Beijing: China Machine Press, 2006 1]付新华,肖明清,袁大勇,等.基于有色 Petri网的FIFO栈建模与优化团仪器仪表学报,20,29(3):577-582 Fu X H, Xiao M Q, Yuan D Y, et al. Colored Petri-net based approach to analyze and optimize FIFO stackJ Chinese Journal of Scientific Instrument, 2008, 29 (3):577-582 [12李阳,武昌,曹洪权.CPN- Tools在装备维修规划中的应月研究.系统仿真学报,2006,18(1):200-203. Li Y, Wu C, Cao H Q. Application of CPN-Tools in making weapon service schema[J. Journal of System Simulation,2006,18(1):200203 13 Vinter R A, Lisa W, Michael L H, et al. CPN tools for editing, simulating, and analyzing coloured Petri net[C // Proceedings of Applications and Theory of Petri Nets 2003: 24th International Conference, ICATPN 2003 Eindhoven. Netherlands. 2003: 23-37

...展开详情
试读 7P 论文研究-基于赋时有色Petri网的测试系统资源优化方法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38744375 你的留言是对我莫大的支持
    2019-09-19
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于赋时有色Petri网的测试系统资源优化方法.pdf 10积分/C币 立即下载
    1/7
    论文研究-基于赋时有色Petri网的测试系统资源优化方法.pdf第1页
    论文研究-基于赋时有色Petri网的测试系统资源优化方法.pdf第2页
    论文研究-基于赋时有色Petri网的测试系统资源优化方法.pdf第3页

    试读已结束,剩余4页未读...

    10积分/C币 立即下载 >