PN机

本文提出PN机的几种范式,讨论它们的串语言与步语言之间的关系,提出拟行为有限状态机概念,给出PN语言的一个拟正规性刻划,从而表明一般Petri网模型的局限性,以及引入PN机模型的必要性.本文结果对于PN机理论框架的建立起到奠基作用.     

Petri网的同步距离计算

同步距离是刻画事件之间同步关系的一个重要的定量分析手段。本文提出了同步距离计算网SDCNet的概念模型并讨论了计算同步距离的几个结论,给出了S_元中初始标识的配置算法以及以此为基础计算同步距离的算法。分析表明该算法与可覆盖性树的生成算法具有相同的复杂性。     

功能确定的离散并发系统的Petri网规范设计方法

本文提出概念模型的概念，作为实际问题到Ｐｅｔｒｉ网模型的桥梁，也就是系统的规格说明，概念模型包括功能图，资源图和约束集三部分，由此将系统设计中的功能与环境严格区分开，给出实际问题到概念模型，以及概念模型到Ｐｅｔｒｉ网模型的转换算法，从而构成一个面向功能的系统的Ｐｅｔｒｉ网规范设计方法，通过一制造系统的建模，说明了该方法的规范性和有效性。     

一种面向移动导航设备的电子地图空间索引结构

传统的R-tree系列和四叉树系列对数据对象的多级显示没有给予足够的支持,在小比例尺地图的显示过程中,影响了检索效率 .即使是支持多级显示的R-tree的各种变形,也由于对资源的要求而不能满足嵌入式设备的应用需求 .针对嵌入式设备数据I/O的特点,从地图数据的分级显示、顺序与批量访问、索引数据的优化等多方面入手,提出了一种基于多级Hilbert网格的线性索引结构 .实验证明该索引结构在空间利用率和查询性能等方面与传统的空间索引技术相比有明显的改善,并在上海市交通信息网格移动交通信息服务终端上获得了良好的实施效果 .     

Petri网的广义笛积运算（II）

本文提出Ｐｅｔｒｉ网的两种新的广义笛积运算，讨论了它们的代数性质，这些结果可以作为受控Ｐｅｔｒｉ网的分析或合成的依据。     

一种双匹配动态调度算法

提出了适于异构环境独立任务调度的双匹配动态调度算法（BM算法）．BM算法将任务与处理机实现双匹配，使大部分任务在执行时间最短而且完成时间最早的处理机上执行．对于无法实现双匹配的任务，采用最早完成时间最小者优先的策略进行调度．BM算法可以同时满足负载均衡和高吞吐率两个目标．BM算法与通常用作评测基准的Min-min算法的比较结果表明，BM算法的运行时间远少于Min-min算法，其调度跨度比Min-min算法减少约9％．     

基于精炼操作的Petri网建模及其分析方法

针对复杂系统的Petri网建模及其分析问题,定义了Petri网的精炼操作及其相关的Petri网模型.基于序列投影,建立精炼Petri网与原网、子网间的动态行为关联关系,并分析了该精炼操作的相关动态性质,得到一组性质保持判据.最后,基于该方法实现了一个顺序资源共享系统的应用案例的建模及其分析.所提出的方法不仅为复杂系统的Petri建模提供了新的思路,而且有助于复杂Petri网模型的分析和验证.     

Petri网化简规则在系统中的实现

Petri网是分析系统的一种很好的数学和图形工具。网的复杂性随着网中可达状态和变迁数目的增加而大大增加。这就使得对一个复杂网分析的难度不易控制。对此,提出了化简的思想,降低复杂度后再分析。文章将化简规则转化成算法,并在实际系统中实现。     

动态网络最短路问题的复杂性与近似算法

有向网络的最短路问题在交通、通信系统的最优路径计算以及多阶段决策过程的最优轨线设计等实际问题中有着重要应用.经典模型及算法解决固定弧权条件下的最短路问题,而实际中,网络往往是动态的,即弧权依赖于时间变化,例如在交通拥堵时运行时间会变长,这时经典的最短路算法不再适用.文中证明了动态网络的最短路问题是NP-困难的;给出了最短路稳定性的充要条件,并在此基础上提出一种基于稳定区间的近似算法,通过模拟实验验证了该算法的有效性.