2.845

2023影响因子

(CJCR)

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

留言板

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

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

无界Petri网的可达树的综述

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

文章导航 > 自动化学报  > 2015 >  41(4): 686-693
干梦迪, 王寿光, 周孟初, 李俊, 李月. 无界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
shu
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
shu

无界Petri网的可达树的综述

doi: 10.16383/j.aas.2015.c140097
  • 1.

    浙江工商大学信息与电子工程学院 杭州 310018, 中国;

  • 2.

    同济大学电子与信息工程学院 上海 201804, 中国;

  • 3.

    新泽西理工学院电子与计算机工程系 纽瓦克市 07102, 美国;

  • 4.

    东南大学自动化学院 南京 210096, 中国

基金项目: 

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

详细信息
    作者简介:

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

    通讯作者:

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

A Survey of Reachability Trees of Unbounded Petri Nets

  • 1.

    School of Information and Electronic Engineering, Zhejiang Gongshang University, Hangzhou 310018, China;

  • 2.

    School of Electronic and Information Engineering, Tongji University, Shanghai 201804, China;

  • 3.

    Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark 07102, USA;

  • 4.

    School of Automation, Southeast University, Nanjing 210096, China

Funds: 

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网可达性问题的研究方向.
    Abstract: In recent years both industry and academia have paid much attention to the theory and applications of Petri nets. Reachability is a basic property of a Petri net, and many properties can be analyzed via it. However, analyzing the reachability problem of unbounded Petri nets by finite reachability trees has been an open problem since the inception of Petri nets. Researchers began to study the problem of reachability trees over 40 years ago. However, they made only limited progress over the last 20 years due to its complexity and difficulty. We present an overview of some important contributions toward its solution. The focuses are on four novel finite reachability trees: finite reachability tree(FRT), augmented reachability tree(ART), modified reachability tree(MRT) and new modified reachailbity tree(NMRT). The paper concludes with a discussion of directions for future research of the reachability problem of unbounded Petri nets.
    • HTML全文
    • 参考文献(64)
  • [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
    • 相关文章
    • 施引文献
  • 资源附件(0)
  • 加载中
计量
  • 文章访问数:  2355
  • HTML全文浏览量:  96
  • PDF下载量:  1777
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-02-19
  • 修回日期:  2014-05-15
  • 刊出日期:  2015-04-20

目录

    /

    返回文章
    返回

    版权所有 © 《自动化学报》编辑部  京ICP备14019135号-6

    地址：北京中关村东路95号邮政编码：100190E-mail：aas_editor@ia.ac.cn

    电话：010-82544677 (日常咨询和稿件处理)，010-82544653(费用管理、寄刊)

    本系统由 北京仁和汇智信息技术有限公司 开发 技术支持： info@rhhz.net   百度统计