基于修正网重写系统的制造系统动态重构

工程科学学报，第38卷，第10期：1447-1457,2016年10月 Chinese Journal of Engineering,Vol.38,No.10:1447-1457,October 2016 D0l:10.13374/j.issn2095-9389.2016.10.014:http://journals..ustb.edu.cn 基于修正网重写系统的制造系统动态重构 李杰林”，陈 明2)✉ 1)同济大学机械与能源工程学院，上海2018042)同济大学中德工程学院，上海201804 ☒通信作者，E-mail:chen.ming@tongji.edu.cn 摘要智能制造模式要求制造系统能够快速动态重构以及时响应多品种、小批量产品的客户化、个性化定制的需求.本文 从生产制造流程出发，针对不同输入输出函数下非托肯守恒复杂制造系统一般PN模型，在网重写系统的基础上提出修正网 重写系统。修正网重写系统依据产品制造流程聚类对规则类库中重构单元子类进行系统的模块化封装，并制定相应的重构 区域边界耦合约束与内部结构使能规则.构建的修正网重写系统重构单元类库具有行为特性继承的特点，保证局部区域重 构后制造系统的活性、有界性及可逆性，根据制造系统修正网重写系统重写规则与重构步序可实现制造系统自主快速的动态 重构.仿真结果与应用实例验证了修正网重写系统的可用性. 关键词制造系统：动态重构：网重写系统：Peti网：行为特性 分类号TH181 Dynamic reconfiguration of manufacturing systems based on MNRS IJie-in”,CHEN Ming?) 1)College of Mechanical Engineering,Tongji University,Shanghai 201804,China 2)Sino-German College of Applied Sciences,Tongji University,Shanghai 201804,China Corresponding author,E-mail:chen.ming@tongji.edu.cn ABSTRACT The manufacturing system under the smart manufacturing model is required to timely respond to the changing customi- zation and individuation production demand of diversified small-lot products through quick dynamic reconfiguration.For the general Pe- tri net with different input/output functions and non-conservative Tokens,a modified net rewriting system (MNRS)is proposed accord- ing to the production process on the basis of NRS.Reconfiguration cells in the rule class library of MNRS are encapsulated systemati- cally and modularly based on the manufacturing process of the products,and the corresponding boundary coupling and internal enab- ling rules of the reconfiguration area are formulated.The class library with reconfiguration cells in MNRS has the characteristic of be- havioral property inheritance,which can guarantee the liveness,boundedness and reversibility of the manufacturing system after the lo- cal area reconfiguration,so that the autonomous,quick and dynamic reconfiguration of the manufacturing system can be achieved ac- cording to the rewriting rules and reconfiguration mechanism of MNRS.Simulation results and application cases verify the usability of MNRS. KEY WORDS manufacturing systems:dynamic reconfiguration:net rewriting systems;Petri nets;behavioral properties Petri网(Petri net,PN)作为一种描述分析系统并 (liveness,boundedness,and reversibility,LBR)作为制 行、并发、异步等特点的形式化工具，具有严格的数学 造系统行为特性的重要表征，当制造系统出现变更时， 模型支撑并便于模块化封装，因此广泛应用在生产制 一般都要对重构后的LBR特性重新进行分析判别，并 造系统建模领域-.PN的活性、有界性和可逆性 对系统进行反馈修正，这种重构后再分析的方法会显 收稿日期：2015-12-13 基金项目：上海市经济与信息化委员会资助项目(11XI07):上海市科学技术委员会专项基金资助项目(11DZ1121000)

工程科学学报，第 38 卷，第 10 期: 1447--1457，2016 年 10 月 Chinese Journal of Engineering，Vol． 38，No． 10: 1447--1457，October 2016 DOI: 10． 13374 /j． issn2095--9389． 2016． 10． 014; http: / /journals． ustb． edu． cn 基于修正网重写系统的制造系统动态重构 李杰林1) ，陈 明2)  1) 同济大学机械与能源工程学院，上海 201804 2) 同济大学中德工程学院，上海 201804  通信作者，E-mail: chen． ming@ tongji． edu． cn 摘 要 智能制造模式要求制造系统能够快速动态重构以及时响应多品种、小批量产品的客户化、个性化定制的需求． 本文 从生产制造流程出发，针对不同输入输出函数下非托肯守恒复杂制造系统一般 PN 模型，在网重写系统的基础上提出修正网 重写系统． 修正网重写系统依据产品制造流程聚类对规则类库中重构单元子类进行系统的模块化封装，并制定相应的重构 区域边界耦合约束与内部结构使能规则． 构建的修正网重写系统重构单元类库具有行为特性继承的特点，保证局部区域重 构后制造系统的活性、有界性及可逆性，根据制造系统修正网重写系统重写规则与重构步序可实现制造系统自主快速的动态 重构． 仿真结果与应用实例验证了修正网重写系统的可用性． 关键词 制造系统; 动态重构; 网重写系统; Petri 网; 行为特性 分类号 TH181 Dynamic reconfiguration of manufacturing systems based on MNＲS LI Jie-lin1) ，CHEN Ming2)  1) College of Mechanical Engineering，Tongji University，Shanghai 201804，China 2) Sino-German College of Applied Sciences，Tongji University，Shanghai 201804，China  Corresponding author，E-mail: chen． ming@ tongji． edu． cn ABSTＲACT The manufacturing system under the smart manufacturing model is required to timely respond to the changing customi￾zation and individuation production demand of diversified small-lot products through quick dynamic reconfiguration． For the general Pe￾tri net with different input /output functions and non-conservative Tokens，a modified net rewriting system ( MNＲS) is proposed accord￾ing to the production process on the basis of NＲS． Ｒeconfiguration cells in the rule class library of MNＲS are encapsulated systemati￾cally and modularly based on the manufacturing process of the products，and the corresponding boundary coupling and internal enab￾ling rules of the reconfiguration area are formulated． The class library with reconfiguration cells in MNＲS has the characteristic of be￾havioral property inheritance，which can guarantee the liveness，boundedness and reversibility of the manufacturing system after the lo￾cal area reconfiguration，so that the autonomous，quick and dynamic reconfiguration of the manufacturing system can be achieved ac￾cording to the rewriting rules and reconfiguration mechanism of MNＲS． Simulation results and application cases verify the usability of MNＲS． KEY WOＲDS manufacturing systems; dynamic reconfiguration; net rewriting systems; Petri nets; behavioral properties 收稿日期: 2015--12--13 基金项目: 上海市经济与信息化委员会资助项目( 11XI--07) ; 上海市科学技术委员会专项基金资助项目( 11DZ1121000) Petri 网( Petri net，PN) 作为一种描述分析系统并 行、并发、异步等特点的形式化工具，具有严格的数学 模型支撑并便于模块化封装，因此广泛应用在生产制 造系统建 模 领 域［1--3］． PN 的活 性、有界性和可逆性 ( liveness，boundedness，and reversibility，LBＲ) 作为制 造系统行为特性的重要表征，当制造系统出现变更时， 一般都要对重构后的 LBＲ 特性重新进行分析判别，并 对系统进行反馈修正，这种重构后再分析的方法会显

