（信号与信息处理专业论文）基于petri网的柔性制造系统的网简化技术研究.pdf

基于p e t r i 网的柔性制造系统的网简化技术研究 摘要 柔性制造系统中共享资源的分配不当是死锁产生的主要原因。一 旦出现死锁，系统生产就会出现停顿，从而导致昂贵设备的生产率低 下，造成生产企业的经济损失，有时候甚至会造成灾难性的后果。有 效处理系统的死锁问题是保证制造系统获得高生产率的前提条件，因 此，寻找有效的方法来预防和控制柔性制造系统中的死锁已经成为近 年来研究的热点。 p e t r i 网是一种重要的建模工具，能够描述资源共享、互斥、并发 和冲突等，而且在计算方面也表现出了优越的性能，相比于自动机等 建模工具具有明显的优势，因而成为研究柔性制造系统死锁问题的主 要建模工具。s 3 p r 网是柔性制造系统p e t r i 网模型的一个重要子类， 也是大多数学者研究柔性制造系统死锁问题通常采用的模型。本文的 研究工作基于s 3 p r 网，主要集中在降低活性p e t r i 网控制器的结构复 杂性、提高其行为许可性，同时降低求解活性控制器的计算复杂性。 本文的主要研究成果如下： 1 现有的死锁控制策略通常是基于信标来添加控制库所，最终得 到活性的控制器。本文通过分析基于信标的死锁控制策略中添加的控 制库所的特点，提出了一种基于信标资源排序的控制库所冗余性检测 i 方法。现有的死锁控制策略得到的活性p e t r i 网控制器中往往含有冗 余控制库所，而本文提出的方法的优点在于能够剔除最大数量的冗余 控制库所，且与检测控制库所冗余性的顺序无关，最终得到的活性控 制器具有较简单的结构和较多的许可行为。 2 本文提出了一种基于必需控制库所设计优化控制器的的方法。 在一般情况下，此法得到的活性控制器在行为许可性和结构复杂性方 面有较好的性能。特别是当输入的活性控制器中含有多组必需控制库 所的时候，此法得到的控制器在行为许可性和结构复杂性方面的优势 更加明显。最优控制器的求解一直是设计活性p e t r i 网控制器的研究 热点。文中的两个柔性制造系统实例表明本文方法得到的优化控制器 能以较简单的结构得到接近最优的行为许可性。 最后，在总结全文的基础上，对基于p e t r i 网的柔性制造系统活 性控制器简化技术的未来研究工作进行了展望。 关键字：冗余控制库所，柔性制造系统，p e t r i 网，死锁预防，信标 h r e s e a r c ho nn e tr e d u n d a n tf o r f l e x i b l em a n u f a c t u r i n gs y s t e m s b a s e do np e t r in e t s a b s t r a c t t h em i s a l l o c a t i o no fs h a r e dr e s o u r c e si st h em a i nc a u s el e a d st od e a d l o c k si n f l e x i b l em a n u f a c t u r i n gs y s t e m s o n c ed e a d l o c ko c c u r s ，t h ef l e x i b l e m a n u f a c t u r i n g s y s t e m w i l lb e h a l t e d ，r e s u l t i n g i nl o wp r o d u c t i v i t yo f e x p e n s i v ee q u i p m e n t ， s o m e t i m e se v e nc a u s es i g n i f i c a n te c o n o m i cl o s s e sa n dc a t a s t r o p h i c c o n s e q u e n c e s s i n c ed e a l i n g e f f i c i e n t l yw i t h d e a d l o c k p r o b l e mb e c o m e si m p o r t a n tf o rh i g h p r o d u c t i v i t y , f i n d i n ga ne f f e c t i v ew a yt oc o n t r o ld e a d l o c k sr u mo u tt ob eah o t r e s e a r c hs p o ti na c a d e m i ca n d e n g i n e e r i n gc i r c l e s p e t r in e ti sa ni m p o r t a n tm o d e l i n gt o o lt od e s c r i b et h es h a r i n go f r e s o u r c e s ， m u t u a le x c l u s i o n ，c o n c u r r e n c ya n dc o n f l i c t i nas y s t e m c o m p a r e dw i t ho t h e r m o d e l i n gt o o l s ，p e t r in e th a so b v i o u se f f i c i e n c ya n ds u p e r i o rp e r f o r m a n c ei n c a l c u l a t i o n t h e r e f o r e ，i th a sb e c o m et h em a i n m o d e l i n g t o o l sf o rf l e x i b l e m a n u f a c t u r i n gs y s t e m s s 3 p ri sa ni m p o r t a n ts u b s e to fp e t r in e t s ，w h i c hi sc o m m o n l v u s e df o rh a n d l i n gd e a d l o c kp r o b l e m s i ng e n e r a l ，d e a d l o c kp r e v e n t i o np o l i c i e sa i e e v a l u a t e dw i t ht h e i r p e r f o r m a n c e si n t e r m so fs t r u c t u r a l c o m p l e x i t y , b e h a v i o r p e r m i s s i v e n e s sa n dc o m p u t i o n a le f f i c i e n c y i nt h i sp a p e r , t w oe f f i c i e n tm o t h o d sa r e p r o p o s e df o ri m p r o v i n gt h ep e r f o r m a n c eo fal i v e n e s s e n f o r c i n gp e t r in e ts u p e r v i s o r , t h e ya r es u m m a r i z e da sf o l l o w s ： i i i i s of a r , t h ee x i s t i n gd e a d l o c kp r e v e n t i o np o l i c i e sa r em a i n l yb a s e do ns i p h o n s i n t h i sp a p e r , t h ec h a r a c t e r i s t i c so ft h em o n i t o ri ns i p h o n b a s e dd e a d l o c kc o n t r o l p o l i c i e sa r ea n a l y z e d ，a n da ne f f e c t i v em e t h o di sp r o p o s e dt ot e s tt h er e d u n d a n c yo f t h em o n i t o r sb a s e do nt h en u m b e ro fr e s o u r c e si ns i p h o n s t h ee x i s t i n gd e a d l o c k p r e v e n t i o np o l i c i e su s u a l l yc o n t a i nr e d u n d a n tm o n i t o r s ，b u tt h ep r o p o s e dm o t h o dc a n l e a d st ot h em a x i m u mn u m b e ro fr e d u n d a n tm o n i t o r s ，a n du l t i m a t e l yl e a d st oa l i v e n e s s e n f o r c i n gs u p e r v i s o rw i t hs i m p l e rs t r u c t u r ea n dm o r ep e r m i s s i v eb e h a v i o r s 2 i nt h i sp a p e r ，am e t h o di sp r o p o s e dt oo b t a i nt h eo p t i m i z e ds u p e r v i s o rb a s e d o nn e c e s s a r ym o n i t o r s i nm o s tc a s e s ，l i v e n e s s - e n f o r c i n gs u p e r v i s o r so b t a i n e db yt h i s m e t h o d a r ew i t hs i m p l e rs t r u c t u r ea n d h i g h e rb e h a v i o rp e r m i s s i v e n e s s i ti sr e m a r k a b l e t h a tt h ep r o p o s e dm e t h o dp r o f o r m sb e a e rw h e nt h e r ea r em u l t i s e to fn e c e s s a r y m o n i t o r si nt h eo r i g i n a ll i v e n e s s e n f o r c i n gs u p e r v i s o r s t h ew a yt od e s i g na no p t i m a l l i v e n e s s - e n f o r c i n gp e t r in e ts u p e r v i s o rh a sb e e ns t u d i e di nt h ep a s tt w od e c a d e s t w o f l e x i b l em a n u f a c t u r i n ge x a m p l e si n t h i sp a p e rs h o wt h a tt h eo p t i m i z e ds u p e r v i s o r g e n e r a t e db yt h ep r o p o s e dm e t h o di sc l o s et o t h eo p t i m a ls u p e r v i s o ri nb e h a v i o r p e r m i s s i v e n e s sa n di t ss t r u c t u r ei ss i m p l i f i e d f i n a l l y ，c o n c l u s i o n sa n df u t u r er e s e a r c ha r ep r o v i d e d k e y w o r d s ：r e d u n d a n tm o n i t o r s ；f l e x i b l em a n u f a c t u r i n gs y s t e m ；p e t r in e t s ； d e a d l o c kp r e v e n t i o n ；s i p h o n i v = ( 尸，正e 功 p r f _ c ( p x 刃u ( t x d 形 p q p k 尸r p 、7 s s 】 、= 钞put i ( k 功毋 ，= 涉pu t j ，力毋 d = u 。毫占x d = u ；e 矗 0 e o m ( p ) m m o ( ，s o ) 灭m o ) 嗍 啪p ，) 嗍( ，f ) m t s 3 p r 麒力= ”，n 尸a 主要符号对照表 v 一个p e t r i 网 库所的集合 变迁的集合 有向弧的集合 有向弧权重的集合 闲置库所的集合 工序库所的集合 资源库所的集合 控制库所的集合 一个信标 信标s 的补集 x 的前置集 x 的后置集 库所子集d 的前置集 库所子集d 的后置集 库所子集d 中的托肯总和 标识集合 初始标识 一个含有初始标识的p e t r i 网系统 p e t r i 网m o ) 的可达图 p e t r i 网的关联矩阵 库所p 的关联向量 变迁t 的关联向量 变迁t 在标识m 下是使能的 含有资源的简单顺序过程系统 资源库所，的持有者的集合 o n n e n 矿 n x = ( 尸x ，t x ，f x ，w x ) 悯i = piy ( p ) 0 ) 人s v 变迁序列 严格极小信标的集合 基本信标的集合 自然数集 正自然数集 p e t r i 网= ( p ，正e 叨导出的子网 只向量】，的支撑 信标s 的邻接集合 1 绪论 课题的研究背景和意义 制造业是按照市场要求对制造资源通过制造过程转化为可供人们使用和利 用的工业品与生活消费品的行业。经过几个世纪的发展，制造业从手工作坊、机 器生产，发展到流水线生产和自动生产，其在社会中的作用和影响随着科技的发 展而不断改变。制造业的发展水平和现代化程度决定了国民经济的发展水平和社 会的现代化程度，因此，制造业的发达程度集中体现了一个国家的综合国力。 从规模经济的角度来说，制造系统只有大批量的生产单一产品，使得生产产 品的平均成本不断降低，才能取得最佳的经济效益；反之，如果制造系统小批量 的同时生产多种产品，则需要频繁的调整生产设备，导致设备专用性低和生产难 度增大，大大降低制造系统的生产效率，进而影响到企业的经营效益【1 】。然而， 随着科技进步和经济的快速发展，人们对产品的多样化及功能和质量的要求越来 越高，制造企业为了在竞争日益加剧的环境中立于不败之地，就必须具备在很短 的周期内生产出高质量、低成本的不同产品的能力。在传统的制造系统已经远远 满足不了市场对于小批量、多样化产品的需求的情况下，柔性制造系统( f l e x i b l e m a n u f a c t u r i n gs y s t e m ，f m s ) 应运而生。 所谓柔性，是指制造系统根据系统内部和外部的变化来调整资源以生产不同 种产品的能力。通常定义柔性制造系统为一个通过计算机控制的可以同时处理多 个零件和多道工序的的生产系统，主要由自动加工系统、物流系统、信息系统和 软件系统这四个部分组成。相比于传统的制造系统，柔性制造系统的主要优势表 现在： 1 ) 设备利用率高：通过调整机器人和机床，柔性制造系统可以同时完成基 于不同工序的多种产品的生产任务； 2 、系统运行灵活：柔性制造系统中的待加工的工件在各个设备之间通过机 器人和机床自动运输、自动加工，在无人照看的情况下也能正常生产； 3 1 产品应变能力大：整个制造系统是由计算机进行集中控制的，能根据不 断变化的市场需求在不停机的情况下调整生产计划并付诸生产( 2 】。 柔性制造系统总的发展趋势是设备投资越来越少，生产周期越来越短，交货 速度越来越快，成本越来越低，设备利用率越来越高。由此可见，采用柔性制造 系统能够帮助制造企业增强竞争力，提高其经营效益【3 1 。 柔性制造系统中的共享资源对应于系统中的共享设备，如机器人，机床等。 当各种不同种类的待加工工件进入到柔性制造系统并竞争有限的共享资源时，如 果缺乏有效的控制方法，就会产生系统死锁【4 】。死锁产生后，制造系统中的加工 任务会被永远阻塞而不能得到完成，导致系统正常的制造活动无法进行，有时不 仅仅是降低系统的生产率和影响企业的经营效益，而是可能造成灾难性的后果。 因此，对一个柔性制造系统来说，其死锁问题的预防和有效处理是至关重要【5 】o p e t r i 网是制造系统的重要建模工具，从上世纪末开始被广泛应用于柔性制 造系统的研究。现有的p e t r i 网死锁控制策略大多是基于信标的，即通过对p e t r i 网中的严格极小信标添加控制器来达到预防死锁发生的目的。而理论上，一个 p e t r i 网中的信标的数量是和网的规模成指数增长的。在实际应用中，柔性制造 系统的p e t r i 网模型往往规模更大、结构更复杂，考虑到在实际生产中的控制成 本和设备的利用率，现有的活性控制器设计方法在结构复杂性和行为许可性方面 均有待改善。 本文研究p e t r i 网中控制库所的性质，提出了剔除冗余控制库所和设计优化 控制器的方法，使p e t r i 网控制器在满足活性的前提下，能以较简单的结构、较 低的计算复杂度以及较少的资源来得到较多的许可性为。本文的研究成果将对死 锁控制策略中控制器的简化理论的发展起到积极作用。 1 2 国内外研究现状 1 2 1 柔性制造系统的建模及死锁的基本概念 p e t r i 网是上世纪6 0 年代由c a p e t r i 博士f 6 】在其博士论文中首先提出的。 通常认为p e t r i 网用来描述离散事件系统具有以下优势【4 ，7 】： 1 1 可简单准确的描述系统中的并发、冲突、资源共享、非确定性和相互抑制等 特征； 2 ) 具有很高的语言复杂性、紧凑而且图形化的状态空间表示、模块化的监控器 综合能力，更适合描述并发； 3 1 通过图形界面可以清晰的给出系统的直观视图； 4 ) 已经有成熟的软件可以从p e t r i 网模型进行分析并直接生成控制代码； 5 ) 能够用于系统设计中的建模、仿真、性能分析、控制、调度等各个阶段。 基于以上优势，p e t r i 网被广泛地应用于自动制造系统的建模、仿真和监控， 在实现生产流程自动化和系统性能优化方面取得了大量研究成果【3 】o 死锁问题是设计柔性制造系统时必须要考虑和解决的问题，其研究起源于操 作系统中的共享资源分配问题。但是操作系统和制造系统中死锁问题的物理背景 不同，因此处理操作系统中死锁问题的方法还不能直接用于柔性制造系统中的死 锁问题的处理。死锁的产生必须具备一定的条件，通常认为产生系统死锁的四个 四个必要条件如下【8 】： 1 ) 互斥( m u t u a le x c l u s i o n ) ：一个任务对其持有的系统资源进行排它性使用，即 一个系统资源一次只能被一个任务使用； 2 ) 非剥夺条件( n op r e e m p t i o n ) ：一个系统资源不允许被其他任务强行剥夺，除 非这个资源是自动被释放的； 3 ) 持有并等待( h o l da n dw a i t ) ：一个任务可以在已经持有系统资源的情况下申请 其它的系统资源； 4 ) 循环等待( c i r c u l a rw a i t ) ：若干个任务形成一条任务链( 尸】，尸2 ，尸n ) ，且满足 如下条件：每一个任务均持有系统资源；每一个任务均在等待着任务链中它 的下一个任务释放其所持有的系统资源，如任务尸i 等待任务尸i + i 持有的系统 资源，而任务尸n 等待任务尸1 持有的系统资源，其中i 1 ，2 ，以) 。 一般来说，发生死锁的系统必然同时满足以上四个必要条件，但这四个必要 条件只要有一条没有成立，系统就不会产生死锁。因此，现有的处理死锁问题的 基本策略是保证在系统运行的时候产生死锁的四个必要条件不会同时成立。在柔 性制造系统中，共享的系统资源对应于系统中的共享设备，如机器人，机床等， 因此系统死锁产生的四个必要条件中的条件1 3 总是成立的，所以通常处理柔 性制造系统中的死锁问题是不让第四个条件满足，从而达到控制死锁的目地。 1 2 2 柔性制造系统死锁控制的研究方法 基于p e t r i 网理论的柔性制造系统的死锁控制策略一般来说可以分为三种： 死锁检测和恢复( d e a d l o c kd e t e c t i o na n dr e c o v e r y ) 【9 】、死锁避免( d e a d l o c k a v o i d a n c e ) 1 1o 】和死锁预防( d e a d l o c kp r e v e n t i o n ) 1 l - 1 5 1 。 死锁检测与恢复方法允许系统中死锁的发生，并在系统的运行过程中不断检 测是否已经产生死锁。一旦系统进入死锁状态并被检测到，系统便采取相应的措 施，通过结束某些导致死锁发生的任务，重新调整资源使得系统返回到无死锁的 状态，从而以最小的代价恢复系统的运行。这种死锁处理方法的效率往往取决于 其死锁检测和恢复算法的反应时间，通常需要处理大量的数据，尤其是当系统中 的共享资源数目比较大或类型比较多时，该方法的计算量往往会变得相当大。因 此这种方法一般适用于死锁较少出现或共享资源数目和类型较少的系统。 死锁避免方法是在系统的每个运行状态，通过一个在线的控制策略计算系统 的演化状态，并从这些状态中做出一个可行的选择，从而保证系统不进入死锁状 态。死锁避免方法的主要特点在于它可以实时的根据系统当前状态的信息进行决 策，通过前瞻过程禁止某些可能的事件的发生而从避免系统进入死锁状态。虽然 死锁避免方法一般拥有较高的资源利用率，但是它在某些情况下并不能消除所有 死锁，这个时候，进入死锁状态的系统仍然需要死锁恢复策略。 死锁预防方法是一种静态的控制方法，它是基于破坏产生死锁的四个必要条 件中的循环等待条件提出的。这种方法通过一种离线计算的机制来控制系统中各 任务对共享资源的请求，一旦这种控制机制建立起来，系统就永远不会发生死锁。 与其他两种方法相比，死锁预防法最大的优势在于它在系统的设计期就已经解决 了死锁控制的问题，从而使得系统无需在运行阶段检测死锁或是从死锁状态中恢 复，尤其是当响应时间作为系统的一项重要指标的时候，死锁预防方法更具优势。 此外，死锁预防方法通常不需要了解系统的运行状态，可以实际应用于较大规模 的系统中，因而逐渐成为死锁控制中较为广泛使用的一种方法。本文的研究工作 也是基于死锁预防方法。 1 2 3 柔性制造系统死锁预防方法的国内外研究现状 基于p e t r i 网的柔性制造系统模型主要有a m g ( a u g m e n t e dm a r k e dg r a p h s ) 1 6 】、 s 3 p m r ( s y s t e mo fs i m p l es e q u e n t i a lp r o c e s s e sw i t hm u l t i p l er e s o u r c e s ) 17 1 、g t a s k 1 引、 s 3 p r ( s y s t e mo fs i m p l es e q u e n t i a lp r o c e s s e sw i t hr e s o u r c e s ) t 1 9 1 、p n r ( p r o c e s sn e t s w i t hr e s o u r c e s ) 2 0 1 、r c n ( r e s o u r c ec o n t r o l n e t s ) m e r g e d 网【2 l 】、e r c n ( e x t e n d e d r e s o u r c ec o n t r o ln e t s ) m e r g e d 网田】、s 4 p k ( s y s t e mo f s e q u e n t i a ls y s t e m sw i t hs h a r e d r e s o u r c e s ) t 2 3 】，g s y s t e m 2 4 】，w n s r ( w o r k f l o wn e t sw i t hs h a r e dr e s o u r c e s ) 1 2 5 1 。其中， 4 s 3 p r 是学者们研究柔性制造系统死锁问题时较常用的模型【1 1 2 2 9 1 ，本文的研究 工作也是基于s 3 p r 网的。 针对含有共享资源的柔性制造系统p e t r i 网模型，z h o u 和d i c e a r e l 3 0 1 提出了 顺序相互抑制和并行相互抑制的概念，并根据制造系统物理设备的特性将柔性制 造系统p e t r i 网模型中的库所分为三类：a 类工序库所，b 类固定资源库所( 如 机器人，机床等) 和c 类可变资源库所( 如工件，托盘等) 。在z h o u 等的框架 里，死锁是运用预防的方法来解决的。他们研究保证系统活性的条件并将这些条 件表征为b 类库所和c 类库所的初始标识关系，然后通过为系统添加缓冲模块 或控制库所，以及限制进入系统的待加工工件数目等方法来保证网系统是活的、 有界的和可逆的。z h o u 和d i c e a r e 的研究工作被视为基于p e t r i 网理论的柔性制 造系统死锁预防方法的首创工作，此后，z h o u ，j e n g ，z o u a r i 和b a r k a o u i 等针对 各种p e t r i 网模型的子类建立了系统活性的条件，逐渐形成了成熟的柔性制造系 统p e t r i 网建模的系统方法 2 4 - 2 5 3 1 - 3 4 。 s 3 p r 网是由e z p e l e t a 等在【1 9 中提出的一种用于柔性制造系统建模的一种 p e t r i 网的子类，其特点是每一个工序只需要一种资源的参与，一个资源不能连 续参与两个工序的加工。e z p e l e t a 等研究了这类网系统中信标和死锁之间的关系， 指出严格极小信标的存在是导致s 3 p r 网死锁的原因，即一个存在死锁的s 3 p r 网中必然存在可被清空的信标。对此，e z p e l e t a 等提出了相应的基于严格极小信 标的死锁控制策略。这种控制策略首先求出p e t r i 网模型中的全部严格极小信标， 然后对每个严格极小信标分别设计控制库所，最终得到保证p e 仃i 网活性受控的 控制器。e z p e l e t a 等的死锁预防控制策略成功的分离了柔性制造系统模型和添加 到系统中的活性控制器，使得两者之间有了清晰的界限，因而被认为是死锁预防 方法中的经典之作。然而，这种死锁控制方法存在着行为许可性、结构复杂性和 计算复杂性这三个性能指标方面的不足 3 5 】。 基于信标的死锁控制器设计方法通常需要求解p e t r i 网中所有严格极小信 标，但p e t r i 网中信标的求解存在其固有复杂性。目前为止，c h u 和x i e 提出的 基于混合整数规划( m i x e di n t e g e rp r o g r a m m i n g ，m i p ) 【1 6 】的信标求解方法是最 高效的求解网系统中最大被清空信标的算法。这种方法是传统信标求解的数学规 划实现，能大大降低信标求解的计算复杂性。由于m i p 法求得的是网系统中的 一个最大被清空信标，而现行的死锁控制策略往往关心的是极小信标。h u a n g 等 【3 6 】基于c h u 和x i e 的方法给出了一种从一个最大被清空信标中提取出一个极小 信标的算法，但h u a n g 等的算法存在明显的缺陷，主要表现在这个算法既没有 明确的给出提取出来的极小信标中含有哪些库所，而且该算法会进入到一个死循 环的状态。l i 和l i u 在 3 7 】中修正了h u a n g 等的算法，但他们的算法也同样存 在缺点，即一次只能从一个最大被清空信标中提取取出一个极小信标。w a n g 等 在【3 8 】中提出了一种基于树的提取极小信标的方法，这种方法能够一次从一个最 大被清空信标中提取出全部的极小信标，但这种方法要借助树的形式来判断，且 没有推广到整个网系统。c o r d o n e 等【3 9 1 基于极小信标的性质将一个p e t r i 网分解 成子网，然后通过求解子网的极小信标来得到原网的极小信标。这种方法能够成 功的提取出一个给定的p e t r i 网中的所有极小信标。 为了解决f 1 9 1 中控制策略的计算复杂性和行为许可性方面的问题，h u a n g 等 【2 8 】针对s 3 p r 网提出了一种基于m i p 法的迭代来设计p e t r i 网活性控制器的方法。 h u a n g 等的方法在迭代的每一步先通过m i p 法求取网系统中的一个最大被清空 信标，然后从得到的这个最大被清空信标中提取出一个极小信标并为该极小信标 设计控制库所来保证其受控性。重复以上步骤直至使用m i p 法不能从网系统中 求取出一个最大被清空信标，即系统中不存在可被清空的信标。h u a n g 等的方法 能够有效降低求解活性控制器的的计算复杂性且得到的活性控制器具有更多的 许可行为，但在解决控制器的结构复杂性方面并没有明确的改善。 系统的柔性与系统拥有的许可行为密切相关，因此，行为许可性是衡量一个 活性p e t r i 网控制器性能的重要指标之一。u z a m 等【4 0 】基于区域理论1 4 1 4 2 】开创性 的提出了一种最优控制器的设计方法。基于u z a m 等的工作，g h a f f a r i 等 4 3 】给出 了最优控制器存在的线性代数不等式约束条件并给出了他们的最优控制器设计 方法。为了降低g h a f f a r i 方法的计算复杂度，l i 和z h o u 4 4 1 提出了一种将基于区 域理论控制的方法和基于信标控制的方法相结合的死锁预防策略。这种策略先应 用信标控制策略，减少一定量的状态变迁分离事例，然后应用区域理论求解信标 控制后剩下的状态变迁分离事例，最终可以得到最优的活性受控系统。l i 和z h o u 的方法较纯基于区域理论的控制策略而言在求解活性p e t r i 网控制器的计算复杂 性方面有很大的改善。 6 为了降低活性p e t r i 网控制器的结构复杂度，l i 和z h o u t 3 5 , 4 5 - 4 6 提出了p e t r i 网基本信标和从属信标的概念并指出设计控制器时只需对基本信标设计控制器， 从属信标可控性可以通过调整基本信标的控制深度变量实现。基本信标和从属信 标的求解可参考 4 7 5 0 1 。基本信标理论简化了p e t r i 网活性控制器的结构，但也 存在着不足之处，主要表现在基本信标的集合不是唯一的且在行为许可性方面有 待提高【2 4 】。基于基本信标理论，l i 等【5 1 】对s 3 p r 网设计了一种基于m i p 死锁检 测方法的迭代死锁预防策略。在迭代的每一步，这种方法先使用m i p 法找出一 个最大被清空信标并从中提取出一个极小信标，然后判断该极小信标是否是基本 信标：若是基本信标，则对其进行显式控制；反之，则判断其可控性来确定是否 需要对其进行显式控制。这种方法改善了求取活性控制器的计算复杂度，但行为 许可性仍然没有明显提高。此后，l i 2 9 1 ，w a n g 5 2 】等对l i 和z h o u 等的方法提出 了进一步的改进，并得到行为许可性得到明显改善且结构较为简单的活性控制 器。 p e t r i 网活性控制器中冗余控制库所的存在使得系统具有结构复杂性的同时 也限制了受控系统行为许可性，如何剔除系统中的冗余控制库所有着重要的研究 意义。u z a m 等在 5 3 q b j ：足出了一种判别和剔除冗余控制器的算法，这种算法通 过检验移去一个控制库所的后得到的系统是否仍然是活性受控的来判断移去的 这个控制库所是否是冗余库所。这种方法能够有效的降低添加的控制器的数量， 但是其剔除冗余控制库所的数目按照不同的检测顺序具有随机性，且不能保证能 够剔除最大数目的冗余控制库所。此外，u z a m 的算法测试控制库所的冗余性需 要进行两次冗余性测试，因此在计算复杂度上亟需改进。 g a r c i a 等在 5 4 q b 给出了隐式库所的定义：隐式库所在一个p e t r i 网中存在与 否并不影响网系统的行为，从网系统来看，它们是冗余的。从隐式库所的定义可 知隐式库所的剔除保持了网系统的无死锁性和活性。l i 等【5 5 】基于g a r c i a 等给出 的隐式库所的定义提出了一种通过求解线性规划问题的方法来确定系统中的一 个控制库所是否为隐式库所的算法。l i 等方法对系统中的每一个控制库所通过 求解其满足一组线性不等式的最优解来判断其是否是隐式库所，可以在多项式时 间内完成，而且剔除隐式库所后的系统具有更多的许可性为。但是这种方法对每 个库所在求解过程中都需要操作其关联矩阵，当网规模很大时候计算复杂度将会 很高。 l i 等在【5 5 】中还考虑了一种剔除活性受限库所的算法。一个活性受限库所不 一定是隐式库所，但它的剔除同样不改变系统的活性，这表明活性受限控制库所 对于网系统来说也是冗余的控制库所。此外，剔除一个活性受限库所可能改变受 控系统的行为但网系统的活性性质不变。因此，理论上可能会使受控系统具有更 多的许可行为。l i 等的提出检测活性受限库所的方法是基于m i p 法进行的，通 过计算剔除一个控制库所后系统中有标识的库所数是否等于为剔除前系统中的 有标识的库所总数减1 来判断该控制库所是否是活性受限库所。若剔除的控制库 所是活性受限库所，它的剔除不会改变原网没有空信标的性质。 综上所述，现有的死锁预防策略大多采用对目标p e t r i 网模型添加控制库所 的方法，存在的主要问题是行为许可性、计算复杂性和结构复杂性这三个方面只 能解决其一或者是对已有成果的改进，还有很多问题有待于进一步的解决。本文 针对基于p e t r i 网的柔性制造系统，研究其剔除冗余控制库所的方法以及如何设 计优化控制器的问题，使p e t r i 网控制器在满足活性的前提下能以较低的计算复 杂性、较简单的结构以及较少的资源来得到较多的许可行为。 1 3 本文的主要研究内容 本文的研究基于s 3 p r 网，围绕如何剔除冗余控制库所和设计性能更优的活 性控制器展开。全文共分为五章，具体结构和各章内容简述如下： 第2 章主要介绍p e t r i 的基本理论，包括p e t r i 网的结构定义，基本性质等， 以及现有的一些经典的死锁预防策略，为随后的章节作理论的铺垫。 第3 章的研究工作主要围绕剔除现有的基于信标的活性p e t r i 网控制器中的冗 余控制库所展开。首先介绍了u z a m 的剔除冗余控制库所的算法，然后针对s 3 p r 网，分析了基于信标的控制器设计原理，结合信标组合理论给出了一种简单直观 的基于信标资源数目排序的冗余控制库所剔除算法。最后通过一个柔性制造系统 实例说明本文提出的算法的应用并将其与u z a m 算法作了比较。 第4 章主要研究优化控制器的设计方法。首先给出优化的活性p e t r i 网控制器 和必需控制库所的定义，然后给出了提取一组必需控制库所的算法，并基于提取 必需控制库所的算法给出了优化控制器的设计方法。最后通过两个柔性制造系统 的实例说明了这个算法的应用并将其同现有的一些方法相比较，给出了行为许可 性方面的比较结果。 第5 章总结全文，并展望未来的研究工作。 1 4 本章小结 本章首先介绍了基于p e t r i 网的柔性制造系统网简化技术的研究背景和研究 意义，然后给出了死锁产生的四个必要条件并概述了现有的基于p e t r i 网理论的 三种系统死锁控制策略，重点综述了基于死锁预防的控制策略以及柔性制造系统 网简化的研究内容及研究方法，最后阐述了本文的研究内容和创新点。 9 2p e t r i 网基本理论 本章介绍p e t r i 网理论的基本定义和基本性质，以及现有的一些基于p e t r i 网 的死锁控制策略。 一7 2 1p e t r i 网的基本定义和概念 1 1 , 1 7 , 1 9 , 络5 7 】 2 1 1p e t r i 网的结构定义 定义2 1 一个p e t r i 网是一个四元组= 妒，ze 叨，p 为库所的集合，丁为变 迁的集合。p 和丁有限，非空且互不相交。f c ( 尸x 乃u ( t x p ) 称为流关系，是一 个p e t r i 网中所有有向弧的集合，其中p 卜川可是由尸指向丁的有向弧，弘m 是由丁指向尸的有向弧，n = 0 ，1 ，2 ，) 。矽：( p du ( t x p ) _ n 是一个映射， 该映射为网系统中的每条有向弧分配一个权值：若厂b 则w q ) o ；反之， w q ) = 0 。称形为p e t r i 网的权函数。 从图论的角度讲，p e t r i 网是一种包含库所和变迁这两类节点的双枝有向图， 库所和变迁分别由圆圈和矩形表示，它们之间用有向弧连接，同一类型的节点之 间不能用有向弧连接。 定义2 2 若v f f ，w q ) = 1 ，则p e t r i 网n = ( 尸，le 叻称为普通网。否则，n 称为一般网。一个普通p e t r i 网可记着= ( 尸，ld 。 定义2 3x pu 丁是p e t r i 网= 妒，le 叨中的节点。称k = t y pu t i ，功 毋为x 的前置集，称，= t y put i ，力毋为x 的后置集。 一个库所的后置变迁称为它的输出变迁，而该库所的的前置变迁称为它的输 入变迁。相同的，一个变迁的后置库所称为它的输入库所，而该变迁的后置库所 称为它的输出库所。 定义2 4 令= ( 尸，正只叻是一个p e t r i 网，称映射胍p _ n 为= ( 尸，兀只叨 的标识。 库所中的标识称之为托肯，用小黑点表示。当库所中托肯的数目比较大时， 可以直接用数字表示。一个p e t r i 网的初始标识用m o 表示，称( ，m o ) 为网系 统或标识网。( ，m o ) 有时也可以记着( p ，正只形m o ) 。 定义2 5 令p p 是p e t r i 网= ( 尸，瓦e 聊中的一个库所。称库所p 在m 下是 l o 被标记的当且仅当朋) 0 。令d 尸是中的一个库所子集，称d 在m 下是 被标记的当且仅当d 中至少有一个库所被标记。称拟d ) = 匕删p ) 为库所子集 d 在m 下的托肯数总和。 定义2 6 令n = ( p ，te 叻是一个p e t r i 网，称变迁t 在标识m 下是使能的 ( e n a b l e ) 当且仅当跏。r ，m ( p ) z e ( p ，f ) ，记为m p 。使能的变迁可以发射。 在标识m 下变迁t 发射后，网系统跃迁到另外一个状态，产生一个新的标识m ， 使得跏尸，mp ) = 朋p ) w ( p ，d + 职r ，力，记着m p m 。称标识m 是从脑可达 的当且仅当存在一个变迁的发射序列盯= t l ，t 2 ，t n 和标识m ，m 2 ，使得 m j 【如 尬【炉【矗 m ，成立。 定义2 7 令( m o ) 是一个p e t r i 网，是其初始标识。称从可达的所有标识 的集合为( ，m o ) 的可达集，记着r m o ) 。 定义2 8 令( ，尬) 是一个p e t r i 网，n = ( 只z 只叨。称t et 是活的( 1 i v e ) 当且 仅当v m e r ( n , m o ) ，j r ( ，胸， p 。称在初始标识下是死的( d e a d ) 当且仅当不存在t nm o t 成立。称( ，m o ) 是无死锁的( d e a d l o c k - f r e e ) 或者 弱活的( w e a k l yl i v e ) 当且仅当v m e r ( n , m o ) ，3 t e t , m 伊。称( ，m o ) 是活的当 且仅当v t e t , f 在下是活的。称，t 在下是准活的( q u a s i 1 i v e ) 当且仅 当jm e 尺m o ) ，使得m p 。称( ，m o ) 是准活的当且仅v t e t , t 在下脑是准 活的。称( ，舰) 是有界的当且仅当j 七矿，v m er ( ，m o ) ，3 p e p ，使得肠) s k 成立。 例2 1 如图2 1 所示是表征p e t r i 网性质的四个简单示例。 能 ( a ) 死的 ( b ) 活的、无界 黜 ( c ) 活的，有界 ( d ) 无死锁，有界 图2 1p e t r i 网性质的简单示例 在图2 1 所示的四个p e t r i 网中：( a ) 中p e t r i 网的所有变迁均为非使能的，所 以这个p e t r i 网是死的。) 中的p e t r i 网是活的，但这个p e t r i 网中存在着这样的 一个变迁，该变迁的发射从它的输入库所移去一个托肯，而往它的输入库所移入 2 个托肯，因此该网是一个无界p e t r i 网。( c ) 中的p e t r i