PDF《第30 卷第 6 期》

第30 卷第

6 期2013 年6月控制理论与应用Control Theory &

Applications Vol.

30 No.

6 Jun.

2013 一一一类 类 类活 活 活性 性性Petri网网网控 控 控制 制 制器 器 器的 的 的冗 冗 冗余 余 余检 检 检测 测 测及 及 及结 结 结构 构 构简 简 简化 化化DOI: 10.7641/CTA.2013.20881 徐姗姗2 , 董利达1? , 朱丹3 , 朱承丞3 (1. 杭州师范大学 杭州国际服务工程学院, 浙江 杭州 310012;

2. 解放军陆军军官学院 管理工程教研室, 安徽 合肥 230031;

3. 浙江大学 电子电路与信息系统研究所, 浙江 杭州 310027) 摘要: S4 R(systems of sequential systems with shared resources)网是分析和解决柔性制造系统死锁现象常用的一种 重要的Petri网子类模型, 现有的基于S4 R网的死锁预防方法通常采用对部分或者全部严格极小信标添加控制库所 来实现. 此类方法的不足在于得到的活性S4 R控制器中往往存在冗余控制库所. 针对已为网中每一个严格极小信标 都逐一添加了控制库所和相关连接弧的活性S4 R控制器, 本文提出并设计了一种基于整数规划技术的冗余检测及 结构简化方法, 由此得到结构更简单、 行为允许度更高的活性S4 R控制器. 该方法的核心思想是: 如果网中已经存 在一个PC不变式使得某个严格极小信标满足最大受控条件, 那么为该严格极小信标添加的控制库所就是冗余的. 由于该方法无需进行Petri网的可达性分析, 避免了状态组合爆炸问题, 因此具有较高的可行性和计算效率. 最后用 实验验证了本文方法的正确性和有效性. 关键词: Petri网;

柔性制造系统;

信标;

死锁预防;

整数规划 中图分类号: TP278 文献标识码: A Redundancy detection and structure simpli?cation for a class of liveness-enforcing Petri net supervisors XU Shan-shan2, DONG Li-da1?, ZHU Dan3, ZHU Cheng-cheng3 (1. Hangzhou Institute of Service Engineering, Hangzhou Normal University, Hangzhou Zhejiang 310012, China;

2. Department of Management Engineering, Army Of?cer Academy, PLA, Hefei Anhui 230031, China;

3. Institute of Electronic Circuit and Information System, Zhejiang University, Hangzhou Zhejiang 310027, China) Abstract: S4 R (systems of sequential systems with shared resources) is an important subclass of Petri nets used in ana- lyzing and solving deadlock problem of ?exible manufacturing systems (FMS). Control places and related arcs are usually added for all or some of the strictly minimal siphons (SMS) by the existing S4 R-oriented deadlock prevention methods. The defect of such methods is that there are redundant control places in the generated liveness-enforcing supervisors. For a liveness-enforcing S4 R supervisor in which each SMS has been controlled by its control place, this paper proposes an integer-programming-technique-based method to detect the redundancy for control places and simplify the structure for the system. Then, it can produce the liveness-enforcing S4 R supervisor with simpler structure and more permissible behaviors. The main idea is that if there is already a P-invariant in the net which makes an SMS max-controlled, then the control place added for this SMS is redundant. Because this method doesn'

t need the reachability analysis, it can avoid the state explosion problem, and therefore it brings about high feasibility and computational ef?ciency. Finally, the experiments validate the correctness and feasibility of the proposed method. Key words: Petri net;