模拟实时系统的点区间优先级时间Petri网与TCTL验证

时间Petri网为实时系统提供了一种形式化的建模方法,时间计算树逻辑(TCTL)为描述实时系统与时间相关的设计需求提供了一种逻辑化的表达方式,因此,基于时间Petri网的TCTL模型检测广泛应用于实时系统的正确性验证.然而对于一些涉及优先级的实时系统,例如多核多任务实时系统,这里不仅需要考虑任务之间的时间约束,还要考虑任务执行的优先级以及引入优先级带来的抢占式调度问题,致使相应的建模和分析变得更加困难.为此,提出了点区间优先级时间Petri网,通过在时间Petri网上定义变迁发生的优先级以及变迁的可挂起性,从而可以模拟实时系统的抢占式调度机制.首先,高优先级的任务抢占低优先级的任务所占用的资源,导致后者被中断;然后,前者执行完毕后释放资源;最后,后者再次获得资源,从中断的地方恢复.通过点区间优先级时间Petri网来模拟多核多任务实时系统,使用TCTL来描述它们的设计需求,设计了相应的模型检测算法,开发了相应的模型检测器以验证它们的正确性.通过一个实例,来说明该模型和方法的有效性.

一种基于用例及优先级策略时间Petri网的建模方法

在给出用例及其相关概念的形式化定义的基础上,构建了从用例到具有优先级策略的时间Petri网模型映射的实施方法;提出了一种基于用例和Petri网的建模方法.它先以用例来捕获需求,再用具有优先级策略的时间Petri网来图形化用例,以此来实现它们各自优势的互补。

基于时间Petri网的区间作业车间调度问题建模与分析

区间作业车间调度问题近年来已成为生产调度研究的热点,现有研究工作主要集中于问题描述和优化求解方面,在理论模型、动态性质等方面还缺乏实质性成果.使用时间Petri网模型建模区间作业车间调度问题,并运用状态类可达性分析方法,分析模型所有可行调度,进而求解具有最小下界和最小上界的优化调度,为区间作业车间调度问题的建模与分析提供有益参考.

一种离散时间区间Petri网

运用Petri网对实际系统进行建模时,事件的发生往往必须在一个时间区间序列内。针对此问题,提出一种离散时间区间Petri网模型。着重对模型的可达性进行了分析,给出模型的合法变迁序列判定算法,并在此基础上提出模型的状态可达性判定算法。通过实例分析,验证了所提的离散时间区间Petri网模型的可行性和有效性,该模型可用于工作流分析、业务过程建模等领域,能够进一步增强Petri网对离散事件系统的模拟与分析能力。

时间Petri网的时间知识推理算法及在铁路智能运输系统中的应用

介绍一种基于时间Petri网的时间知识推理算法,它是在已有算法的基础上,引入模糊时间区间的操作进行扩展而形成。该算法可一次性构建相应的时间知识系统的生成图,再用生成图进行时间知识验证和推理,相对于已有的算法来说,具有效率高、可处理时间区间的不确定性问题等优点。针对列车运行的时间知识系统进行算法的应用研究得出:本算法可验证时间约束的列车运行调整方案的可行性;能验证铁路专家系统中时间知识的一致性问题;用生成图可推导出某些带时间约束事件同时发生的可能性等。

时间Petri网保持活性、有界性的两个充要条件

活性和有界性是Petri网最重要的性质,对于传统Petri网的这些性质,国内外学者作过大量的研究工作,并且得到了不少成果,而对舍时间因素的Petri网的这些相应性质国内外研究得很少。本文首先介绍了时间Petri网TPN的若干基本定义,然后说明了时间Petri网TPN的活性、有界性和对应传统Petri网的相应性质并无关系,接着给出了时间Petri网保持活性、有界性的时间区间上的两个充分必要条件。为利用传统Petri网的性质判定结果来判定时间Petri网的相应性质提供了可能性。

时间Petri网的随机模拟

模拟是Peri网进行系统分析的常用方法之一。由于时间Petri网采用时间区间来描述变迁实施的时间范围,因此变迁的实施时间点在区间内是不确定的。提出了时间Petri网的随机模拟方法。该方法在变迁开始使能时,根据某种随机分布确定实施区间内的实施时间点;然后基于模拟仿真的实验数据,运用统计分析方法及算法,构造时间Petri网状态类树,计算变迁实施区间及实施概率,为时间Petri网的系统模拟提供了一种新的探索途径。

基于时间贝叶斯Petri网的溯因故障诊断

针对复杂系统发生故障时告警信号间的时序约束关系,提出一种时间贝叶斯Petri网模型(TBPN),并基于该模型提出一种复杂系统的溯因故障诊断方法。该方法首先对观测到的告警信息建立时间Petri网,随后将其求逆并转换为TBPN。通过时间区间计算和溯因推理,分析告警信号的时序一致性并验证故障假说,最后对时序正确的故障事件链计算其故障概率并进一步分析干扰信息。仿真实验表明,该方法可对复杂故障进行快速诊断,并在告警信息存在丢失、虚警、时标差错时表现出较好的鲁棒性。与不考虑时间约束的同类方法相比,该方法具有搜索空间更小,抗干扰性更强的特点。

