PDF《第30 卷第 6 期》

?exible manufacturing system (FMS);

siphon;

deadlock prevention;

integer programming

1 引引引言 言言(Introduction) 在柔性制造系统(?exible manufacturing system, FMS)对工件并行处理、 加工过程中, 需要高度共 享、 竞争使用系统中有限的资源, 由此可能导致系 统运行中的死锁[1] . 死锁发生时, 系统中部分或者全 部工作流程停滞, 它们互相等待彼此占有的资源而 无法继续执行, 给生产造成经济损失. 为分析和解决 FMS中的死锁问题, 基于Petri网[2C3] , 研究人员构建 了一系列的FMS模型, 其中, S3 PR(systems of simple sequential processes with resources)[4] 和S4 R[5] (也称作S4 PR[6] 或S3 PGR2 : systems of simple sequential pro- cesses with general resources requirement[7] )是研究FMS死锁预防策略的两种经典模型. 近年来, S4 R模 型逐渐取代S3 PR, 成为当前国内外学术界研究的热 点. S4 R模型具备了对大部分FMS的建模与分析能 力(S3 PR是其特殊子类), 是一种结构复杂性与行为 收稿日期: 2012?08?17;

收修改稿日期: 2013?01?20. ?通信作者. E-mail: [email protected]. 基金项目: 国家自然科学基金资助项目(61071062);

浙江省自然科学基金资助项目(Y12F02030).

674 控制理论与应用第30 卷 分析复杂性都适中的数学模型. 因此, 本文利用S4 R 这一Petri网子类模型作为研究FMS死锁预防问题的 数学工具是非常适宜的. Petri网中, 信标(siphon)是与死锁现象密切相关 的一种结构. 现有的FMS模型的死锁预防策略通常 采用对部分或者全部严格极小信标(strict minimal siphon, SMS)添加控制库所来保证该信标是最大受 控的, 由此得到活性Petri网控制器(liveness-enforcing Petri net supervisor), 从而实现对原型网的死锁控 制[4C6,8C11] . 活性Petri网控制器的结构复杂度和行为 允许度是衡量控制器设计优劣的两个重要因素. 近 年来, 为获得更优的活性控制器, 围绕着降低活性网 系统的结构复杂度, 提高行为允许度这一目的, 研究 人员展开了许多卓有成效的工作[9C16] . 文献[10]表明, 对S4 R网中每一个SMS分别添加一个控制库所是 得到活性控制器的充分条件. Li和Zhou提出的基本 信标理论[8,17] 将SMS集合划分为基本信标和从属信 标两类, 并提出, 只需对网中基本信标添加相应的控 制库所, 就可以得到活性网, 从而简化了活性S4 R网 控制器[9] . 但多数情况下, 基于基本信标理论设计的 活性S4 R网控制器仍然存在冗余的控制库所. 为进 一步删除冗余, 得到结构更简单的活性控制器, 本文 提出了一种基于整数规划技术的活性控制器简化 方法. 该方法首先以三元组的方式定义了SMS的监 控器(monitor), 每一个监控器包含了添加的控制库 所、 监控PC不变式以及控制库所初始值3个元素. 然 后通过构造方法对S4 R网中每一个SMS设置监控器 使其成为最大受控的信标, 由此得到活性S4 R网控制 器. 该活性控制器中, 如果存在一个PC不变式使得 某个SMS满足最大受控条件, 并且这个SMS的控制 库所并不属于该PC不变式的支撑集, 那么为该SMS 所设置的监控器就是冗余的. 文中最后给出了相应 的算法对网中冗余的监控器进行求解和删除. 实例 表明, 本文提出的方法不仅简化了活性控制器的结 构, 而且提高了网系统的行为允许度.

2 Petri网网网及 及及S4 R基基基本 本 本理 理 理论 论论(Basics of Petri nets and S4 R) Petri网[2C3] 可由四元组表示, 即N = (P, T, F, W), 其中: P是一个有限非空库所集, T是一个有限 非空变迁集, P ∩ T = ?, P∪T = ?;