信标可控性定义及问题

尤丹; 王寿光; 周孟初

doi:10.3724/SP.J.1004.2014.02687

信标可控性定义及问题

doi: 10.3724/SP.J.1004.2014.02687

尤丹¹,
王寿光^1, ,,
周孟初^2,3

1.
浙江工商大学信息与电子工程学院杭州 310018, 中国;
2.
同济大学教育部嵌入式系统与服务计算重点实验室上海 201804, 中国;
3.
美国新泽西理工学院电子与计算机工程系纽瓦克市 NJ 07102, 美国

基金项目:

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

详细信息

作者简介:
尤丹浙江工商大学信息与电子工程学院硕士研究生. 主要研究方向为离散事件系统监控理论, Petri 网理论与应用.E-mail: youdan000@hotmail.com

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

计量
- 文章访问数: 1845
- HTML全文浏览量: 65
- PDF下载量: 738
- 被引次数: 0
出版历程
- 收稿日期: 2013-10-28
- 修回日期: 2014-02-17
- 刊出日期: 2014-12-20

Siphon Controllability Definitions and Issues

1.
School of Information & Electronic Engineering, Zhejiang Gongshang University, Hangzhou 310018, China;
2.
The Key Laboratory of Embedded System and Service Computing of Ministry of Education, Tongji University, Shanghai 201804, China;
3.
Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark NJ 07102, USA

Funds:

Supported by National Natural Science Foundation of China (61472361, 61100056, 61374148), Zhejiang Natural Science Foundation for Distinguished Young Scholar (LR14F020001), Zhejiang Science and Technology Project (2013C31111), the New Network Standard and Technology Key Laboratory of Zhejiang Province Project(2013E10012), and Zhejiang Gongshang University Innovation Project (CX201411010)

摘要

摘要: 死锁是资源分配系统中极不希望出现的现象,目前死锁控制的一个重要的方法是信标控制法,信标控制法的基础是信标可控性的定义.对于普通Petri网,已有一个完善的信标可控性定义,而对于一般Petri网,这方面的工作还需改进和完善.近年来,学者们针对一般Petri 网及其子类提出了不少信标可控性定义,但这些定义并不完善,仍有大量的问题亟待解决.首先回顾了文献中的各个信标可控性定义,提出了两个新的信标可控性定义,然后从可控性定义的宽松程度、应用范围以及等价性等方面分析比较了现有的信标可控性定义优缺点.最后给出了今后的研究方向.
- Petri网 /
- 活性 /
- 信标 /
- 可控性
Abstract: Deadlocks are an extremely undesirable situation in resource allocation systems. Nowadays, siphon control, which is based on siphon controllability conditions, is one of the important methods to ensure that deadlocks never occur in systems. For ordinary Petri nets, the siphon controllability condition is well defined. However, it remains an open question for generalized Petri nets despite many attempts to define their siphon controllability conditions. In recent years, many such conditions have been proposed for them or their subclasses, but suffer from various problems. This paper surveys the existing siphon controllability conditions and then presents two new ones. All of them are compared in terms of their condition strictness, application scope and equivalence. Future research directions are also indicated.
- Petri net /
- liveness /
- siphon /
- controllability

HTML全文

参考文献(34)

