工程科学学报,第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 MNRS 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 ABSTRACT The manufacturing system under the smart manufacturing model is required to timely respond to the changing customization and individuation production demand of diversified small-lot products through quick dynamic reconfiguration. For the general Petri net with different input /output functions and non-conservative Tokens,a modified net rewriting system ( MNRS) is proposed according to the production process on the basis of NRS. Reconfiguration cells in the rule class library of MNRS are encapsulated systematically and modularly based on the manufacturing process of the products,and the corresponding boundary coupling and internal enabling rules of the reconfiguration area are formulated. The class library with reconfiguration cells in MNRS has the characteristic of behavioral property inheritance,which can guarantee the liveness,boundedness and reversibility of the manufacturing system after the local area reconfiguration,so that the autonomous,quick and dynamic reconfiguration of the manufacturing system can be achieved according 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 收稿日期: 2015--12--13 基金项目: 上海市经济与信息化委员会资助项目( 11XI--07) ; 上海市科学技术委员会专项基金资助项目( 11DZ1121000) Petri 网( Petri net,PN) 作为一种描述分析系统并 行、并发、异步等特点的形式化工具,具有严格的数学 模型支撑并便于模块化封装,因此广泛应用在生产制 造系统建 模 领 域[1--3]. PN 的活 性、有界性和可逆性 ( liveness,boundedness,and reversibility,LBR) 作为制 造系统行为特性的重要表征,当制造系统出现变更时, 一般都要对重构后的 LBR 特性重新进行分析判别,并 对系统进行反馈修正,这种重构后再分析的方法会显
·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, NRS) ,研究并行系统的 PN 网络结构动态重组,并确 保重组后的系统继承原系统的 LBR 特性. 为了提高网 重写系统的适用性,Li 等[6--10]在网重写系统的基础上, 提出了改进的网重写系统( improved net rewriting system,INRS) ,并基于此重写方法,根据不同类型的库所 针对的一系列 PN 单元结构进行了可重构分析,大幅 扩充了可重构单元类库,并证得 PN 单元结构库中任 意类型的结构互换都不会改变重构前系统的 LBR 特 性. 谢楠和李爱平[11]根据网重写系统提出可重构 PN 制造系统控制器设计方法,动态重构自身结构以适应 新的生产需求,并判定了其行为特性. Renna 和 Ambrico[12]借助 LINGO 软件提出了对应的数学模型来解决 单元制造系统的设计、可重构以及调度问题,取得了良 好效果. 然而目前的行为特性继承可重构单元主要针对的 是普通 PN,不曾考虑输入输出权重对制造系统可重构 能力的影响,但在实际工业生产中,由于生产设备制造 能力、生产成本、生产效率等客观约束的影响,制造系 统所对应的 PN 节点间不只是互连与否,而是需要一 定数量的托肯支撑,这就导致了以往的重构方法不再 适用这种新的重构要求. 同时,目前的网重写系统与 改进的网重写系统重构类库是松散而不成体系的,重 构单元的自组织及自律能力欠缺,因此针对工业生产 制造流程特点提出修正网重写系统( modified net rewriting system,MNRS) ,通过系统化模块化的重构单元 子类封装,以及边界耦合与内部结构使能规则的制定, 来实现具有行为特性继承特点的制造系统快速动态 重构. 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 可达,所有的可 达标识构成可达集合 RM . 标识改变遵循以下规则: 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 的行为特性主要有活性、有界性和可逆性,简 称为 LBR,该三个行为特性是相互独立的且是 PN 系 统动态行为特性分析的基础. ( 1) 活性: 对于任一变迁 t,在任一标识 M∈RM 下,总存在某一变迁激发序列 s = ( M1,M2,…) 使得 Ms (·t) ≥F(·t,t) ; ( 2) 有界性: 对于一给定 PN 及其可达集合 RM,若 max( M( p) ) ≤k,其中 M∈RM,则该 PN 是 k 有 界的; ( 3) 可逆性: 对于一给定 PN 及其可达集合 RM,初 始标识 M0 由 M∈RM 可达. 1. 2 修正网重写系统定义 映射定义: 若 RX × Y 是一二元关系,令 X'R = { y∈Y | x∈X',( x,y) ∈R} 表示 X'X 的 象( image) ,令 RY' = { x∈X| y∈Y',( x,y) ∈R} 表示 Y'Y 的原象( inverse image) . R 的定义域( domain) 与陪域 ( codomain) 分别为 Dom( R) = RY 和 Cod( R) = XR. 修正重写网系统由以下三元组组成: N = ( G,R, L) ,其中,G = ( Γ,M0 ) 为重构前的 PN,M0 为 PN 的初 始标识,Γ= ( P,T,F) 为一般 PN 且满足一般 PN 约束 关系. R = ( r1,r2,…) 为有限重构规则集合,r = ( L,R, τ,·τ,τ·) ,其中 L = ( PL,TL,FL ) 与 R = ( PR,TR,FR ) 分 别称 为 G 重 构 的 左 手 侧 ( left-hand side) 与 右 手 侧 ( right-hand side) ,如图 1 所示,L 为可重构区域重构之 前的 PN 结构,R 为重构之后的 PN 结构,kI 与 kO 分别 为输入与输出量. τ: ( PL∪TL ) ( PR∪TR ) 表示重构 前结构与重构后之间的双向映射关系且 PL τPR ∧ TL τTR∧τPRPL∧τTRTL,·τ 与 τ·分别为重构结 构输 入 端 与 输 出 端 的 端 口 关 系,在 图 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 进行重构后 得到的新网络可继承原网的 LBR 行为特性. 图 1 修正网重写系统左手侧与右手侧 Fig. 1 Left-hand and right-hand of the MNRS 1. 3 修正网重写系统结构重写 一般 PN 网络结构重构后得到: G' = ( Γ',M' 0 ) = ( P',T',F',M' 0 ) . 当 Γ → r Γ'时,亦即 Γ 通过重构规 则 r 重写为 Γ',其库所与变迁遵循以下变动关系: P' = P - f( PL ) + PR, T' = T - f( TL ) + TR { . ( 2) 其中,PR = PL τ,TR = TL τ. f 为全嵌入式子网映射,定义 如下: f: L→Γ. 其中,对于xf( L) ,y∈L 有以下 推导关系成立: x∈·f( y) y∈Dom(·τ) 且 x∈f( y)· y∈Dom( τ·) . 重构后的网络节点关系如下所示: F'( x,y) = F( x,y) , x,y PR ∪ T; FR ( x,y) , x,y ∈ PR ∪ TR ; 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 网络 FR 需要满足一定的结构要求, 因为封装后的不同重构单元对于内部输入输出函数的 重构要求也是各不相同的,具体结构关系在下文中详 细阐述. 同时,边界节点关系不只是单纯的连接与否, 具体的输入输出函数需要满足以下关系: F'( x,* ) = F( x,* ) ,x∈·TI ; {F'( * ,y) = F( * ,y) ,y∈TO ·. ( 4) 其中,* 表示通配符. 而对于 PN 初始标识影响如下: M' 0 ( p) = M0 ( p) , pR; M0 { ( f( p) ) , p∈R. ( 5) 值得一提的是,当初始标识 M0 经过变迁激发序 列 s 可达 M0[s > Ms 时,倘若产品托肯未处于可重构 区域 L 中,便可对 G = ( Γ,M0 ) 进行 Γ → r Γ'结构重 构,标识改变如下: M' s ( p) = Ms ( p) , pR; Ms { ( f( p) ) , p∈R. ( 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,R,L) 的修正网重写系 统,其中 G = ( Γ,M0 ) ,R = { r} ,r = ( L,R,τ,·τ,τ·) . L 为一变迁,R 为一相同输入输出的 BC. 可得结论: 倘 若 G 具有 LBR 特性,则重构后得到的 G' = ( Γ',M' 0 ) 也 具备 LBR 特性. 在此以 BC 子类为例证明 LBR 特性继 承,其他子类特性继承的证明方法与此相类似. 证明: 以图 4 中所示具体实例证明 BC 重构时的 LBR 特性继承. 修正网重写系统为 N = ( G,r,L) ,其 中 G = ( Γ,M0 ) ,重构规则 r = ( L,R,τ,·τ,τ·) ,L = ( TL,FL ) 为 G 重构的左手侧,且输入输出函数满足关 系 kO = nkI,对应切割等托肯增加操作,R = ( PR,TR, FR ) 为 G 重构右手侧,且内部结构满足 ki = kO,重构结 构输入端与输出 端 的 端 口 关 系 分 别 为·τ = ( { TL } , { TI } ) ,τ·= ( { TL } ,{ TO } ) ,这一 BC 重构可视作在切 割完成之后添加质检工序. 图 4 LBR 特性继承证明实例 Fig. 4 Proof example of LBR property inheritance G 具有活性,因此对于具有相同输入输出的重构 右手侧,必然存在某一变迁序列使得变迁 TI 使能,随 后,图 4 所示 BC 结构能够在 TI 点火情况下激发变迁 TO,并输出 M( TO ·) = kO,剩余的所有变迁t∈( T' - TR ) 回归到原有的( T - TL ) ,因此,G'是活的. 对于有 界性,假定 G 是 k 有界的,图 4 所示 BC 重构的结构特 点满足 M( p) ≤kO≤k,即 R 是 k 有界的,而根据修正 网重写系统的局部特性,p∈P' - PR 是 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 ) 替换 为 R = ( PR,TR,FR ) ,由于 BC 的局部特性以及输入输 出一致性,仍旧存在这样的变迁序列 si 以及 sk,分别 使得 M' 0[si > M' si 以及 M' sj [sk > M' 0 成立,其中,M' 0 = M0 ( P) ∪M' 0 ( PR ) ,M' 0 ( PR ) = 0,对于 M' si ,M' si = Msi ( P) ∪ M' si ( PR ) ,M' si ( PR ) = 0,并且,M' sj = Msj ( P) ∪M' sj ( PR ) , M' sj ( PR ) = 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 所示为封装后的顺序( 串联) 结构单元( sequence 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,R,L) 的修正网重写系 统,其中 G = ( Γ,M0 ) ,R = { r} ,r = ( L,R,τ,·τ,τ·) . L 为一 BC,R 为 一 相 同 输 入 输 出 的 SC,且 ∏ ( I: PSC × TSC ) / ∏ ( O: TSC × PSC ) = kI / kO . 可得结论: 倘 若 G 具有 LBR 特性,则重构后得到的 G' = ( Γ',M' 0 ) 也 具备 LBR 特性. 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 ·
·1452· 工程科学学报,第38卷,第10期 一CSC. 给定某个结构为=(G,R,团的修正网重写系 迹择约束为宫V宫4 统,其中G=(T,M),R={r},r=(L,R,x,,). 其中,n为支路数目.则该L为一PCC. L为一BC,R为一相同输入输出的CSC,且∏(I: 给定某个结构为=(G,R,)的修正网重写系 统,其中G=(T,M),R={r},r=(L,R,x,r,r). Psx×Tx)/∏(O:Tc×Psc)=k,/ko:可得结论:倘 L为一BC,R为一相同输入输出的PCC,其主干等效 若G具有LBR特性,则重构后得到的G=(T,M6)也 非缓冲结构满足Π(I:Pc×Tsc)/∏(O:Tc× 具备LBR特性 2.4PCC子类 Pc)× 三名=,可得结论:销若G具有 图l0所示为封装后的并行选择单元(parallel LBR特性,则重构后得到的G=(T,M,)也具备LBR choice cell,PCC),在逻辑上是XOR-SPLIT-XOR- 特性 JON的,实现多选一和先到先得的关系映射,对应生 2.5PMC子类 产制造中的分拣质检等操作.在此假定,对于·T,中的 图l2所示为封装后的并行聚合单元(parallel 托肯,总能找到对应的条件使其实现变迁1∈T,激发, merge cell,PMC),在逻辑上是XOR-SPLIT-AND- 并且选择不存在冗余,所有的支路都被有效利用,抑制 JON的,实现多选一、同步聚合的关系映射,对应生产 支路资源长期占有情形的出现.为了防止出现资源堵 制造中的零件组装等操作.在此假定,对于·T,中的任 塞情况,引入带有缓冲区结构的$C,同时为了不失一 一托肯,总能找到对应的条件使其实现变迁·T,激发, 般性,借助SC结构构建PCC主干,得到如图11所示 并且选择不存在冗余.当单元主干不存在资源堵塞情 更具普适性的PCC结构. 况并且同步聚合变迁输出0:1=k。时,即为图12所示 单元结构,但是在有资源堵塞情况时,必须引入带有缓 冲区结构的SC,同时单元内的变迁激发遵循PN的激 发规则,如图13所示.需要注意的是,同步聚合变迁t 处,任意一条支路输入函数满足O:k: 图10并行选择单元 Fig.10 Parallel choice cell 图12并行聚合单元 Fig.12 Parallel merge cell 图11PCC结构 Fig.11 Structure of the PCC PCC定义:给定一如图11所示的异步结构L= (P,T,F),I…T,I≥1∧IT。l≥1 节点数量约束为l·Htl=1(t∈T-T,),It1= 图13PMC结构 1(teT-To),l3pl>1或1·3pl>1 Fig.13 Structure of the PMC 输入函数边界条件为F(T,*)Ih,Vk,F(T,*) 输出函数边界条件为F(*,T。)Iko V kolF(*, PMC定义:给定一如图13所示的结构单元L= To) (P,T,F),IT,I≥1∧IT。l≥1 节点数量约束为1·Hpl=1,1H1=1(t∈T- 并行约束为, 日V三 To),1 3p-I>1,1.3tl>1(tET-T
工程科学学报,第 38 卷,第 10 期 一 CSC. 给定某个结构为 N = ( G,R,L) 的修正网重写系 统,其中 G = ( Γ,M0 ) ,R = { r} ,r = ( L,R,τ,·τ,τ·) . L 为一 BC,R 为一相同输入输出的 CSC,且 ∏ ( I: PSC × TSC ) / ∏ ( O: TSC × PSC ) = kI / kO . 可得结论: 倘 若 G 具有 LBR 特性,则重构后得到的 G' = ( Γ',M' 0 ) 也 具备 LBR 特性. 2. 4 PCC 子类 图 10 所 示 为 封 装 后 的 并 行 选 择 单 元 ( parallel choice cell,PCC) ,在 逻 辑 上 是 XOR--SPLIT--XOR-- JOIN 的,实现多选一和先到先得的关系映射,对应生 产制造中的分拣质检等操作. 在此假定,对于·TI 中的 托肯,总能找到对应的条件使其实现变迁 t∈TI 激发, 并且选择不存在冗余,所有的支路都被有效利用,抑制 支路资源长期占有情形的出现. 为了防止出现资源堵 塞情况,引入带有缓冲区结构的 SC,同时为了不失一 般性,借助 SC 结构构建 PCC 主干,得到如图 11 所示 更具普适性的 PCC 结构. 图 10 并行选择单元 Fig. 10 Parallel choice cell 图 11 PCC 结构 Fig. 11 Structure of the PCC PCC 定义: 给定一如图 11 所示的异步结构 L = ( P,T,F) ,|·TI | ≥1∧| TO ·| ≥1 节点数量约束为|·t | = 1( t∈T - TI ) ,| t·| = 1( t∈T - TO ) ,| p·| > 1或|·p | > 1 输入函数边界条件为 F( TI,* ) |kI∨kI |F( TI,* ) 输出函数边界条件为 F( * ,TO ) | kO∨kO | F( * , TO ) 并行约束为 kI ∑ n i = 1 ki∨ ∑ n i = 1 ki kI 选择约束为 kI ∑ n i = 1 k'i∨ ∑ n i = 1 k'i kI 其中,n 为支路数目. 则该 L 为一 PCC. 给定某个结构为 N = ( G,R,L) 的修正网重写系 统,其中 G = ( Γ,M0 ) ,R = { r} ,r = ( L,R,τ,·τ,τ·) . L 为一 BC,R 为一相同输入输出的 PCC,其主干等效 非缓冲结 构 满 足 ∏ ( I: PSC × TSC ) / ∏ ( O: TSC × PSC ) × ∑ n i = 1 ki ∑ n i = 1 k'i = kI / kO . 可得结论: 倘若 G 具有 LBR 特性,则重构后得到的 G' = ( Γ',M' 0 ) 也具备 LBR 特性. 2. 5 PMC 子类 图 12 所示为封装后的并行聚合单元 ( parallel merge cell,PMC) ,在 逻 辑 上 是 XOR--SPLIT--AND-- JOIN 的,实现多选一、同步聚合的关系映射,对应生产 制造中的零件组装等操作. 在此假定,对于·TI 中的任 一托肯,总能找到对应的条件使其实现变迁·TI 激发, 并且选择不存在冗余. 当单元主干不存在资源堵塞情 况并且同步聚合变迁输出 O: t = kO 时,即为图 12 所示 单元结构,但是在有资源堵塞情况时,必须引入带有缓 冲区结构的 SC,同时单元内的变迁激发遵循 PN 的激 发规则,如图 13 所示. 需要注意的是,同步聚合变迁 t 处,任意一条支路输入函数满足 O: t | k'i . 图 12 并行聚合单元 Fig. 12 Parallel merge cell 图 13 PMC 结构 Fig. 13 Structure of the PMC PMC 定义: 给定一如图 13 所示的结构单元 L = ( P,T,F) ,|·TI | ≥1∧| TO ·| ≥1 节点数量约束为 |·p | = 1,| t·| = 1 ( t∈T - TO ) ,| p·| > 1,|·t | > 1( t∈T - TI ) · 2541 ·
李杰林等:基于修正网重写系统的制造系统动态重构 ·1453· 输入函数边界条件为F(T,*)Ik,Vk,IF(T, 由上述规则类库=(BC,SC,CSC,PCC,PMC) *) 重构定理可知,在网络不断重构的过程中,LBR的特 输出函数边界条件为F(*,T,)Iko VkolF(*, 性会一直继承下去,同时,基于修正网重写系统的重 To) 构过程都是可逆的(有兴趣的读者可以依照BC子类 并行约束为名V合点 继承证明方法自行验证),这也就意味着修正网重写 系统具有可逆特性和传递特性,直接导致类库模块 聚合约束为kolkVk1ko 子类之间的结构重构可以继承LBR行为特性.修正 其中,n为支路数目.则该L为一PMC. 网重写系统规则类库为重构提供了组织结构依据, 给定某个结构为=(G,R,分的修正网重写系 提高了动态重构的自组织能力,同时,修正网重写系 统,其中G=(T,M),R={r},r=(L,R,r,·r,r). 统所具有的重写特性使系统重构单元具有一定的自 L为一BC,R为一相同输入输出的PMC,其主干等效 律能力,基于修正网重写系统的制造系统动态重构 非缓冲结构满足∏(I:Px×Tx)/∏(O:Tx× 在方法论上就保证了LBR的继承性而不需要进行实 验验证 P)×k=k,k。可得结论:倘若G具有BR 特性,则重构后得到的G=(T,M)也具备LBR 3重构功能步序设计 特性. 由于用户产品个性化定制需求的频繁变动,相应 2.6类库内部子类关系 的制造系统会接收到反映制造资源配置变化的一系列 重构规则类劣泛化(generalization)为BC、SC、 动态重构指令,通过特征比对与模式匹配,将重构任务 CSC、PCC和PMC五大继承子类,并且子类之间又以 分解为依托模块子类重构的子任务,借助带有行为特 聚合(aggregation)这种强关联形式相互嵌套集成.其 性继承的修正网重写系统重构机制保证每次局部重构 中,BC与SC之间为多对一的聚合关系,SC与CSC、 后制造系统整体的LBR特性,具体的修正网重写系统 PCC、PMC之间分别为多对一的聚合关系. 重构机制如图14所示 重构后的制造系统物理实体配置 修正网重写系统重构步序 实时 (P.TFM) 控制 PV网络标识重写 PN模型反向映射 M→M' G=(T'M") 产品托肯约束 T=(P'.TF) LBR特性继承 输入输出函数重写 作所、变迁重写 Fx)→",y) P=P-∫(P+P 输入输山函数约束 T=T-fTHT 块 重构 修正网重与系统重与规则 重构规则往立 形=LRx,·t,t·) L=(P T F) 规则兼容 PN模型映射 G=(T.M) PV模型映射 T=(PTF) R=PTF) LBR特性 规则片兼容 泛在 互 制造系统物理实体配置 重构模块实体配置 图14修正网重写系统重构机制 Fig.14 Reconfiguration mechanism of the MNRS 可以看到,修正网重写系统重构机制主要分为重 及其重构要求,在冗余模块配置的基础上自主生成修 写规则与重构步序两大部分,根据现有制造系统配置 正网重写系统重写规则,按照重写规则依次更新生产
李杰林等: 基于修正网重写系统的制造系统动态重构 输入函数边界条件为 F( TI,* ) | kI ∨kI | F( TI, * ) 输出函数边界条件为 F( * ,TO ) | kO∨kO | F( * , TO ) 并行约束为 kI ∑ n i = 1 ki∨ ∑ n i = 1 ki kI 聚合约束为 kO | k'i∨k'i | kO 其中,n 为支路数目. 则该 L 为一 PMC. 给定某个结构为 N = ( G,R,L) 的修正网重写系 统,其中 G = ( Γ,M0 ) ,R = { r} ,r = ( L,R,τ,·τ,τ·) . L 为一 BC,R 为一相同输入输出的 PMC,其主干等效 非缓冲结 构 满 足 ∏ ( I: PSC × TSC ) / ∏ ( O: TSC × PSC ) × ∑ n i = 1 ki / k'i = kI / kO . 可得结论: 倘若 G 具有 LBR 特性,则 重 构 后 得 到 的 G' = ( Γ',M' 0 ) 也具 备 LBR 特性. 2. 6 类库内部子类关系 重构 规 则 类 L 泛 化 ( generalization) 为 BC、SC、 CSC、PCC 和 PMC 五大继承子类,并且子类之间又以 聚合( aggregation) 这种强关联形式相互嵌套集成. 其 中,BC 与 SC 之间为多对一的聚合关系,SC 与 CSC、 PCC、PMC 之间分别为多对一的聚合关系. 由上述规则类库 L = ( BC,SC,CSC,PCC,PMC) 重构定理可知,在网络不断重构的过程中,LBR 的特 性会一直继承下去,同时,基于修正网重写系统的重 构过程都是可逆的( 有兴趣的读者可以依照 BC 子类 继承证明方法自行验证) ,这也就意味着修正网重写 系统具有可逆特性和传递特性,直接导致类库模块 子类之间的结构重构可以继承 LBR 行为特性. 修正 网重写系统规则类库为重构提供了组织结构依据, 提高了动态重构的自组织能力,同时,修正网重写系 统所具有的重写特性使系统重构单元具有一定的自 律能力,基于修正网重写系统的制造系统动态重构 在方法论上就保证了 LBR 的继承性而不需要进行实 验验证. 3 重构功能步序设计 由于用户产品个性化定制需求的频繁变动,相应 的制造系统会接收到反映制造资源配置变化的一系列 动态重构指令,通过特征比对与模式匹配,将重构任务 分解为依托模块子类重构的子任务,借助带有行为特 性继承的修正网重写系统重构机制保证每次局部重构 后制造系统整体的 LBR 特性,具体的修正网重写系统 重构机制如图 14 所示. 图 14 修正网重写系统重构机制 Fig. 14 Reconfiguration mechanism of the MNRS 可以看到,修正网重写系统重构机制主要分为重 写规则与重构步序两大部分,根据现有制造系统配置 及其重构要求,在冗余模块配置的基础上自主生成修 正网重写系统重写规则,按照重写规则依次更新生产 · 3541 ·
·1454. 工程科学学报,第38卷,第10期 资源及其相互关系,并最终映射到现实物理实体配置 具体重构机制在重构规则建立的过程中就考虑到重构 模块的规则库兼容性,从方法上就保障了重构后系统 6 的行为特性而无需进行反馈修正. 4仿真验证与实例应用 卤4○回 为了便于理解并验证修正网重写系统重构机制的 可用性,通过软件仿真与实例应用进行说明. 4.1仿真验证 借助PN模拟仿真软件TINA,以图15(a)中所示 PN模型为例做仿真验证,其中库所中数值表示托肯数 量,有向弧带有一定的数值权重,未标数值默认为1. 2 图16BC-SC重构仿真示例 0 Fig.16 Reconfiguration case of the BC-SC 4 0 5 p5( 回8○8回 4 ○p4 ○pm 回8○向 2 p3( 8 a (b) 图15BC重构仿真示例.(a)原始PN模型:(b)BC重构后的 pl2 PN模型 Fig.15 Reconfiguration case of the BC:(a)original PN model: 图17 BC-CSC重构仿真示例 (b)reconfigured PN model by the BC Fig.17 Reconfiguration case of the BC-CSC 图I5(a)中为具有LBR特性的原始制造系统PN 模型,现有重构需求为在输入输出函数分别为4与8 的变迁t0区域添加一BC结构,对应现实生产制造过 程中在现有制造系统中加入某一道工序的重构指令, 根据修正网重写系统重构机制可得到图15(b)中的 PN模型结构.同理,图16为在图15(b)基础上对区域 0p55进行BCSC重构后得到的PN模型,图16中 $C模块存在有限容量缓冲区结构,能够有效缓解资源 堵塞等问题,并且在后续的库所p5处,PN结构使能规 3 15 则能够积累返还相应的托肯,保证行为特性的继承. 10 图17为在图15(b)基础上对BC区域t1-p2-2 2 进行BC-CSC重构后得到的PN模型,其中·?= pll ({1},{4}),x·=({2},{12}).图18为在图15 图18BC-PCC重构仿真示例 (b)基础上对BC区域5plt1进行BC-PCC重构后 Fig.18 Reconfiguration case of the BC-PCC 得到的PN模型,其中·=({5},{7,11}),·= 仿真结果显示,上述PN重构过程能够继承原始 ({1},{14}),无向弧是为了方便仿真加入的抑制 制造系统的LBR特性.以图15(b)以及图18中BC- 弧.图19为在图15(b)基础上对BC区域t122进 PCC重构为例,图20和图21分别为其LBR分析结果. 行BC-PMC重构后得到的PN模型,其中·r=({}, 因此由修正网重写系统的传递性,规则类库罗=(BC, {1,4}),x=({2},{7}). SC,CSC,PCC,PMC)中子类之间的结构重构不会破坏
工程科学学报,第 38 卷,第 10 期 资源及其相互关系,并最终映射到现实物理实体配置. 具体重构机制在重构规则建立的过程中就考虑到重构 模块的规则库兼容性,从方法上就保障了重构后系统 的行为特性而无需进行反馈修正. 4 仿真验证与实例应用 为了便于理解并验证修正网重写系统重构机制的 可用性,通过软件仿真与实例应用进行说明. 4. 1 仿真验证 借助 PN 模拟仿真软件 TINA,以图 15( a) 中所示 PN 模型为例做仿真验证,其中库所中数值表示托肯数 量,有向弧带有一定的数值权重,未标数值默认为 1. 图 15 BC 重构仿真示例. ( a) 原始 PN 模型; ( b) BC 重构后的 PN 模型 Fig. 15 Reconfiguration case of the BC: ( a) original PN model; ( b) reconfigured PN model by the BC 图 15( a) 中为具有 LBR 特性的原始制造系统 PN 模型,现有重构需求为在输入输出函数分别为 4 与 8 的变迁 t0 区域添加一 BC 结构,对应现实生产制造过 程中在现有制造系统中加入某一道工序的重构指令, 根据修正网重写系统重构机制可得到图 15 ( b) 中的 PN 模型结构. 同理,图 16 为在图 15( b) 基础上对区域 t0--p5--t5 进行 BC--SC 重构后得到的 PN 模型,图 16 中 SC 模块存在有限容量缓冲区结构,能够有效缓解资源 堵塞等问题,并且在后续的库所 p5 处,PN 结构使能规 则能够积累返还相应的托肯,保证行为特性的继承. 图 17 为在图 15 ( b) 基础上对 BC 区域 t1--p2--t2 进行 BC--CSC 重 构 后 得 到 的 PN 模 型,其 中·τ = ( { t1} ,{ t4} ) ,τ·= ( { t2} ,{ t12} ) . 图 18 为在 图 15 ( b) 基础上对 BC 区域 t5--p1--t1 进行 BC--PCC 重构后 得到的 PN 模 型,其 中·τ = ( { t5 } ,{ t7,t11 } ) ,τ·= ( { t1} ,{ t14} ) ,无向弧是为了方便仿真加入的抑制 弧. 图 19 为在图 15( b) 基础上对 BC 区域 t1--p2--t2 进 行 BC--PMC 重构后得到的 PN 模型,其中·τ = ( { t1} , { t1,t4} ) ,τ·= ( { t2} ,{ t7} ) . 图 16 BC--SC 重构仿真示例 Fig. 16 Reconfiguration case of the BC--SC 图 17 BC--CSC 重构仿真示例 Fig. 17 Reconfiguration case of the BC--CSC 图 18 BC--PCC 重构仿真示例 Fig. 18 Reconfiguration case of the BC--PCC 仿真结果显示,上述 PN 重构过程能够继承原始 制造系统的 LBR 特性. 以图 15( b) 以及图 18 中 BC-- PCC 重构为例,图20 和图21 分别为其 LBR 分析结果. 因此由修正网重写系统的传递性,规则类库 L = ( BC, SC,CSC,PCC,PMC) 中子类之间的结构重构不会破坏 · 4541 ·
李杰林等:基于修正网重写系统的制造系统动态重构 ·1455· 制造系统PN模型原有的LBR特性,制造系统可以针 0 对生产重构需求,根据修正网重写系统重构机制与重 构步序实现对生产资料的快速自主配置。 4.2实例应用 以某表面贴装技术(surface mount technology, SMT)双面混合组装生产线改造为例进行实例验证. 8 该表面贴装技术生产线可以实现正常元器件贴片,其 4 PN模型如图22所示,输入输出函数权重表示单次容 量,变迁与库所的具体内容如表1所示,易知该模型为 e 活的、有界的和可逆的 2亩 该生产线现改用新型高速同步贴片机,通过多个 贴片头双面贴片提高组装速度,减轻由于贴片等待造 图19BC-PMC重构仿真示例 成的印刷线路板(printed circuit board,PCB)氧化,加 Fig.19 Reconfiguration case of the BC-PMC 74 C\UsersVaeGer\Desktop\Article4_PN\BC_TINA.ktz digest net 5 5 4 图20BC重构仿真结果 Fig.20 Simulation result of BC reconfiguration 76 CA\UsersVaeGer DesktoplArticle4_PN\PCC_TINA.ktz 回3 digest places 9 uansliors 10 net abatraction heb 19 10 图21BC-PCC重构仿真结果 Fig.21 Simulation result of BC-PCC reconfiguration ©1⊙1⊙ @1@1 @1@1@1@/@1©1 22 p20 25 26. 图22表面贴装技术生产线对应PW模型 Fig.22 PN model of the SMT production line
李杰林等: 基于修正网重写系统的制造系统动态重构 图 19 BC--PMC 重构仿真示例 Fig. 19 Reconfiguration case of the BC--PMC 制造系统 PN 模型原有的 LBR 特性,制造系统可以针 对生产重构需求,根据修正网重写系统重构机制与重 构步序实现对生产资料的快速自主配置. 4. 2 实例应用 以某 表 面 贴 装 技 术 ( surface mount technology, SMT) 双面混合组装生产线改造为例进行实例验证. 该表面贴装技术生产线可以实现正常元器件贴片,其 PN 模型如图 22 所示,输入输出函数权重表示单次容 量,变迁与库所的具体内容如表 1 所示,易知该模型为 活的、有界的和可逆的. 该生产线现改用新型高速同步贴片机,通过多个 贴片头双面贴片提高组装速度,减轻由于贴片等待造 成的印刷线路板( printed circuit board,PCB) 氧化,加 图 20 BC 重构仿真结果 Fig. 20 Simulation result of BC reconfiguration 图 21 BC--PCC 重构仿真结果 Fig. 21 Simulation result of BC--PCC reconfiguration 图 22 表面贴装技术生产线对应 PN 模型 Fig. 22 PN model of the SMT production line · 5541 ·
·1456· 工程科学学报,第38卷,第10期 表1PN模型中库所/变迁对应含义 Table 1 Corresponding meaning of P/T in the PN model 库所/变迁 对应含义 库所/变迁 对应含义 库所/变迁 对应含义 pl 元器件齐套(32) 原材料输送 P5 自动检测 卫 缓冲区 2/t6/10/14 涂胶开始 P8 缓冲区 p3/p6/p9/p12 印刷线路板贴片A面 3/7/11/15 涂胶结束 p9 元件检测 p4/p7/p10/p13 印刷线路板贴片B面 4/8/12/16 贴片结束 p25 产品打包 P5/p8/pl1/p14 人工检测 5/9/t13/t17 检测结束 p28 制标识 pl5 缓冲区 t18/21 回流焊接开始 r7 原材料输送 p16/p18 回流焊接 t19/22 回流焊接结束 t2/t6 高速贴片开始 p17/p19 质量检测 t20/23 检测结束 t3/t7 高速贴片结束 p20 缓冲区 t24/26 波峰焊接开始 19 自动检测结束 p21/p23 波峰焊接 25/27 波蜂焊接结束 14 质量检测 p22/p24 最终检测 28/29 检测结束 t15 检测结束 p25 产品打包 t30 打包结束 t30 开始打包 p26 成品仓储 31 资源释放 t32 打包结束 p27 缓冲区 p3/p6 印刷线路板高速贴片 快生产节拍.同时,在贴片操作前添加元器件检测工 23中A区域所示结构:对于B区域,规则类库中的子 序,防止元器件本身质量问题对印刷线路板的影响,并 类不能直接应用到该结构,但注意到,2为一缓冲区 用自动检测装置代替回流焊接前的人工检测,提高标 库所,起到缓解资源堵塞作用,因此,可将p2纳入B区 准化水平.最后,在产品打包过程中,借助无线射频识 域使之成为一PCC结构,因此,重构规则r2左右手侧 别同步关联产品生产过程信息以便质量追溯. 为不同结构的PCC类型,·r=({15},{t15}),x·= 根据该生产线的物理实体配置以及重构需求,可 ({5,9,13,t17},{9}),重构为图23中B区域所示 知图22的PN模型中A、B和C部分为对应重构区域, 结构:对于C区域,根据重构要求,重构右手侧应当为 相应的修正网重写系统重写规则为=(G,R,, 一CSC结构,但是在图22的C区域难以直接集成 其中G=(T,M。)为如图22所示重构前的PN,R= CSC,实际上,该结构隐含防止资源堵塞的缓冲区p27, (r,r2,3)为重构规则集合.对于A区域,易知重构规 将该区域细化后可知重构规则,3左手侧为一BC,重 则r1左手侧为一变迁1,右手侧为一满足约束条件的 构后为图23中C区域所示的CSC结构.最终该表面 SC,x=({1},{t1}),x·=({},{15}),重构为图 贴装技术生产线重构后的PN模型如图23所示 8-38+ 2 .3 p28 @-1@ 图23基于修正网重写系统重构后PN模型 Fig.23 PN model after reconfiguration based on the MNRS 通过分析该PN模型的可达性可知,重构后的生 重写系统重构机制对该生产线进行重构,能够在重构 产系统仍旧是活的、有界的和可逆的,因此根据修正网 过程中继承系统原有的LBR行为特性.按照该修正网
工程科学学报,第 38 卷,第 10 期 表 1 PN 模型中库所/变迁对应含义 Table 1 Corresponding meaning of P /T in the PN model 库所/变迁 对应含义 库所/变迁 对应含义 库所/变迁 对应含义 p1 元器件齐套( 32) t1 原材料输送 p'5 自动检测 p2 缓冲区 t2 /t6 /t10 /t14 涂胶开始 p'8 缓冲区 p3 / p6 / p9 / p12 印刷线路板贴片 A 面 t3 /t7 /t11 /t15 涂胶结束 p'9 元件检测 p4 / p7 / p10 / p13 印刷线路板贴片 B 面 t4 /t8 /t12 /t16 贴片结束 p'25 产品打包 P5 / p8 / p11 / p14 人工检测 t5 /t9 /t13 /t17 检测结束 p'28 制标识 p15 缓冲区 t18 /t21 回流焊接开始 t'1 原材料输送 p16 / p18 回流焊接 t19 /t22 回流焊接结束 t'2 /t'6 高速贴片开始 p17 / p19 质量检测 t20 /t23 检测结束 t'3 /t'7 高速贴片结束 p20 缓冲区 t24 /t26 波峰焊接开始 t'9 自动检测结束 p21 / p23 波峰焊接 t25 /t27 波峰焊接结束 t'14 质量检测 p22 / p24 最终检测 t28 /t29 检测结束 t'15 检测结束 p25 产品打包 t30 打包结束 t'30 开始打包 p26 成品仓储 t31 资源释放 t'32 打包结束 p27 缓冲区 p'3 / p'6 印刷线路板高速贴片 快生产节拍. 同时,在贴片操作前添加元器件检测工 序,防止元器件本身质量问题对印刷线路板的影响,并 用自动检测装置代替回流焊接前的人工检测,提高标 准化水平. 最后,在产品打包过程中,借助无线射频识 别同步关联产品生产过程信息以便质量追溯. 根据该生产线的物理实体配置以及重构需求,可 知图 22 的 PN 模型中 A、B 和 C 部分为对应重构区域, 相应的修正网重写系统重写规则为 N = ( G,R,L) , 其中 G = ( Γ,M0 ) 为如图 22 所示重构前的 PN,R = ( r1,r2,r3 ) 为重构规则集合. 对于 A 区域,易知重构规 则 r1 左手侧为一变迁 t1,右手侧为一满足约束条件的 SC,·τ = ( { t1} ,{ t'1} ) ,τ·= ( { t1} ,{ t'15} ) ,重构为图 23 中 A 区域所示结构; 对于 B 区域,规则类库中的子 类不能直接应用到该结构,但注意到,p2 为一缓冲区 库所,起到缓解资源堵塞作用,因此,可将 p2 纳入 B 区 域使之成为一 PCC 结构,因此,重构规则 r2 左右手侧 为不同结构的 PCC 类型,·τ = ( { t'15} ,{ t'15} ) ,τ·= ( { t5,t9,t13,t17} ,{ t'9} ) ,重构为图 23 中 B 区域所示 结构; 对于 C 区域,根据重构要求,重构右手侧应当为 一 CSC 结 构,但 是 在 图 22 的 C 区域难以直接集成 CSC,实际上,该结构隐含防止资源堵塞的缓冲区 p27, 将该区域细化后可知重构规则 r3 左手侧为一 BC,重 构后为图 23 中 C 区域所示的 CSC 结构. 最终该表面 贴装技术生产线重构后的 PN 模型如图 23 所示. 图 23 基于修正网重写系统重构后 PN 模型 Fig. 23 PN model after reconfiguration based on the MNRS 通过分析该 PN 模型的可达性可知,重构后的生 产系统仍旧是活的、有界的和可逆的,因此根据修正网 重写系统重构机制对该生产线进行重构,能够在重构 过程中继承系统原有的 LBR 行为特性. 按照该修正网 · 6541 ·