制造系统Petri网特殊标识求解算法

doi:10.3969/j.issn.1001-2400.2013.06.015

J4 ›› 2013, Vol. 40 ›› Issue (6): 85-91.doi: 10.3969/j.issn.1001-2400.2013.06.015

制造系统Petri网特殊标识求解算法

王祺;王安荣;蒲绪强

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

收稿日期:2013-04-15 出版日期:2013-12-20 发布日期:2014-01-10
通讯作者: 王祺
作者简介:王祺(1978-)，男，西安电子科技大学博士研究生，E-mail: wangqixu486@sina.com．
基金资助:
国家自然科学基金资助项目(61074035)；教育部高等学校博士点基金资助项目(20090203110009)

Computation of special markings of Petri nets of manufacturing systems

WANG Qi;WANG Anrong;PU Xuqiang

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

Received:2013-04-15 Online:2013-12-20 Published:2014-01-10
Contact: WANG Qi

摘要/Abstract

摘要：

基于整数规划提出了一种在Petri网部分可达图范围内求解危险标识的算法．该算法首先从死标识的定义出发，结合结构不变式(P-不变式)，求出Petri网的所有死标识；再利用状态方程，推算出到达这些死锁标识的坏标识及危险标识(如果Petri网不含有这些特殊标识，则输出结果为空集)；最后，用一个制造系统的Petri网对该算法进行仿真．仿真结果表明，使用该算法求解网的特殊标识(死标识和危险标识)，是通过求解部分可达标识实现的．该算法有效减小了算法的搜索空间，避免了Petri 网的状态空间爆炸问题．

关键词: 整数规划, Petri网, 危险状态, 死锁控制

Abstract:

This paper proposes a method to find the set of dangerous markings of Petri nets based on integer programming by computing a partial set of reachability markings. The proposed method can be used to find all deadlock markings by employing the definition of deadlock markings and the structure information(P-invariant) on Petri nets. Then the state equation is used to derive the sets of bad and dangerous markings. Finally, using the Petri net model of a manufacturing system，we verify the computation of special markings(such as deadlock markings and dangerous markings). Experimental results show that the special markings can be computed by obtaining the partial reachability graph，which reduces state the space explosion problem.

Key words: integer programming, Petri nets, dangerous markings, deadlock control

王祺;王安荣;蒲绪强. 制造系统Petri网特殊标识求解算法[J]. J4, 2013, 40(6): 85-91.

WANG Qi;WANG Anrong;PU Xuqiang. Computation of special markings of Petri nets of manufacturing systems[J]. J4, 2013, 40(6): 85-91.

参考文献

［1］ Ezpeleta J, Colom J M, Martinez J. A Petri Net Based Deadlock Prvention Policy for Flexible Manufacturing Systems ［J］. IEEE Transcations on Robotics and Automation, 1995, 11(2): 173-184.
［2］陈玉峰, 李志武. 安全Petri网事件分离状的BDD算法［J］. 西安电子科技大学学报, 2010, 37(1): 119-124.
Chen Yufeng, Li Zhiwu. Computation of Marking/Transition Separation Instances for Safe Petri Nets Using BDD ［J］. Journal of Xidian University, 2010, 37(1): 119-124.
［3］ Zhu Rongming. Deadlock Prvention Approach for Flexible Manufacturing Systems with Uncontrollable Transitions in Their Petri Net Models ［J］. Asian Journal of Control, 2012, 14(1): 217-229.
［4］ Daniel Y C. A New Optimal Control Policy for a Well-known S³PR(Systems of Simple Sequential Processes with Resources) ［J］. International Journal of Production Research, 2012, 50(22): 6259-6271.
［5］ Wu Naiqi, Zhou Mengchu, Hu Gang. One-Step Look-Ahead Maximally Permissive Deadlock Control of AMS by Using Petri Nets ［J］. ACM Transactions on Embedded Computing Systems(TECS), 2013, 12(10): 1-23.
［6］ Chen Yufeng, Li Gaiyun. Computation of Minimal Siphons in Petri Nets by Using Binary Decision Diagrams ［J］. ACM Transactions on Embedded Computing Systems(TECS), 2013, 12(3): 1-15.
［7］ Hu Hesuan, Zhou Mengchu, Li Zhiwu, et al. Deadlock-free Control of Automated Manufacturing Systems with Flexible Routes and Assembly Operations Using Petri Nets ［J］. IEEE Transactions on Industrial Informatics, 2013, 9(1): 109-121.
［8］ Ghaffari A, Rezg N, Xie X L. Design of a Live and Maximally Permissive Petri Net Controller Using the Theory of Regions ［J］. IEEE Transcations on Robotics and Automation, 2003, 19(1): 137-142.
［9］ Chen Yufeng, Li Zhiwu. Design of a Maximally Permissive Liveness-enforcing Supervisor with a Compressed Supervisory Structure for Flexible Manufacturing Systems ［J］. IEEE Transcations on Automation and Engineering, 2011, 8(2): 374-393.
［10］ Li Zhiwu, Zhou Mengchu. Deadlock Resolution in Automated Manufacturing Systems: a Novel Petri Net Approach ［M］. London: Springer Verlag, 2009.
［11］李志武, 周孟初. 自动制造系统建模、分析与死锁控制［M］. 北京: 科学出版社, 2009.

[1]	刘益岑,陈兴凯,卢昱,乔文欣. 一种软件定义网络的安全服务路径优化构建机制[J]. 西安电子科技大学学报, 2019, 46(1): 158-165.
[2]	王祺;陈晓亮. 一种用于柔性制造系统混惑状态估计的算法[J]. 西安电子科技大学学报, 2017, 44(2): 69-74.
[3]	马子玥;童音. 采用基本标识图的Petri网控制策略[J]. 西安电子科技大学学报, 2016, 43(6): 68-73.
[4]	蒋忠远;张秀艳;马子玥. 智能电网中电能存储系统的容量优化[J]. J4, 2015, 42(6): 106-112.
[5]	张秀艳;钟春富;贾建援. S³PR网的可达标识集算法[J]. J4, 2015, 42(5): 105-109.
[6]	张丽;赵良煦;王寿光;汪成英. 针对α网的最优线性约束转换方法[J]. J4, 2015, 42(5): 183-187+212.
[7]	陈晓亮;蒋忠远;叶剑虹 . 工作流网的混或检测和预防策略 [J]. J4, 2015, 42(2): 77-83.
[8]	朱承丞;董利达. 一种多线程软件并发漏洞检测方法 [J]. J4, 2015, 42(2): 167-173+212.
[9]	尤丹;刘苗;吴文慧;王寿光. S³PR网的严格极小信标计算方法[J]. J4, 2014, 41(4): 193-197+204.
[10]	洪良. S³PR网可达标识数的一种有效估算方法[J]. J4, 2014, 41(3): 169-173.
[11]	李晔;王映辉;于振华. 信息物理融合系统的面向对象Petri网建模[J]. J4, 2014, 41(2): 165-171.
[12]	张曼;段振华. 工作流网合成规则及其在流程设计中的应用[J]. J4, 2012, 39(2): 200-206.
[13]	陈玉峰;李志武. 安全Petri网事件分离状态的BDD算法[J]. J4, 2010, 37(1): 119-124+141.
[14]	郭金维;李志武. 一种时延Petri网的死锁预防方法[J]. J4, 2009, 36(5): 902-908.
[15]	朱森;李志武. 双航母编队C³I系统Petri网建模与分析研究[J]. J4, 2009, 36(4): 661-668.

制造系统Petri网特殊标识求解算法

Computation of special markings of Petri nets of manufacturing systems

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0