[1]	Li Zhi-Wu, Zhou Meng-Chu. Modeling, Analysis, and Deadlock Control of Automated Manufacturing Systems. Beijing: Science Press, 2009.(李志武, 周孟初. 自动制造系统的建模、分析与死锁控制. 北京: 科学出版社, 2009.)
[2]	Uzam M. An optimal deadlock prevention policy for flexible manufacturing systems using Petri net models with resources and the theory of regions. The International Journal of Advanced Manufacturing Technology, 2002, 19(3): 192-208
[3]	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
[4]	Chen Y F, Li Z W. On structural minimality of optimal supervisors for flexible manufacturing systems. Automatica, 2012, 48(10): 2647-2656
[5]	Chen Y F, Li Z W, 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
[6]	Chen Y F, Li Z W. Design of a maximally permissive liveness-enforcing supervisor with a compressed supervisory structure for flexible manufacturing systems. Automatica, 2011, 47(5): 1028-1034
[7]	Li Z W, Hu H S, Wang A R. Design of liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2007, 37(4): 517-526
[8]	Li Z W, Zhou M C. Control of elementary and dependent siphons in Petri nets and their application. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2008, 38(1): 133-148
[9]	Park J, Reveliotis S A. Deadlock avoidance in sequential resource allocation systems with multiple resource acquisitions and flexible routings. IEEE Transactions on Automatic Control, 2001, 46(10): 1572-1583
[10]	Chao D Y. Max'-controlled siphons for liveness of S3PGR2. IET Control Theory & Applications, 2007, 1(4): 933-936
[11]	Ezpeleta J, Colom J M, Martinez J. A Petri net based deadlock prevention policy for flexible manufacturing systems. IEEE Transactions on Robotics and Automation, 1995, 11(2): 173-184
[12]	Wang S G, Wang C Y, Zhou M C, Li Z W. A method to compute strict minimal siphons in a class of Petri nets based on loop resource subsets. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2012, 42(1): 226-237
[13]	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
[14]	Wang S G, Wang C Y, Yu Y P. Comments on "Siphon-based deadlock prevention policy for flexible manufacturing systems". IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2011, 41(2): 338-340
[15]	Wang S G, Wang C Y, Yu Y P. Design of liveness-enforcing supervisors for S^3PR based on complementary places. ACM Transactions on Embedded Computing Systems-Special Issue on Modeling and Verification of Discrete Event, 2013, 12(1): 1-18
[16]	Chu F, Xie X L. Deadlock analysis of Petri nets using siphons and mathematical programming. IEEE Transactions on Robotics and Automation, 1997, 13(6): 793-804
[17]	Li Zhi-Wu, Wang An-Rong. A Petri net based deadlock prevention approach for flexible manufacturing systems. Acta Automatica Sinica, 2003, 29(5): 733-740(李志武, 王安荣. 基于Petri网的柔性制造系统一种预防死锁方法. 自动化学报, 2003, 29(5): 733-740)
[18]	Li Z W, Zhou M C. Elementary siphons of Petri nets and their application to deadlock prevention in flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2004, 34(1): 38-51
[19]	Li Z W, Zhou M C. Two-stage method for synthesizing liveness-enforcing supervisors for flexible manufacturing systems using Petri nets. IEEE Transactions on Industrial Informatics, 2006, 2(4): 313-325
[20]	Li Z W, Zhou M C. A polynomial-complexity approach to decide the existence of a maximally permissive Petri net supervisor using elementary siphons. In: Proceedings of the 2009 IEEE International Conference on Networking, Sensing and Control. Okayama, Japan: IEEE, 2009. 608-613
[21]	Huang Y S. Design of deadlock prevention supervisors using Petri nets. The International Journal of Advanced Manufacturing Technology, 2007, 35(3-4): 349-362
[22]	Xing K Y, Hu B S. Optimal liveness Petri net controllers with minimal structures for automated manufacturing systems. In: Proceedings of the 2005 IEEE International Conference on Systems, Man, and Cybernetics. Hawaii, USA: IEEE, 2005. 282-287
[23]	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)
[24]	Xu Shan-Shan, Dong Li-Da, Zhu Dan, Zhu Cheng-Cheng. Redundancy detection and structure simplification for a class of liveness-enforcing Petri net supervisors. Control Theory & Applications, 2013, 30(6): 673-682 (徐姗姗, 董利达, 朱丹, 朱承丞. 一类活性Petri网控制器的冗余检测及结构简化. 控制理论与应用, 2013, 30(6): 673-682)
[25]	Huang Y S, Jeng M D, Xie X L, Chung S L. A deadlock prevention policy for flexible manufacturing systems using siphons. In: Proceedings of the 2001 IEEE International Conference on Robotics and Automation. Seoul, Korea: IEEE, 2001. 541-546
[26]	Barkaoui K, Pradat-Peyre J F. On liveness and controlled siphons in Petri nets. In: Proceedings of the 17th International Conference on Applications and Theory of Petri Nets. Berlin, Heidelberg: Springer, 1996. 57-72
[27]	Abdallah I B, ElMaraghy H A. Deadlock prevention and avoidance in FMS: a Petri net based approach. The International Journal of Advanced Manufacturing Technology, 1998, 14(10): 704-715
[28]	Liu Gai-Yun. Structural Analysis of and Supervisor Design for Petri Nets of Automated Manufacturing Systems [Ph.D. dissertation], Xidian University, China, 2011(刘改云. 自动制造系统的Petri网结构分析和控制器设计 [博士学位论文], 西安电子科技大学, 中国, 2011)
[29]	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)
[30]	Wang Y, Kelly T, Kudlur M, Lafortune S, Mahlke S. Gadara: dynamic deadlock avoidance for multi-threaded programs. Operating Systems Design & Implementation, 2008, 8: 281-294
[31]	Wang Y, Liao H W, Reveliotis S, Kelly T, Mahlke S A, Lafortune S. Gadara nets: modeling and analyzing lock allocation for deadlock avoidance in multi-threaded software. In: Proceedings of the 48th IEEE Conference on Decision and Control. Shanghai, China: IEEE, 2009. 4971-4976
[32]	Liao H W, Wang Y, Cho H K, Stanley J, Kelly T, Lafortune S, Mahlke S, Reveliotis S. Concurrency bugs in multithreaded software: modeling and analysis using Petri nets. Discrete Event Dynamic Systems, 2013, 23(2): 157-195
[33]	Liao H W, Wang Y, Stanley J, Lafortune S, Reveliotis S, Kelly T, Mahlke S. Eliminating concurrency bugs in multithreaded software: a new approach based on discrete-event control. IEEE Transactions on Control Systems Technology, 2013, 21(6): 2067-2082
[34]	Zhong C, Li Z. Self-liveness of a class of Petri net models for flexible manufacturing systems. IET Control Theory & Applications, 2010, 4(3): 403-410

施引文献

资源附件(0)

访问统计

点击查看大图

计量

文章访问数: 1845
HTML全文浏览量: 65
PDF下载量: 738
被引次数: 0

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

留言板

信标可控性定义及问题

doi: 10.3724/SP.J.1004.2014.02687

作者简介:
尤丹浙江工商大学信息与电子工程学院硕士研究生. 主要研究方向为离散事件系统监控理论, Petri 网理论与应用.E-mail: youdan000@hotmail.com

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

计量

Siphon Controllability Definitions and Issues

计量

目录

留言板

信标可控性定义及问题

doi: 10.3724/SP.J.1004.2014.02687

作者简介: 尤丹 浙江工商大学信息与电子工程学院硕士研究生. 主要研究方向为离散事件系统监控理论, Petri 网理论与应用.E-mail: youdan000@hotmail.com

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

计量

出版历程

Siphon Controllability Definitions and Issues

计量

出版历程

目录

作者简介:
尤丹浙江工商大学信息与电子工程学院硕士研究生. 主要研究方向为离散事件系统监控理论, Petri 网理论与应用.E-mail: youdan000@hotmail.com

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