基于基本信标的自动制造系统活性控制器设计
|
摘要
柔性制造系统是由计算机数控机床和物料传输系统构成的可以高效地生产中小批量不同产品的自动制造系统。死锁是设计柔性制造系统控制器时必须考虑和解决的问题。在有些情况下,死锁造成的局部或整体的系统停顿并不单纯地降低生产率,更可能造成重大经济损失甚至灾难性后果。因此,柔性制造系统中死锁的描述、分析及控制对系统控制的实现和运行至关重要。目前,基于Petri网的自动制造系统死锁处理方法大致分为三种策略：死锁检测与恢复、死锁避免和死锁预防。死锁检测与恢复策略是一种在线检测及恢复死锁状态的机制,一旦检测到死锁发生,便通过在线策略重新分配共享资源使系统恢复到正常状态。死锁避免是一种在线资源分配机制,通过在线策略合理分配系统资源使系统不能进入死锁状态。死锁预防策略通过离线机制控制系统对共享资源的使用请求,保证死锁不会发生。
一般地,死锁预防可以通过为网系统添加控制器来预防死锁发生。衡量Petri网活性控制器的性能指标主要分为结构复杂性、计算复杂性及行为许可性三个方面。信标作为表征Petri网结构特性的重要对象,与Petril网系统的死锁密切相关,这一点在普通Petri网和一般Petri网中均成立。为了获得最大许可行为的、结构简单的及计算复杂度较低的Petri网活性控制器,许多研究者提出了大量基于信标分析控制技术的死锁控制策略。因此,Petri网中信标的提取及分析方法是系统死锁控制中一种非常重要的技术手段。由于Petri网信标求解的固有复杂性,任何依赖完全枚举信标的死锁预防算法在理论上必然为指数复杂度。本文立足于Petri网的信标分析及基本信标提取技术,研究柔性制造系统的活性Petri网控制器设计方法。主要完成以下工作：
1.行为许可性是衡量Petri网活性控制器性能的重要指标之一。针对一类普通Petri网-S3PR网系统,提出了关于初始标识的S3PR网最大许可行为活性控制器存在性的充分条件。基于基本信标理论,提出了最大许可行为活性监督控制器存在性的判定算法。该算法基于基本信标与信标复合的计算,关于网规模为多项式复杂度。在S3PR网中,一定存在可以得到最大许可行为的活性控制器的初始标识。同时,结合给出的充分条件,提出了S3PR网最大许可行为活性控制器迭代设计算法。在每一步迭代中,该算法运用混合整数规划的死锁检测方法获得一个信标并加以控制。大量实例验证了该方法的有效性。本研究可视为对基本信标理论的进一步应用。
2.在柔性制造系统中,基于信标的死锁控制往往面临计算复杂性和结构复杂性问题。为了降低控制器的结构复杂度,基本信标理论最初成功地应用于普通Petri网中。但考虑到在一般Petri网系统中资源分配具有更为复杂的情况,基本信标的选取及其可控性的分析仍需要进一步改进。为了改进基本信标在一般Petri网中的扩展应用,针对一类一般Petri网-WS3PR网系统,首次引入了扩展信标的概念。扩展信标是一个能够反映其原始信标中资源复杂使用的多集。考虑WS3PR网系统的拓扑结构和权值信息,提出扩展基本信标概念,并给出了改进的基本信标定义,通过该定义可以得到一组与系统结构紧密相关的基本信标集合。同时,基于图论,在WS3PR网中引入初始资源加权有向图,并提出了结构同构网系统的概念。对于结构同构的不同网系统,可以共用一组基本信标。
3.定义了一类一般Petri网-GLS3PR网系统,该网系统可以较好地建模柔性制造系统,同时具有便于分析的结构特性。针对GLS3PR网提出了一种高效的严格极小信标和基本信标提取方法。通过结构分析引入了扩展信标概念,并由此改进了基本信标定义。基于图论,在普通网中可利用初始资源有向图来计算所有的严格极小信标。本文针对GLS3PR网系统,引入初始资源加权有向图。在满足一定的约束条件下,从初始资源加权有向图中求取一组约束导出子图。考虑GLS3PR网结构,利用这些子图,建立了提取所有严格极小信标及其扩展信标的方法。此外,根据信标和约束导出子图之间的关系,给出了扩展基本信标个数的上确界。大量实验结果表明,通过该方法获得的基本信标结构紧凑且更适用于GLS3PR网系统。
4.为了改善活性控制器的结构复杂性和行为许可性,针对一类一般Petri网-S4PR网系统,提出一种有效的死锁预防策略。通过分析一般Petri网系统发现,一般Petri网系统的死锁可以通过非充分标识信标来反映,而基本信标理论的提出为设计结构简单的活性控制器提供了可行方向。由此,在S4PR网系统中将非充分标识信标划分为基本信标和从属信标,从属信标的可控性可以通过对其基本信标的合理控制来实现。为了获得一组结构紧凑且适用的基本信标集合,通过结构分析在S4PR网系统中引入扩展基本信标概念,然后结合松弛的信标最大可控性条件来满足信标的可控性。该方法仅对基本信标添加控制器,即可获得活性受控网系统。此外,通过设计控制库所输出弧撤弧算法来获得许可行为更优的活性控制器。
A flexible manufacturing system (FMS) is an automated manufacturing system (AMS) that can efficiently produce medium or small batches of different products. An FMS is made up of computer numerical control machine tools and a material trans-mission system. Deadlocks must be considered and resolved in control system design of FMSs. In some cases, a local or global system halt caused by deadlocks can not only lead to the deterioration of productivity but also heavy economic losses and even fatal results. Therefore, it is vital to ensure the realization and operation of system control based on deadlock description, analysis, and control in an FMS. At present, deadlock resolution methods in AMSs modeled with Petri nets are mainly classified into three strategies: deadlock detection and recovery, deadlock avoidance, and deadlock prevention. Dead-lock detection and recovery is an online mechanism of detecting and recovering deadlock states. When a deadlock occurs, it is detected and then the system is put back to a deadlock-free state, by simply reallocating the shared resources. Deadlock avoidance is a resources allocation mechanism, behind which an online control policy is used to make a correct decision to proceed among the feasible evolutions that keep the system away from deadlock states. Deadlock prevention is usually achieved by using an off-line computational mechanism to control the request for resources to ensure that deadlocks never occur.
Generally, deadlock prevention policies can be realized by adding monitors to a Petri net system to forbid deadlock states. There are three important criteria in evalu-ating the performance of a liveness-enforcing supervisor for a system to be controlled: behavioral permissiveness, structural complexity, and computational complexity. As a structural object of Petri nets, siphons are closely related to deadlocks, which is always true whether in ordinary Petri nets or generalized ones. Many researchers have developed a great number of siphon-based deadlock control policies in order to achieve liveness-enforcing supervisors with maximal permissiveness, simple supervisory structure, and low computational complexity. Therefore, siphons analysis is important for deadlock control. Due to the inherent complexity of siphons resolution, any deadlock preven-tion algorithm with a complete siphon enumeration must be of exponential complexity in theory. This thesis focuses on liveness-enforcing Petri net supervisors considering siphon-based structural analysis and an elementary siphons extraction method. The following research contributions are proposed in this thesis.
1. Behavioral permissiveness is one of the most important criteria in evaluating the performance of a liveness-enforcing supervisor. For a class of ordinary Petri nets, S3PR, this work explores sufficient conditions with respect to an initial marking under which there exists a maximally permissive liveness-enforcing Petri net supervisor. Based on elementary siphons, an algorithm with polynomial complexity is proposed to decide the existence of a maximally permissive supervisor for S3PR. Its development is based on the computation of a set of elementary siphons and siphons composition operations, which has been shown to be of polynomial complexity with respect to the size of a plant net model. It can be concluded that, for any S3PR, there exist initial markings such that a maximally permissive liveness-enforcing supervisor can be always found. By combining the proposed sufficient conditions, an iterative algorithm is developed to design maximally permissive liveness-enforcing supervisors for S3PR. At each iteration, a siphon is derived by an MIP-based deadlock detection method and then controlled by adding a monitor. Several examples are used to demonstrate the proposed methods. This study can be considered as further applications of elementary siphons of Petri nets.
2. Siphon-based deadlock control in an FMS suffers from the problems of computa-tional and structural complexity. Thus, the concept of elementary siphons is originally proposed in ordinary Petri nets to reduce structural complexity of a supervisor. Due to the complex requirement of multiple resource types by an operation, the selection of elementary siphons and their controllability still need improvements in generalized Petri nets. From this, the concept of augmented siphons is proposed to extend the applica-tion of the elementary ones to a class of generalized Petri nets, WS3PR. An augmented siphon is a multiset that reflects the weights information of resource places contained by its original siphon. Among augmented siphons, the elementary siphons are redefined, from which a set of elementary siphons that strongly connects the system structure can be found for WS3PR. Moreover, based on graph theory, initial resource weighted di-graphs are presented for WS3PR, and the concept of isomorphic structures of Petri nets is introduced. A same set of elementary siphons can be admitted by different WS3PR with isomorphic structures.
3. A class of generalized Petri nets, GLS3PR, is proposed, which can well model FMSs and facilitate structure analysis. An efficient strict minimal siphons (SMSs) and elementary ones extraction method is developed for GLS3PR. Augmented siphons are proposed based on the structural analysis, and the elementary siphons are redefined. Based on graph theory, the concept of initial resource digraphs is first introduced to compute all SMSs in ordinary Petri nets. In this thesis, the initial resource weighted digraph for GLS3PR is presented. A restrictive induced subgraph can be obtained by in-ducing an initial resource weighted digraph under certain restrictions. Based on them, a method for computing all SMSs and their augmented versions is developed through fully investigating the structure of GLS3PR. According to the relationship between siphons and their restrictive induced subgraphs, the supremum of the number of augmented elementary siphons is found. Experimental results show that the set of elementary siphons obtained by the proposed method is more compact and well suits for the class of generalized Petri nets considered.
4. In order to improve the structural complexity and behavioral permissiveness for a class of generalized Petri nets, S4PR, a novel deadlock prevention policy is pre-sented. The analysis of generalized Petri nets leads us to characterize deadlock situa-tions in terms of insufficiently marked siphons. The theory of elementary siphons guides our efforts toward the development of structurally simple liveness-enforcing supervisors. Therefore, insufficiently marked siphons can be classified into elementary and dependent ones. The controllability of a dependent siphon can be ensured by properly supervising its elementary ones. In order to find a compact and proper set of elementary siphons, the concept of augmented siphons is proposed for S4PR. Meanwhile, the concept of max'-controlled siphons is employed, which can relax the siphon controllability condition. By explicitly controlling elementary siphons via adding monitors, a live controlled sys-tem can be gained. In addition, the liveness-enforcing supervisor with more permissive behavior is obtained through the rearrangement of the output arcs of monitors.
一般地,死锁预防可以通过为网系统添加控制器来预防死锁发生。衡量Petri网活性控制器的性能指标主要分为结构复杂性、计算复杂性及行为许可性三个方面。信标作为表征Petri网结构特性的重要对象,与Petril网系统的死锁密切相关,这一点在普通Petri网和一般Petri网中均成立。为了获得最大许可行为的、结构简单的及计算复杂度较低的Petri网活性控制器,许多研究者提出了大量基于信标分析控制技术的死锁控制策略。因此,Petri网中信标的提取及分析方法是系统死锁控制中一种非常重要的技术手段。由于Petri网信标求解的固有复杂性,任何依赖完全枚举信标的死锁预防算法在理论上必然为指数复杂度。本文立足于Petri网的信标分析及基本信标提取技术,研究柔性制造系统的活性Petri网控制器设计方法。主要完成以下工作：
1.行为许可性是衡量Petri网活性控制器性能的重要指标之一。针对一类普通Petri网-S3PR网系统,提出了关于初始标识的S3PR网最大许可行为活性控制器存在性的充分条件。基于基本信标理论,提出了最大许可行为活性监督控制器存在性的判定算法。该算法基于基本信标与信标复合的计算,关于网规模为多项式复杂度。在S3PR网中,一定存在可以得到最大许可行为的活性控制器的初始标识。同时,结合给出的充分条件,提出了S3PR网最大许可行为活性控制器迭代设计算法。在每一步迭代中,该算法运用混合整数规划的死锁检测方法获得一个信标并加以控制。大量实例验证了该方法的有效性。本研究可视为对基本信标理论的进一步应用。
2.在柔性制造系统中,基于信标的死锁控制往往面临计算复杂性和结构复杂性问题。为了降低控制器的结构复杂度,基本信标理论最初成功地应用于普通Petri网中。但考虑到在一般Petri网系统中资源分配具有更为复杂的情况,基本信标的选取及其可控性的分析仍需要进一步改进。为了改进基本信标在一般Petri网中的扩展应用,针对一类一般Petri网-WS3PR网系统,首次引入了扩展信标的概念。扩展信标是一个能够反映其原始信标中资源复杂使用的多集。考虑WS3PR网系统的拓扑结构和权值信息,提出扩展基本信标概念,并给出了改进的基本信标定义,通过该定义可以得到一组与系统结构紧密相关的基本信标集合。同时,基于图论,在WS3PR网中引入初始资源加权有向图,并提出了结构同构网系统的概念。对于结构同构的不同网系统,可以共用一组基本信标。
3.定义了一类一般Petri网-GLS3PR网系统,该网系统可以较好地建模柔性制造系统,同时具有便于分析的结构特性。针对GLS3PR网提出了一种高效的严格极小信标和基本信标提取方法。通过结构分析引入了扩展信标概念,并由此改进了基本信标定义。基于图论,在普通网中可利用初始资源有向图来计算所有的严格极小信标。本文针对GLS3PR网系统,引入初始资源加权有向图。在满足一定的约束条件下,从初始资源加权有向图中求取一组约束导出子图。考虑GLS3PR网结构,利用这些子图,建立了提取所有严格极小信标及其扩展信标的方法。此外,根据信标和约束导出子图之间的关系,给出了扩展基本信标个数的上确界。大量实验结果表明,通过该方法获得的基本信标结构紧凑且更适用于GLS3PR网系统。
4.为了改善活性控制器的结构复杂性和行为许可性,针对一类一般Petri网-S4PR网系统,提出一种有效的死锁预防策略。通过分析一般Petri网系统发现,一般Petri网系统的死锁可以通过非充分标识信标来反映,而基本信标理论的提出为设计结构简单的活性控制器提供了可行方向。由此,在S4PR网系统中将非充分标识信标划分为基本信标和从属信标,从属信标的可控性可以通过对其基本信标的合理控制来实现。为了获得一组结构紧凑且适用的基本信标集合,通过结构分析在S4PR网系统中引入扩展基本信标概念,然后结合松弛的信标最大可控性条件来满足信标的可控性。该方法仅对基本信标添加控制器,即可获得活性受控网系统。此外,通过设计控制库所输出弧撤弧算法来获得许可行为更优的活性控制器。
A flexible manufacturing system (FMS) is an automated manufacturing system (AMS) that can efficiently produce medium or small batches of different products. An FMS is made up of computer numerical control machine tools and a material trans-mission system. Deadlocks must be considered and resolved in control system design of FMSs. In some cases, a local or global system halt caused by deadlocks can not only lead to the deterioration of productivity but also heavy economic losses and even fatal results. Therefore, it is vital to ensure the realization and operation of system control based on deadlock description, analysis, and control in an FMS. At present, deadlock resolution methods in AMSs modeled with Petri nets are mainly classified into three strategies: deadlock detection and recovery, deadlock avoidance, and deadlock prevention. Dead-lock detection and recovery is an online mechanism of detecting and recovering deadlock states. When a deadlock occurs, it is detected and then the system is put back to a deadlock-free state, by simply reallocating the shared resources. Deadlock avoidance is a resources allocation mechanism, behind which an online control policy is used to make a correct decision to proceed among the feasible evolutions that keep the system away from deadlock states. Deadlock prevention is usually achieved by using an off-line computational mechanism to control the request for resources to ensure that deadlocks never occur.
Generally, deadlock prevention policies can be realized by adding monitors to a Petri net system to forbid deadlock states. There are three important criteria in evalu-ating the performance of a liveness-enforcing supervisor for a system to be controlled: behavioral permissiveness, structural complexity, and computational complexity. As a structural object of Petri nets, siphons are closely related to deadlocks, which is always true whether in ordinary Petri nets or generalized ones. Many researchers have developed a great number of siphon-based deadlock control policies in order to achieve liveness-enforcing supervisors with maximal permissiveness, simple supervisory structure, and low computational complexity. Therefore, siphons analysis is important for deadlock control. Due to the inherent complexity of siphons resolution, any deadlock preven-tion algorithm with a complete siphon enumeration must be of exponential complexity in theory. This thesis focuses on liveness-enforcing Petri net supervisors considering siphon-based structural analysis and an elementary siphons extraction method. The following research contributions are proposed in this thesis.
1. Behavioral permissiveness is one of the most important criteria in evaluating the performance of a liveness-enforcing supervisor. For a class of ordinary Petri nets, S3PR, this work explores sufficient conditions with respect to an initial marking under which there exists a maximally permissive liveness-enforcing Petri net supervisor. Based on elementary siphons, an algorithm with polynomial complexity is proposed to decide the existence of a maximally permissive supervisor for S3PR. Its development is based on the computation of a set of elementary siphons and siphons composition operations, which has been shown to be of polynomial complexity with respect to the size of a plant net model. It can be concluded that, for any S3PR, there exist initial markings such that a maximally permissive liveness-enforcing supervisor can be always found. By combining the proposed sufficient conditions, an iterative algorithm is developed to design maximally permissive liveness-enforcing supervisors for S3PR. At each iteration, a siphon is derived by an MIP-based deadlock detection method and then controlled by adding a monitor. Several examples are used to demonstrate the proposed methods. This study can be considered as further applications of elementary siphons of Petri nets.
2. Siphon-based deadlock control in an FMS suffers from the problems of computa-tional and structural complexity. Thus, the concept of elementary siphons is originally proposed in ordinary Petri nets to reduce structural complexity of a supervisor. Due to the complex requirement of multiple resource types by an operation, the selection of elementary siphons and their controllability still need improvements in generalized Petri nets. From this, the concept of augmented siphons is proposed to extend the applica-tion of the elementary ones to a class of generalized Petri nets, WS3PR. An augmented siphon is a multiset that reflects the weights information of resource places contained by its original siphon. Among augmented siphons, the elementary siphons are redefined, from which a set of elementary siphons that strongly connects the system structure can be found for WS3PR. Moreover, based on graph theory, initial resource weighted di-graphs are presented for WS3PR, and the concept of isomorphic structures of Petri nets is introduced. A same set of elementary siphons can be admitted by different WS3PR with isomorphic structures.
3. A class of generalized Petri nets, GLS3PR, is proposed, which can well model FMSs and facilitate structure analysis. An efficient strict minimal siphons (SMSs) and elementary ones extraction method is developed for GLS3PR. Augmented siphons are proposed based on the structural analysis, and the elementary siphons are redefined. Based on graph theory, the concept of initial resource digraphs is first introduced to compute all SMSs in ordinary Petri nets. In this thesis, the initial resource weighted digraph for GLS3PR is presented. A restrictive induced subgraph can be obtained by in-ducing an initial resource weighted digraph under certain restrictions. Based on them, a method for computing all SMSs and their augmented versions is developed through fully investigating the structure of GLS3PR. According to the relationship between siphons and their restrictive induced subgraphs, the supremum of the number of augmented elementary siphons is found. Experimental results show that the set of elementary siphons obtained by the proposed method is more compact and well suits for the class of generalized Petri nets considered.
4. In order to improve the structural complexity and behavioral permissiveness for a class of generalized Petri nets, S4PR, a novel deadlock prevention policy is pre-sented. The analysis of generalized Petri nets leads us to characterize deadlock situa-tions in terms of insufficiently marked siphons. The theory of elementary siphons guides our efforts toward the development of structurally simple liveness-enforcing supervisors. Therefore, insufficiently marked siphons can be classified into elementary and dependent ones. The controllability of a dependent siphon can be ensured by properly supervising its elementary ones. In order to find a compact and proper set of elementary siphons, the concept of augmented siphons is proposed for S4PR. Meanwhile, the concept of max'-controlled siphons is employed, which can relax the siphon controllability condition. By explicitly controlling elementary siphons via adding monitors, a live controlled sys-tem can be gained. In addition, the liveness-enforcing supervisor with more permissive behavior is obtained through the rearrangement of the output arcs of monitors.
引文
[1]I. B. Abdallah and H. A. ElMaraghy, "Deadlock prevention and avoidance in FMS:A Petri net based approach," International Journal of Advanced Manufacturing Technology, vol.14, no.10, pp.704-715,1998.
[2]T. Araki, Y. Sugiyama, T. Kasami, and J. Okui, "Complexity of the deadlock avoidance prob-lem," In Proc.2nd IBM Symposium on the Mathematical Foundations of Computer Science, pp.229-252,1977.
[3]E. Badouel and P. Darondeau, "Theory of regions," Lectures on Petri Nets I:Basic Models, Lecture Notes in Computer Science, vol.1491, W. Reisig and G. Rozenberg (Eds.), pp.529-586, 1998.
[4]Z. A. Banaszak and B. H. Krogh, "Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows," IEEE Transactions on Robotics and Automation, vol. 6, no.6, pp.724-734,1990.
[5]K. Barkaoui and J. F. Pradat-Peyre, "On liveness and controlled siphons in Petri nets," In Proc.17th International Conference on Application and Theory of Petri Nets, Lecture Notes in Computer Science, vol.1091, pp.57-72,1996.
[6]J. A. Bondy and U. S. R. Murty, "Graph Theory," Springer,2007.
[7]D. Y. Chao, "Max'-controlled siphons for liveness of S3PGR2." IET Control Theory and Application, vol.1, no.4, pp.933-936,2007.
[8]D. Y. Chao, "Incremental approach to computation of elementary siphons for arbitrary simple sequential processes with resources," IET Control Theory and Application, vol.2, no.2, pp.168-179,2008.
[9]D. Y. Chao, "Revised dependent siphons," International Journal of Advanced Manufacturing Technology, vol.43, no.1-2, pp.182-188,2009.
[10]Y. F. Chen and Z.W. Li, "Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems," Automatica, vol.47, no.5, pp.1028-1034,2011.
[11]Y. F. Chen, Z.W. Li, and M. Khalgui, "Design of a maximally permissive liveness-enforcing Petri net supervisor for flexible manufacturing systems," IEEE Transactions on Automation Science and Engineering, vol.8, no.2, pp.374-393,2011.
[12]Y. F. Chen, Z. W. Li, and A. M. Al-Ahmari, " Nonpure Petri Net Supervisors for Optimal Deadlock Control of Flexible Manufacturing Systems," IEEE Transactions on Systems, Man, and Cybernetics:Systems, vol.43, no.2, pp.252-265,2013.
[13]H. Cho, T. K. Kumaran, and R. A. Wysk, "Graph-theoretic deadlock detection and resolution for flexible manufacturing systems," IEEE Transactions on Robotics and Automation, vol.11, no.3, pp.413-421,1995.
[14]F. Chu and X. L. Xie, "Deadlock analysis of Petri nets using siphons and mathematical programming," IEEE Transactions on Robotics and Automation, vol.13, no.6, pp.793-804, 1997.
[15]E. G. Coffman, M. Elphick, and A. Shoshani, "Systems deadlocks," A CM Computing Surveys, vol.3, no.2, pp.67-78,1971.
[16]J. Ezpeleta, J. M. Couvreur, and M. Silva, "A new technique for finding a generating family of siphons, traps, and st-components:Application to colored Petri nets," In Advances in Petri Nets, Lecture Notes in Computer Science, vol.674, G. Rozenberg (Ed.), pp.126-147,1993.
[17]J. Ezpeleta, J. M. Colom, and J. Martinez, "A Petri net based deadlock prevention policy for flexible manufacturing systems," IEEE Transactions on Robotics and Automation, vol.11, no.2, pp.173-184,1995.
[18]J. Ezpeleta, F. Garcia-Valles, and J. M. Colom, "A class of well structured Petri nets for flexible manufacturing systems," In Proc.19th International Conference on Application and Theory of Petri Nets, Lecture Notes in Computer Science, vol.1420, J. Desel and M. Silva (Eds.), pp.64-83,1998.
[19]J. Ezpeleta, F. Tricas, F. Garcia-Valles, and J. M. Colom, "A banker's solution for deadlock aviodance in FMS with flexible routing and multiresource states," IEEE Transactions on Robotics and Automation, vol.18, no.4, pp.621-625,2002.
[20]J. Ezpeleta and L. Recalde, "A deadlock avoidance approach for non-sequential resource allocation systems," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.34, no.1, pp.93-101,2004.
[21]M. P. Fanti, G. Maione, and B. Turchiano, "Digraph-theoretic approach for deadlock detection and recovery in flexible production systems," Studies in Informatics and Control, vol.5, no. 4, pp.373-383,1996.
[22]M. P. Fanti, B. Maione, S. Mascolo, and B. Turchiano, "Performance of deadlock avoidance algorithms in flexible manufacturing systems," Journal of Manufacturing Systems, vol.15, no.3, pp.164-178,1996.
[23]M. P. Fanti, B. Maione, S. Mascolo, and B. Turchiano, "Event-based feedback control for deadlock avoidance in flexible production systems," IEEE Transactions on Robotics and Au-tomation, vol.13, no.3, pp.347-363,1997.
[24]M. P. Fanti, B. Maione, and B. Turchiano, "Comparing digraph and Petri net approaches to deadlock avoidance in FMS," IEEE Transactions on Systems, Man and Cybernetics, Part B, vol.30, no.5, pp.783-798,2000.
[25]M. P. Fanti, G. Maione, and B. Turchiano, "Distributed event-control for deadlock avoidance in automated manufacturing systems," International Journal Production Research, vol.39, no.9, pp.1993-2021,2001.
[26]M. P. Fanti, "Event-based controller to avoid deadlock and collisions in zone-control AGVs," International Journal of Production Research, vol.40, no.6, pp.1453-1478,2002.
[27]M. P. Fanti, G. Maione, and B. Turchiano, "Design of supervisors to avoid deadlock in flexible assembly systems," International Journal of Flexible Manufacturing Systems, vol.14. no.2, pp.153-171,2002.
[28]M. P. Fanti and M. C. Zhou, "Deadlock control methods in automated manufacturing sys-tems," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.34, no.1, pp. 5-22,2004.
[29]A. Ghaffari, N. Rezg, and X. L. Xie, "Design of a live and maximally permissive Petri net controller using the theory of regions," IEEE Transactions on Robotics and Automation, vol. 19, no.1, pp.137-141,2003.
[30]A. Giua, F. DiCesare, and M. Silva, "Generalized mutual exclusion constraints on nets with uncontrollable transitions," in Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, Chicago, U.S.A., pp.974-979,1992.
[31]Y. F. Hou, Z. W. Li, L. Hong, and A. M. Al-Ahmari, "On Optimal Controllability of 3-Composed Siphons in a Class of Petri Nets", Electronics Letters, vol.49, no.11, pp.697-699, 2013.
[32]F. S. Hsieh and S. C. Chang, "Dispatching-driven deadlock avoidance controller synthesis for flexible manufacturing systems," IEEE Transactions on Robotics and Automation, vol.10, no.2, pp.196-209,1994.
[33]F. S. Hsieh, "Fault-tolerant deadlock avoidance algorithm for assembly processes," IEEE Transactions Systems, Man, and Cybernetics, Part A, vol.34, no.1, pp.65-79,2004.
[34]Y. S. Huang, M. D. Jeng, X. L. Xie, and S. L. Chung, "Deadlock prevention policy based on Petri nets and siphons," International Journal of Production Research, vol.39, no.2, pp. 283-305,2001.
[35]Y. S. Huang, M. D. Jeng, X. L. Xie, and D. H. Chung, "Siphon-based deadlock preven-tion policy for flexible manufacturing systems," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.36, no.6, pp.1248-1256,2006.
[36]Y. S. Huang, "Deadlock prevention for sequence resource allocation systems," Journal of Information Science and Engineering, vol.23, no.1, pp.215-231,2007.
[37]M. V. Iordache, J. O. Moody, and P. J. Antsaklis, "A method for the synthesis of liveness-enforcing supervisors in Petri nets," Proceedings of the American Control Conference, Arling-ton, Virginia, USA, pp.4943-4948,2001.
[38]M. V. Iordache, J. O. Moody, and P. J. Antsaklis, " Synthesis of deadlock prevention super-visors using Petri nets," IEEE Transactions on Robotics and Automation, vol.18, no.1, pp. 59-68,2002.
[39]M. D. Jeng and X. L. Xie, "Deadlock detection and prevention of automated manufacturing systems using Petri nets and siphons," Deadlock Resolution in Computer-Integrated Systems, M. C. Zhou and M. P. Fanti (Eds.), New York:Marcel-Dekker Inc, pp.233-281,2005.
[40]T. K. Kumaran, W. Chang, H. Cho, and R. A. Wysk, "A structured approach to deadlock detection, avoidance and resolution in flexible manufacturing systems," International Journal of Production Research, vol.32, no.10, pp.2361-2379,1994.
[41]LAAS/CNRS, "TINA:Time Petri Net Analyzer," http://projects.laas.fr/tina/,2013.
[42]K. Lautenbach, "Linear algebraic calculation of deadlocks and traps," In Concurrency and Nets, K. Voss, H. J. Genrich and G. Rozenberg (Eds.), pp.315-336,1987.
[43]K. Lautenbach and H. Ridder, "Liveness in bounded Petri nets which are covered by T-invariants," In Proc.13th International Conference on Application and Theory of Petri Nets, Lecture Notes in Computer Science, vol.815, R. Valette (Ed.), pp.358-375,1994.
[44]K. Lautenbach and H. Ridder, "The linear algebra of deadlock avoidance-a Petri net approach," No.25-96, Technical Report, Institute of Software Technology, University of Koblenz-Landau, Koblenz, Germany,1996.
[45]M. A. Lawley, S. A. Reveliotis, and P. M. Ferreira, "Flexible manufacturing system structural control and the Neighborhood Policy, Part 2. Generalization, optimization, and efficiency," HE Transactions, vol.29, no.10, pp.889-899,1997.
[46]M. A. Lawley, S. A. Reveliotis, and P. M. Ferreira, "A correct and scalable deadlock avoidance policy for flexible manufacturing systems," IEEE Transactions on Robotics and Automation, vol.14, no.5, pp.796-809,1998.
[47]M. A. Lawley, S. A. Reveliotis, and P. M. Ferreira, "The application and evaluation of banker's algorithm for deadlock-free buffer space allocation in flexible manufacturing systems," Inter-national Journal of Flexible Manufacturing Systems, vol.10, no.1, pp.73-100,1998.
[48]M. A. Lawley, "Deadlock avoidance for production systems with flexible routing," IEEE Transactions on Robotics and Automation, vol.15, no.3, pp.497-509,1999.
[49]M. A. Lawley, "Integrating flexible routing and algebraic deadlock avoidance policies in au-tomated manufacturing systems," International Journal of Production Research, vol.38, no. 13, pp.2931-2950,2000.
[50]M. A. Lawley and S. A. Reveliotis, "Deadlock avoidance for sequential resource allocation systems:hard and easy cases," International Journal of Flexible Manufacturing Systems, vol. 13, no.4, pp.385-404,2001.
[51]M. A. Lawley and W. Sulistyono, "Robust supervisory control policies for manufacturing systems with unreliable resources," IEEE Transactions on Robotics and Automation, vol.18, no.3, pp.346-359,2002.
[52]Z. W. Li and A. R. Wang, "A Petri net based deadlock prevention approach for flexible manufacturing systems," Acta Automatica Sinca, vol.29, no.5, pp.733-740,2003.
[53]Z. W. Li and M. C. Zhou, "Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.34, no.1, pp.38-51,2004.
[54]Z. W. Li and N. Wei, "A deadlock control policy for FMS using elementary siphons of Petri nets and an MIP approach," in Proceedings of the IEEE International Conference on In-dustrial Technology, City University of Hong Kong, Hong Kong, Dec.14-17, pp.938-943, 2005.
[55]Z. W. Li and M. C. Zhou, "Comparison of two deadlock prevention methods for different-size flexible manifacturing systems," International Journal of Intelligent Control Systems, vol.10, no.3, pp.235-243,2005.
[56]Z. W. Li and M. C. Zhou, "Clarifications on the definitions of elementary siphons in Petri nets," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.36, no.6, pp. 1227-1229,2006.
[57]Z. W. Li and M. C. Zhou, "Two-stage method for synthesizing liveness-enforcing supervi-sors for flexible manufacturing systems using Petri nets," IEEE Transactions on Industrial Informatics, vol.2, no.4, pp.313-325,2006.
[58]Z. W. Li, H. S. Hu, and A. R. Wang, "Design of liveness-enforcing supervisors for flexible man-ufacturing systems using Petri nets," IEEE Transactions on Systems, Man, and Cybernetics, Part C, vol.37, no.4, pp.517-526,2007.
[59]Z. W. Li, J. Zhang, and M. Zhao, "Liveness-enforcing supervisor design for a class of gener-alized Petri net models of flexible manufacturing systems," IET Control Theory and Appli-cations, vol.1, no.4, pp.955-967,2007.
[60]Z. W. Li and M. C. Zhou, "Control of elementary and dependent siphons in Petri nets and their application," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.38, no.1, pp.133-148,2008.
[61]Z. W. Li, M. C. Zhou, and N. Q. Wu, "A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems," IEEE Transactions on Systems, Man, and Cybernetics, Part C, vol.38, no.2, pp.173-188,2008.
[62]Z. W. Li and M. C. Zhou, "On siphon computation for deadlock control in a class of Petri nets," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.38, no.3, pp.667-679,2008.
[63]Z. W. Li and M. Zhao, "On controllability of dependent siphons for deadlock prevention in generalized Petri nets," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol. 38, no.2, pp.369-384,2008.
[64]Z. W. Li, M. C. Zhou, and M. D. Jeng, "A maximally permissive deadlock prevention policy for FMS based on Petri net siphon control and the theory of regions," IEEE Transactions on Automation Science and Engineering, vol.5, no.1, pp.182-188,2008.
[65]Z. W. Li and M. C. Zhou, "Deadlock Resolution in Automated Manufacturing Systems:A Novel Petri Net Approach," Springer, London,2009.
[66]Z. W. Li, N. Q. Wu, and M. C. Zhou, "Deadlock control of automated manufacturing sys-tems based on Petri nets-a literature review," IEEE Transactions on Systems, Man, and Cybernetics, Part C:Applications and Reviews, vol.42, no.4, pp.437-462,2012.
[67]Z. W. Li, G. Y. Liu, M-H. Hanisch, and M. C. Zhou, "Deadlock prevention based on structure reuse of Petri net supervisors for flexible manufacturing systems," IEEE Transactions on Systems, Man and Cybernetics, Part A, vol.42, no.1, pp.178-191,2012.
[68]Z. W. Li and M. C. Zhou, "On Siphon Computation for Deadlock Control in a Class of Petri Nets", IEEE Transactions on Systems, Man and Cybernetics, Part A:Systems and Humans, vol.38, no.3, pp.667-679,2012.
[69]D. Liu, Z. W. Li, and M. C. Zhou, "Liveness of an extend S3PR," Automatica, vol.46, no.6, pp.1008-1018,2010.
[70]D. Liu, Z. W. Li, and M. C. Zhou, "Hybrid Liveness-Enforcing Policy for Generalized Petri Net Models of Flexible Manufacturing Systems", IEEE Transactions on Systems, Man, and Cybernetics:Systems, vol.43, no.l, pp.85-97,2013.
[71]J. O-Moody and P. J. Antsaklis, "Supervisory Control of Discrete Event Systems Using Petri Nets," Boston:Kluwer Academic Publishers,1998.
[72]T. Murata, "Petri nets:properties, analysis and application," Proceedings of the IEEE, vol. 77, no.4, pp.541-580,1989.
[73]J. Pablo and J. M. Colom, "Resource allocation systems:Some complexity results on the S4PR class," In Proc. IFIP International Federation for Information Processing, Lecture Notes in Computer Scicence, vol.4229, E. Najm et al. (Eds.), pp.323-338,2006.
[74]H. T. Papadopoulos, C. Heavey, and J. Browne, "Queueing Theory in Manufacturing Systems Analysis and Design," Chapman & Hall, London,1993.
[75]J. Park and S. A. Reveliotis, "Algebraic synthesis of efficient deadlock aviodance policies for sequential resource allocation systems," IEEE Transactions on Robotics and Automation, vol. 16, no.2, pp.190-195,2000.
[76]J. Park and S. A. Reveliotis, "Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings," IEEE Transactions on Automatic Control, vol.46, no.10, pp.1572-1583,2001.
[77]J. M. Proth and X. L. Xie, "Petri Nets. A tool for design and management of manufacturing systems," John Wiley and Sons,1996.
[78]M. Qin, Z. W. Li, M. C. Zhou, M. Khalgui, and O. Mosbahi, "Deadlock Prevention for a Class of Petri Nets with Uncontrollable and Unobservable Transitions", IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.42, no.3, pp.727-738,2012.
[79]P. J. Ramadge and W. M. Wonham, "Supervisory control of a class of discrete event pro-cesses," SIAM journal on Control and Optimization, vol.25, no.1, pp.206-230,1987.
[80]P. J. Ramadge and W. M. Wonham, "Modular feedback logic for discrete event systems," SIAM Journal on Control and Optimization, vol.25, no.5, pp.1202-1218,1987.
[81]P. J. Ramadge and W. M. Wonham, "The control of discrete event systems," Proceedings of the IEEE, vol.77, no.1, pp.81-98,1989.
[82]S. A. Reveliotis and P. M. Ferreira, "Deadlock avoidance policies for automated manufacturing cells," IEEE Transactions on Robotics and Automation, vol.12, no.6, pp.845-857,1996.
[83]S. A. Reveliotis, M. A. Lawley, and P. M. Ferreira, "Polynomial-complexity deadlock avoid-ance policies for sequential resource allocation systems," IEEE Transactions on Automatic Control, vol.42, no.10, pp.1344-1357,1997.
[84]M. Silva and E. Teruel, "Petri nets for the design and operation of manufacturing systems," European Journal of Control, vol.3, no.3, pp.182-199,1997.
[85]M. Silva and R. Valette, "Petri nets and flexible manufacturing," In Advances in Petri Nets, Lecture Notes in Computer Science, vol.424, G. Rozenberg (Ed.), pp.374-417,1990.
[86]F. Tricas and J. Martinez, "An extension of the liveness theory for concurrent sequential pro-cesses competing for shared resources," In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, Vancouver, British Columbia, Canada, pp.3035-3040, 1995.
[87]F. Tricas, F. Garcia-Valles, J. M. Colom, and J. Ezpelata, "A structural approach to the problem of deadlock prevention in processes with resources," In Proceedings of WODES'98, Italy,26-28 Auguest, pp.273-278,1998.
[88]F. Tricas, F. Garcia-Valles, J. M. Colom, and J. Ezpelata, "An iterative method for dead-lock prevention in FMS," In Discrete Event Systems:Analysis and Control, R. Boel and G. Stremersch (Eds.), Kluwer Academic:Boston, MA, pp.139-148,2000.
[89]F. Tricas, F. Garcia-Valles, J. M. Colom, and J. Ezpelata, "A Petri net structure-based deadlock prevention solution for sequential resource allocation systems," in Proceedings of the IEEE Transactions Conference on Robotics and Automation, Barcelona, Spain, Apr.18-22, pp.271-277,2005.
[90]W. T. Tutte, "Graph Theory,"Cambridge, U.K.:Cambridge Univ. Press,2001.
[91]M. Uzam, "An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions," International Journal of Advanced Manufacturing Technology, vol.19, no.3, pp.192-208,2002.
[92]M. Uzam and M. C. Zhou, "An improved iterative synthesis method for liveness enforcing supervisors of flexible manufacturing systems," International Journal of Production Research, vol.44, no.10, pp.1987-2030,2006.
[93]N. Viswanadham, Y. Narahari, and T. L. Johnson, "Deadlock prevention and deadlock avoidance in flexible manufacturing systems using Petri net models," IEEE Transactions on Robotics and Automation, vol.6, no.6, pp.713-723,1990.
[94]N. Viswanadham and Y. Narahari, "Performance modeling of automated manufacturing sys-tems," Prentice Hall, Engelwood Cliffs, NJ,1992.
[95]A. R. Wang, Z. W. Li, J. Y. Jia, and M. C. Zhou, "An effective algorithm to find elementary siphons in a class of petri nets," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.39, no.4, pp.912-923,2009.
[96]A. R. Wang, Z. W. Li, and M. C. Zhou, "Computation of strict minimal siphons in a class of Petri nets," Proceedings of 10th International Conference on Automation Technology, pp. 247-252,2009.
[97]A. R. Wang, Z. W. Li, and J. Y. Jia, "Efficient computation of strict minimal siphons for a class of Petri nets models of automated manufacturing systems," Transactions of the Institute of Measurement and Control, vol.33, no.1, pp.182-201,2011.
[98]N. Wei and Z. W. Li, "On the suboptimal liveness-enforcing supervisors based on Petri net structural analysis and the theory of regions," International Journal of Advanced Manufac-turing Technology, vol.38, no.1-2, pp.195-204,2008.
[99]D. B. West, "Introduction to Graph Theory," NJ:Pearson Education Inc.,2001.
[100]N. Q. Wu, "Necessary and sufficient conditions for deadlock-free operation in flexible man-ufacturing systems using a colored Petri net model," IEEE Transactions on Systems, Man, and Cybernetics, Part C, vol.29, no.2, pp.192-204,1999.
[101]N. Q. Wu and M. C. Zhou, "Avoiding deadlock and reducing starvation and blocking in automated manufacturing systems," IEEE Transactions on Robotics and Automation, vol. 17, no.5, pp.658-669,2001.
[102]N. Q. Wu and M. C. Zhou, "Modeling and deadlock avoidance of automated manufacturing systems with multiple automated guided vehicles," IEEE Transactions on Systems, Man, and Cybernetics, Part B, vol.35, no.6, pp.1193-1202,2005.
[103]N. Q. Wu and M. C. Zhou, "System Modeling and Control with Resource-Oriented Petri Nets," CRC Press, New York,2010.
[104]R. A. Wysk, N. S. Yang, and S. Joshi, "Detection of deadlocks in flexible manufacturing cells," IEEE Transactions on Robotics and Automation, vol.7, no.6, pp.853-859,1991.
[105]R. A. Wysk, N. S. Yang, and S. Joshi, "Resolution of deadlocks in flexible manufacturing systems:avoidance and recovery approaches," Journal of Manufacturing Systems, vol.13, no.2, pp.128-138,1994.
[106]K. Y. Xing, B. S. Hu, and H. X. Chen, "Deadlock avoidance policy for flexible manufac-turing systems," In Petri Nets in Flexible and Agile Automation, M. C. Zhou (Ed.), Kluwer Academic:Boston, MA, pp.239-263,1995.
[107]K. Y. Xing, B. S. Hu, and H. X. Chen, "Deadlock avoidance policy for Petri-net modeling of flexible manufacturing systems with shared resources," IEEE Transactions on Automatic Control, vol.41, no.2, pp.289-295,1996.
[108]A. Yalcin and T. O. Boucher, "Deadlock avoidance in flexible manufacturing systems using finite automata," IEEE Transactions on Robotics and Automation, vol.16, no.4, pp.424-429, 2000.
[109]M. Zhao and Z. W. Li, "On deadlock control for a class of generalised Petri net models of flexible manufacturing systems," International Journal of Production and Research, vol.47, no.21, pp.6085-6107,2009.
[110]M. Zhao, Z. W. Li, and H. S. Hu, "Suboptimal liveness-enforcing supervisor design for a class of generalized Petri nets using partial siphon enumeration and mathematical programming," International Journal of Systems Science, vol.41, no.9, pp.1013-1026,2010.
[111]M. Zhao. Y. F. Hou, and D. Liu, "Liveness-enforcing supervisors synthesis for a class of generalised Petri nets based on two-stage deadlock control and mathematical programming," International Journal of Control, vol.83, no.10, pp.2053-2066,2010.
[112]M. C. Zhou and F. DiCesare, "Petri net synthesis for discrete event control of manufacturing systems" Kluwer Academic Publishers, London,1993.
[113]M. C. Zhou and K. Venkatesh, "Modeling, Simulation and Control of Flexible Manufacturing Systems:A Petri Net Approach" World Scientific, Singapore,1998.
[114]C. F. Zhong, Z. W. Li, Y. F. Chen, and A. M. Al-Ahmari, "On Nonexistence of a Maximally Permissive Liveness-Enforcing Pure Net Supervisor," IEEE Transactions on Systems, Man, and Cybernetics:Systems, vol.43, no.1, pp.29-37,2013.
[115]B. Zouari and K. Barkaoui, "Parameterized supervisor synthesis for a modular class of discrete event systems," In Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, pp.1874-1879,2003.
[2]T. Araki, Y. Sugiyama, T. Kasami, and J. Okui, "Complexity of the deadlock avoidance prob-lem," In Proc.2nd IBM Symposium on the Mathematical Foundations of Computer Science, pp.229-252,1977.
[3]E. Badouel and P. Darondeau, "Theory of regions," Lectures on Petri Nets I:Basic Models, Lecture Notes in Computer Science, vol.1491, W. Reisig and G. Rozenberg (Eds.), pp.529-586, 1998.
[4]Z. A. Banaszak and B. H. Krogh, "Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows," IEEE Transactions on Robotics and Automation, vol. 6, no.6, pp.724-734,1990.
[5]K. Barkaoui and J. F. Pradat-Peyre, "On liveness and controlled siphons in Petri nets," In Proc.17th International Conference on Application and Theory of Petri Nets, Lecture Notes in Computer Science, vol.1091, pp.57-72,1996.
[6]J. A. Bondy and U. S. R. Murty, "Graph Theory," Springer,2007.
[7]D. Y. Chao, "Max'-controlled siphons for liveness of S3PGR2." IET Control Theory and Application, vol.1, no.4, pp.933-936,2007.
[8]D. Y. Chao, "Incremental approach to computation of elementary siphons for arbitrary simple sequential processes with resources," IET Control Theory and Application, vol.2, no.2, pp.168-179,2008.
[9]D. Y. Chao, "Revised dependent siphons," International Journal of Advanced Manufacturing Technology, vol.43, no.1-2, pp.182-188,2009.
[10]Y. F. Chen and Z.W. Li, "Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems," Automatica, vol.47, no.5, pp.1028-1034,2011.
[11]Y. F. Chen, Z.W. Li, and M. Khalgui, "Design of a maximally permissive liveness-enforcing Petri net supervisor for flexible manufacturing systems," IEEE Transactions on Automation Science and Engineering, vol.8, no.2, pp.374-393,2011.
[12]Y. F. Chen, Z. W. Li, and A. M. Al-Ahmari, " Nonpure Petri Net Supervisors for Optimal Deadlock Control of Flexible Manufacturing Systems," IEEE Transactions on Systems, Man, and Cybernetics:Systems, vol.43, no.2, pp.252-265,2013.
[13]H. Cho, T. K. Kumaran, and R. A. Wysk, "Graph-theoretic deadlock detection and resolution for flexible manufacturing systems," IEEE Transactions on Robotics and Automation, vol.11, no.3, pp.413-421,1995.
[14]F. Chu and X. L. Xie, "Deadlock analysis of Petri nets using siphons and mathematical programming," IEEE Transactions on Robotics and Automation, vol.13, no.6, pp.793-804, 1997.
[15]E. G. Coffman, M. Elphick, and A. Shoshani, "Systems deadlocks," A CM Computing Surveys, vol.3, no.2, pp.67-78,1971.
[16]J. Ezpeleta, J. M. Couvreur, and M. Silva, "A new technique for finding a generating family of siphons, traps, and st-components:Application to colored Petri nets," In Advances in Petri Nets, Lecture Notes in Computer Science, vol.674, G. Rozenberg (Ed.), pp.126-147,1993.
[17]J. Ezpeleta, J. M. Colom, and J. Martinez, "A Petri net based deadlock prevention policy for flexible manufacturing systems," IEEE Transactions on Robotics and Automation, vol.11, no.2, pp.173-184,1995.
[18]J. Ezpeleta, F. Garcia-Valles, and J. M. Colom, "A class of well structured Petri nets for flexible manufacturing systems," In Proc.19th International Conference on Application and Theory of Petri Nets, Lecture Notes in Computer Science, vol.1420, J. Desel and M. Silva (Eds.), pp.64-83,1998.
[19]J. Ezpeleta, F. Tricas, F. Garcia-Valles, and J. M. Colom, "A banker's solution for deadlock aviodance in FMS with flexible routing and multiresource states," IEEE Transactions on Robotics and Automation, vol.18, no.4, pp.621-625,2002.
[20]J. Ezpeleta and L. Recalde, "A deadlock avoidance approach for non-sequential resource allocation systems," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.34, no.1, pp.93-101,2004.
[21]M. P. Fanti, G. Maione, and B. Turchiano, "Digraph-theoretic approach for deadlock detection and recovery in flexible production systems," Studies in Informatics and Control, vol.5, no. 4, pp.373-383,1996.
[22]M. P. Fanti, B. Maione, S. Mascolo, and B. Turchiano, "Performance of deadlock avoidance algorithms in flexible manufacturing systems," Journal of Manufacturing Systems, vol.15, no.3, pp.164-178,1996.
[23]M. P. Fanti, B. Maione, S. Mascolo, and B. Turchiano, "Event-based feedback control for deadlock avoidance in flexible production systems," IEEE Transactions on Robotics and Au-tomation, vol.13, no.3, pp.347-363,1997.
[24]M. P. Fanti, B. Maione, and B. Turchiano, "Comparing digraph and Petri net approaches to deadlock avoidance in FMS," IEEE Transactions on Systems, Man and Cybernetics, Part B, vol.30, no.5, pp.783-798,2000.
[25]M. P. Fanti, G. Maione, and B. Turchiano, "Distributed event-control for deadlock avoidance in automated manufacturing systems," International Journal Production Research, vol.39, no.9, pp.1993-2021,2001.
[26]M. P. Fanti, "Event-based controller to avoid deadlock and collisions in zone-control AGVs," International Journal of Production Research, vol.40, no.6, pp.1453-1478,2002.
[27]M. P. Fanti, G. Maione, and B. Turchiano, "Design of supervisors to avoid deadlock in flexible assembly systems," International Journal of Flexible Manufacturing Systems, vol.14. no.2, pp.153-171,2002.
[28]M. P. Fanti and M. C. Zhou, "Deadlock control methods in automated manufacturing sys-tems," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.34, no.1, pp. 5-22,2004.
[29]A. Ghaffari, N. Rezg, and X. L. Xie, "Design of a live and maximally permissive Petri net controller using the theory of regions," IEEE Transactions on Robotics and Automation, vol. 19, no.1, pp.137-141,2003.
[30]A. Giua, F. DiCesare, and M. Silva, "Generalized mutual exclusion constraints on nets with uncontrollable transitions," in Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, Chicago, U.S.A., pp.974-979,1992.
[31]Y. F. Hou, Z. W. Li, L. Hong, and A. M. Al-Ahmari, "On Optimal Controllability of 3-Composed Siphons in a Class of Petri Nets", Electronics Letters, vol.49, no.11, pp.697-699, 2013.
[32]F. S. Hsieh and S. C. Chang, "Dispatching-driven deadlock avoidance controller synthesis for flexible manufacturing systems," IEEE Transactions on Robotics and Automation, vol.10, no.2, pp.196-209,1994.
[33]F. S. Hsieh, "Fault-tolerant deadlock avoidance algorithm for assembly processes," IEEE Transactions Systems, Man, and Cybernetics, Part A, vol.34, no.1, pp.65-79,2004.
[34]Y. S. Huang, M. D. Jeng, X. L. Xie, and S. L. Chung, "Deadlock prevention policy based on Petri nets and siphons," International Journal of Production Research, vol.39, no.2, pp. 283-305,2001.
[35]Y. S. Huang, M. D. Jeng, X. L. Xie, and D. H. Chung, "Siphon-based deadlock preven-tion policy for flexible manufacturing systems," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.36, no.6, pp.1248-1256,2006.
[36]Y. S. Huang, "Deadlock prevention for sequence resource allocation systems," Journal of Information Science and Engineering, vol.23, no.1, pp.215-231,2007.
[37]M. V. Iordache, J. O. Moody, and P. J. Antsaklis, "A method for the synthesis of liveness-enforcing supervisors in Petri nets," Proceedings of the American Control Conference, Arling-ton, Virginia, USA, pp.4943-4948,2001.
[38]M. V. Iordache, J. O. Moody, and P. J. Antsaklis, " Synthesis of deadlock prevention super-visors using Petri nets," IEEE Transactions on Robotics and Automation, vol.18, no.1, pp. 59-68,2002.
[39]M. D. Jeng and X. L. Xie, "Deadlock detection and prevention of automated manufacturing systems using Petri nets and siphons," Deadlock Resolution in Computer-Integrated Systems, M. C. Zhou and M. P. Fanti (Eds.), New York:Marcel-Dekker Inc, pp.233-281,2005.
[40]T. K. Kumaran, W. Chang, H. Cho, and R. A. Wysk, "A structured approach to deadlock detection, avoidance and resolution in flexible manufacturing systems," International Journal of Production Research, vol.32, no.10, pp.2361-2379,1994.
[41]LAAS/CNRS, "TINA:Time Petri Net Analyzer," http://projects.laas.fr/tina/,2013.
[42]K. Lautenbach, "Linear algebraic calculation of deadlocks and traps," In Concurrency and Nets, K. Voss, H. J. Genrich and G. Rozenberg (Eds.), pp.315-336,1987.
[43]K. Lautenbach and H. Ridder, "Liveness in bounded Petri nets which are covered by T-invariants," In Proc.13th International Conference on Application and Theory of Petri Nets, Lecture Notes in Computer Science, vol.815, R. Valette (Ed.), pp.358-375,1994.
[44]K. Lautenbach and H. Ridder, "The linear algebra of deadlock avoidance-a Petri net approach," No.25-96, Technical Report, Institute of Software Technology, University of Koblenz-Landau, Koblenz, Germany,1996.
[45]M. A. Lawley, S. A. Reveliotis, and P. M. Ferreira, "Flexible manufacturing system structural control and the Neighborhood Policy, Part 2. Generalization, optimization, and efficiency," HE Transactions, vol.29, no.10, pp.889-899,1997.
[46]M. A. Lawley, S. A. Reveliotis, and P. M. Ferreira, "A correct and scalable deadlock avoidance policy for flexible manufacturing systems," IEEE Transactions on Robotics and Automation, vol.14, no.5, pp.796-809,1998.
[47]M. A. Lawley, S. A. Reveliotis, and P. M. Ferreira, "The application and evaluation of banker's algorithm for deadlock-free buffer space allocation in flexible manufacturing systems," Inter-national Journal of Flexible Manufacturing Systems, vol.10, no.1, pp.73-100,1998.
[48]M. A. Lawley, "Deadlock avoidance for production systems with flexible routing," IEEE Transactions on Robotics and Automation, vol.15, no.3, pp.497-509,1999.
[49]M. A. Lawley, "Integrating flexible routing and algebraic deadlock avoidance policies in au-tomated manufacturing systems," International Journal of Production Research, vol.38, no. 13, pp.2931-2950,2000.
[50]M. A. Lawley and S. A. Reveliotis, "Deadlock avoidance for sequential resource allocation systems:hard and easy cases," International Journal of Flexible Manufacturing Systems, vol. 13, no.4, pp.385-404,2001.
[51]M. A. Lawley and W. Sulistyono, "Robust supervisory control policies for manufacturing systems with unreliable resources," IEEE Transactions on Robotics and Automation, vol.18, no.3, pp.346-359,2002.
[52]Z. W. Li and A. R. Wang, "A Petri net based deadlock prevention approach for flexible manufacturing systems," Acta Automatica Sinca, vol.29, no.5, pp.733-740,2003.
[53]Z. W. Li and M. C. Zhou, "Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.34, no.1, pp.38-51,2004.
[54]Z. W. Li and N. Wei, "A deadlock control policy for FMS using elementary siphons of Petri nets and an MIP approach," in Proceedings of the IEEE International Conference on In-dustrial Technology, City University of Hong Kong, Hong Kong, Dec.14-17, pp.938-943, 2005.
[55]Z. W. Li and M. C. Zhou, "Comparison of two deadlock prevention methods for different-size flexible manifacturing systems," International Journal of Intelligent Control Systems, vol.10, no.3, pp.235-243,2005.
[56]Z. W. Li and M. C. Zhou, "Clarifications on the definitions of elementary siphons in Petri nets," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.36, no.6, pp. 1227-1229,2006.
[57]Z. W. Li and M. C. Zhou, "Two-stage method for synthesizing liveness-enforcing supervi-sors for flexible manufacturing systems using Petri nets," IEEE Transactions on Industrial Informatics, vol.2, no.4, pp.313-325,2006.
[58]Z. W. Li, H. S. Hu, and A. R. Wang, "Design of liveness-enforcing supervisors for flexible man-ufacturing systems using Petri nets," IEEE Transactions on Systems, Man, and Cybernetics, Part C, vol.37, no.4, pp.517-526,2007.
[59]Z. W. Li, J. Zhang, and M. Zhao, "Liveness-enforcing supervisor design for a class of gener-alized Petri net models of flexible manufacturing systems," IET Control Theory and Appli-cations, vol.1, no.4, pp.955-967,2007.
[60]Z. W. Li and M. C. Zhou, "Control of elementary and dependent siphons in Petri nets and their application," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.38, no.1, pp.133-148,2008.
[61]Z. W. Li, M. C. Zhou, and N. Q. Wu, "A survey and comparison of Petri net-based deadlock prevention policies for flexible manufacturing systems," IEEE Transactions on Systems, Man, and Cybernetics, Part C, vol.38, no.2, pp.173-188,2008.
[62]Z. W. Li and M. C. Zhou, "On siphon computation for deadlock control in a class of Petri nets," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.38, no.3, pp.667-679,2008.
[63]Z. W. Li and M. Zhao, "On controllability of dependent siphons for deadlock prevention in generalized Petri nets," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol. 38, no.2, pp.369-384,2008.
[64]Z. W. Li, M. C. Zhou, and M. D. Jeng, "A maximally permissive deadlock prevention policy for FMS based on Petri net siphon control and the theory of regions," IEEE Transactions on Automation Science and Engineering, vol.5, no.1, pp.182-188,2008.
[65]Z. W. Li and M. C. Zhou, "Deadlock Resolution in Automated Manufacturing Systems:A Novel Petri Net Approach," Springer, London,2009.
[66]Z. W. Li, N. Q. Wu, and M. C. Zhou, "Deadlock control of automated manufacturing sys-tems based on Petri nets-a literature review," IEEE Transactions on Systems, Man, and Cybernetics, Part C:Applications and Reviews, vol.42, no.4, pp.437-462,2012.
[67]Z. W. Li, G. Y. Liu, M-H. Hanisch, and M. C. Zhou, "Deadlock prevention based on structure reuse of Petri net supervisors for flexible manufacturing systems," IEEE Transactions on Systems, Man and Cybernetics, Part A, vol.42, no.1, pp.178-191,2012.
[68]Z. W. Li and M. C. Zhou, "On Siphon Computation for Deadlock Control in a Class of Petri Nets", IEEE Transactions on Systems, Man and Cybernetics, Part A:Systems and Humans, vol.38, no.3, pp.667-679,2012.
[69]D. Liu, Z. W. Li, and M. C. Zhou, "Liveness of an extend S3PR," Automatica, vol.46, no.6, pp.1008-1018,2010.
[70]D. Liu, Z. W. Li, and M. C. Zhou, "Hybrid Liveness-Enforcing Policy for Generalized Petri Net Models of Flexible Manufacturing Systems", IEEE Transactions on Systems, Man, and Cybernetics:Systems, vol.43, no.l, pp.85-97,2013.
[71]J. O-Moody and P. J. Antsaklis, "Supervisory Control of Discrete Event Systems Using Petri Nets," Boston:Kluwer Academic Publishers,1998.
[72]T. Murata, "Petri nets:properties, analysis and application," Proceedings of the IEEE, vol. 77, no.4, pp.541-580,1989.
[73]J. Pablo and J. M. Colom, "Resource allocation systems:Some complexity results on the S4PR class," In Proc. IFIP International Federation for Information Processing, Lecture Notes in Computer Scicence, vol.4229, E. Najm et al. (Eds.), pp.323-338,2006.
[74]H. T. Papadopoulos, C. Heavey, and J. Browne, "Queueing Theory in Manufacturing Systems Analysis and Design," Chapman & Hall, London,1993.
[75]J. Park and S. A. Reveliotis, "Algebraic synthesis of efficient deadlock aviodance policies for sequential resource allocation systems," IEEE Transactions on Robotics and Automation, vol. 16, no.2, pp.190-195,2000.
[76]J. Park and S. A. Reveliotis, "Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings," IEEE Transactions on Automatic Control, vol.46, no.10, pp.1572-1583,2001.
[77]J. M. Proth and X. L. Xie, "Petri Nets. A tool for design and management of manufacturing systems," John Wiley and Sons,1996.
[78]M. Qin, Z. W. Li, M. C. Zhou, M. Khalgui, and O. Mosbahi, "Deadlock Prevention for a Class of Petri Nets with Uncontrollable and Unobservable Transitions", IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.42, no.3, pp.727-738,2012.
[79]P. J. Ramadge and W. M. Wonham, "Supervisory control of a class of discrete event pro-cesses," SIAM journal on Control and Optimization, vol.25, no.1, pp.206-230,1987.
[80]P. J. Ramadge and W. M. Wonham, "Modular feedback logic for discrete event systems," SIAM Journal on Control and Optimization, vol.25, no.5, pp.1202-1218,1987.
[81]P. J. Ramadge and W. M. Wonham, "The control of discrete event systems," Proceedings of the IEEE, vol.77, no.1, pp.81-98,1989.
[82]S. A. Reveliotis and P. M. Ferreira, "Deadlock avoidance policies for automated manufacturing cells," IEEE Transactions on Robotics and Automation, vol.12, no.6, pp.845-857,1996.
[83]S. A. Reveliotis, M. A. Lawley, and P. M. Ferreira, "Polynomial-complexity deadlock avoid-ance policies for sequential resource allocation systems," IEEE Transactions on Automatic Control, vol.42, no.10, pp.1344-1357,1997.
[84]M. Silva and E. Teruel, "Petri nets for the design and operation of manufacturing systems," European Journal of Control, vol.3, no.3, pp.182-199,1997.
[85]M. Silva and R. Valette, "Petri nets and flexible manufacturing," In Advances in Petri Nets, Lecture Notes in Computer Science, vol.424, G. Rozenberg (Ed.), pp.374-417,1990.
[86]F. Tricas and J. Martinez, "An extension of the liveness theory for concurrent sequential pro-cesses competing for shared resources," In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, Vancouver, British Columbia, Canada, pp.3035-3040, 1995.
[87]F. Tricas, F. Garcia-Valles, J. M. Colom, and J. Ezpelata, "A structural approach to the problem of deadlock prevention in processes with resources," In Proceedings of WODES'98, Italy,26-28 Auguest, pp.273-278,1998.
[88]F. Tricas, F. Garcia-Valles, J. M. Colom, and J. Ezpelata, "An iterative method for dead-lock prevention in FMS," In Discrete Event Systems:Analysis and Control, R. Boel and G. Stremersch (Eds.), Kluwer Academic:Boston, MA, pp.139-148,2000.
[89]F. Tricas, F. Garcia-Valles, J. M. Colom, and J. Ezpelata, "A Petri net structure-based deadlock prevention solution for sequential resource allocation systems," in Proceedings of the IEEE Transactions Conference on Robotics and Automation, Barcelona, Spain, Apr.18-22, pp.271-277,2005.
[90]W. T. Tutte, "Graph Theory,"Cambridge, U.K.:Cambridge Univ. Press,2001.
[91]M. Uzam, "An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions," International Journal of Advanced Manufacturing Technology, vol.19, no.3, pp.192-208,2002.
[92]M. Uzam and M. C. Zhou, "An improved iterative synthesis method for liveness enforcing supervisors of flexible manufacturing systems," International Journal of Production Research, vol.44, no.10, pp.1987-2030,2006.
[93]N. Viswanadham, Y. Narahari, and T. L. Johnson, "Deadlock prevention and deadlock avoidance in flexible manufacturing systems using Petri net models," IEEE Transactions on Robotics and Automation, vol.6, no.6, pp.713-723,1990.
[94]N. Viswanadham and Y. Narahari, "Performance modeling of automated manufacturing sys-tems," Prentice Hall, Engelwood Cliffs, NJ,1992.
[95]A. R. Wang, Z. W. Li, J. Y. Jia, and M. C. Zhou, "An effective algorithm to find elementary siphons in a class of petri nets," IEEE Transactions on Systems, Man, and Cybernetics, Part A, vol.39, no.4, pp.912-923,2009.
[96]A. R. Wang, Z. W. Li, and M. C. Zhou, "Computation of strict minimal siphons in a class of Petri nets," Proceedings of 10th International Conference on Automation Technology, pp. 247-252,2009.
[97]A. R. Wang, Z. W. Li, and J. Y. Jia, "Efficient computation of strict minimal siphons for a class of Petri nets models of automated manufacturing systems," Transactions of the Institute of Measurement and Control, vol.33, no.1, pp.182-201,2011.
[98]N. Wei and Z. W. Li, "On the suboptimal liveness-enforcing supervisors based on Petri net structural analysis and the theory of regions," International Journal of Advanced Manufac-turing Technology, vol.38, no.1-2, pp.195-204,2008.
[99]D. B. West, "Introduction to Graph Theory," NJ:Pearson Education Inc.,2001.
[100]N. Q. Wu, "Necessary and sufficient conditions for deadlock-free operation in flexible man-ufacturing systems using a colored Petri net model," IEEE Transactions on Systems, Man, and Cybernetics, Part C, vol.29, no.2, pp.192-204,1999.
[101]N. Q. Wu and M. C. Zhou, "Avoiding deadlock and reducing starvation and blocking in automated manufacturing systems," IEEE Transactions on Robotics and Automation, vol. 17, no.5, pp.658-669,2001.
[102]N. Q. Wu and M. C. Zhou, "Modeling and deadlock avoidance of automated manufacturing systems with multiple automated guided vehicles," IEEE Transactions on Systems, Man, and Cybernetics, Part B, vol.35, no.6, pp.1193-1202,2005.
[103]N. Q. Wu and M. C. Zhou, "System Modeling and Control with Resource-Oriented Petri Nets," CRC Press, New York,2010.
[104]R. A. Wysk, N. S. Yang, and S. Joshi, "Detection of deadlocks in flexible manufacturing cells," IEEE Transactions on Robotics and Automation, vol.7, no.6, pp.853-859,1991.
[105]R. A. Wysk, N. S. Yang, and S. Joshi, "Resolution of deadlocks in flexible manufacturing systems:avoidance and recovery approaches," Journal of Manufacturing Systems, vol.13, no.2, pp.128-138,1994.
[106]K. Y. Xing, B. S. Hu, and H. X. Chen, "Deadlock avoidance policy for flexible manufac-turing systems," In Petri Nets in Flexible and Agile Automation, M. C. Zhou (Ed.), Kluwer Academic:Boston, MA, pp.239-263,1995.
[107]K. Y. Xing, B. S. Hu, and H. X. Chen, "Deadlock avoidance policy for Petri-net modeling of flexible manufacturing systems with shared resources," IEEE Transactions on Automatic Control, vol.41, no.2, pp.289-295,1996.
[108]A. Yalcin and T. O. Boucher, "Deadlock avoidance in flexible manufacturing systems using finite automata," IEEE Transactions on Robotics and Automation, vol.16, no.4, pp.424-429, 2000.
[109]M. Zhao and Z. W. Li, "On deadlock control for a class of generalised Petri net models of flexible manufacturing systems," International Journal of Production and Research, vol.47, no.21, pp.6085-6107,2009.
[110]M. Zhao, Z. W. Li, and H. S. Hu, "Suboptimal liveness-enforcing supervisor design for a class of generalized Petri nets using partial siphon enumeration and mathematical programming," International Journal of Systems Science, vol.41, no.9, pp.1013-1026,2010.
[111]M. Zhao. Y. F. Hou, and D. Liu, "Liveness-enforcing supervisors synthesis for a class of generalised Petri nets based on two-stage deadlock control and mathematical programming," International Journal of Control, vol.83, no.10, pp.2053-2066,2010.
[112]M. C. Zhou and F. DiCesare, "Petri net synthesis for discrete event control of manufacturing systems" Kluwer Academic Publishers, London,1993.
[113]M. C. Zhou and K. Venkatesh, "Modeling, Simulation and Control of Flexible Manufacturing Systems:A Petri Net Approach" World Scientific, Singapore,1998.
[114]C. F. Zhong, Z. W. Li, Y. F. Chen, and A. M. Al-Ahmari, "On Nonexistence of a Maximally Permissive Liveness-Enforcing Pure Net Supervisor," IEEE Transactions on Systems, Man, and Cybernetics:Systems, vol.43, no.1, pp.29-37,2013.
[115]B. Zouari and K. Barkaoui, "Parameterized supervisor synthesis for a modular class of discrete event systems," In Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, pp.1874-1879,2003.