一种时延Petri网的死锁预防方法

J4 ›› 2009, Vol. 36 ›› Issue (5): 902-908.

一种时延Petri网的死锁预防方法

郭金维;李志武

(西安电子科技大学机电工程学院，陕西西安 710071)

收稿日期:2008-07-15 出版日期:2009-10-20 发布日期:2009-11-30
通讯作者: 郭金维
基金资助:
国家自然科学基金资助(60474018，60773001);高等学校博士点基金资助(20070701013);国家部委预研基金资助(J4.3.6)

Deadlock prevention approach for a class of timed Petri nets

GUO Jin-wei;LI Zhi-wu

(School of Mechano-electronic Engineering, Xidian Univ., Xi'an 710071， China)

Received:2008-07-15 Online:2009-10-20 Published:2009-11-30
Contact: GUO Jin-wei

摘要/Abstract

摘要：

针对时延Petri网的死锁预防问题，提出了一个有效的预防控制算法，将信标控制死锁预防的方法应用到时延Petri网中，不需要列举全部可达状态的情况下实现死锁预防，而且实现最后的控制器为活．首先将时延Petri网拉伸为拉伸时延Petri网(SPN)，使得不改变原来系统性能的情况下，拉伸后的网所有变迁均为单位时延，然后针对SPN忽略时间因素，采用信标控制方法，根据所得标识约束添加控制库所，使所有严格极小信标均为P-不变式可控，最后还原时延Petri网，得到活的、结构简单的Petri网监督控制器．

关键词: 柔性制造系统, 时延Petri网, 死锁预防

Abstract:

To solve the problem of deadlock prevention for timed Petri nets, an effective prevention policy based on siphons is proposed. Without enumerating the reachable markings, deadlock prevention is achieved and the final supervisor is live. First, a timed Petri net is stretched into an SPN. Without influence on the system performance, each transition in the SPN has a unit time delay. Then by ignoring the factor of delay time, the siphon-control-based approach is applied. Monitors based on the marking constraints are added to the plant model to ensure all strict minimal siphons in the net invariant-controlled. A liveness-enforcing supervisor with a simple structure can be realized by reverting the TPN.

Key words: flexible manufacturing systems, timed Petri nets, deadlock prevention

中图分类号:

TP278

郭金维;李志武. 一种时延Petri网的死锁预防方法[J]. J4, 2009, 36(5): 902-908.

参考文献

［1］Murata T. Petri Nets: Properties, Analysis, and Applications ［J］. Proceedings of the IEEE, 1989, 77(4): 541-580.
［2］Salum L. Petri Nets and Time Modelling ［J］. Int J Adv Manuf Technol, 2008, 38(3-4): 377-382.
［3］Bowden F D J. A Brief Survey and Synthesis of the Roles of Time in Petri Nets ［J］. Mathematical and Computer Modeling, 2000, 31(10): 55-68.
［4］Wang J C. Timed Petri Nets: Theory and Application ［M］. Norwell: Kluwer Academic, 1998.
［5］Zhou M C, Venkatesh K. Modeling, Simulation, and Control of Flexible Manufacturing Systems: A Petri Net Approach ［M］. Singapore: Singapore World Scientific, 1999.
［6］Wang J C, Deng Y, Xu G. Reachability Analysis of Real-Time Systems Using Time Petri Nets ［J］, IEEE Trans on Syst Man and Cybern, 2000, 30(5): 725-736,
［7］Salum L. New Perspectives in Time (d) Petri Nets and their Analysis［C］//Proceedings of the 2003 IEEE Conference on Control Applications. Istanbul: IEEE, 2003:1041-1045.
［8］Salum L. Representing Time as a State in Petri Nets ［C］//Proceeding of the 2nd International Responsive Manufacturing. Gaziantep: Wikitedia Press, 2002: 955-960.
［9］Aybar A, Iftar A. Supervisory Controller Design for Timed Petri Nets ［C］//Proceedings of the 2006 IEEE/SMC International Conference on Systems Engineering. Los Angeles: IEEE, 2006: 59-64.
［10］Giua A, Seatzu C, Basile F. Observer-Based State-Feedback Control of Timed Petri Nets with Deadlock Recovery ［J］. IEEE Trans on Automatic Control, 2004, 49(1):17-29.
［11］Li Z W, Zhou M C. Elementary Siphons of Petri Nets and Their Application to Deadlock Prevention in Flexible Manufacturing Systems ［J］. IEEE Trans on Syst Man Cybern, 2004, 34(1): 38-51.
［12］Ezpeleta J, Colom J M, Martinez J. A Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems ［J］. IEEE Trans. on Robot Automat, 1995, 11(2): 173-184.
［13］Li Z W, Zhang X F. A Deadlock Prevention Approach Using Elementary Siphons for a Class of Petri Nets［C］//Proceedings of the 2004 IEEE International Conference on Systems, Man and Cybernetics: 2. Hague: IEEE, 2004: 1728-1733.
［14］Huang Y S, Jeng M D, Xie X L, et al. A Deadlock Prevention Policy for Flexible Manufacturing Systems Using Siphons［C］//Proc IEEE Int Conj Robot Automat. Seoul: IEEE, 2001: 541-546.
［15］Barkaoui K, Pradat-Peyre J F. On the Liveness and Controlled Siphons in Petri Nets［C］//Proc of 17th Int Conf Application and Theory of Petri Nets, LNCS. New York: Springer-Verlag,1996: 57-72.
［16］Abdallah I B, Elmaraghy H A. Deadlock Prevention and Avoidance in FMS: a Petri Net Based Approach［J］. Int J Adv Manuf Technol, 1998, 14(10): 704-715.
［17］Li Z W, Zhou M C. Clarifications on the Definitions of Elementary Siphons of Petri Nets ［J］. IEEE Trans on Syst Man Cybern, 2006, 36(6): 1227-1229.
［18］Li Z W, Zhou M C. Control of Elementary and Dependent Siphons in Petri Nets and Their Application ［J］. IEEE Trans on Syst Man Cybern, 2008, 38(1): 133-148.

[1]	王祺;陈晓亮. 一种用于柔性制造系统混惑状态估计的算法[J]. 西安电子科技大学学报, 2017, 44(2): 69-74.
[2]	尤丹;刘苗;吴文慧;王寿光. S³PR网的严格极小信标计算方法[J]. J4, 2014, 41(4): 193-197+204.
[3]	洪良. S³PR网可达标识数的一种有效估算方法[J]. J4, 2014, 41(3): 169-173.
[4]	闫明明;李志武;钟春富. S<sup>3</sup>PR网的一种死锁预防策略 [J]. J4, 2008, 35(2): 330-333.
[5]	赵咪;李志武. 一类离散事件系统的非阻塞监督控制器设计 [J]. J4, 2006, 33(5): 735-738.
[6]	胡核算;李志武;王安荣. 最优基本信标在柔性制造系统死锁控制中的应用[J]. J4, 2006, 33(4): 607-611.
[7]	李志武;徐平江;朱荣明;王兴平. 柔性制造系统活性监督控制器的简化设计[J]. J4, 2006, 33(3): 442-447.
[8]	李志武;马雄. 一种利用基本信标的柔性制造系统死锁控制器设计方法[J]. J4, 2006, 33(2): 262-267.
[9]	李志武;丁伟;朱荣明. 考虑FMS资源故障的一种死锁预防策略[J]. J4, 2005, 32(6): 833-838.
[10]	暂时无作者信息. 柔性制造系统调度算法研究[J]. J4, 2002, 29(1): 35-39.
[11]	暂时无作者信息. 集成电路虚拟制造系统[J]. J4, 2001, 28(4): 443-448.
[12]	刘宏;李志武;叶尚辉. FMS的一种实时控制Petri网模型及其应用[J]. J4, 1997, 24(2): 0-0.