LS3PR网信标数目与网结构之间的关系研究

摘要

柔性制造系统是典型的离散事件系统，不合理的资源分配会导致死锁的产生。死锁不仅会导致生产率的下降，而且可能会造成灾难性的后果。Petri网是对离散事件系统进行建模和分析的主要数学工具之一。信标是 Petri网的结构特性之一，信标清空与死锁的发生密切相关。死锁控制是近二十多年来国际 Petri网领域的一个研究热点也是难点问题。死锁控制中的两个主要方向是死锁预防和死锁避免，其中死锁预防是一种离线的控制策略，而死锁避免是一种在线的控制策略。死锁预防方法通过对Petri网模型中的可被清空信标添加控制库所和控制弧来达到死锁控制的目的。随着信标数目的增加，Petri网监督控制器的结构更加复杂。理论上，信标的数目与 Petri网的规模呈指数关系。
　　柔性制造系统的一种Petri网模型为LS3PR网，该类网中可被清空信标总是严格极小信标。现有文献已经证明，LS3PR网中的严格极小信标与其资源有向图中的强连通块之间存在一一对应的关系，并且当资源有向图为全图时，严格极小信标的数目与系统中的资源数目呈指数关系。但是，当 LS3PR网的资源有向图不是全图时，严格极小信标数目与资源数目之间的关系还没有得到仔细研究。本文针对这一问题展开研究，研究的具体内容是：LS3PR网资源数n已知，且资源有向图中的边数 E满足条件E≤2?（n?1)，确定资源有向图中的边呈现何种分布时，网中的严格极小信标数目达到最大，及这个最大数目的具体表达式。
　　显然的，在资源数目n和边数∣E∣给定的条件下，边的分布种类等于组合数C∣E∣n?(n?1)。本文借助枚举法，在资源数较小时，枚举所有的符合已知条件的资源有向图，进而找到严格极小信标数目较多的几种典型结构。然后，通过严格的数学证明，给出了在∣E∣=2?（n?1)的条件下，取得最大严格极小信标数目的边分布结构为星形方式分布，且此时对应的严格极小信标数目表达式为max∣Π∣=2n-1?1。论文又进一步推出，当资源有向图中的边数∣E∣≤2?(n?1)、且图中的边以星形方式分布时，严格极小信标数目达到最大值。根据资源有向图，进而能够确定出相应的LS3PR网的结构。需要注意的是，同一个资源有向图，对应的LS3PR网结构可以不同。
　　对于满足∣E∣>2?(n?1)的LS3PR网，“什么样的分布才能达到严格极小信标数目最多?”依然是一个有待解决的问题。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1 课题研究背景

1.2 国内外研究现状

1.3 论文组织结构

第二章 图论基本理论

2.1 笛卡尔集和无序集

2.2 图的基本概念

2.3 图的图形表示

2.4 一些图的种类

2.5 图的子图

2.6 路与连通

2.7 小结

第三章 Petri网的基本知识

3.1 Petri网的定义

3.2 结构不变式

3.3 信标和陷阱

3.4 Petri网的基本信标理论

3.5 Petri网的子类

3.6 小结

第四章 LS3PR网资源有向图及其SMS

4.1 LS3PR的资源有向图

4.2 LS3PR的SMS与资源有向图的关系

4.3 LS3PR网资源有向图为全图时的SMS数目

4.4 小结

第五章 LS3PR网的SMS数目

5.1 资源有向图的特性

5.2 星形结构、线形结构和环形结构的信标计算

5.3 三种典型结构对应SMS值的比较

5.4 星形结构的组合

5.5 任意分布结构

5.6 对星形结构的补充讨论

5.7 小结

第六章 全文总结

附录A

参考文献

致谢

作者简介