Petri网与CDFG相结合的调度模型及其调度技术的研究

论文提出一种Petri网与控制数据流图(CDFG)结构相结合的调度模型,以及基于该模型的调度技术。Petri网表示VHDL源描述中的I/O时序信息,Petri网同一个位置结点中的信号赋值都是在同一个时刻进行的。根据每个位置结点中的语句再生成各自的CDFG。CDFG中条件的计算显式地表示在数据流部分,便于操作的调度。该CDFG结构上前驱操作和后继操作的判断不但与数据依赖相关,还与操作的条件相关。调度过程中既要考虑直接的数据依赖关系,还要考虑与条件相关的间接依赖关系。传统的调度算法需要经过修改才能应用到该模型上。     

基于平行Petri网的制造系统调度与控制一体化方法

为了消除制造系统调度层与控制层之间的隔阂,实现对生产事件快速灵活响应,本文提出了一种调度与控制一体化的方法.首先,定义了一种新型Petri网模型,即平行Petri网,从而集成地描述了传感器、执行器、任务和资源信息,构建制造系统的信息物理系统模型;其次,提出了一种从平行Petri网到赋时Petri网的抽象简化方法,大规模压缩优化调度所需搜索的状态空间;再次,定义了策略Petri网以描述最优调度策略.最后,给出了平行Petri网与策略Petri网同步执行算法,使得平行Petri网与物理系统同步执行.     

基于带抑制弧的Petri网的min-min算法模型研究*

为了解决已有的min-min算法Petri网模型不能模拟min-min算法运行过程的问题,根据min-min算法的调度特点,利用带抑制弧的Petri网提出了一种算法模型,该模型运行过程可以严格模拟min-min算法对独立任务集的调度顺序,能够正确地描述独立任务调度系统使用min-min算法的情况。最后对该模型的空间复杂度以及每调度一个任务模型的变化情况进行了分析,随着独立任务的调度执行,该基于带抑制弧的Petri网的变迁数和弧数会随之减少,模型的空间复杂度会不断降低。     

基于Petri网推理的监控视频事件识别

Petri网模型对复合时序事件具有较好的描述和检测能力,提出基于Petri网描述和推理的监控视频事件信息的自动识别方法。将运动目标及其特征间的空间关系用Petri网的库表示,时间关系及其他推理规则用变迁表示,结合低级计算机视觉算法获得的运动目标特征以及基本事件信息,通过对Petri网推理执行,实现监控视频复杂语义事件的交互式查询,通过实验验证了该方法的有效性。     

作战事件跟踪描述建模及验证方法研究

为了对体系结构设计中的作战事件跟踪描述进行建模分析,提出了用扩展时序图模型对作战事件跟踪描述进行建模的方法。定义时序图的生命线为时间消息,研究了时序图模型与Petri模型之间的同构关系,以此为依据给出了时序图转换为Petri网的算法。在此基础上,研究了扩展时序图和对象Petri网之间的转换算法,并处理了扩展时序图中的自环消息特例。最后,结合防空作战过程给出该方法的一个应用案例。     

网上证券交易系统的时序Petri网描述及验证

基于时序Petri网对我国现行网上静态和动态证券交易系统进行了模拟、形式描述及功能正确性验证.应用时序逻辑推理规则,从形式上严格证明了证券交易系统需求规范及其时序Petri网模型动态行为的一致性.结果表明,时序Petri网能够清楚而简单地描述事件间的因果关系和时序关系以及并发系统中某些与时间有关的重要性质,如最终性和公平性.因此,时序Petri网可作为并发系统形式化描述和分析的有力工具.     

基于Petri网的Web服务BPEL4WS建模与分析

描述了Web服务业务流程执行语言(BPEL4WS或BPEL)的Petri网建模方法，利用网结构描述基于Web服务业务流程的行为特性。在对BPEL4WS的结构性活动和故障补偿处理机制进行逐层分析的基础上，提出了一个利用Petri网的逐步求精技术对流程进行建模的算法。然后结合具体实例阐述了利用该算法建模的详细过程，并对所生成的Petri网模型进行了完整性（soundness)验证     

基于知识Petri网和归结规则的推理方法

本文提出了一种基于知识Petri网和归结规则的推理方法.通过知识Petri网描述命题逻辑知识库,将归结规则映射到知识Petri网上,根据库所和变迁的连接关系,定义了知识Petri网中的归结结构.利用归结结构,给出了基于知识Petri网的归结推理算法和扩展知识库的推理算法,并利用Wumpus实例验证了推理算法.该推理方法是可靠且完备的,能够利用知识Petri网的网络结构降低计算复杂性.     

一种基于时变Petri网的服务组合质量检验方法

为了解决动态服务组合过程中功能执行时序与工作流的关系问题,提出了一种基于时变Petri网技术的Web服务组合模型.引入Petri网有向网结构来描述组合过程中输入/输出功能及时间因素影响,以Petri网的有向弧结构表示服务组合过程中服务功能时间参数输入/输出表达式,利用时变函数表示服务的时间消耗,进而将服务组合转化为时变Petri网的流程正确性检验和时间开销优化问题,使建立的服务组合模型在组合成功率和用户满意度间达到良好的动态平衡.提出了一种基于回溯方法的服务组合流程检验和QoS计算方法,用于时变Petri网系统下服务组合策略的构建和验证.为了说明该方法的有效性,以一个实际电厂信息调度平台系统提供的Web服务为研究对象,通过两组仿真实验,分别说明该方法具有良好的组合成功率及使用相同候选服务集构建组合策略的有效性.实验数据和结果分析表明,该建模方法能够达到特定用户对服务功能的使用需求.     