基于优先级时间Petri网的实时嵌入式多核系统分析

已有的基于点区间优先级时间Petri网分析实时嵌入式多核系统的工作,存在以下不足:(1)点区间优先级时间Petri网只考虑每个任务的执行时间是一个固定值的情况,而更多的实际应用中每个任务的执行时间是在一个区间范围内,因此不能模拟这些应用;(2)没有实现从任务依赖图到点区间优先级时间Petri网的自动转化,不便于工程设计人员使用;(3)没有考虑任务间互斥访问共享变量的情况.为此,定义了优先级时间Petri网(Pri-TPN)以弥补第1个不足;定义带有资源分配与优先级的任务依赖图(TDG-RAP)以弥补第3个不足;给出从TDG-RAP到Pri-TPN的转化规则与算法以弥补第2个不足,以及基于Pri-TPN分析任务最坏执行时间与系统死锁的算法;开发工具软件,方便工程设计人员使用.

基于逻辑数据Petri网的业务过程建模与分析

为了解决逻辑Petri网中处理托肯优先级的问题,结合逻辑Petri网和时间Petri网的思想,提出逻辑数据Petri网、引发规则及其可达图。在该网中,为每个托肯添加了属性和到达时间,为逻辑输入、输出变迁添加了批处理等待时间和变迁引发持续时间,为普通变迁添加了引发持续时间。针对托肯定义了属性、时间删除函数和写函数,对库所中托肯的属性和到达时间进行了操作。建立了基于逻辑数据Petri网的电子商务系统模型,构建了可达图并重新定义了可达图中的状态信息,分析了优先级不同的托肯的时间优越性以及系统处理用户请求时的公平性。

基于Petri网的物流仓库多AGV调度方法的研究

针对多自动导引车(AGV)在大规模物流仓储中存在的路径规划问题,对基于时间Petri网的多AGV调度优化算法进行了研究。该算法利用时间Petri网对大规模双向车道环境下多AGV的仓库调度过程进行建模,并在分解后对AGV进行单独分析,减少了算法的时间复杂度;引入传统外点惩罚函数法构建以AGV调度时间为指标的目标函数,通过对AGV运行路径信息的依次迭代和更新解决了其在调度过程中的碰撞问题;在此基础上增加碰撞类型分析,以目标函数最优为原则对路径进行局部规划,实现调度方案最优。实验结果表明在大规模调度环境中该算法能快速收敛出无碰撞死锁的最优路径方案,并能保证多AGV在动态仓库物流调度中具有良好的实时适应性。

不确定性时间知识推理和验证算法及列车群建模分析

时间知识的推理和验证技术对列车群行为建模分析具有重要意义,是其实施关键。本文在原来工作的基础上,引入模糊时间区间、扩展模糊时间Petri网(EFTPN)及可能性值运算等内容,提出了一种基于EFTPN的不确定性时间知识推理和验证算法。该算法效率高,占用空间少;不但能够进行不确定性时间信息的精确推理,而且适用面更广,可以较好解决复杂情况下的时间推理和验证问题。

TCPN的可调度性及调度区间的约束分析

时间约束 Petri网 (TCPN)通过引入时间因素 ,增强了对网的时间约束的描述能力。但由于TCPN网拓扑结构的多样性以及时间约束的复杂性 ,使得网的可调度性及调度区间的分析十分困难。针对常见的如顺序、并发、同步、冲突等拓扑结构 ,对变迁的可成功调度与否以及影响调度区间的约束条件进行了分析和研究 ,简化了 TCPN网的可达性与可调度性的分析方法。

ICPN的时间自动机构造方法

为克服Petri网行为演变分析技术的局限性,利用时间自动机技术分析区间速率连续Petri网(ICPN)特性。根据区间速率连续Petri网模型语义提出基于冲突消解的区间速率连续Petri网状态演变图构造算法,给出状态演变图的时间自动机构造方法。对某化工生产过程的分析表明了该方法的必要性和有效性。

基于PTCPN的协同维修操作冲突建模

针对3D仿真环境下复杂系统协同维修过程中出现的操作冲突问题,提出由角色属性及零件属性决定的相似度优先级的概念。结合协同维修多人操作及并行操作的特点,采用CPN Tools建模仿真工具,建立相似度优先级模块并引入反库所,在优先级时间着色Petri网(PTCPN)基础上对3D仿真环境下协同维修过程中冲突建模。经3D维修平台上验证,模型可以有效地削减操作冲突。

导弹部队机动作战过程的DTSPN模型

为了在建立导弹部队机动作战过程Petri网模型时充分体现其时间特性,定义了一种离散时间区间Petri网(discrete time span Petri net,DTSPN);在充分考虑敌方侦察威胁对部队机动作战影响的基础上,将各阶段任务实施的时机限定在一个离散时间区间序列内,建立了导弹部队机动作战过程的DTSPN模型;通过对模型的可达性分析,判定作战任务能否按时完成;实验结果显示,提出的DTSPN能够体现导弹部队机动作战过程的时间特性,并能够分析作战任务能否在有利于作战行动实施的时间间隙内按时完成。