2.793

2018影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

无界Petri网的可达树的综述

干梦迪 王寿光 周孟初 李俊 李月

干梦迪, 王寿光, 周孟初, 李俊, 李月. 无界Petri网的可达树的综述. 自动化学报, 2015, 41(4): 686-693. doi: 10.16383/j.aas.2015.c140097
引用本文: 干梦迪, 王寿光, 周孟初, 李俊, 李月. 无界Petri网的可达树的综述. 自动化学报, 2015, 41(4): 686-693. doi: 10.16383/j.aas.2015.c140097
GAN Meng-Di, WANG Shou-Guang, ZHOU Meng-Chu, LI Jun, LI Yue. A Survey of Reachability Trees of Unbounded Petri Nets. ACTA AUTOMATICA SINICA, 2015, 41(4): 686-693. doi: 10.16383/j.aas.2015.c140097
Citation: GAN Meng-Di, WANG Shou-Guang, ZHOU Meng-Chu, LI Jun, LI Yue. A Survey of Reachability Trees of Unbounded Petri Nets. ACTA AUTOMATICA SINICA, 2015, 41(4): 686-693. doi: 10.16383/j.aas.2015.c140097

无界Petri网的可达树的综述


DOI: 10.16383/j.aas.2015.c140097
详细信息
    作者简介:

    干梦迪 同济大学电子与信息工程学院硕士研究生.2014年获浙江工商大学信息与电子工程学院学士学位.主要研究方向为离散事件系统监控理论和Petri网理论与应用.E-mail:mengdigan@126.com

    通讯作者: 王寿光 浙江工商大学信息与电子工程学院教授.2005年获浙江大学电气学院控制理论与控制工程专业博士学位.主要研究方向为离散事件系统监控理论,Petri网理论与应用,生产调度.本文通信作者.E-mail:wsg5000@hotmail.com
  • 基金项目:

    国家自然科学基金(61374148,61100056,61374069),浙江省杰出青年基金(LR14F020001),浙江省科技计划项目(2013C31111),浙江省新型网络标准与应用技术重点实验室(2013E10012)资助

A Survey of Reachability Trees of Unbounded Petri Nets