基于Petri网与GA算法的FMS调度优化

提出了一种应用遗传算法解决柔性制造系统调度优化问题的新方法．首先用Petri网对柔性制造系统进行建模,然后应用遗传算法对该模型进行调度并获取近似最优解．在该算法中,用Petri网模型的激发序列作为染色体,采用期望值方法作为选择算子,总加工时间作为适应度函数,两点交叉法作为交叉算子,交叉点选择能到达相同标记的转移．对于变异算子,首先从染色体上随机选择一点作为变异点,然后从这点开始应用变异算法,该变异算法类似于Petri网的可达树算法．由于算法中的选择、交叉和变异算子都是对．Petri网模型中的元素进行操作,与问题空间中的元素无关,因此,与其它调度算法相比,它有较高的通用性．既可以处理典型的Job—Shop问题,也可以处理小批量、多品种的FMS(Flexible Manufacturing System)调度问题．文中通过实验验证了算法的有效性。     

Petri网到VHDL的翻译器设计与实现

研究了如何用CONPAR语言对Petri网图形进行描述,来获得Petri网模型对应的等效文本文件;然后设计了由Petri网文本文件到VHDL转换的文法规则及对应的语义动作源文件,并由编译工具YACC自动生成Petri网到VHDL转换的语法分析器;语法分析生成的中间代码是一棵抽象语法树,可以自顶向下遍历此抽象语法树,并按照相应的语义规则,通过比较Petri网文本描述和VHDL代码的差别生成VHDL目标代码;由此实现了Petri网到VHDL的翻译器,为基于Petri网的并行控制器的自动硬件实现提供了一种快速有效的方法。     

着色Petri网模型检测工具的扩展及其在Web服务组合中的应用

Web服务组合的形式化描述和验证是一个重要的研究问题.为了更好地完成验证工作,提出了扩展着色Petri网的模型检测方法.首先,在着色Petri网原有的基于CTL的局部模型检测算法基础上,给出了获取模型检测证据/反例的算法,并在着色Petri网模型检测工具--CPN Tools--中使用ML(meta language)语言实现了这些算法,然后将扩展后的CPN模型检测工具应用在Web服务组合的验证问题中.该方法不仅可以验证Web服务组合是否存在逻辑错误,还能告诉用户发生错误的原因,为Web服务组合的验证提供了技术上的保障.实验表明对着色Petri网的模型检测工具的扩展是正确、有效的.     

一种自适应负载的I/O调度算法

I/O调度算法对磁盘阵列(RAID)性能具有至关重要的影响。虽然已有很多典型的I/O调度算法在一定负载情况下可获得较好的性能,但很难有哪一种算法在各种负载情况下均能获得很好的性能。本文提出了一种智能RAID控制模型,结合C4.5决策树和AdaBoost算法实现负载自动分类,根据负载变化和性能反馈情况动态调整I/O调度策略,实现面向应用需求的自治调度。模拟实验结果表明,自适应调度算法具有较好的适应性,在各种负载情况下优于现有的I/O调度算法,尤其适用于多线程混合负载环境的I/O性能优化。     

考虑非确定加工时间的柔性作业车间调度问题研究

加工时间不确定的柔性作业车间调度问题已逐渐成为生产调度研究的热点。采用区间表示加工时间范围,利用时间Petri网建立区间柔性作业车间调度问题形式化模型,并运用网模型的状态类图进行可达性分析,计算出所有可行变迁触发序列。通过对触发序列的时序分析,提出一种有效的逆向分步法来构造触发序列的时间约束不等式,进而求解线性规划问题来获得最小完工时间下界(上界)的优化调度策略。最后利用实例分析验证了模型及所提方法的正确性和可行性,为实际的区间柔性作业车间调度问题提供有效方案。     

P/T系统的VHDL描述及实现

利用超高速集成电路硬件描述语言(VHDL)描述P/T系统,在EDA软件平台MAX+plusII上,对Petri网模型的VHDL描述进行编译、仿真、适配,将结果下载到可编程逻辑器件中,通过实验开发系统GW48-CK进行硬件测试。给出一个P/T系统实例——服务系统的描述及实现。仿真波形及硬件测试结果证明了该方法的正确性。     

Petri网仿真和自动化分析中的存储结构及算法研究

存储结构及算法是Petri网仿真和自动化分析研究中的重要内容，Petri网是一种特殊的有向图，通过对图的存储问题进行研究，提出了一种有向图的存储结构-树链式结构，给出了其构造算法，与其它有向图存储结构相比，它既可提高算法速度又能降低算法复杂性，树链式结构在Petri网仿真和自动化分析中应用优势明显，着重讨论了Petri网的树逻式存储结构，提出了基于该存储结构的可达树生成算法，所生成的可达树的树链结构形式，利于展开Petri网的各种分析算法。     

移动网可达树

随着计算机技术和网络通信技术的高速发展,对于并发分布式系统,已经提出了进程代数以及Petri网等形式化分析方法。近年来由于移动互联网的出现和快速发展,通过在进程代数中增加移动性得到了pi演算,与此同时,Petri网领域也采用谓词/变迁网、颜色网等构建移动系统模型。但它们仍存在一些不足之处。在此基础上,A.Asperti和N.Busi提出了移动网这一系统模型。移动网是在Petri网的基础上增加了移动性并结合了进程代数的优势得到的,适用于描述和刻画移动计算系统。然而,目前并没有对于移动网相应分析方法的研究。为此开展了移动网模型分析方法的研究,给出了移动网可达树的构造算法,提供了移动网模型可达性分析方法,并对移动车辆电话通信系统实例进行了分析。