论文部分内容阅读
在诸如柔性制造系统、半导体生产线等这样的典型离散事件系统中,由于资源的分配不合理会导致死锁的产生.死锁不仅会导致生产率的下降,而且可能会造成灾难性的后果. Petri网是对离散事件系统进行建模和分析的主要数学工具之一.死锁预防和死锁避免是近二十年来死锁控制方法中的两个主要研究方向.死锁预防是一种离线的资源分配机制,而死锁避免是一种在线决策算法.传统的死锁预防方法对系统Petri网模型中的每个可被清空的极小信标添加一个控制库所和多条控制弧,从而达到死锁控制的目的.由于信标是Petri网的一个结构特性,在理论上,信标的数量与Petri网的规模呈指数关系,所以规模较大Petri网的控制器结构过于复杂.基本信标理论已从理论上证明可以得到与Petri网规模呈线性关系的受控Petri网模型,但在确定一组基本信标时同样受到枚举Petri网中所有信标问题的困扰.传统的死锁避免策略采用在线计算的方式,保证系统不要演化到死锁状态,从而达到死锁控制的目的,但是这种方法受到状态组合爆炸问题的严重制约.通常情况下,网的整个可达标识需要事先知道且存储到内存中.本论文针对以上两种死锁控制策略中的瓶颈问题展开研究,取得的主要研究结论如下.第一,通过对Petri网的子类S3PR网的结构分析,得出该类Petri网的补集矩阵的秩等于基本信标数目的结论.结合Petri网理论和图论,分别给出了LS3PR和S3PR网的资源有向图的概念,分别证明了在资源有向图和有效资源有向图中的强连通块对应LS3PR和S3PR网中的一个严格极小信标的结论.对于LS3PR网给出了一种确定基本信标数目的算法,并且证明该算法的计算时间复杂度为LS3PR网中资源库所数目的多项式时间复杂度.基于以上结论,提出了一种确定S3PR网中基本信标数目的算法,并且证明最坏情况下该算法的计算时间复杂度为S3PR网中资源库所数目的指数时间复杂度.值得庆幸的是,在特殊情况下,该算法依然是S3PR网中资源库所数目的一个多项式算法.第二,在已知Petri网中部分或全部严格极小信标的条件下,提出了一种基于二分法原理确定一组基本信标的快速算法.第三,通过对ES3PR子类的结构分析,提出扩展补集和扩展补集矩阵的概念,同时证明了扩展补集矩阵的秩等于基本信标数目的结论.在这些概念的基础上,给出了ELS3PR网资源有向图的概念,证明了ELS3PR网资源有向图中的一个强连通块对应网中的一个信标的结论,进而给出了基于资源有向图的求取ELS3PR网中所有严格极小信标的算法.第四,给出了一种分两步走的死锁避免策略,该策略中首先离线计算出网系统中的特殊标识,包括死标识、坏标识和危险标识,然后在线控制时,仅保证系统不要到达禁止标识,包括死标识和坏标识.相对于现有的大多数死锁避免策略而言,本文给出的策略适于控制大的系统,控制器的许可行为最大,而且成功避免了对系统的Petri网模型的整个可达图的计算.基本信标理论在简化活性Petri控制器结构方面的作用正在日益深入地得到了解和认识.本文的研究工作对于Petri网理论以及以Petri网为分析工具的离散事件监督控制理论均具有重要的意义.