More Information
  • Fund Project:

    Supported by National Natural Science Foundation of China(61374148, 61100056, 61374069), Zhejiang Natural Science Foundation for Distinguished Young Scholar(LR14F020001), Zhejiang Science and Technology Project(2013C31111), and Zhejiang New Network Standard and Technology(NNST) Key Laboratory(2013E10012)

  • 摘要: Petri网自提出以来得到了学术界和工业界的广泛关注. Petri网系统的可达性是最基本性质之一.系统的其他相关性质都可以通过可达性进行分析.利用等价的有限可达树来研究无界Petri网可达性,依然是一个开放性问题.该研究可以追溯到40年前,但由于问题本身的复杂性和难度太大,直到最近20年,经过国内外诸多学者的不懈努力,才逐渐取得了一些阶段性的成果和部分突破.本文回顾了近40年来国内外学者为彻底解决该问题作出的贡献.重点对4种开创性的研究成果展开讨论,分别为有限可达树、扩展可达树、改进可达树及新型改进可达树.探讨了今后无界Petri网可达性问题的研究方向.
  • [1] Petri C A. Kommunikation Mit Automater [Ph.D. dissertation], Insitiut fur Instrumentelle Mathematik Schriften des ⅡM Nr.z, Germany. 1962.
    [2] [2] Bourdeaud'huy T, Hanafi S, Yim P. Solving the Petri Nets Reachability Problem Using the Logical Abstraction Technique and Mathematical Programming. Berlin:Springer, 2004. 112-126
    [3] [3] Finkel A. The Minimal Coverability Graph for Petri Nets. Berlin:Springer Berlin Heidelberg, 1993. 210-243
    [4] [4] Hrz B, Zhou M C. Modeling and Control of Discrete-Event Dynamic Systems:With Petri Nets and Other Tools. Berlin:Springer, 2007.
    [5] [5] Keller R M. Vector Replacement Systems:A Formalism for Modeling Asynchronous Systems. Princeton:Department of Electrical Engineering Computer Sciences Laboratory Princeton University, 1972.
    [6] [6] Li Z W, Zhou M C. Deadlock Resolution in Automated Manufacturing Systems:A Novel Petri Net Approach. Berlin:Springer, 2009.
    [7] [7] Wang S G, Wang C Y, Yu Y P. On the existence of complementary-place supervisors that enforce the liveness in S3PR. In:Proceedings of the 2010 International Conference on Mechatronics and Automation. Xi'an, China:IEEE, 2010. 1624-1628
    [8] [8] Wang S G, Wang C Y, Zhou M C. Controllability conditions of resultant siphons in a class of petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part A:Systems and Humans, 2012, 42(5):1206-1215
    [9] [9] Wang S G, Wang C Y, Zhou M C, Li Z W. A method to compute strict minimal siphons in S3PR based on loop resource subsets. IEEE Transactions on Systems, Man, and Cybernetics, Part A:Systems and Humans, 2012, 42(1):226-237
    [10] Wang Y H, Jiang B, Jiao L. Property checking for 1-place-unbounded petri nets. In:Proceedings of the 2010 IEEE International Symposium on Theoretical Aspects of Software Engineering(TASE). Taipei, China:IEEE, 2010. 117-125
    [11] Yuan Chong-Yi. The Principle and Application of Petri Nets. Beijing:Electronic Industry Press, 2005.(袁祟义. Petri 网原理与应用. 北京:电子工业出版社, 2005.)
    [12] Bellettini C, Carlo L, Capra L. Reachability analysis of time basic Petri nets:a time coverage approach. In:Proceedings of the 2011 International Symposium on Symbolic and Numeric Algorithms for Scientific Computing. Timisoara, Romania:IEEE, 2011. 110-117
    [13] Ferrarini L. On the reachability and reversibility problems in a class of Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, 1994, 24(10):1474-1482
    [14] Fanti M P, Zhou M C. Deadlock control methods in automated manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics, Part A:Systems and Humans, 2004, 34(1):5-22
    [15] Jeng M D, Peng M Y. On the liveness problem of 1-place-unbounded Petri nets. In:Proceedings of the 1997 International Conference on Systems, Man, and Cybernetics, Computational Cybernetics and Simulation. Orlando, FL:IEEE, 1997. 3221-3226
    [16] Jeng M D, Peng M Y. Augmented reachability trees for 1-place-unbounded generalized Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part A:Systems and Humans, 1999, 29(2):173-183
    [17] Jones N D, Landweber L H, Edmund L Y. Complexity of some problems in Petri nets. Theoretical Computer Science, 1977, 4(3):277-299
    [18] Mayr E W. An algorithm for the general Petri net reachability problem. SIAM Journal on Computing, 1984, 13(3):441-460
    [19] Murata T. Petri nets:properties, analysis and applications. Proceedings of the IEEE, 1989, 77(4):541-580
    [20] Ru Y, Hadjicostis C N. Reachability analysis for a class of Petri nets. In:Proceedings of the 48th IEEE Conference on Decision and Control. Shanghai, China:IEEE, 2009. 1261-1266
    [21] Wang J, Deng Y, Xu G. Reachability analysis of real-time systems using time Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 2000, 30(5):725-736
    [22] Wu N Q. Necessary and sufficient conditions for deadlock-free operation in flexible manufacturing systems using a colored Petri net model. IEEE Transactions on Systems, Man, and Cybernetics, Part C:Applications and Reviews, 1999, 29(2):192-204
    [23] Wu N Q, Bai L, Chu C. Modeling and conflict detection of crude oil operations for refinery process based on controlled colored timed Petri net. IEEE Transactions on Systems, Man, and Cybernetics, Part C:Applications and Reviews, 2007, 37(4):461-472
    [24] Wu Zhe-Hui, Jiang Chang-Jun. Conversion algorithm of bounded Petri nets. Journal of Software, 1992, 3(1):23-29(吴哲辉, 蒋昌俊. 有界 Petri 网的可达图到网图的转换算法. 软件学报, 1992, 3(1):23-29)
    [25] Bourdeaud'huy T, Hanafi S, Yim P. Mathematical programming approach to the Petri nets reachability problem. European Journal of Operational Research, 2007, 177(1):176-197
    [26] Jiang Chang-Jun, Wu Zhe-Hui. Labeled reachability tree of Petri nets. Journal of Software, 1993, 4(6):22-28(蒋昌俊, 吴哲辉. Petri 网的标注可达树. 软件学报, 1993, 4(6):22-28)
    [27] Karp R M, Miller R E. Parallel program schemata. Journal of Computer and System Sciences, 1969, 3(2):147-195
    [28] Li J Q, Fan Y S, Zhou M C. Performance modeling and analysis of workflow. IEEE Transactions on Systems, Man, and Cybernetics, Part A:Systems and Humans, 2004, 34(2):229-242
    [29] Kultz R M, Knzle L A, Silva F. Applying Hm Heuristics in Petri Nets Reachability Problem. Berlin:Springer, 2010. 163-173
    [30] Taoka S, Watanabe T. Heuristic algorithms for the marking construction problem of Petri nets. In:Proceedings of the 2010 International Symposium on Circuits and Systems(ISCAS). Paris, France:IEEE, 2010. 1344-1347
    [31] Takahashi K, Ono I, Satoh H, Kobayashi S. An efficient genetic algorithm for reachability problems. In:Proceedings of the 30th International Conference on System Sciences. Wailea, HI, USA:IEEE, 1997. 89-98
    [32] Yeh W J, Young M. Compositional reachability analysis using process algebra. In:Proceedings of the 1991 ACM Transactions on the Symposium on Testing, Analysis, and Verification. New York, USA:IEEE, 1991. 49-59
    [33] Notomi M, Murata T. Hierarchical reachability graph of bounded Petri nets for concurrent-software analysis. IEEE Transactions on Software Engineering, 1994, 20(5):325-336
    [34] Ahmad F, Huang H J, Wang X L, Anwer W. A technique for generating the reduced reachability graph of Petri net models. In:Proceedings of the 2008 IEEE International Conference on Systems, Man, and Cybernetics. Singapore:IEEE, 2008. 3636-3641
    [35] Schmidt K. Parameterized reachability trees for algebraic Petri nets. Application and Theory of Petri Nets. Berlin:Springer, 1995. 392-411
    [36] Peterson J L. Petri Net Theory and the Modeling of Systems. NJ:Prentice-Hall, 1981.
    [37] Wang F Y. A modified reachability tree for Petri nets. In:Proceedings of the 1991 International Conference on Systems, Man, and Cybernetics. Charlottesville, VA:IEEE, 1991. 329-334
    [38] Wang F Y, Gao Y Q, Zhou M C. A modified reachability tree approach to analysis of unbounded Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 2004, 34(1):303-308
    [39] Wang S G, Zhou M C, Li Z W, Wang C Y. A new modified reachability tree approach and its applications to unbounded Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part A:Systems and Humans, 2013, 43(4):932-940
    [40] Zhou M C. Modeling, analysis, simulation, scheduling, and control of semiconductor manufacturing systems:a Petri net approach. IEEE Transactions on Semiconductor Manufacturing, 1998, 11(3):333-357
    [41] Wong H M, Zhou M C. Automated generation of modified reachability trees for Petri nets. In:Proceedings of the 1992 Regional Control Conference. Brooklyn, NY, 1992. 119-121
    [42] Ru Y, Wu W, Hadjicostis C N. Comments on a modified reachability tree approach to analysis of unbounded petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 2006, 36(5):1210-1210
    [43] Ding Z J, Jiang C J, Zhou M C. Deadlock checking for one-place unbounded Petri nets based on modified reachability trees. IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 2008, 38(3):881-883
    [44] Wang S G, Gan M D, Zhou M C. Macro liveness graph and liveness of -independent unbounded nets. Science China Information Sciences, 2015, 58(3):1-10
    [45] Li Zhi-Wu, Wang An-Rong. A Petri net based deadlock pre-vention approach for exible manufacturing systems. Acta Automatica Sinica, 2003, 29(5):733-740(李志武, 王安荣. 基于Petri 网的柔性制造系统一种预防死锁方法. 自动化学报, 2003, 29(5):733-740)
    [46] Xing Ke-Yi, Tian Feng, Yang Xiao-Jun, Hu Bao-Sheng. Polynomial-complexity deadlock avoidance policies for automated manufacturing systems. Acta Automatica Sinica, 2007, 33(8):893-896(邢科义, 田锋, 杨小军, 胡保生. 具有多项式时间复杂性的避免制造系统死锁控制策略. 自动化学报, 2007, 33(8):893-896)
    [47] Fu Jian-Feng, Dong Li-Da, Xu Shan-Shan, Zhu Dan, Zhu Cheng-Cheng. An improved liveness condition for S4PR nets. Acta Automatica Sinica, 2013, 39(9):1439-1446(傅健丰, 董利达, 徐姗姗, 朱丹, 朱承丞. 一种改进型的S4PR 网活性条件. 自动化学报, 2013, 39(9):1439-1446)
    [48] Florin G, Natkin S. Generalization of queueing network product form solutions to stochastic Petri nets. IEEE Transactions on Software Engineering, 1991, 17(2):99-107
    [49] Wang Y, Ding Z J. Analysis for one-place unbounded Petri nets based on modified reachability trees. In:Proceedings of the 2010 International Conference on Networking, Sensing and Control(ICNSC). Beijing, China:IEEE, 2012. 107-111
    [50] Chen Y, Li Z, Zhou M C. Optimal supervisory control of flexible manufacturing systems by Petri nets:a set classification approach. IEEE Transactions on Automation Science and Engineering, 2014, 11(2):549-563
    [51] Chen Y, Li Z, Zhou M C. Behaviorally optimal and structurally simple liveness-enforcing supervisors of flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans, 2012, 42(3):615-629
    [52] Ding Z H, Zhou M C, Wang S G. Ordinary differential equation based deadlock detection. IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2014, 44(10):1435-1454
    [53] Ding Z H, Zhou Y, Zhou M C. A polynomial algorithm to performance analysis of concurrent systems via Petri nets and ordinary differential equations. IEEE Transactions on Automation Science and Engineering, 2015, 12(1):295-308
    [54] Huang Y S, Pan Y L, Zhou M C. Computationally improved optimal deadlock control policy for flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans, 2012, 42(2):404-415
    [55] Li Z, Zhou M C, Jeng M D. 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, 2008, 5(1):182-188
    [56] Uzam M, Zhou M C. An iterative synthesis approach to Petri netbased deadlock prevention policy for flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics, Part A, 2007, 37(3):362-371
    [57] Uzam M, Zhou M C. An improved iterative synthesis method for liveness enforcing supervisors of flexible manufacturing systems. International Journal of Production Research, 2006, 44(10):1987-2030
    [58] Chen Y F, Li Z W, Khalgui M, Mosbahi O. Design of a maximally permissive liveness-enforcing Petri net supervisor for flexible manufacturing systems. IEEE Transactions on Automation Science and Engineering, 2011, 8(2):374-393
    [59] Chen Y F, Li Z W. Design of a maximally permissive livenessenforcing supervisor with a compressed supervisory structure for flexible manufacturing systems. Automatica, 2011, 47(5):1028-1034
    [60] Chen Y F, Li Z W, Al-Ahmari A. Nonpure Petri net supervisors for optimal deadlock control of flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2013, 43(2):252-265
    [61] Xing K, Han L, Zhou M C. Deadlock-free genetic scheduling algorithm for automated manufacturing systems based on deadlock control policy. IEEE Transactions on Systems, Man, and Cybernetics:Part B, 2012, 42(3):603-615
    [62] Xiong H H, Zhou M C. Scheduling of semiconductor test facility via Petri nets and hybrid heuristic search. IEEE Transactions on Semiconductor Manufacturing, 1998, 11(3):384-393
    [63] Luo J C, Xing K Y, Zhou M C, Li X L, Wang X N. Deadlock-free scheduling of automated manufacturing systems via Petri nets and hybrid heuristic search. IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2015, 45(3):530-541
    [64] Huang B, Zhu H, Zhang G, Lu X. On further reduction of constraints in nonpure Petri net supervisors for optimal deadlock control of flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2015, 45(3):542-543
  • [1] 董易, 施心陵, 王霞, 王耀民, 吕丹桔, 张松海, 李孙寸. 斐波那契树优化算法求解多峰函数全局最优解的可达性分析[J]. 自动化学报, 2018, 44(9): 1679-1689. doi: 10.16383/j.aas.2017.c160703
    [2] 甘永梅, 晁武杰, 王兆安. 基于状态树结构的离散事件系统模块化监督控制[J]. 自动化学报, 2013, 39(7): 1018-1026. doi: 10.3724/SP.J.1004.2013.01018
    [3] 吴敏, 颜钢锋, 林志赟. 多面体上彷射系统可达性问题研究[J]. 自动化学报, 2009, 35(12): 1528-1533. doi: 10.3724/SP.J.1004.2009.01528
    [4] 吴敏, 颜钢锋, 张瑶瑶, 刘妹琴. 基于Petri网结构分析的监控器综合[J]. 自动化学报, 2008, 34(8): 964-971. doi: 10.3724/SP.J.1004.2008.00964
    [5] 罗继亮, 吴维敏, 苏宏业, 褚健. 事件图的混合控制器设计[J]. 自动化学报, 2007, 33(2): 218-221. doi: 10.1360/aas-007-0218
    [6] 李志武, 贾建援. 自动制造系统Petri网的公平活性控制策略[J]. 自动化学报, 2003, 29(1): 62-71.
    [7] 吴维敏, 董利达, 王肖, 苏宏业, 褚健. 离散事件系统的混合型Petri网控制器[J]. 自动化学报, 2003, 29(5): 681-688.
    [8] 张军英, 许进, 保铮. 遗传交叉运算的可达性研究[J]. 自动化学报, 2002, 28(1): 120-125.
    [9] 邢科义, 席裕庚, 胡保生. 具有不可控变迁离散事件系统的Petri网控制器[J]. 自动化学报, 2001, 27(2): 180-185.
    [10] 田国会, 刘长有, 徐心和. 旋转货架系统运行过程的时态逻辑描述与分析[J]. 自动化学报, 1998, 24(3): 373-376.
    [11] 古天龙, 高衿畅, 周春晖. 离散事件系统的一种N步在线监控策略[J]. 自动化学报, 1997, 23(3): 404-407.
    [12] 陈浩勋. 一类受控Petri网的状态反馈逻辑的综合[J]. 自动化学报, 1996, 22(5): 576-580.
    [13] 曾宪强, 吴智铭. 广义随机Petri网在制造系统中的应用[J]. 自动化学报, 1995, 21(2): 198-202.
    [14] 颜文俊, 孙优贤. 部分能观的DES监控器设计[J]. 自动化学报, 1995, 21(6): 730-733.
    [15] 杨小军, 法京怀, 郑应平. 一种求可观子语言的算法[J]. 自动化学报, 1994, 20(3): 352-355.
    [16] 李勇华, 高为炳. 实时离散事件系统的动态反馈控制[J]. 自动化学报, 1994, 20(2): 209-212.
    [17] 陆维明, 林闯. 生产系统的Petri网模型[J]. 自动化学报, 1993, 19(3): 290-299.
    [18] 杨小军, 郑应平. 离散事件系统监控与状态反馈方法的等价性[J]. 自动化学报, 1993, 19(6): 670-677.
    [19] 张军英. 对DES实行优化控制的一种方法[J]. 自动化学报, 1992, 18(1): 96-101.
    [20] 杨小军, 郑应平. 部分同步离散事件系统的分散监控[J]. 自动化学报, 1992, 18(6): 728-732.
  • 加载中