·1448 工程科学学报，第38卷，第10期 著降低系统对环境变化的动态适应能力.尤其是在智 变迁满足以下约束PUT=O,PUT≠⑦.F:P×TU 能生产制造模式下，制造系统的各个环节都要考虑消 T×P为库所与变迁之间的连接关系，I:P×T是输入 费者的客户化和个性化需求，在生产的不同阶段都要 函数，O:T×P是输出函数，若3：P×T>1V3O: 能够快速响应订单变动，并根据业务流程的变更对生 T×P>1,则该PN为一般PN,反之则为普通PN.鉴于 产资源（生产设备、传送装置、缓冲区单元等）进行自 PN重构的普适性，我们的研究对象是一般PW. 主的、快速的动态配置. 任一变迁t当且仅当()满足以下关系时才可使 这种针对生产环境动态变化的快速重构必须具有 能：M(p)≥F(p,t),其中M为PN标识，Hp∈.使 一定的自组织和自律特性，在结构上继承原有系统的 能变迁1的激发伴随着托肯在输入输出连接弧中的流 某些结构特点，不必再对重构后的系统重新进行行为 动，记作M>M',亦称M'由标识M可达，所有的可 特性分析.鉴于此，在PN模型基础上，Badouel与 达标识构成可达集合R:标识改变遵循以下规则： Llorens等A提出网重写系统(net rewriting system, M(p)-F(p,t）+F(t,p),p∈tnt; NRS),研究并行系统的PN网络结构动态重组，并确 M(p)-F(p,t), p∈t\l·: M'(p)= 保重组后的系统继承原系统的LBR特性.为了提高网 M(p)+F(t,p), pEt\t: 重写系统的适用性，Li等-@在网重写系统的基础上， IM(p), 其他. 提出了改进的网重写系统(improved net rewriting sys- (1) tem,NRS),并基于此重写方法，根据不同类型的库所 PN的行为特性主要有活性、有界性和可逆性，简 针对的一系列PW单元结构进行了可重构分析，大幅 称为LBR,该三个行为特性是相互独立的且是PN系 扩充了可重构单元类库，并证得PN单元结构库中任 统动态行为特性分析的基础. 意类型的结构互换都不会改变重构前系统的LBR特 (1)活性：对于任一变迁，在任一标识M∈R 性.谢楠和李爱平四根据网重写系统提出可重构PW 下，总存在某一变迁激发序列s=(M,,M,…)使得 制造系统控制器设计方法，动态重构自身结构以适应 M(t)≥F(t,t): 新的生产需求，并判定了其行为特性.Renna和Ambri-- (2)有界性：对于一给定PN及其可达集合R,若 co网借助LNGO软件提出了对应的数学模型来解决 max(HM(Hp))≤k,其中MeRy,则该PN是k有 单元制造系统的设计、可重构以及调度问题，取得了良 界的： 好效果 (3)可逆性：对于一给定PN及其可达集合R,初 然而目前的行为特性继承可重构单元主要针对的 始标识M。由M∈R,可达. 是普通PN,不曾考虑输入输出权重对制造系统可重构 1.2修正网重写系统定义 能力的影响，但在实际工业生产中，由于生产设备制造 映射定义：若RCX×Y是一二元关系，令XR= 能力、生产成本、生产效率等客观约束的影响，制造系 {y∈YI]x∈X,(x,y)∈R}表示XCX的象(im- 统所对应的PN节点间不只是互连与否，而是需要一 age),令RY={xeXI3yeY,(x,y)eR}表示YCY 定数量的托肯支撑，这就导致了以往的重构方法不再 的原象(inverse image).R的定义域(domain)与陪域 适用这种新的重构要求.同时，目前的网重写系统与 (codomain)分别为Dom(R)=RY和Cod(R)=XR. 改进的网重写系统重构类库是松散而不成体系的，重 修正重写网系统由以下三元组组成：=（G,R, 构单元的自组织及自律能力欠缺，因此针对工业生产 ),其中，G=(T,M。)为重构前的PN,M为PN的初 制造流程特点提出修正网重写系统(modified net re- 始标识，T=(P,T,F)为一般PN且满足一般PN约束 writing system,MNRS),通过系统化模块化的重构单元 关系 子类封装，以及边界耦合与内部结构使能规则的制定， R=(r1,2,…)为有限重构规则集合，r=(L,R, 来实现具有行为特性继承特点的制造系统快速动态 x,,x）,其中L=(P,T,F)与R=(Pg,TR,F)分 重构. 别称为G重构的左手侧(left-hand side)与右手侧 1修正网重写系统数学模型 (right-hand side),如图1所示，L为可重构区域重构之 前的PN结构，R为重构之后的PN结构，k,与k。分别 1.1一般PN模型 为输入与输出量.T:(P,UT)(P&UTR)表示重构 对制造系统的重构是建立在PN模型上的，首先， 前结构与重构后之间的双向映射关系且Px二P。A 对一般PN进行定义 T,TCTRATPRCP,∧TCT,·T与·分别为重构结 一般PN是由一三元组组成的有向图，PN=(P, 构输入端与输出端的端口关系，在图1中，·？= T,F),其中，P={pP2,P}为有限库所集合且n> ({T},{T}),r·=({To},{T}),其中Tu和T。分 0,T={l1,2,…,l}为有限变迁集合且m>0,库所与 别为左手端输入与输出，T,和T。分别为右手端输入

工程科学学报，第 38 卷，第 10 期 著降低系统对环境变化的动态适应能力． 尤其是在智 能生产制造模式下，制造系统的各个环节都要考虑消 费者的客户化和个性化需求，在生产的不同阶段都要 能够快速响应订单变动，并根据业务流程的变更对生 产资源( 生产设备、传送装置、缓冲区单元等) 进行自 主的、快速的动态配置． 这种针对生产环境动态变化的快速重构必须具有 一定的自组织和自律特性，在结构上继承原有系统的 某些结构特点，不必再对重构后的系统重新进行行为 特性 分 析． 鉴 于 此，在 PN 模 型 基 础 上，Badouel 与 Llorens 等［4--5］ 提出 网 重 写 系 统( net rewriting system， NＲS) ，研究并行系统的 PN 网络结构动态重组，并确 保重组后的系统继承原系统的 LBＲ 特性． 为了提高网 重写系统的适用性，Li 等［6--10］在网重写系统的基础上， 提出了改进的网重写系统( improved net rewriting sys￾tem，INＲS) ，并基于此重写方法，根据不同类型的库所 针对的一系列 PN 单元结构进行了可重构分析，大幅 扩充了可重构单元类库，并证得 PN 单元结构库中任 意类型的结构互换都不会改变重构前系统的 LBＲ 特 性． 谢楠和李爱平［11］根据网重写系统提出可重构 PN 制造系统控制器设计方法，动态重构自身结构以适应 新的生产需求，并判定了其行为特性． Ｒenna 和 Ambri￾co［12］借助 LINGO 软件提出了对应的数学模型来解决 单元制造系统的设计、可重构以及调度问题，取得了良 好效果． 然而目前的行为特性继承可重构单元主要针对的 是普通 PN，不曾考虑输入输出权重对制造系统可重构 能力的影响，但在实际工业生产中，由于生产设备制造 能力、生产成本、生产效率等客观约束的影响，制造系 统所对应的 PN 节点间不只是互连与否，而是需要一 定数量的托肯支撑，这就导致了以往的重构方法不再 适用这种新的重构要求． 同时，目前的网重写系统与 改进的网重写系统重构类库是松散而不成体系的，重 构单元的自组织及自律能力欠缺，因此针对工业生产 制造流程特点提出修正网重写系统( modified net re￾writing system，MNＲS) ，通过系统化模块化的重构单元 子类封装，以及边界耦合与内部结构使能规则的制定， 来实现具有行为特性继承特点的制造系统快速动态 重构． 1 修正网重写系统数学模型 1. 1 一般 PN 模型 对制造系统的重构是建立在 PN 模型上的，首先， 对一般 PN 进行定义． 一般 PN 是由一三元组组成的有向图，PN = ( P， T，F) ，其中，P = { p1，p2，…，pn } 为有限库所集合且 n ＞ 0，T = { t1，t2，…，tm } 为有限变迁集合且 m ＞ 0，库所与 变迁满足以下约束 P∪T = ，P∪T≠． F: P × T∪ T × P 为库所与变迁之间的连接关系，I: P × T 是输入 函数，O: T × P 是输出函数，若I: P × T ＞ 1∨O: T × P ＞ 1，则该 PN 为一般 PN，反之则为普通 PN． 鉴于 PN 重构的普适性，我们的研究对象是一般 PN． 任一变迁 t 当且仅当( iff) 满足以下关系时才可使 能: M( p) ≥F( p，t) ，其中 M 为 PN 标识，p∈·t． 使 能变迁 t 的激发伴随着托肯在输入输出连接弧中的流 动，记作 M［t ＞ M'，亦称 M'由标识 M 可达，所有的可 达标识构成可达集合 ＲM ． 标识改变遵循以下规则: M'( p) = M( p) － F( p，t) + F( t，p) ， p∈·t∩t·; M( p) － F( p，t) ， p∈·t \t·; M( p) + F( t，p) ， p∈t·\·t; M( p) ， 其他 { ． ( 1) PN 的行为特性主要有活性、有界性和可逆性，简 称为 LBＲ，该三个行为特性是相互独立的且是 PN 系 统动态行为特性分析的基础． ( 1) 活性: 对于任一变迁 t，在任一标识 M∈ＲM 下，总存在某一变迁激发序列 s = ( M1，M2，…) 使得 Ms (·t) ≥F(·t，t) ; ( 2) 有界性: 对于一给定 PN 及其可达集合 ＲM，若 max( M( p) ) ≤k，其中 M∈ＲM，则该 PN 是 k 有 界的; ( 3) 可逆性: 对于一给定 PN 及其可达集合 ＲM，初 始标识 M0 由 M∈ＲM 可达． 1. 2 修正网重写系统定义 映射定义: 若 ＲX × Y 是一二元关系，令 X'Ｒ = { y∈Y | x∈X'，( x，y) ∈Ｒ} 表示 X'X 的 象( im￾age) ，令 ＲY' = { x∈X| y∈Y'，( x，y) ∈Ｒ} 表示 Y'Y 的原象( inverse image) ． Ｒ 的定义域( domain) 与陪域 ( codomain) 分别为 Dom( Ｒ) = ＲY 和 Cod( Ｒ) = XＲ． 修正重写网系统由以下三元组组成: N = ( G，Ｒ， L) ，其中，G = ( Γ，M0 ) 为重构前的 PN，M0 为 PN 的初 始标识，Γ= ( P，T，F) 为一般 PN 且满足一般 PN 约束 关系． Ｒ = ( r1，r2，…) 为有限重构规则集合，r = ( L，Ｒ， τ，·τ，τ·) ，其中 L = ( PL，TL，FL ) 与 Ｒ = ( PＲ，TＲ，FＲ ) 分 别称 为 G 重 构 的 左 手 侧 ( left-hand side) 与 右 手 侧 ( right-hand side) ，如图 1 所示，L 为可重构区域重构之 前的 PN 结构，Ｒ 为重构之后的 PN 结构，kI 与 kO 分别 为输入与输出量． τ: ( PL∪TL ) ( PＲ∪TＲ ) 表示重构 前结构与重构后之间的双向映射关系且 PL τPＲ ∧ TL τTＲ∧τPＲPL∧τTＲTL，·τ 与 τ·分别为重构结 构输 入 端 与 输 出 端 的 端 口 关 系，在 图 1 中，·τ = ( { TLI } ，{ TI } ) ，τ·= ( { TLO } ，{ TO } ) ，其中 TLI和 TO 分 别为左手端输入与输出，TI 和 TO 分别为右手端输入 · 8441 ·

李杰林等：基于修正网重写系统的制造系统动态重构 ·1449· 与输出. 值得一提的是，当初始标识M。经过变迁激发序 为一系列的重构规则类库，在后文中可以看 列s可达M。5>M,时，倘若产品托肯未处于可重构 到，按照该规则库中的重构规则对原网G进行重构后 区域L中，便可对G=(T,M,)进行下「r结构重 得到的新网络可继承原网的LBR行为特性 构，标识改变如下： R [M.(p), PR: M(p)= (6) M (f(p)),pER. 1.4 修正网重写系统特性 局域性：重构针对的只是整个PW系统的局域部 分，重构单元的改变不会对重构区域之外产生影响，即 使在重构单元内部托肯带有了颜色，移出重构单元之 外后也不会影响后续生产. 输入输出一致性：只要可重构区域L中未含有产 品托肯，便可对L进行结构重构，将重构对生产的影 图1修正网重写系统左手侧与右手侧 响降至最低.重构单元的总体输入函数与重构之前相 Fig.1 Left-hand and right-hand of the MNRS 等，总输出函数亦不变 1.3修正网重写系统结构重写 模块化封装：可以看出，只要满足一定的输入输出 般PN网络结构重构后得到：G=（,M6)= 条件，修正网重写系统的结构特点使得重构区域可处 于黑箱状态，这样便于将重构区域进行模块化，并且模 (P,T,F,M.当r'r时，亦即r通过重构规 块内部的结构十分灵活多变. 则”重写为“，其库所与变迁遵循以下变动关系： 原子操作：托肯在PN基本封装单元中的转移是 [P'=P-f(P)+P, (2) 彻底的，每个库所或者变迁在状态转移过程中，不允许 T'=T-f(T)+Tr 被打断进行重构.亦即，制造系统的重构必须保证重 其中，PR=Pr,TR=T不∫为全嵌入式子网映射，定义 构区域的生产资料是闲置可用的，制造系统的重构不 如下：fL→T其中，对于Hxf(L),Hy∈L有以下 与PN标识的迁移相干扰. 推导关系成立：x∈f(y）→y∈Dom(·)且x∈f(y)·→ 1.5修正网重写系统与改进的网重写系统对比 yE Dom() 由文献6-10]可知，改进的网重写系统的可重构 重构后的网络节点关系如下所示： 性能优于网重写系统，故在此与改进的网重写系统在 F(x,y), x,y主PeUT: 定义、结构、特性方面进行对比说明： Fe(x,y）, x,y∈PR UTR: (1)修正网重写系统延伸了改进的网重写系统定 F(x,y)= ∑F(xf(y)，x∈·Ty∈T: 义，更加明确了边界节点关系，制定了新的边界耦合规 则，只要满足边界节点关系要求，就能够保证PN系统 ∑Fx),yW,xeIy∈To 的局域性重构不会受到输入输出函数数量的影响： G" (2)重构区域边界的输入输出函数在一定程度上 (3) 决定了内部的输入输出函数约束，借助于一般PN模 需要说明的是，对于一般PN,输入函数与输出函 型，修正网重写系统在结构上更系统地反映了制造系 数的权重对整个PN行为特性以及动态特性的影响是 统重构需求，并通过模块化封装规则类库整合了松散 巨大的，上述PN网络F。需要满足一定的结构要求， 的改进的网重写系统重构类模块，简化了重构规则子 因为封装后的不同重构单元对于内部输入输出函数的 单元，提高了自组织能力： 重构要求也是各不相同的，具体结构关系在下文中详 (3)在重构特性方面，修正网重写系统的局域性、 细阐述.同时，边界节点关系不只是单纯的连接与否， 输入输出一致性适用范围更广，不同的类库保证了模 具体的输入输出函数需要满足以下关系： 块化封装内部可以存在相同类型不同结构或者不同类 rF(x,*）=F(x,*）,x∈·T: (4) 型不同结构的重构选择，制造系统的重构更加灵活 F(*,y）=F(*,y),yeTo. 多变 其中，*表示通配符.而对于PN初始标识影响如下： 综上所述，与改进的网重写系统相比，修正网重写 rM。(p),pER: M6(p)= (5) 系统能够以更优越的重构性能实现制造系统的快速 M。(f(p)),peR. 重构

李杰林等: 基于修正网重写系统的制造系统动态重构 与输出． L 为一系列的重构规则类库，在后文中可以看 到，按照该规则库中的重构规则对原网 G 进行重构后 得到的新网络可继承原网的 LBＲ 行为特性． 图 1 修正网重写系统左手侧与右手侧 Fig． 1 Left-hand and right-hand of the MNＲS 1. 3 修正网重写系统结构重写 一般 PN 网络结构重构后得到: G' = ( Γ'，M' 0 ) = ( P'，T'，F'，M' 0 ) ． 当 Γ → r Γ'时，亦即 Γ 通过重构规 则 r 重写为 Γ'，其库所与变迁遵循以下变动关系: P' = P － f( PL ) + PＲ， T' = T － f( TL ) + TＲ { ． ( 2) 其中，PＲ = PL τ，TＲ = TL τ． f 为全嵌入式子网映射，定义 如下: f: L→Γ． 其中，对于xf( L) ，y∈L 有以下 推导关系成立: x∈·f( y) y∈Dom(·τ) 且 x∈f( y)· y∈Dom( τ·) ． 重构后的网络节点关系如下所示: F'( x，y) = F( x，y) ， x，y  PＲ ∪ T; FＲ ( x，y) ， x，y ∈ PＲ ∪ TＲ ; y ∑i ∈·τy F( x，f( yi ) ) ， x ∈·TI，y ∈ TI ; x ∑i ∈τ·x F( f( xi ) ，y) ， x ∈ TO，y ∈ TO ·        ． ( 3) 需要说明的是，对于一般 PN，输入函数与输出函 数的权重对整个 PN 行为特性以及动态特性的影响是 巨大的，上述 PN 网络 FＲ 需要满足一定的结构要求， 因为封装后的不同重构单元对于内部输入输出函数的 重构要求也是各不相同的，具体结构关系在下文中详 细阐述． 同时，边界节点关系不只是单纯的连接与否， 具体的输入输出函数需要满足以下关系: F'( x，* ) = F( x，* ) ，x∈·TI ; {F'( * ，y) = F( * ，y) ，y∈TO ·． ( 4) 其中，* 表示通配符． 而对于 PN 初始标识影响如下: M' 0 ( p) = M0 ( p) ， pＲ; M0 { ( f( p) ) ， p∈Ｒ． ( 5) 值得一提的是，当初始标识 M0 经过变迁激发序 列 s 可达 M0［s ＞ Ms 时，倘若产品托肯未处于可重构 区域 L 中，便可对 G = ( Γ，M0 ) 进行 Γ → r Γ'结构重 构，标识改变如下: M' s ( p) = Ms ( p) ， pＲ; Ms { ( f( p) ) ， p∈Ｒ． ( 6) 1. 4 修正网重写系统特性 局域性: 重构针对的只是整个 PN 系统的局域部 分，重构单元的改变不会对重构区域之外产生影响，即 使在重构单元内部托肯带有了颜色，移出重构单元之 外后也不会影响后续生产． 输入输出一致性: 只要可重构区域 L 中未含有产 品托肯，便可对 L 进行结构重构，将重构对生产的影 响降至最低． 重构单元的总体输入函数与重构之前相 等，总输出函数亦不变． 模块化封装: 可以看出，只要满足一定的输入输出 条件，修正网重写系统的结构特点使得重构区域可处 于黑箱状态，这样便于将重构区域进行模块化，并且模 块内部的结构十分灵活多变． 原子操作: 托肯在 PN 基本封装单元中的转移是 彻底的，每个库所或者变迁在状态转移过程中，不允许 被打断进行重构． 亦即，制造系统的重构必须保证重 构区域的生产资料是闲置可用的，制造系统的重构不 与 PN 标识的迁移相干扰． 1. 5 修正网重写系统与改进的网重写系统对比 由文献［6--10］可知，改进的网重写系统的可重构 性能优于网重写系统，故在此与改进的网重写系统在 定义、结构、特性方面进行对比说明: ( 1) 修正网重写系统延伸了改进的网重写系统定 义，更加明确了边界节点关系，制定了新的边界耦合规 则，只要满足边界节点关系要求，就能够保证 PN 系统 的局域性重构不会受到输入输出函数数量的影响; ( 2) 重构区域边界的输入输出函数在一定程度上 决定了内部的输入输出函数约束，借助于一般 PN 模 型，修正网重写系统在结构上更系统地反映了制造系 统重构需求，并通过模块化封装规则类库整合了松散 的改进的网重写系统重构类模块，简化了重构规则子 单元，提高了自组织能力; ( 3) 在重构特性方面，修正网重写系统的局域性、 输入输出一致性适用范围更广，不同的类库保证了模 块化封装内部可以存在相同类型不同结构或者不同类 型不同结构的重构选择，制造系统的重构更加灵活 多变． 综上所述，与改进的网重写系统相比，修正网重写 系统能够以更优越的重构性能实现制造系统的快速 重构． · 9441 ·

·1450 工程科学学报，第38卷，第10期 构输入端与输出端的端口关系分别为·？=({T}, 2规则类库定义及特性继承 {T,}),x=({T},{T}),这一BC重构可视作在切 2.1BC子类 割完成之后添加质检工序. 图2所示为兼有状态库所与活动变迁的PN基本 结构单元(basic cell,BC),带有托肯的库所表示该生 产设备是闲置资源，处于可用状态，空的库所表示该机 器的生产过程状态.资源托肯可具体分为设备托肯与 产品托肯，对制造系统的分析主要是面向所要生产的 产品，亦即主要针对产品托肯流进行分析，而不考虑易 图4LBR特性继承证明实例 导致系统锁死的生产设备竞争问题.因此为了便于分 Fig.4 Proof example of LBR property inheritance 析，采用图3所示的简化结构.因为所构建的PN子网 为现实物理世界中生产资料实体的映射，故封装后的 G具有活性，因此对于具有相同输入输出的重构 单元要与现实约束一致，鉴于BC为基本单元，k,与k。 右手侧，必然存在某一变迁序列使得变迁T,使能，随 之间的约束关系为k,Ik,或者kIk,即相除关系.对 后，图4所示BC结构能够在T,点火情况下激发变迁 于加工、运输等托肯守恒操作，k,=k:对于切割等托 To,并输出M(T。）=ko,剩余的所有变迁Vt∈(（T- 肯增加操作，k,Ik:对于零件冲压焊接组合等托肯减 T)回归到原有的(T-T),因此，G是活的.对于有 少操作，koIk 界性，假定G是k有界的，图4所示BC重构的结构特 点满足M(p)≤k。≤k,即R是k有界的，而根据修正 网重写系统的局部特性，Hp∈P·-Pg是k有界的，因 此G是有界的. 由于G具有可逆特性，不妨假设存在这样的变迁 序列sS以及s使得M[S:>M,>M,S>M- 其中，M,=M(P-·T-T2)UM(T)UM(T2), 图2PN基本结构单元 M,(·T)=k,且M,（T.·)=0.将可重构区域视为黑 Fig.2 Basic cell of the PN 箱状态，即不关注具体的内部结构以及内部托肯的变 迁序列，而只需确定给定输入状态下的单元输出状态 S,为黑箱内部某变迁序列，M,=M,(P-·T,-T,·)U M(T)UM(T）,M（·T)=0且M(T,）=ko 由于重构前为一单独变迁，因此M(P-·T,-T,)= M,(P-T,-T,·).将黑箱内部由L=（T,F)替换 图3BC简化结构 为R=(P,TR,F),由于BC的局部特性以及输入输 Fig.3 Simplified structure of the BC 出一致性，仍旧存在这样的变迁序列s:以及S,分别 BC定义：给定一L=(P,T,F),若1T,I≥1，IT。· 使得M6s:>M;以及M;S.>M。成立，其中，M。= I≥1,1·pl=1,1pl=1,IP1=1,且F(T,*)Ik M(P)UM(P),M6(Pe)=0,对于M,M=M,(P)U Vk,IF(T,*),则该L为一BC. M(PR),M(Pe)=0,并且，M=M(P)UM(PR), 给定某个结构为=(G,R,分的修正网重写系 M;(P)=O.同时由BC的结构使能规则易知存在s 统，其中G=(T,M),R={r},r=(L,R,T,·T,T). 变迁序列，使得M,5>M因此，对于重构后的结构 L为一变迁，R为一相同输入输出的BC.可得结论：倘 G,存在变迁激发序列使得M6S:>MS>M;[s:> 若G具有LBR特性，则重构后得到的G=(T,M)也 M。,故G是可逆的. 具备LBR特性.在此以BC子类为例证明LBR特性继 2.2SC子类 承，其他子类特性继承的证明方法与此相类似 图5所示为封装后的顺序（串联）结构单元(se- 证明：以图4中所示具体实例证明BC重构时的 quence cell,SC).易知，BC可看作是最简单的SC.在 LBR特性继承.修正网重写系统为=(G,r,),其 SC中，如果后续生产加工设备能够恰巧容纳之前的产 中G=(T,M),重构规则r=(L,R,T,·T,?),L= 品数量，亦即，：P×T=O:T×P,这种情形下肯定 (T,F)为G重构的左手侧，且输入输出函数满足关 3M(P)=I:P×T,单元内生产进程会平稳有序进行. 系ko=nk,对应切割等托肯增加操作，R=(PR,Te, 然而，在实际生产制造过程中，由于前置生产工序存在 F®)为G重构右手侧，且内部结构满足k:=k。,重构结 分解等操作使得托肯数量增加，后续设备往往无法提

工程科学学报，第 38 卷，第 10 期 2 规则类库定义及特性继承 2. 1 BC 子类 图 2 所示为兼有状态库所与活动变迁的 PN 基本 结构单元( basic cell，BC) ，带有托肯的库所表示该生 产设备是闲置资源，处于可用状态，空的库所表示该机 器的生产过程状态． 资源托肯可具体分为设备托肯与 产品托肯，对制造系统的分析主要是面向所要生产的 产品，亦即主要针对产品托肯流进行分析，而不考虑易 导致系统锁死的生产设备竞争问题． 因此为了便于分 析，采用图 3 所示的简化结构． 因为所构建的 PN 子网 为现实物理世界中生产资料实体的映射，故封装后的 单元要与现实约束一致，鉴于 BC 为基本单元，kI 与 kO 之间的约束关系为 kI | kO 或者 kO | kI，即相除关系． 对 于加工、运输等托肯守恒操作，kI = kO ; 对于切割等托 肯增加操作，kI | kO ; 对于零件冲压焊接组合等托肯减 少操作，kO | kI ． 图 2 PN 基本结构单元 Fig． 2 Basic cell of the PN 图 3 BC 简化结构 Fig． 3 Simplified structure of the BC BC 定义: 给定一 L = ( P，T，F) ，若|·TI | ≥1，| TO · | ≥1，|·p | = 1，| p·| = 1，| P | = 1，且 F( TI，* ) | ki ∨ki | F( TI，* ) ，则该 L 为一 BC． 给定某个结构为 N = ( G，Ｒ，L) 的修正网重写系 统，其中 G = ( Γ，M0 ) ，Ｒ = { r} ，r = ( L，Ｒ，τ，·τ，τ·) ． L 为一变迁，Ｒ 为一相同输入输出的 BC． 可得结论: 倘 若 G 具有 LBＲ 特性，则重构后得到的 G' = ( Γ'，M' 0 ) 也 具备 LBＲ 特性． 在此以 BC 子类为例证明 LBＲ 特性继 承，其他子类特性继承的证明方法与此相类似． 证明: 以图 4 中所示具体实例证明 BC 重构时的 LBＲ 特性继承． 修正网重写系统为 N = ( G，r，L) ，其 中 G = ( Γ，M0 ) ，重构规则 r = ( L，Ｒ，τ，·τ，τ·) ，L = ( TL，FL ) 为 G 重构的左手侧，且输入输出函数满足关 系 kO = nkI，对应切割等托肯增加操作，Ｒ = ( PＲ，TＲ， FＲ ) 为 G 重构右手侧，且内部结构满足 ki = kO，重构结 构输入端与输出 端 的 端 口 关 系 分 别 为·τ = ( { TL } ， { TI } ) ，τ·= ( { TL } ，{ TO } ) ，这一 BC 重构可视作在切 割完成之后添加质检工序． 图 4 LBＲ 特性继承证明实例 Fig． 4 Proof example of LBＲ property inheritance G 具有活性，因此对于具有相同输入输出的重构 右手侧，必然存在某一变迁序列使得变迁 TI 使能，随 后，图 4 所示 BC 结构能够在 TI 点火情况下激发变迁 TO，并输出 M( TO ·) = kO，剩余的所有变迁t∈( T' － TＲ ) 回归到原有的( T － TL ) ，因此，G'是活的． 对于有 界性，假定 G 是 k 有界的，图 4 所示 BC 重构的结构特 点满足 M( p) ≤kO≤k，即 Ｒ 是 k 有界的，而根据修正 网重写系统的局部特性，p∈P' － PＲ 是 k 有界的，因 此 G'是有界的． 由于 G 具有可逆特性，不妨假设存在这样的变迁 序列 si、sj 以及 sk 使得 M0［si ＞ Msi ［sj ＞ Msj ［sk ＞ M0 ． 其中，Msi = Msi ( P －·TL － TL ·) ∪Msi (·TL ) ∪Msi ( TL ·) ， Msi (·TL ) = kI 且 Msi ( TL ·) = 0． 将可重构区域视为黑 箱状态，即不关注具体的内部结构以及内部托肯的变 迁序列，而只需确定给定输入状态下的单元输出状态． sj 为黑箱内部某变迁序列，Msj = Msj ( P －·TL － TL ·) ∪ Msj (·TL ) ∪Msj ( TL ·) ，Msj (·TL ) = 0 且 Msj ( TL ·) = kO ． 由于重构前为一单独变迁，因此 Msi ( P －·TL － TL ·) = Msj ( P －·TL － TL ·) ． 将黑箱内部由 L = ( TL，FL ) 替换 为 Ｒ = ( PＲ，TＲ，FＲ ) ，由于 BC 的局部特性以及输入输 出一致性，仍旧存在这样的变迁序列 si 以及 sk，分别 使得 M' 0［si ＞ M' si 以及 M' sj ［sk ＞ M' 0 成立，其中，M' 0 = M0 ( P) ∪M' 0 ( PＲ ) ，M' 0 ( PＲ ) = 0，对于 M' si ，M' si = Msi ( P) ∪ M' si ( PＲ ) ，M' si ( PＲ ) = 0，并且，M' sj = Msj ( P) ∪M' sj ( PＲ ) ， M' sj ( PＲ ) = 0． 同时由 BC 的结构使能规则易知存在 s' j 变迁序列，使得 M' si ［s' j ＞ M' sj ． 因此，对于重构后的结构 G'，存在变迁激发序列使得 M' 0［si ＞ M' si ［s' j ＞ M' sj ［sk ＞ M' 0，故 G'是可逆的． 2. 2 SC 子类 图 5 所示为封装后的顺序( 串联) 结构单元( se￾quence cell，SC) ． 易知，BC 可看作是最简单的 SC． 在 SC 中，如果后续生产加工设备能够恰巧容纳之前的产 品数量，亦 即，I: P × T = O: T × P，这 种 情 形 下 肯 定 M( P) = I: P × T，单元内生产进程会平稳有序进行． 然而，在实际生产制造过程中，由于前置生产工序存在 分解等操作使得托肯数量增加，后续设备往往无法提 · 0541 ·

李杰林等：基于修正网重写系统的制造系统动态重构 ·1451· 供足够的生产制造能力，使得：P×T>O:T×P,亦即 Psc×Tsc)/Π(0：Tc×Psc）=k,/ko可得结论：倘 ]M(P)>:P×T,这时便会出现资源堵塞情形而阻 若G具有LBR特性，则重构后得到的G=(T,M6)也 断生产进程.在顺序单元中，有效的解决办法便是引 具备LBR特性 入有限容量缓冲区，缓冲区是特殊的库所结构，它允许 2.3CSC子类 左右侧存在数量差异，在进行重构计算时，要注意采用 图8所示为封装后的并发同步单元(concurrent 最大容纳值而不是缓冲后的托肯值.而对于：P× synchronization cell,CSC),在逻辑上是AND-SPLT- T>O:T×P这种“伪非使能”情形，在SC中是可以存 AND-JON的，实现一对多和多对一的并发同步关系 在并始终伴随缓冲区存在的，此种情形充分利用缓冲 映射.但是，由于现实制造流程的限制，在实际生产加 区中的冗余资源以免托肯急剧增加造成的PN无界， 工中采用如图9所示更具普适性的单元结构，同样引 而缓冲区为其提供3M(P)=:P×T的使能条件，因 入有限容量缓冲区缓解资源过剩造成的系统堵塞，并 此此种情形共存于缓冲区之后的工位中. 且为了不失一般性，借助SC结构构建CSC主干.CSC 支路之间是平行关系，并且虚线内的支路$C是特殊 的顺序结构，符合托肯守恒性，并且所有条件符合之后 才能聚合使能变迁激发.主干上的$C是顺序结构集 成单元. 图5PN顺序结构单元 Fig.5 Sequence cell of the PN 因为M(·T)=k,不妨假定缓冲区容量最大为 k,某个工位i处的变迁使能托肯数为k,且满足k1 (nk,),即k可整除nk.如图6所示，工位i的前置缓 冲区可实现k,到k的负载下降，而鉴于SC的输入输 出一致性，必须有相应的“返还”操作，因此后置工位 的加入使得工作流中"个托肯负载恢复到之前的k。, 图8并发同步单元 其中"Ink Fig.8 Concurrent synchronization cell 图6SC内部输入输出函数约束 Fig.6 Input and output constraints of the SC C自身除了作为修正网重写系统模块化重构单 元，还兼作其他封装单元的组成部分，为了便于与其他 单元进行集成，采用图7所示的集成结构，其中(kIk, Vk,Ik）A(k"Iko Vkolk") 图9CSC结构 ○○* Fig.9 Structure of the CSC CSC定义：给定一如图9所示的PN结构L=(P, 图7SC集成结构 T,F),1…Tl≥1∧1Tol≥1 Fig.7 Integration structure of the SC 节点数量约束为l·Hpl=1,1pl=1,I3> 1(teT-To),1·3l>1(t∈T-T,) SC定义：给定如图7中所示的顺序结构L=(P, 输入函数边界条件为F(T,*)Ik,Vk,IF(T, T,F),IT,I≥1，IT。l≥1,1·Hpl=1,1pl=1, *) IPI>1,并且，(F(T,*）Ik,Vk,IF(T,*)A(F 输出函数边界条件为F(*,T)Ik。Vk。IF(*, (*,T,)lko VkolF(*,T)),则该L为一SC. To) 给定某个结构为=(G,R,的修正网重写系 同步约束为(k=k)Ik,Vk,I(k=k,) 统，其中G=(T,M),R={r},r=(L,R,T,·,). 支路SC遵循托肯守恒 L为一BC,R为一相同输入输出的SC,且(I: 其中，i为任一支路，其余为SC子结构，则该L为

李杰林等: 基于修正网重写系统的制造系统动态重构 供足够的生产制造能力，使得 I: P × T ＞ O: T × P，亦即 M( P) ＞ I: P × T，这时便会出现资源堵塞情形而阻 断生产进程． 在顺序单元中，有效的解决办法便是引 入有限容量缓冲区，缓冲区是特殊的库所结构，它允许 左右侧存在数量差异，在进行重构计算时，要注意采用 最大容纳值而不是缓冲后的托肯值． 而对于 I: P × T ＞ O: T × P 这种“伪非使能”情形，在 SC 中是可以存 在并始终伴随缓冲区存在的，此种情形充分利用缓冲 区中的冗余资源以免托肯急剧增加造成的 PN 无界， 而缓冲区为其提供M( P) = I: P × T 的使能条件，因 此此种情形共存于缓冲区之后的工位中． 图 5 PN 顺序结构单元 Fig． 5 Sequence cell of the PN 因为 M(·TI ) = kI，不妨假定缓冲区容量最大为 nkI，某个工位 i 处的变迁使能托肯数为 k'，且满足 k' | ( nkI ) ，即 k'可整除 nkI ． 如图 6 所示，工位 i 的前置缓 冲区可实现 nkI 到 k'的负载下降，而鉴于 SC 的输入输 出一致性，必须有相应的“返还”操作，因此后置工位 的加入使得工作流中 k″个托肯负载恢复到之前的 kO， 其中 k″| nkI ． 图 6 SC 内部输入输出函数约束 Fig． 6 Input and output constraints of the SC SC 自身除了作为修正网重写系统模块化重构单 元，还兼作其他封装单元的组成部分，为了便于与其他 单元进行集成，采用图 7 所示的集成结构，其中( k' | kI ∨kI | k') ∧( k″| kO∨kO | k″) ． 图 7 SC 集成结构 Fig． 7 Integration structure of the SC SC 定义: 给定如图 7 中所示的顺序结构 L = ( P， T，F) ，|·TI | ≥1，| TO·| ≥1，|·p | = 1，| p·| = 1， | P| ＞ 1，并且，( F( TI，* ) | kI ∨kI | F( TI，* ) ) ∧( F ( * ，TO ) | kO∨kO | F( * ，TO ) ) ，则该 L 为一 SC． 给定某个结构为 N = ( G，Ｒ，L) 的修正网重写系 统，其中 G = ( Γ，M0 ) ，Ｒ = { r} ，r = ( L，Ｒ，τ，·τ，τ·) ． L 为一 BC，Ｒ 为 一 相 同 输 入 输 出 的 SC，且 ∏ ( I: PSC × TSC ) / ∏ ( O: TSC × PSC ) = kI / kO ． 可得结论: 倘 若 G 具有 LBＲ 特性，则重构后得到的 G' = ( Γ'，M' 0 ) 也 具备 LBＲ 特性． 2. 3 CSC 子类 图 8 所示为封装后 的 并 发 同 步 单 元( concurrent synchronization cell，CSC) ，在逻 辑 上 是 AND--SPLIT-- AND--JOIN 的，实现一对多和多对一的并发同步关系 映射． 但是，由于现实制造流程的限制，在实际生产加 工中采用如图 9 所示更具普适性的单元结构，同样引 入有限容量缓冲区缓解资源过剩造成的系统堵塞，并 且为了不失一般性，借助 SC 结构构建 CSC 主干． CSC 支路之间是平行关系，并且虚线内的支路 SC 是特殊 的顺序结构，符合托肯守恒性，并且所有条件符合之后 才能聚合使能变迁激发． 主干上的 SC 是顺序结构集 成单元． 图 8 并发同步单元 Fig． 8 Concurrent synchronization cell 图 9 CSC 结构 Fig． 9 Structure of the CSC CSC 定义: 给定一如图 9 所示的 PN 结构 L = ( P， T，F) ，|·TI | ≥1∧| TO ·| ≥1 节点数量约束为|·p | = 1，| p·| = 1，| t·| ＞ 1( t∈T － TO ) ，|·t | ＞ 1( t∈T － TI ) 输入函数边界条件为 F( TI，* ) | kI ∨kI | F( TI， * ) 输出函数边界条件为 F( * ，TO ) | kO∨kO | F( * ， TO ) 同步约束为( k' = ki ) | kI∨kI | ( k' = ki ) 支路 SC 遵循托肯守恒 其中，i 为任一支路，其余为 SC 子结构，则该 L 为 · 1541 ·