Petri网基本信标的求取算法及死锁避免策略研究
|
摘要
在诸如柔性制造系统、半导体生产线等这样的典型离散事件系统中,由于资源的分配不合理会导致死锁的产生.死锁不仅会导致生产率的下降,而且可能会造成灾难性的后果. 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网为分析工具的离散事件监督控制理论均具有重要的意义.
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.
本论文针对以上两种死锁控制策略中的瓶颈问题展开研究,取得的主要研究结论如下.
第一,通过对Petri网的子类S3PR网的结构分析,得出该类Petri网的补集矩阵的秩等于基本信标数目的结论.结合Petri网理论和图论,分别给出了LS3PR和S3PR网的资源有向图的概念,分别证明了在资源有向图和有效资源有向图中的强连通块对应LS3PR和S3PR网中的一个严格极小信标的结论.对于LS3PR网给出了一种确定基本信标数目的算法,并且证明该算法的计算时间复杂度为LS3PR网中资源库所数目的多项式时间复杂度.基于以上结论,提出了一种确定S3PR网中基本信标数目的算法,并且证明最坏情况下该算法的计算时间复杂度为S3PR网中资源库所数目的指数时间复杂度.值得庆幸的是,在特殊情况下,该算法依然是S3PR网中资源库所数目的一个多项式算法.
第二,在已知Petri网中部分或全部严格极小信标的条件下,提出了一种基于二分法原理确定一组基本信标的快速算法.
第三,通过对ES3PR子类的结构分析,提出扩展补集和扩展补集矩阵的概念,同时证明了扩展补集矩阵的秩等于基本信标数目的结论.在这些概念的基础上,给出了ELS3PR网资源有向图的概念,证明了ELS3PR网资源有向图中的一个强连通块对应网中的一个信标的结论,进而给出了基于资源有向图的求取ELS3PR网中所有严格极小信标的算法.
第四,给出了一种分两步走的死锁避免策略,该策略中首先离线计算出网系统中的特殊标识,包括死标识、坏标识和危险标识,然后在线控制时,仅保证系统不要到达禁止标识,包括死标识和坏标识.相对于现有的大多数死锁避免策略而言,本文给出的策略适于控制大的系统,控制器的许可行为最大,而且成功避免了对系统的Petri网模型的整个可达图的计算.
基本信标理论在简化活性Petri控制器结构方面的作用正在日益深入地得到了解和认识.本文的研究工作对于Petri网理论以及以Petri网为分析工具的离散事件监督控制理论均具有重要的意义.
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.
引文
[1] Ramadge P. J., Wonham W. M. Supervisory control of a class of discreteevent processes. SIAM Journal on Control and Optimization, 25(1):206–230,1987.
[2] Ramadge P. J., Wonham W. M. Modular feedbank logic for discrete eventsystems. SIAM Journal on Control and Optimization, 25(5):1202–1218,1987.
[3] Ramadge P. J., Wonham W. M. The control of discrete event systems.Proceedings of the IEEE, 77(1):81–98, 1989.
[4] Cao X. R., Cohen G., Giua A., Wonham W. M., Van Schuppen, J. H.Unity in diversity, diversity in unity: retrospective and prospective viewson control of discrete event systems. Journal of Discrete Event DynamicSystems: Theory and Applications, 12(3):253–264, 2002.
[5]吴哲辉. Petri网导论,第1版,第1次印刷.机械工业出版社, 2006.
[6] David R., Alla H. Petri nets and Grafcet. Prentice Hall, 1992.
[7] David R., Hassane A. Petri nets for modeling of dynamic systems-a survey.Auotomatica, 30(2):175–202, 1994.
[8] David R. Grafcet: a powerful tool for specification of logical controller.IEEE Transactions on Control Systems Technology, 3(3):253–268, 1995.
[9]王寿光,林善法,张有兵.基于Grafcet的电梯控制系统建模.系统仿真学报,19(Suppl.1):263–270, 2007.
[10] Kumaran T. k., Chang W., Cho H., Wysk A. A structured approach to deadlockdetection, avoidance and resolution in flexible manufacturing systems.International Journal of Production Research, 32(10):2361–2379, 1994.
[11] Wysk R. A., Yang N. S., Joshi S. Resolution of deadlocks in flexible manufacturingsystems: avoidance and recovery approaches. Journal of ManufacturingSystems, 13(2):128–138, 1994.
[12] Viswanadham N., Narahari Y., Johnson T. Deadlock prevention and deadlockavoidance in flexible manufacturing systems using Petri net models.IEEE Transactions on Robotics and Automation, 6(6):713–723, 1990.
[13] Hsieh F. S., Chang S. C. Dispatching-driven deadlock avoidance controllersynthesis for flexible manufacturing systems. IEEE Transactions on Roboticsand Automation, 10(2):196–209, 1994.
[14] Hsieh F. S. Fault-tolerant deadlock avoidance algorithm for assembly processes.IEEE Transactions on Systems, Man, and Cybernetics, Part A,34(1):65–79, 2004.
[15] Banaszak Z., Krogh B. H. Deadlock avoidance in flexible manufacturingsystems with concurrently competing process flows. IEEE Transactions onRobotics and Automation, 6(6):724–734, 1990.
[16] Ezpeleta J., Recalde L. A deadlock avoidance approach for nonsequentialresource allocation systems. IEEE Transactions on Systems, Man, and Cybernetics,Part A, 34(1):93–101, 2004.
[17] Abdallah I. B., ElMaraghy H. A. Deadlock prevention and avoidance inFMS: a Petri net based approach. International Journal of Advanced ManufacturingTechnology, 14(10):704–715, 1998.
[18] Wu N. Q. Necessary and sufficient conditions for deadlock-free operationin flexible manufacturing systems using a colored Petri net model. IEEETransactions on Systems, Man, and Cybernetics, Part C, 29(2):192–204,1999.
[19] Wu N. Q., Zhou M. C. Avoiding deadlock and reducing starvation and blockingin automated manufacturing systems. IEEE Transactions on Roboticsand Automation, 17(5):658–669, 2001.
[20] Wu N. Q., Zhou M. C. Modeling and deadlock avoidance of automated manufacturingsystems with multiple automated guided vehicles. IEEE Transactionson Systems, Man, and Cybernetics, Part B, 35(6):1193–1202, 2005.
[21] Ezpeleta J, Colom J. M., Martinez J. A Petri net based deadlock preventionpolicy for flexible manufacturing systems. IEEE Transactions on Roboticsand Automation, 11(2):173–184, 1995.
[22] Fanti M. P., Zhou M. C. Deadlock control methods in automated manufacturingsystems. IEEE Transactions on Systems, Man, and Cybernetics,Part A, 34(1):5–22, 2004.
[23] Xing K. Y., Hu B. S., Chen H. X. Deadlock avoidance policy for Petri netmodelling of flexible manufacturing systems with shared resources. IEEETransactions on Automatic Control, 41(2):289–295, 1996.
[24] Lautenbach K., Ridder H. The linear algebra of deadlock avoidance-a Petrinet approach. No.25-1996, Technical Report, Institute of Software Technology,University of Koblenz-Landau, Koblenz, Germany.
[25] Zhou M. C., DiCesare F. Parallel and sequential exclusions for Petri netmodeling for manufacturing systems. IEEE Transactions on Robotics andAutomation, 7(4):515–527, 1991.
[26] Zhou M. C., DiCesare F. A hybrid methodology for synthesis of Petri nets formanufacturing systems. IEEE Transactions on Robotics and Automation,8(3):515–527, 1992.
[27] Zhou M. C., DiCesare F. Petri Net Synthesis for Discrete Event Control ofManufacturing Systems. Kluwer Academic Publishers, Boston, 1993.
[28] Jeng M. D., DiCesare F. Synthesis using resource control nets for modelingshared-resource systems. IEEE Transactions on Robotics and Automation,11(3):317–327, 1995.
[29] Jeng M. D. A Petri net synthesis theory for modeling flexible manufacturingsystems. IEEE Transactions on Systems, Man and Cybernetics, Part B,27(2):169–183, 1997.
[30] Jeng M. D., Xie X. L. Analysis of modularly composed nets by siphons.IEEE Transactions on Systems, Man, and Cybernetics, Part A, 29(4):399–406, 1999.
[31] Jeng M. D., Xie X. L., Peng M. Y. Process nets with resources for manufacturingmodeling and their analysis. IEEE Transactions on Robotics andAutomation, 18(6):875–889, 2002.
[32] Jeng M. D., Xie X. L., Chung S. L. ERCN* merged nets for modelingdegraded behavior and parallel processes in semiconductor manufacturingsystems. IEEE Transactions on Systems, Man, and Cybernetics, Part A,34(1):102–112, 2004.
[33] Chu F., Xie X. L. Deadlock analysis of Petri nets using siphons and mathematicalprogramming. IEEE Transactions on Robotics and Automation,13(6):793–804, 1997.
[34] Barkaoui K., Chaoui A., Zouari B. Supervisory control of discrete eventsystems based on structure theory of Petri nets. In Proc. IEEE Int. Conf.on Systems, Man, and Cybernetics, pp. 3750-3755, 1997.
[35] Lautenbach K., Ridder H. Liveness in bounded Petri nets which are coveredby T-invariants. In Proc. 13th Int. Conf. on Applications and Theory ofPetri Nets, Lecture Notes in Computer Science, 815:358–375, 1993.
[36] Reveliotis S. A. On the siphon-based characterization of liveness in sequentialresource allocation systems. In Proc. Int. Conf. on Applications andTheory of Petri Nets, Lecture Notes in Computer Scienc, 2679:241–255,2003.
[37] Lautenbach K. Linear algebraic calculation of deadlocks and traps. InConcurrency and Nets, pp. 315-336, 1987.
[38] Ezpeleta J., Couvreur J. M., Silva M. A new technique for finding a generatingfamily of siphons, traps, and st-Components: application to coloredPetri nets. In Advances in Petri Nets, Lecture Notes in Computer Science,674:126–147, 1993.
[39] Huang Y. S., Jeng M. D., Xie X. L., Chung S. L. A deadlock preventionPolicy for flexible manufacturing systems using siphons. In Proc. IEEE Int.Conf. on Robotics and Automation, pp. 541-546, 2001.
[40] Tricas F., Garcia-Valles F., Colom J. M., Ezpeleta J. A structural approachto the problem of deadlock prevention in processes with shared resources. inProc. Inst. Electr. Eng. 4th Workshop Discrete Event Syst., Cagliari, Italy,Aug. 26–28, 1998. pp. 273-278, 1998.
[41] Tricas F., Martinez J. An extension of the liveness theory for concurrentsequential processes competing for shared resources. In Proc. IEEE Int.Conf. on Systems, Man, and Cybernetics, pp. 3035-3040, 1995.
[42] Tricas F., Garcia-Valles F., Colom J. M., Ezpeleta J. An iterative methodfor deadlock prevention in FMSs. In Proc. 5th Workshop on Discrete EventSystems, R. Boel and G. Stremersch, Eds.Ghent, Belgium, Aug. 21–23,2000. pp. 139-148, 2000.
[43] Park J., Reveliotis S. A. Deadlock avoidance in sequential resource allocationsystems with multiple resource acquisitions and flexible routings. IEEETransactions on Automatic Control, 46(10):1572–1583, 2001.
[44] Ezpeleta J., Tricas F., Garcia-Valles F., Colom J. M. A banker’s solutionfor deadlock avoidance in FMS with flexible routing and multiresourceStates. IEEE Transactions on Robotics and Automaton, 18(4):621–625,2002.
[45] Xie X. L., Jeng M. D. ERCN-merged nets and their analysis using siphons.IEEE Transactions on Robotics and Automation, 15(4):692–703, 1999.
[46] Zouari B., Barkaoui K. Parameterized supervisor synthesis for a modularclass of discrete event systems. In Proc. IEEE Int. Conf. on Systems, Man,and Cybernetics, Washington, DC, Oct. 5–8, 2003. pp. 1874-1879, 2003.
[47] Huang Y. S., Jeng M. D., Xie X. L., Chung D. H. Siphon-based deadlockprevention policy for flexible manufacturing systems. IEEE Transactions onSystems, Man, and Cybernetics, Part A, 36(6):1248–1256, 2006.
[48] Huang Y. S., Jeng M. D., Xie X. L., Chung S. L. Deadlock preventionpolicy based on Petri nets and siphons. International Journal of ProductionResearch, 39(2):283–305, 2001.
[49] Badouel E., Darondeau P. Theory of Regions. Lectures on Petri Nets I:Basic Models, Lecture Notes in Computer Science, 1491:529–586, 1998.
[50] Uzam M. An optimal deadlock prevention policy for flexible manufacturingsystems using Petri net models with resources and the theory of regions.International Journal of Advanced Manufacturing Technology, 19(3):192–208, 2002.
[51] Ghaffari A., Rezg N., Xie X. L. Design of a live and maximally permissivePetri net controller using the theory of regions. IEEE Transactions onRobotics and Automation, 19(1):137–141, 2003.
[52] Li Z. W., Zhou M. C., Jeng M. D. A Maximally Permissive Deadlock PreventionPolicy for FMS based on Petri Net Siphon Control and the Theoryof Regions. IEEE Transactions on Automation Science and Engineering,5(1):182–188, 2008.
[53] Li Z. W., Hu H. S., Wang A. R. Design of liveness-enforcing supervisorsfor flexible manufacturing systems using Petri nets. IEEE Transactions onSystems, Man, and Cybernetics, Part C, 37(4):517–526, 2007.
[54] Li Z. W., Zhou M. C. Two-stage method for synthesizing liveness-enforcingsupervisors for flexible manufacturing systems using Petri nets. IEEE Transactionson Industrial Informatics, 2(4):313–325, 2006.
[55] Li Z. W., Zhou M. C. Elementary siphons of Petri nets and their applicationto deadlock prevention in flexible manufacturing systems. IEEE Transactionson Systems, Man, and Cybernetics, Part A, 34(1):38–51, 2004.
[56] Li Z. W., Zhou M. C. Clarifications on the definitions of elementary siphonsof Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, PartA, 36(6):1227–1229, 2006.
[57] Li Z. W., Zhou M. C., Wu N. Q. A survey and comparison of Petri netbaseddeadlock prevention policies for flexible manufacturing systems. IEEETransactions on Systems, Man, and Cybernetics, Part C, 38(2):173–188,2008.
[58] Li Z. W., Zhou M. C. On siphon computation for deadlock control in a classof Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, PartA, 38(3):667–679, 2008.
[59] Li Z. W., Zhou M. C. Control of elementary and dependent siphons inPetri nets and their application. IEEE Transactions on Systems, Man, andCybernetics, Part A, 38(1):133–148, 2008.
[60] Li Z. W., Zhang J., Zhao M. Liveness-enforcing Supervisor Design for aClass of Generalised Petri Net Models of Flexible Manufacturing Systems.IET Control Theory and Applications, 1(4):955–967, 2007.
[61] Colom J. M., Silva M. Improving the linearly based characterization of P/Tnets. In Proc. 10th Int. Conf. on Applications and Theory of Petri Nets, G.Rozenberg (Ed.), Lecture Notes in Computer Science, 483:113–145, 1989.
[62] Garcia-Valles F., Colom J. M. Implicit places in net systems. In Proc. 8thInt. Workshop on Petri Nets and Performance Models. pp. 104-113, 1999.
[63] Recalde L., Teruel E., Silva M. Improving the decision power of rank theorems.In Proc. IEEE Int. Conf. on Systems, Man, and Cybernetics. pp.3768-3773, 1997.
[64] Silva M., Teruel E., Colom J. M. Linear algebraic and linear programmingtechniques for the analysis of place/transition net systems. In Lectures onPetri Nets I: Basic Models, Lectures Notes in Computer Science, 1491:309–373, 1998.
[65] West D. B. Introduction to graph theory(Second Edition 2001)影印版.北京：机械工业出版社, 2004.
[66] Weiss M. A. Java数据结构与算法分析(影印版)(Data Structures and AlgorithmAnalysis in Java).科学出版社(Addison-Wesley Publishing LongmanInc.), 2004(1999).
[67] Bondy J. A., Murty U. S. R. Graph Theory with Applications. The MacmillanPress LTD, 1976.
[68] Tutte W. T. Graph theory. Cambridge University Press, 2001.
[69] Rosen K. H. Discrete Mathematics and Its Applications, Fifth Edition.McGraw-Hill Companies, Inc., 2003.
[70]耿素云,屈婉玲.离散数学.高等教育出版社, 2001.
[71]徐凤生.离散数学及其应用.机械工业出版社, 2006.
[72]肖位枢.图论及其算法.航空工业出版社, 1993.
[73]徐俊明.图论及其应用(第2版).中国科学技术大学出版社, 2004.
[74] Rosen K. H.著；袁崇义,屈婉玲,王捍贫,刘田译.离散数学及其应用(原书第4版),第1版,第1次印刷.机械工业出版社, 2002.
[75] Warshall S. A theorem on boolean matrices. Journal of the ACM, 9(1):11–12, 1962.
[76] Tarjan R. E. Depth First Search and Linear Graph Algorithms. SIAMJournal on Computing, 1:146–160, 1972.
[77] Even S. Graph Algorithms. Computer Science Press, 1979.
[78]李志武,王安荣. Petri网不变式和状态方程的求解.西安电子科技大学学报, 30(2):259–263, 2003.
[79] Schrijver A. Theory of Linear and Integer Programming. New York: Wiley,1998.
[80] Desel J., Reisig W. Place/transition Petri nets. In Lectures on Petri NetsI: Basic Models, Lecture Notes in Computer Science, 1491:122–174, 1998.
[81] Desel J. Basic linear algebraic techniques for place/transition nets. InLectures on Petri Nets I: Basic Models, Lecture Notes in Computer Science,1491:257–308, 1998.
[82] Ohta A., Tsuji K. Insufficiently marked siphon of Petri nets—extensionof token-free siphon. in Proceedings of IEEE International Symposium onCircuits and Systems, May 25-28 2003, Bangkok, Thailand, 3:244–247, 2003.
[83] Barkaoui K., Lemaire B. An effective characterization of minimal deadlocksand traps in Petri nets based on graph theory. In Proc. 10th Int. Conf. onApplications and Theory of Petri Nets. pp. 1-21, 1989.
[84] Barkaoui K., Pradat-Peyre J. F. On liveness and controlled siphons in Petrinets. In Proc. 17th Int. Conf. on Applications and Theory of Petri NetsLecture Notes in Computer Science, 1091:57–72, 1996.
[85] Li Z. W., Zhao M. On controllability of dependent siphons for deadlockprevention in generalized Petri nets. IEEE Transactions on Systems, Man,and Cybernetics, Part A, 38(2):369–384, 2008.
[86] Yamalidou E., Moody J. O., Antsaklis P. J. Feedback control of Petri netsbased on place invariants. Automatica, 32(1):15–28, 1996.
[87] Iordache M. V., Moody J. O., Antsaklis P. J. Synthesis of deadlock preventionsupervisors using Petri nets. IEEE Transactions on Robotics andAutomation, 18(1):59–68, 2002.
[88] Ezpeleta J., Garcia-Valles F., Colom J. M. A class of well structured Petrinets for flexible manufacturing systems. In Proc. 19th Int. Conf. on Applicationsand Theory of Petri Nets, Lecture Notes in Computer Science,1420:64–83, 1998.
[89] Park J., Reveliotis S. A. Algebraic synthesis of efficient deadlock avoidancepolicies for sequential resource allocation systems. IEEE Transactions onRobotics and Automation, 16(2):190–195, 2000.
[90] Esparza J., Silva M. A polynomial-time algorithm to decide liveness ofbounded free choice nets. Theoretical Computer Sciences, 102(1):185–205,1992.
[91] Desel J., Esparza J. Free Choice Petri Nets. Cambridge University Press,1995.
[92] Barkaoui K., Abdallah I. B. A deadlock prevention method for a classof FMS. in Proc. IEEE Int. Conf. Syst., Man, Cybern., Vancouver, BC,Canada, Oct. 22–25. pp. 4119-4124, 1995.
[93] Huang Y. S. Design of deadlock prevention supervisors using Petri nets.Int. J. Adv. Manuf. Tech., 35(3-4):349–362, 2007.
[94] Uzam M., Zhou M. C. An improved iterative synthesis method for livenessenforcing supervisors of flexible manufacturing systems. Int. J. Prod. Res.,44(10):1987–2030, 2006.
[95] Xing K. Y., Hu B. S. Optimal liveness Petri net supervisor synthesis forautomated manufacturing systems. in Proc. IEEE Int. Conf. Syst., Man,Cybern., Hawaii, USA, Oct. 10–12. pp. 282-287, 2005.
[96] Barkaoui K., Abdallah I. B. Deadlock avoidance in FMS based on structuraltheory of Petri nets. in Proceedings of the INRIA/IEEE Symposium onEmerging Technologies and Factory Automation: 2, Paris, France, Oct.10–13. pp. 499-510, 1995.
[97] Araki T., Sugiyama Y., Kasami T. Complexity of the deadlock avoidanceproblem. In proc. 2nd IBM symp. Math. Found. Comp. Sci., pp. 229-257,1977.
[98] Tricas F., Garcia-Valles F., Colom J. M., Ezpeleta J. A Petri net structurebaseddeadlock prevention solution for sequential resource allocation systems.in Proc. IEEE Int. Conf. Robot. Autom., Barcelona, Spain, Apr.18–22. pp. 271-277, 2005.
[99] Uzam M., Zhou M. C. Iterative synthesis of Petri net based deadlock preventionpolicy for flexible manufacturing systems. in Proc. IEEE Int. Conf.Syst.,Man, Cybern., The Hague, The Netherlands,Oct. 10–13, 2004. pp.4260-4265, 2004.
[100] Uzam M., Zhou M. C. An iterative synthesis approach to Petri net baseddeadlock prevention policy for flexible manufacturing systems. IEEE Trans.Syst.,Man, Cybern., A, Syst., Humans, 37(3):362–371, 2007.
[101] Liu X. L., Wang A. R., Li Z. W. A fast algorithm to find a set of elementarysiphons for a class of Petri nets. 2006 IEEE International Conference onAutomation Science and Engineering, Shanghai, China, Oct 8-10. pp. 399-404, 2006.
[102]李志武,王安荣.基于Petri网的柔性制造系统一种预防死锁方法(英文)(Petri net based deadlock prevention approach for flexible manufacturingsystems).自动化学报/Acta Automatica Sinica, 29(5):773–740, 2003.
[103] Starke P. H. INA: Integrated Net Analyzer. http://www2. informatik. huberlin.de/ starke/ina.html, 2003.
[104]朱洪,陈增武,段振华,周克成.算法设计和分析.上海科学技术文献出版社, 1989.
[105] Sedgewick B, Flajolet P(著),冯舜玺,李学武,裴伟东(译).算法分析导论.机械工业出版社, 2006.
[106]田绪红,李庆华.基于曙光1000A的并行SVD图像滤波方法.华中理工大学学报, 27(2):92–94, 1999.
[107]于寅.高等工程数学.华中理工大学出版社, 1995.
[108] Murata T. Petri nets: properties, analysis, and applications. Proceedings ofthe IEEE, 77(4):541–580, 1989.
[109]李志武,刘宏.并行共享资源死锁结构的一种判断方法.西安电子科技大学学报, 26(1):18–21, 1999.
[110] Wysk R. A., Yang N. S., Joshi S. Detection of deadlocks in flexible manufacturingcells. IEEE Transactions on Robotics and Automation, 7(6):853–859,1991.
[111] Jeng M. D. Modular synthesis of Petri nets for modeling flexible manufacturingsystem. International Journal of Flexible Manufacturing System,7(4):287–310, 1995.
[112] Desrocher A. A., AI-Jaar R. Y. Applications of Petri Nets in ManufacturingSystems: Modeling, Control, and Performance Analysis. IEEE Press, 1995.
[2] Ramadge P. J., Wonham W. M. Modular feedbank logic for discrete eventsystems. SIAM Journal on Control and Optimization, 25(5):1202–1218,1987.
[3] Ramadge P. J., Wonham W. M. The control of discrete event systems.Proceedings of the IEEE, 77(1):81–98, 1989.
[4] Cao X. R., Cohen G., Giua A., Wonham W. M., Van Schuppen, J. H.Unity in diversity, diversity in unity: retrospective and prospective viewson control of discrete event systems. Journal of Discrete Event DynamicSystems: Theory and Applications, 12(3):253–264, 2002.
[5]吴哲辉. Petri网导论,第1版,第1次印刷.机械工业出版社, 2006.
[6] David R., Alla H. Petri nets and Grafcet. Prentice Hall, 1992.
[7] David R., Hassane A. Petri nets for modeling of dynamic systems-a survey.Auotomatica, 30(2):175–202, 1994.
[8] David R. Grafcet: a powerful tool for specification of logical controller.IEEE Transactions on Control Systems Technology, 3(3):253–268, 1995.
[9]王寿光,林善法,张有兵.基于Grafcet的电梯控制系统建模.系统仿真学报,19(Suppl.1):263–270, 2007.
[10] Kumaran T. k., Chang W., Cho H., Wysk A. A structured approach to deadlockdetection, avoidance and resolution in flexible manufacturing systems.International Journal of Production Research, 32(10):2361–2379, 1994.
[11] Wysk R. A., Yang N. S., Joshi S. Resolution of deadlocks in flexible manufacturingsystems: avoidance and recovery approaches. Journal of ManufacturingSystems, 13(2):128–138, 1994.
[12] Viswanadham N., Narahari Y., Johnson T. Deadlock prevention and deadlockavoidance in flexible manufacturing systems using Petri net models.IEEE Transactions on Robotics and Automation, 6(6):713–723, 1990.
[13] Hsieh F. S., Chang S. C. Dispatching-driven deadlock avoidance controllersynthesis for flexible manufacturing systems. IEEE Transactions on Roboticsand Automation, 10(2):196–209, 1994.
[14] Hsieh F. S. Fault-tolerant deadlock avoidance algorithm for assembly processes.IEEE Transactions on Systems, Man, and Cybernetics, Part A,34(1):65–79, 2004.
[15] Banaszak Z., Krogh B. H. Deadlock avoidance in flexible manufacturingsystems with concurrently competing process flows. IEEE Transactions onRobotics and Automation, 6(6):724–734, 1990.
[16] Ezpeleta J., Recalde L. A deadlock avoidance approach for nonsequentialresource allocation systems. IEEE Transactions on Systems, Man, and Cybernetics,Part A, 34(1):93–101, 2004.
[17] Abdallah I. B., ElMaraghy H. A. Deadlock prevention and avoidance inFMS: a Petri net based approach. International Journal of Advanced ManufacturingTechnology, 14(10):704–715, 1998.
[18] Wu N. Q. Necessary and sufficient conditions for deadlock-free operationin flexible manufacturing systems using a colored Petri net model. IEEETransactions on Systems, Man, and Cybernetics, Part C, 29(2):192–204,1999.
[19] Wu N. Q., Zhou M. C. Avoiding deadlock and reducing starvation and blockingin automated manufacturing systems. IEEE Transactions on Roboticsand Automation, 17(5):658–669, 2001.
[20] Wu N. Q., Zhou M. C. Modeling and deadlock avoidance of automated manufacturingsystems with multiple automated guided vehicles. IEEE Transactionson Systems, Man, and Cybernetics, Part B, 35(6):1193–1202, 2005.
[21] Ezpeleta J, Colom J. M., Martinez J. A Petri net based deadlock preventionpolicy for flexible manufacturing systems. IEEE Transactions on Roboticsand Automation, 11(2):173–184, 1995.
[22] Fanti M. P., Zhou M. C. Deadlock control methods in automated manufacturingsystems. IEEE Transactions on Systems, Man, and Cybernetics,Part A, 34(1):5–22, 2004.
[23] Xing K. Y., Hu B. S., Chen H. X. Deadlock avoidance policy for Petri netmodelling of flexible manufacturing systems with shared resources. IEEETransactions on Automatic Control, 41(2):289–295, 1996.
[24] Lautenbach K., Ridder H. The linear algebra of deadlock avoidance-a Petrinet approach. No.25-1996, Technical Report, Institute of Software Technology,University of Koblenz-Landau, Koblenz, Germany.
[25] Zhou M. C., DiCesare F. Parallel and sequential exclusions for Petri netmodeling for manufacturing systems. IEEE Transactions on Robotics andAutomation, 7(4):515–527, 1991.
[26] Zhou M. C., DiCesare F. A hybrid methodology for synthesis of Petri nets formanufacturing systems. IEEE Transactions on Robotics and Automation,8(3):515–527, 1992.
[27] Zhou M. C., DiCesare F. Petri Net Synthesis for Discrete Event Control ofManufacturing Systems. Kluwer Academic Publishers, Boston, 1993.
[28] Jeng M. D., DiCesare F. Synthesis using resource control nets for modelingshared-resource systems. IEEE Transactions on Robotics and Automation,11(3):317–327, 1995.
[29] Jeng M. D. A Petri net synthesis theory for modeling flexible manufacturingsystems. IEEE Transactions on Systems, Man and Cybernetics, Part B,27(2):169–183, 1997.
[30] Jeng M. D., Xie X. L. Analysis of modularly composed nets by siphons.IEEE Transactions on Systems, Man, and Cybernetics, Part A, 29(4):399–406, 1999.
[31] Jeng M. D., Xie X. L., Peng M. Y. Process nets with resources for manufacturingmodeling and their analysis. IEEE Transactions on Robotics andAutomation, 18(6):875–889, 2002.
[32] Jeng M. D., Xie X. L., Chung S. L. ERCN* merged nets for modelingdegraded behavior and parallel processes in semiconductor manufacturingsystems. IEEE Transactions on Systems, Man, and Cybernetics, Part A,34(1):102–112, 2004.
[33] Chu F., Xie X. L. Deadlock analysis of Petri nets using siphons and mathematicalprogramming. IEEE Transactions on Robotics and Automation,13(6):793–804, 1997.
[34] Barkaoui K., Chaoui A., Zouari B. Supervisory control of discrete eventsystems based on structure theory of Petri nets. In Proc. IEEE Int. Conf.on Systems, Man, and Cybernetics, pp. 3750-3755, 1997.
[35] Lautenbach K., Ridder H. Liveness in bounded Petri nets which are coveredby T-invariants. In Proc. 13th Int. Conf. on Applications and Theory ofPetri Nets, Lecture Notes in Computer Science, 815:358–375, 1993.
[36] Reveliotis S. A. On the siphon-based characterization of liveness in sequentialresource allocation systems. In Proc. Int. Conf. on Applications andTheory of Petri Nets, Lecture Notes in Computer Scienc, 2679:241–255,2003.
[37] Lautenbach K. Linear algebraic calculation of deadlocks and traps. InConcurrency and Nets, pp. 315-336, 1987.
[38] Ezpeleta J., Couvreur J. M., Silva M. A new technique for finding a generatingfamily of siphons, traps, and st-Components: application to coloredPetri nets. In Advances in Petri Nets, Lecture Notes in Computer Science,674:126–147, 1993.
[39] Huang Y. S., Jeng M. D., Xie X. L., Chung S. L. A deadlock preventionPolicy for flexible manufacturing systems using siphons. In Proc. IEEE Int.Conf. on Robotics and Automation, pp. 541-546, 2001.
[40] Tricas F., Garcia-Valles F., Colom J. M., Ezpeleta J. A structural approachto the problem of deadlock prevention in processes with shared resources. inProc. Inst. Electr. Eng. 4th Workshop Discrete Event Syst., Cagliari, Italy,Aug. 26–28, 1998. pp. 273-278, 1998.
[41] Tricas F., Martinez J. An extension of the liveness theory for concurrentsequential processes competing for shared resources. In Proc. IEEE Int.Conf. on Systems, Man, and Cybernetics, pp. 3035-3040, 1995.
[42] Tricas F., Garcia-Valles F., Colom J. M., Ezpeleta J. An iterative methodfor deadlock prevention in FMSs. In Proc. 5th Workshop on Discrete EventSystems, R. Boel and G. Stremersch, Eds.Ghent, Belgium, Aug. 21–23,2000. pp. 139-148, 2000.
[43] Park J., Reveliotis S. A. Deadlock avoidance in sequential resource allocationsystems with multiple resource acquisitions and flexible routings. IEEETransactions on Automatic Control, 46(10):1572–1583, 2001.
[44] Ezpeleta J., Tricas F., Garcia-Valles F., Colom J. M. A banker’s solutionfor deadlock avoidance in FMS with flexible routing and multiresourceStates. IEEE Transactions on Robotics and Automaton, 18(4):621–625,2002.
[45] Xie X. L., Jeng M. D. ERCN-merged nets and their analysis using siphons.IEEE Transactions on Robotics and Automation, 15(4):692–703, 1999.
[46] Zouari B., Barkaoui K. Parameterized supervisor synthesis for a modularclass of discrete event systems. In Proc. IEEE Int. Conf. on Systems, Man,and Cybernetics, Washington, DC, Oct. 5–8, 2003. pp. 1874-1879, 2003.
[47] Huang Y. S., Jeng M. D., Xie X. L., Chung D. H. Siphon-based deadlockprevention policy for flexible manufacturing systems. IEEE Transactions onSystems, Man, and Cybernetics, Part A, 36(6):1248–1256, 2006.
[48] Huang Y. S., Jeng M. D., Xie X. L., Chung S. L. Deadlock preventionpolicy based on Petri nets and siphons. International Journal of ProductionResearch, 39(2):283–305, 2001.
[49] Badouel E., Darondeau P. Theory of Regions. Lectures on Petri Nets I:Basic Models, Lecture Notes in Computer Science, 1491:529–586, 1998.
[50] Uzam M. An optimal deadlock prevention policy for flexible manufacturingsystems using Petri net models with resources and the theory of regions.International Journal of Advanced Manufacturing Technology, 19(3):192–208, 2002.
[51] Ghaffari A., Rezg N., Xie X. L. Design of a live and maximally permissivePetri net controller using the theory of regions. IEEE Transactions onRobotics and Automation, 19(1):137–141, 2003.
[52] Li Z. W., Zhou M. C., Jeng M. D. A Maximally Permissive Deadlock PreventionPolicy for FMS based on Petri Net Siphon Control and the Theoryof Regions. IEEE Transactions on Automation Science and Engineering,5(1):182–188, 2008.
[53] Li Z. W., Hu H. S., Wang A. R. Design of liveness-enforcing supervisorsfor flexible manufacturing systems using Petri nets. IEEE Transactions onSystems, Man, and Cybernetics, Part C, 37(4):517–526, 2007.
[54] Li Z. W., Zhou M. C. Two-stage method for synthesizing liveness-enforcingsupervisors for flexible manufacturing systems using Petri nets. IEEE Transactionson Industrial Informatics, 2(4):313–325, 2006.
[55] Li Z. W., Zhou M. C. Elementary siphons of Petri nets and their applicationto deadlock prevention in flexible manufacturing systems. IEEE Transactionson Systems, Man, and Cybernetics, Part A, 34(1):38–51, 2004.
[56] Li Z. W., Zhou M. C. Clarifications on the definitions of elementary siphonsof Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, PartA, 36(6):1227–1229, 2006.
[57] Li Z. W., Zhou M. C., Wu N. Q. A survey and comparison of Petri netbaseddeadlock prevention policies for flexible manufacturing systems. IEEETransactions on Systems, Man, and Cybernetics, Part C, 38(2):173–188,2008.
[58] Li Z. W., Zhou M. C. On siphon computation for deadlock control in a classof Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, PartA, 38(3):667–679, 2008.
[59] Li Z. W., Zhou M. C. Control of elementary and dependent siphons inPetri nets and their application. IEEE Transactions on Systems, Man, andCybernetics, Part A, 38(1):133–148, 2008.
[60] Li Z. W., Zhang J., Zhao M. Liveness-enforcing Supervisor Design for aClass of Generalised Petri Net Models of Flexible Manufacturing Systems.IET Control Theory and Applications, 1(4):955–967, 2007.
[61] Colom J. M., Silva M. Improving the linearly based characterization of P/Tnets. In Proc. 10th Int. Conf. on Applications and Theory of Petri Nets, G.Rozenberg (Ed.), Lecture Notes in Computer Science, 483:113–145, 1989.
[62] Garcia-Valles F., Colom J. M. Implicit places in net systems. In Proc. 8thInt. Workshop on Petri Nets and Performance Models. pp. 104-113, 1999.
[63] Recalde L., Teruel E., Silva M. Improving the decision power of rank theorems.In Proc. IEEE Int. Conf. on Systems, Man, and Cybernetics. pp.3768-3773, 1997.
[64] Silva M., Teruel E., Colom J. M. Linear algebraic and linear programmingtechniques for the analysis of place/transition net systems. In Lectures onPetri Nets I: Basic Models, Lectures Notes in Computer Science, 1491:309–373, 1998.
[65] West D. B. Introduction to graph theory(Second Edition 2001)影印版.北京：机械工业出版社, 2004.
[66] Weiss M. A. Java数据结构与算法分析(影印版)(Data Structures and AlgorithmAnalysis in Java).科学出版社(Addison-Wesley Publishing LongmanInc.), 2004(1999).
[67] Bondy J. A., Murty U. S. R. Graph Theory with Applications. The MacmillanPress LTD, 1976.
[68] Tutte W. T. Graph theory. Cambridge University Press, 2001.
[69] Rosen K. H. Discrete Mathematics and Its Applications, Fifth Edition.McGraw-Hill Companies, Inc., 2003.
[70]耿素云,屈婉玲.离散数学.高等教育出版社, 2001.
[71]徐凤生.离散数学及其应用.机械工业出版社, 2006.
[72]肖位枢.图论及其算法.航空工业出版社, 1993.
[73]徐俊明.图论及其应用(第2版).中国科学技术大学出版社, 2004.
[74] Rosen K. H.著；袁崇义,屈婉玲,王捍贫,刘田译.离散数学及其应用(原书第4版),第1版,第1次印刷.机械工业出版社, 2002.
[75] Warshall S. A theorem on boolean matrices. Journal of the ACM, 9(1):11–12, 1962.
[76] Tarjan R. E. Depth First Search and Linear Graph Algorithms. SIAMJournal on Computing, 1:146–160, 1972.
[77] Even S. Graph Algorithms. Computer Science Press, 1979.
[78]李志武,王安荣. Petri网不变式和状态方程的求解.西安电子科技大学学报, 30(2):259–263, 2003.
[79] Schrijver A. Theory of Linear and Integer Programming. New York: Wiley,1998.
[80] Desel J., Reisig W. Place/transition Petri nets. In Lectures on Petri NetsI: Basic Models, Lecture Notes in Computer Science, 1491:122–174, 1998.
[81] Desel J. Basic linear algebraic techniques for place/transition nets. InLectures on Petri Nets I: Basic Models, Lecture Notes in Computer Science,1491:257–308, 1998.
[82] Ohta A., Tsuji K. Insufficiently marked siphon of Petri nets—extensionof token-free siphon. in Proceedings of IEEE International Symposium onCircuits and Systems, May 25-28 2003, Bangkok, Thailand, 3:244–247, 2003.
[83] Barkaoui K., Lemaire B. An effective characterization of minimal deadlocksand traps in Petri nets based on graph theory. In Proc. 10th Int. Conf. onApplications and Theory of Petri Nets. pp. 1-21, 1989.
[84] Barkaoui K., Pradat-Peyre J. F. On liveness and controlled siphons in Petrinets. In Proc. 17th Int. Conf. on Applications and Theory of Petri NetsLecture Notes in Computer Science, 1091:57–72, 1996.
[85] Li Z. W., Zhao M. On controllability of dependent siphons for deadlockprevention in generalized Petri nets. IEEE Transactions on Systems, Man,and Cybernetics, Part A, 38(2):369–384, 2008.
[86] Yamalidou E., Moody J. O., Antsaklis P. J. Feedback control of Petri netsbased on place invariants. Automatica, 32(1):15–28, 1996.
[87] Iordache M. V., Moody J. O., Antsaklis P. J. Synthesis of deadlock preventionsupervisors using Petri nets. IEEE Transactions on Robotics andAutomation, 18(1):59–68, 2002.
[88] Ezpeleta J., Garcia-Valles F., Colom J. M. A class of well structured Petrinets for flexible manufacturing systems. In Proc. 19th Int. Conf. on Applicationsand Theory of Petri Nets, Lecture Notes in Computer Science,1420:64–83, 1998.
[89] Park J., Reveliotis S. A. Algebraic synthesis of efficient deadlock avoidancepolicies for sequential resource allocation systems. IEEE Transactions onRobotics and Automation, 16(2):190–195, 2000.
[90] Esparza J., Silva M. A polynomial-time algorithm to decide liveness ofbounded free choice nets. Theoretical Computer Sciences, 102(1):185–205,1992.
[91] Desel J., Esparza J. Free Choice Petri Nets. Cambridge University Press,1995.
[92] Barkaoui K., Abdallah I. B. A deadlock prevention method for a classof FMS. in Proc. IEEE Int. Conf. Syst., Man, Cybern., Vancouver, BC,Canada, Oct. 22–25. pp. 4119-4124, 1995.
[93] Huang Y. S. Design of deadlock prevention supervisors using Petri nets.Int. J. Adv. Manuf. Tech., 35(3-4):349–362, 2007.
[94] Uzam M., Zhou M. C. An improved iterative synthesis method for livenessenforcing supervisors of flexible manufacturing systems. Int. J. Prod. Res.,44(10):1987–2030, 2006.
[95] Xing K. Y., Hu B. S. Optimal liveness Petri net supervisor synthesis forautomated manufacturing systems. in Proc. IEEE Int. Conf. Syst., Man,Cybern., Hawaii, USA, Oct. 10–12. pp. 282-287, 2005.
[96] Barkaoui K., Abdallah I. B. Deadlock avoidance in FMS based on structuraltheory of Petri nets. in Proceedings of the INRIA/IEEE Symposium onEmerging Technologies and Factory Automation: 2, Paris, France, Oct.10–13. pp. 499-510, 1995.
[97] Araki T., Sugiyama Y., Kasami T. Complexity of the deadlock avoidanceproblem. In proc. 2nd IBM symp. Math. Found. Comp. Sci., pp. 229-257,1977.
[98] Tricas F., Garcia-Valles F., Colom J. M., Ezpeleta J. A Petri net structurebaseddeadlock prevention solution for sequential resource allocation systems.in Proc. IEEE Int. Conf. Robot. Autom., Barcelona, Spain, Apr.18–22. pp. 271-277, 2005.
[99] Uzam M., Zhou M. C. Iterative synthesis of Petri net based deadlock preventionpolicy for flexible manufacturing systems. in Proc. IEEE Int. Conf.Syst.,Man, Cybern., The Hague, The Netherlands,Oct. 10–13, 2004. pp.4260-4265, 2004.
[100] Uzam M., Zhou M. C. An iterative synthesis approach to Petri net baseddeadlock prevention policy for flexible manufacturing systems. IEEE Trans.Syst.,Man, Cybern., A, Syst., Humans, 37(3):362–371, 2007.
[101] Liu X. L., Wang A. R., Li Z. W. A fast algorithm to find a set of elementarysiphons for a class of Petri nets. 2006 IEEE International Conference onAutomation Science and Engineering, Shanghai, China, Oct 8-10. pp. 399-404, 2006.
[102]李志武,王安荣.基于Petri网的柔性制造系统一种预防死锁方法(英文)(Petri net based deadlock prevention approach for flexible manufacturingsystems).自动化学报/Acta Automatica Sinica, 29(5):773–740, 2003.
[103] Starke P. H. INA: Integrated Net Analyzer. http://www2. informatik. huberlin.de/ starke/ina.html, 2003.
[104]朱洪,陈增武,段振华,周克成.算法设计和分析.上海科学技术文献出版社, 1989.
[105] Sedgewick B, Flajolet P(著),冯舜玺,李学武,裴伟东(译).算法分析导论.机械工业出版社, 2006.
[106]田绪红,李庆华.基于曙光1000A的并行SVD图像滤波方法.华中理工大学学报, 27(2):92–94, 1999.
[107]于寅.高等工程数学.华中理工大学出版社, 1995.
[108] Murata T. Petri nets: properties, analysis, and applications. Proceedings ofthe IEEE, 77(4):541–580, 1989.
[109]李志武,刘宏.并行共享资源死锁结构的一种判断方法.西安电子科技大学学报, 26(1):18–21, 1999.
[110] Wysk R. A., Yang N. S., Joshi S. Detection of deadlocks in flexible manufacturingcells. IEEE Transactions on Robotics and Automation, 7(6):853–859,1991.
[111] Jeng M. D. Modular synthesis of Petri nets for modeling flexible manufacturingsystem. International Journal of Flexible Manufacturing System,7(4):287–310, 1995.
[112] Desrocher A. A., AI-Jaar R. Y. Applications of Petri Nets in ManufacturingSystems: Modeling, Control, and Performance Analysis. IEEE Press, 1995.