计量
  • 文章访问数:  1682
  • HTML全文浏览量:  86
  • PDF下载量:  1726
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-02-19
  • 修回日期:  2014-05-15
  • 刊出日期:  2015-04-20

无界Petri网的可达树的综述

doi: 10.16383/j.aas.2015.c140097
    基金项目:

    国家自然科学基金(61374148,61100056,61374069),浙江省杰出青年基金(LR14F020001),浙江省科技计划项目(2013C31111),浙江省新型网络标准与应用技术重点实验室(2013E10012)资助

    作者简介:

    干梦迪 同济大学电子与信息工程学院硕士研究生.2014年获浙江工商大学信息与电子工程学院学士学位.主要研究方向为离散事件系统监控理论和Petri网理论与应用.E-mail:mengdigan@126.com

    通讯作者: 王寿光 浙江工商大学信息与电子工程学院教授.2005年获浙江大学电气学院控制理论与控制工程专业博士学位.主要研究方向为离散事件系统监控理论,Petri网理论与应用,生产调度.本文通信作者.E-mail:wsg5000@hotmail.com

摘要: Petri网自提出以来得到了学术界和工业界的广泛关注. Petri网系统的可达性是最基本性质之一.系统的其他相关性质都可以通过可达性进行分析.利用等价的有限可达树来研究无界Petri网可达性,依然是一个开放性问题.该研究可以追溯到40年前,但由于问题本身的复杂性和难度太大,直到最近20年,经过国内外诸多学者的不懈努力,才逐渐取得了一些阶段性的成果和部分突破.本文回顾了近40年来国内外学者为彻底解决该问题作出的贡献.重点对4种开创性的研究成果展开讨论,分别为有限可达树、扩展可达树、改进可达树及新型改进可达树.探讨了今后无界Petri网可达性问题的研究方向.

English Abstract

干梦迪, 王寿光, 周孟初, 李俊, 李月. 无界Petri网的可达树的综述. 自动化学报, 2015, 41(4): 686-693. doi: 10.16383/j.aas.2015.c140097
引用本文: 干梦迪, 王寿光, 周孟初, 李俊, 李月. 无界Petri网的可达树的综述. 自动化学报, 2015, 41(4): 686-693. doi: 10.16383/j.aas.2015.c140097
GAN Meng-Di, WANG Shou-Guang, ZHOU Meng-Chu, LI Jun, LI Yue. A Survey of Reachability Trees of Unbounded Petri Nets. ACTA AUTOMATICA SINICA, 2015, 41(4): 686-693. doi: 10.16383/j.aas.2015.c140097
Citation: GAN Meng-Di, WANG Shou-Guang, ZHOU Meng-Chu, LI Jun, LI Yue. A Survey of Reachability Trees of Unbounded Petri Nets. ACTA AUTOMATICA SINICA, 2015, 41(4): 686-693. doi: 10.16383/j.aas.2015.c140097
参考文献 (64)

目录

    /

    返回文章
    返回