下载文档原格式
长沙理工大学硕士学位论文基于时间Petri网的并行测试研究姓名：肖良清申请学位级别：硕士专业：计算机软件与理论指导教师：乐晓波20100301摘并行测试技术是ＡＴＳ（Ａｕｔｏ要ＴｅｓｔＳｙｓｔｅｍ）在进一步降低测试的时间、削减测试的成本的趋势下新兴的一项技术，它正以不可比拟的优势成为下～代ＡＴＳ发展的热点。
在运用并行测试技术时，要求分析系统执行过程中可能产生的冲突和竞争情况，特别是如何生成并行测试序列一直是一个复杂的、难于优化的ＮＰ难题。
Ｐｅｔｒｉ网作为一种图形化建模工具，可以很直观的表示系统并发、异步等系统常见现象，而引入时间Ｐｅｔｒｉ网，可以更便捷地描述实时系统。
因此，进一步发展并行测试技术理论和拓宽并行测试应用领域的关键在于：如何建立准确、可靠的并行测试时间Ｐｅｔｒｉ网模型，并在所建模型的基础上，探讨并行测试的任务调度算法。
本文在探讨时间Ｐｅｔｒｉ网构建过程中的约简步骤，并深入分析现今并行测试任务模型不足的基础上，提出了一种基于时间Ｐｅｔｒｉ网的并行测试建模方法。
为说明该方法的应用步骤，选用一雷达接收机的实例建立相应的时间Ｐｅｔｒｉ网，并对其进行了动态性质分析。
在此基础上，详细研究了群智能的各类优化算法，结合时间Ｐｅｔｒｉ网的特点和现有并行调度算法的局限，提出了一种基于遗传一蚁群算法的时间Ｐｅｔｒｉ网变迁序列求解算法，针对一雷达接收机的具体实例，快速地求得了最优调度方案。
仿真实验表明，与现有研究成果相比，本文所提出的算法效率更高，具有重要的实用价值。
关键词：并行测试；任务调度；时间Ｐｅｔｒｉ网；变迁序列；遗传一蚁群算法ＡＢＳＴＲＡＣＴＰａｒａｌｌｅｌｔｅｓｔｔｅｃｈｎｉｑｕｅｉｓａｎｅｗｔｅｃｈｎｉｑｕｅａｒｉｓｉｎｇｕｎｄｅｒｔｈｅｔｅｎｄｅｎｃｙｏｆｓｒｅｄｕｃｉｎｇｔｅｓｔｔｉｍｅａｎｄｌｏｗｉｎｇｔｅｓｔｃｏｓｔ，ｗｈｉｃｈｉｎｅｘｔｂｅｃｏｍｉｎｇｈｏｔｓｐｏｔｏｆｔｈｅＡＴＳｆｏｒｕｎｐａｒａｌｌｅｌｅｄａｄｖａｎｔａｇｅ．Ｔｈｅｐａｒａｌｌｅｌｔｅｓｔｓｙｓｔｅｍｒｅｑｕｉｒｅｓｔｈｅｒｕｎａｎａｌｙｓｉｓｏｆｃｏｍｐｅｔｉｔｉｏｎａｎｄｃｏｎｆｌｉｃｔｉｎｔｉｍｅ，Ｗｏｒｓｅｍｏｒｅ，ｔｈｅｏｐｔｉｍｉｚｅｄａｐａｒａｌｌｅｌｔｅｓｔｔａｓｋｓｃｈｅｄｕｌｉｎｇｓｅｑｕｅｎｃｅｈａｓｂｅｅｎＮＰｐｒｏｂｌｅｍ．Ｐｅｔｒｉｎｅｔ，ａｓａｃｏｍｐｌｉｃａｔｅｄａｎｄｄｉｆｆｉｃｕｌｔｃａｎｇｒａｐｈｉｃａｌｍｏｄｅｌｉｎｇｔｏｏｌ，ｗｈｉｃｈｒｅｐｒｅｓｅｎｔｃｏｎｃｕｒｒｅｎｃｅ，ａｓｙｎｃｈｒｏｎｙｉｎｉｎｔｕｉｔｉｖｅｗａｙ，ｈａｓｂｅｅｎｗｉｄｅｌｙｕｓｅｄｉｎｖａｒｉｏｕｓｃａｎｆｉｅｌｄｓ．Ａｔｔｈｅｓａｍｅｔｉｍｅ，ｔｈｅｉｎｔｒｏｄｕｃｔｉｏｎｏｆＴｉｍｅｄＰｅｔｒｉｎｅｔｃｏｎｖｅｎｉｅｎｔｔｏｄｅｖｅｌｏｐｍｅｎｔｂｅｍｏｒｅｄｅｓｃｒｉｂｅｔｈｅｒｅａｌ—ｔｉｍｅｓｙｓｔｅｍ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｅｋｅｙｏｆｆｕｒｔｈｅｒｏｆｔｈｅｔｈｅｏｒｙｔｅｓｔｏｆｉｓｐａｒａｌｌｅｌｈｏｗｔｏｔｅｓｔｔｅｃｈｎｏｌｏｇｙ，ａｎｄａｎｂｒｏａｄｅｎｔｈｅａｐｐｌｉｃａｔｉｏｎｏｆｐａｒａｌｌｅｌｅｓｔａｂｌｉｓｈｔｏａｃｃｕｒａｔｅａｎｄｒｅｌｉａｂｌｅｔｅｓｔＴｉｍｅｄＰｅｔｒｉｎｅｔｍｏｄｅｌｏｎｆｏｒｐａｒａｌｌｅｌｔｅｓｔ，ａｎｄｓｔｕｄｙｐａｒａｌｌｅｌｔａｓｋｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍＩｎｔｈｉｓｔｈｅｂａｓｉｓｏｆｔｈｅｍｏｄｅｌａｃｔｉｖｉｔｙ．ｏｎａｒｔｉｃｌｅ，ｂａｓｅｄａｎｄａｎａｌｙｚｉｎｇｄｉｓｃｕｓｓｉｎｇｔｈｅｐｒｏｃｅｄｕｒｅｏｆｓｉｍｐｌｉｆｙｉｎｇｓｈｏｒｔａｇｅｏｆｃｕｒｒｅｎｔａＴＰＮｍｏｄｅｌｐｒｏｐｏｓｅｄｏｒｄｅｒｔｏａｔｈｅｐａｒａｌｌｅｌｔｅｓｔｍｏｄｅｌ，ｍｏｄｅｌｉｎｇｍｅｔｈｏｄｆｏｒｐａｒａｌｌｅｌｔｅｓｔｂａｓｅｄｏｎＴｉｍｅｄＰｅｔｒｉｎｅｔ．Ｉｎａｎｅｘｐｌａｉｎｔｈｅｍｅｔｈｏｄｆｏｒａｐｐｌｉｃａｔｉｏｎｏｆｓｔｅｐｓ，ｕｓｅｄｉｎｓｔａｎｃｅｏｆｒａｄａｒｒｅｃｅｉｖｅｒｔｏｅｓｔａｂｌｉｓｈｔｈｅｃｏｒｒｅｓｐｏｎｄｉｎｇＴｉｍｅｄＰｅｔｒｉｎｅｔ，ａｌｓｏｓｔｕｄｉｅｄｔｈｅｄｙｎａｍｉｃｎａｔｕｒｅｏｆｔｈｅｍｏｄｅｌ．Ｏｎｔｈｉｓｂａｓｉｓ，ａｄｅｔａｉｌｅｄｓｔｕｄｙｏｆｖａｒｉｏｕｓｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｓｏｆｓｗａｒｍｉｎｔｅｌｌｉｇｅｎｃｅｃｏｍｂｉｎｅｄｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆＴｉｍｅｄＰｅｔｒｉｎｅｔｗｉｔｈｔｈｅｌｉｍｉｔａｔｉｏｎｓｏｆｅｘｉｓｔｉｎｇｐａｒａｌｌｅｌｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｓ，ａｎａｌｇｏｒｉｔｈｍｏｆｅｘｐｌｏｒｉｎｇｔｒａｎｓｉｔｉｏｎｓｅｑｕｅｎｃｅｏｆＴｉｍｅｄＰｅｔｒｉｎｅｔｂａｓｅｄｏｎｇｅｎｅｔｉｃ—ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｉｓｏｒｉｇｉｎａｌｌｙｐｒｏｐｏｓｅｄ．Ｔｈｅｏｐｔｉｍａｌｃａｎｓｃｈｅｄｕｌｉｎｇｂｅｆｏｕｎｄｉｎｏｎａａｖｅｒｙｓｈｏｒｔｐｅｒｉｏｄｏｆｔｉｍｅｗａｓｐｒｅｓｅｎｔｅｄｉｎｔｅｒｍｓｏｆｃｏｍｐａｒｅｄａｎｅｘａｍｐｌｅｔｈｅｒａｄａｒｒｅｃｅｉｖｅｒ．Ｓｉｍｕｌａｔｅｄｅｘｐｅｒｉｍｅｎｔｓｈｏｗｓｔｈａｔｒｅｓｅａｒｃｈｒｅｓｕｌｔｓ，ｔｈｅｇｉｖｅｎｗｉｔｈｅｘｉｓｔｉｎｇａｌｇｏｒｉｔｈｍｈａｓＩｌｉｍｐｏｒｔａｎｔｐｒａｃｔｉｃａｌｖａｌｕｅｆｏｒｍｏｒｅｅｆｆｉｃｉｅｎｃｙ．Ｋｅｙｗｏｒｄｓ：ｐａｒａｌｌｅｌｔｅｓｔ；ｔａｓｋｓｃｈｅｄｕｌｉｎｇ；ＴｉｍｅｄＰｅｔｒｉｎｅｔ；ｔｒａｎｓｉｔｉｏｎｓｅｑｕｅｎｃｅ；ｇｅｎｅｔｉｃ－ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｎｌＩＩＩ长沙理工大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。
收稿日期:1997212222 范玉顺。
主要从事863 C I M S 专题及烟草工业C I M S 研究与开发。
面向对象的Petri 网方法及其在软件工程中的应用范玉顺 张 军 清华大学自动化系 北京(100084)摘 要 本文介绍了面向对象Petri 网(OO PN )方法,给出了OO PN 的基本定义和图形表示,讨论了OO PN 的特性和子网细化方法。
结合软件设计开发周期,给出了OO PN 在软件工程中的应用方法及步骤。
给出了利用OO PN 方法进行柔性制造系统(FM S )控制软件设计开发的应用实例,并给出了部分对象类和应用程序。
利用OO PN 方法可以对软件系统设计开发过程进行有效的控制,保证软件系统的可靠性和规范化水平。
关键词 面向对象,Petri 网,软件工程,柔性制造系统OBJECT -OR IENTED PETR I NET M ETHOD AND ITS APPL I CAT I ON IN S OFT W ARE ENGINEER INGFan Y ushun Zhang JunD ep a rt m en t of A u to m a tion ,Q ing hua U n iversity ,B eij ing 100084Abstract In this paper O bject -O riented PetriN et (OO PN )m ethod is introduced .The basic definiti onsand deno tati ons are p resented .The characteristics and subnet refinem ent m ethod of the OO PN are giv 2en .In considerati on of softw are design and developm ent life cycle ,the m ethod and app licati on step s in softw are engineering using OO PN are fo rm ulated .A n examp le of the design and developm ent of contro l softw are fo r flexi 2ble m anufacturing system using OO PN is given .Som e of the codes fo r the object class and app licati on p rogram s are also p resented .The using OO PN in softw are engineering w ill i m p rove the efficiency in contro lling the soft 2w are system developm ent p rocess and ensure the reliability and standardizati on of softw are system .Keywords O b ject -o rien ted ,Petri N et ,Softw are engineering ,F lex ib le m anufactu ring sys 2tem1 引言Petri 网方法已经被广泛应用于C I M 系统的设计、分析和实施中。
●基础科学与技术Basic Science ＆TechnologyPetri 网在智能评估系统知识表示和推理中的应用聂伟（陆军军事交通学院镇江校区，江苏镇江212003）摘要：为解决考核评估中传统算法存在的问题，实现计算机自动评估，将Petri 网应用于模拟训练系统操作评估。
提出Petri 网的评估知识表示方法，针对故障处理操作的复杂性和动态性，将模糊Petri 网应用于机电人员故障处理操作的评估推理。
该应用能提升评估知识表示的质量，改善故障课目评估效果。
所开发的智能评估系统应用在培训教学中，提升了艇员的培训效率和质量。
关键词：Petri 网；知识表示；推理方法；智能评估系统DOI ：10．16807/j．cnki．12-1372/e．2021．02．018中图分类号：TP311文献标志码：A文章编号：1674-2192（2021）02-0084-05Application of Petri Net in Knowledge Ｒepresentation andＲeasoning of Intelligent Evaluation SystemNIE Wei（Zhenjiang Campus ，Army Military Transportation University ，Zhenjiang 212003，China ）Abstract ：In order to solve the problems existing in the traditional evaluation algorithm and realize the computer automatic evaluation ，the Petri net is applied to the operation evaluation of simulation training system．In view of the complexity and dynamics of fault handling operation ，fuzzy Petri net is applied to the evaluation reasoning of electromechanical personnel ’s fault handling operation．The application can improve the quality of knowledge representation and the effect of fault course evaluation．The developed intelligent evaluation system should improve the training efficiency and quality of the crew in the training and teaching．Keywords ：Petri net ；knowledge representation ；reasoning method ；intelligent evaluation system收稿日期：2020-09-03；修回日期：2020-11-10．基金项目：军队科研项目．作者简介：聂伟（1987—），男，博士，讲师．20世纪60年代初，国外研究者就开始尝试开发考核评估系统。
Petr i网在电力系统中的应用①林振智1,2,文福拴1,2,钟志勇3,黄杰波3(1.华南理工大学电力学院,广州510640;2.华北电力大学电力系统保护与动态安全监控教育部重点实验室,北京102206;3.香港理工大学电机系,香港)摘要:介绍了Petri网的基本原理及其在电力系统中的应用。
通过收集和整理国内外相关学术期刊和会议论文集中已发表的数十篇有关Petri网在电力系统中应用研究方面的学术论文,按故障诊断、系统恢复、配电系统重构、机组组合、网络拓扑分析、可靠性分析、继电保护建模与混杂电力系统分析等方面分别进行了分类述评。
从现有的研究工作情况来看,Petri网在电力系统中的应用涉及面很广,并受到了比较普遍的重视。
关键词:电力系统;Petri网;故障诊断;系统恢复;配电系统重构中图分类号:TM7;T P18 文献标识码:A 文章编号:100328930(2007)0520014210Appl ica tion s of Petr i Nets i n Power System sL I N Zhen2zh i1,2,W EN Fu2shuan1,2,Chung Ch i Yung3,W ong K it Po3(1.Co llege of E lectric Pow er,Sou th Ch ina U inversity ofT echno logy,Guangzhou510640,Ch ina;2.Key L abo rato ry of Pow er System P ro tecti on and D ynam ic Secu rity M on ito ringand Con tro l(N o rth Ch ina E lectric Pow er U n iversity),M in istry of Educati on,B eijing102206,Ch ina;3.D ep artm en t of E lectrical Engineering,the Hong Kong Po lytechn ic U n iversity,Hong Kong,Ch ina)Abstract:T he fundam ental theo ry of the Petri net and its app licati ons in pow er system s are introduced in th is paper.T h rough analyzing and comparing m any published papers associated w ith Petri net app licati ons,a concise and system atic survey is m ade from several specific areas invo lved,including fault diagno sis,pow er system resto rati on,distributi on netw o rk reconfigurati on,unit comm itm ent,pow er netw o rk topo logy analysis,reliability analysis,p ro tective relay modeling and hybrid pow er system s.F rom th is review,it is clear that m uch research w o rk has been done on the app licati on of the Petri net in so lving m any p roblem s in pow er system.Key words:pow er system s;Petri net;fault diagno sis;system resto rati on;distributi on netw o rk reconfigurati on1 前言 现代电力系统是高维复杂动态系统。
Petri网的综述及应用蔡振宇摘要：一、Petri网的发展Carl Adam Petri于1962年在他的博士论文中首次提出了有关Petri网的概念。
自上世纪八十年代第一次Petri网理论和应用的国际研讨会的召开以来,与之相关研讨会在世界范围内就开始以一年一度的频率召开。
人们通常称赞Petri网描述异步并发与图形表示的能力，而这两个特点来源于其网状结构。
世间万物皆由网构成，只是这个网是有形的或是无形的，万事万物在这些网上发生着变化。
事物间依赖关系，正是Petri网的完美体现。
描述物理世界的客观存在，使客观存在成为论文的研究对象，同时还必须保证凡是用其描述的系统都能转换为客观存在。
前者称为系统模型的仿真性，后者则是系统模型的可实现性。
目前Petri 网己扩展成多种形式，如基础Petri网、时间Petri网、层次Petri网、有色Petri网等等[}z6-3 y。
一个Petri网的结构元素包括:库所(place)、变迁(transition)和弧(acr)。
库所也称位置，它是一个抽象的词语，不是具体指哪个确定位置，而是建模中恰巧画的位置，它主要的作用是描述网中的一个局部资源状态或者是条件。
变迁是用于描述变化着的系统事件，它表示的是一种资源相互作用的事件发生关系。
弧的意义是描述资源的使能转化方向，是库所中消耗和产生的依据。
如图2-1中，以红点来显示的是托肯(token)或者称为标记，它存在于库所中，呈现库所的资源数量，是Petri网中的一个重要概念。
托肯在网中的动态变化意味着网的不同状态。
一个简单的网系统模型，如图2-1所示。
-+Petri网从客观的角度对系统的发生进行定性和定量的描述，并能呈现出有规律的定性和定量的改变。
在Petri网中，把对象统称为资源。
定性相同的资源定为一类，用一个状态元素P来表示。
托肯的数量代表了库所P的状态。
尸的定性和定量的改变也就是上面所称的变迁T。
在建模中库所P用圆圈来表示，变迁T用方框来表示，有向弧用箭头来表示。
[汇编]petri网原理与应用综述petri网原理与应用综述摘要:本文概述了Petri网的历史、发展、研究方法及应用领域，同时介绍了Petri网的基本原理，并给出了1个计算机网络链路层数据传输协议——停等协议的Petri网模型。
最后，概述了Petri网研究和应用中出现的问题，展望了Petri网的发展方向。
关键字:Petri网;状态变迁模型;并发;停等协议中图法分类号:TP312Research Surveys of the Petri NetWU QiangDepartment of Electronics and Information Engineering，Henan Vocational College of Agriculture，Zhengzhou，Henan Province 451450，ChinaAbstract: The article summarizes the history， thedevelopment， the research methods， the application areas and the basic principle of Petri net， and gave a Petri net model of stop-and-wait protocol。
Meanwhile， according to the problem of Petri net research and application， the paper gave some ideas。
Key words: Petri net; States transition model; Concurrency;Stop-and-wait protocol1。
历史和发展Petri网的概念最早是在1962年Carl Adam Petri 的博士论文中提出来的，后来该模型就成为理论计算机科学包括自动机模型和形式语言理论的1个分支。
实验一 Petri网建模工具的使用一实验目的和要求1）了解Petri网的特点。
2）通过上机实践，了解PetriLab的使用，并借助该工具，对网上购物系统进行建模。
二实验内容与步骤1、Petri网的描述Petri 网是描述具有分布、并发、异步特征的离散事件动态系统的有效工具。
作为一种图示和数学融合的模型工具，Petri 网有两个显著的特点。
首先，作为一种图示组合模型，具有直观、易懂和易用的优点，它能形象化地描述和分析系统的资源并发、同步(或异步)、并行、冲突分布等行为特征。
其次，Petri 网又有严格而准确的数学描述，可以借助数学工具得到 Petri 网的分析方法和技术，可以对 Petri 网进行静态的结构分析和动态的行为分析，能与随机过程论、信息论结合在一起描述和分析系统的不确定性或随机性。
Petri 网是由节点和有向弧组成的一种有向图。
它有两类节点，一类称为库所(Place)，另一类称为变迁(Transition)，两类元素之间的连接用有向弧表示。
Petri 网中另一重要元素是令牌(token)，代表系统的条件、资源、状态等。
令牌在库所中的分布称为标识，用来。
描述网系统的状态，其中网的初始标识记为M2、一个网上购物的例子用户小王(买方)正和一个网上商店服务器(卖方)通信以购买商品。
为此小王需要发送她的信用卡细节给公共服务器(她已认证并确信和她通信的不是入侵者)。
小王除了想确保她的信用卡细节在传输中不被偷看外(用加密实现)，还希望确保交易细节在到达服务器前不受任何改变。
商店服务器需要使小王以后不能否认已完成的购买，并且需要小王已授权服务器支取她的信用卡帐目。
为此，可用数字签名：既为小王提供数据完整性，又为网上商店服务器提供不可否认功能。
小王可用私钥为消息产生和添加数字签名，当网上商店服务器接收到该消息后，它用小王的公钥检查数字签名，验证它是否与消息内容匹配。
若是，则消息一定是小王发出的，因为只有小王知道其私钥，这样就提供了不可否认。
