【作者】 王安荣；

【导师】 贾建援；

【作者基本信息】 西安电子科技大学 ， 机械制造及其自动化， 2009， 博士

【摘要】 在诸如柔性制造系统、半导体生产线等这样的典型离散事件系统中,由于资源的分配不合理会导致死锁的产生.死锁不仅会导致生产率的下降,而且可能会造成灾难性的后果. 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网为分析工具的离散事件监督控制理论均具有重要的意义.更多还原

【Abstract】 Deadlocks caused by improper resource allocation in ?exible manufacturing sys-tems and semiconductor production lines that are the representatives of discrete eventsystems, can directly lead to the deterioration of productivity and fatal results. Petrinets are one of commonly used mathematical tools for modeling and analysis of dis-crete event systems. Deadlock prevention and deadlock avoidance have been twoprimary methodologies for handling deadlocks in Petri nets for the last two decades. Adeadlock prevention policy provides an of?ine resource allocation mechanism , whilea deadlock avoidance one needs an online decision-making algorithm. A monitor andrelated arcs are added for every emptible minimal siphon in a plant Petri net model bytraditional deadlock prevention methods in literature. Since siphons are a structuralobject of Petri nets and in theory, their number has an exponential relationship withthe net size, the structure of a large-sized Petri net’s supervisor is usually too com-plicated to manage. The theory of elementary siphons has proved that a supervisorcan be computed and its size is linear with the size of the plant net model. But siphonenumeration is required for the purpose of determining a set of elementary siphons. Astate explosion problem is the bottleneck of the traditional deadlock avoidance policiesthat ensure a live net by forbidding its evolution into deadlocks. Usually, all reachablemarkings of the net are required to be known in advance and stored in memory.This dissertation aims to tackle the limitations mentioned above and the mainresults of this research are as follows.First, by studying the structure of S3PR nets, a subclass of Petri nets, it is provedthat the rank of the complementary matrix of an S3PR net is equal to the number ofits elementary siphons. Combining Petri nets and graph theory, the definitions of re-source digraphs of an LS3PR net and resource digraphs of an S3PR net are proposedrespectively. In an LS3PR net, it is verified that there exists a bijective mapping froma strongly connected block of its resource digraph into a strict minimal siphon. In anS3PR net, it is verified that there exists a bijective mapping from a strongly connectedcontributing subdigraph of its contributing resource digraph into a strict minimal siphonin it. An algorithm is given by which the number of elementary siphons of an LS3PRnet can be determined, and it is verified that the algorithm is of polynomial complexitywith respect to the number of resource places of the plant net. Based on the aboveresults, an algorithm for determining the number of elementary siphons in an S3PR net is developed, and it is verified that in the worst case this algorithm has an exponentialcomplexity relationship with respect to the number of resource places of an S3PR net.Fortunately, in special cases this algorithm has a polynomial complexity relationshipwith the number of its resource places.Second, based on binary search, an efficient algorithm is proposed for finding aset of elementary siphons given a set of strict minimal siphons of a Petri net.Third, by studying structural properties, extended complementary set of a siphonand extended complementary matrix of an ES3PR net, a subclass of Petri nets, arenewly defined. It is proved that the rank of extended complementary matrix of anES3PR net is equal to the number of its elementary siphons. Based on these newconcepts, the resource digraphs of an ELS3PR net are accordingly proposed. It isproved that a strongly connected block of the resource digraph of an ELS3PR netcorresponds to a siphon in it. Furthermore, a method to find the set of strict minimalsiphons is proposed.Fourth, a two-step deadlock avoidance policy is proposed. The first step is anof?ine method for calculating special markings, such as dead markings, bad markings,and dangerous markings, of the Petri net model of the system to be controlled. Thesecond step is an online method that makes sure that the system never reaches aforbidden state such as dead markings and bad markings. The major advantage ofthis policy lies in the fact that it is suitable for much larger systems than the mostavailable ones and the supervisory controller is maximally permissive. Meanwhile, thecomputation of the whole reachability graph of the Petri net is successfully avoided.The role of elementary siphons is fully and gradually recognized in simplifying thestructural complexity of liveness-enforcing Petri net supervisors. This research is ofsignificance to the theory of Petri nets and the supervisory control of discrete eventsystems in a Petri net formalism.更多还原