（管理科学与工程专业论文）petri网在fms中的若干应用研究.pdf

摘要 中文摘要 柔性制造系统( f m s ) 是一种典型的离散事件动态系统( d e d s ) 。本文对p e t r i 网在其中的若干应用问题进行了较深入的研究。首先，对p e t r i 网在f m s 中的建模理 论与方法做了一个较全面的综述。在前人启发式调度算法的基础上，通过在网中引入 资源成本的概念，在算法的执行过程中综合考虑时间成本和资源成本，实现了资源成 本与时间成本的多目标调度：通过在算法中对各机器虚成本的跟踪，动态增加当前系 统中负载较大机器的使用成本，降低其再被使用的机会，使得调度结果中的各机器负 载能相对均衡。调度算法均用c 语言实现，并经实例验证。最后运用c p n 仿真工具 ( c p n t o o l s ) 对一个柔性制造单元进行了仿真研究，找出了其中物流策略的不当之处 并提出改进方法。 关键字：f m sp e t r i 调度仿真 a b s t r a c t a b s t r a c t f m si sat y p i c a ld e d s t h i sp a p e rm a k e sai n d e p t hs t u d yo fs o m ea p p l i c a t i o n so f p e t r in e ti ni t f i r s t ，ag e n e r a ls u r v e ya b o u tt h em o d e l i n gt h e o r ya n dm e t h o do fp e t r in e t f o rf m si s g i v e n b a s e d o n p r e v i o u s h e u r i s t i c s c h e d u l i n ga l g o r i t h m s ，m u l t i o b j e c t s c h e d u l i n go f t i m ea n dr e s o u r c ec o s t si s i m p l e m e n t e db yi n t r o d u c i n gt h ec o n c e p t i o n o f r e s o u r c ec o s t si n t ot h en e t ，c o n s i d e r i n gt i m ea n dr e s o u r c ec o s ts y n t h e t i c a l l yi nt h ep r o c e s s b yt r a c i n gt h e v i r t u a lc o s to fm a c h i n e si nt h ea l g o r i t h m ，t h eu s i n gc o s t so ft h o s eh e a v yl o a d m a c h i n e sa r ei n c r e a s e dd y n a m i c a l l ya n dt h e i rc h a n c e so fb e i n gu s e da g a i na r er e d u c e d w h i c hr e s u l t si nar e l a t i v eb a l a n c eo fm a c h i n e sl o a d si nt h es c h e d u l i n gr e s u l t a i lt h e s e a l g o r i t h m sa r ei m p l e m e n t e d i nca n dv e r i f i e db ye x a m p l e s a tl a s t ，ac p ns i m u l a t i o n t o o l ( c p n t o o l s ) i su s e dt os i m u l a t eaf m c s o m e f a u l t so fi t sl o g i s t i cs t r a t e g i e sa r ef o u n d a n di m p r o v i n gm e t h o d sa r ep r o p o s e d k e y w o r d s ：f m sp e t r i s c h e d u l i n g s i m u l a t i o n 第一章绪论 第一章绪论 1 1 柔性制造系统( f m s ) 1 1 1f m s 出现的历史条件和意义5 8 随着科学技术的发展利多品种、小批量自动化生产的需要，柔性制造系统( f m s ) 已经越来越受到人们的重视。f m s 涉及的领域包括机床、电予技术、液压传动、机器 人技术、计算机技术以及系统工程等众多领域，它是一种集多种高新技术于一体的现 代化制造系统，是c i m s 不可缺少的重要的制造单元。 在2 0 世纪3 0 旬j 代到2 0 世纪5 0 年代，对于大批量、少品种的牛产情况，一般采 用自动流水线制造设备包括物流设备和相对固定的加工工艺，这可称为刚性自动化 方式。自动流水线设备的价格通常相当昂贵，设备固定，不灵活，只能加工几个指定 工件。追求高生产枣，是选择自动流水线的主要依据。 到了2 0 世纪6 0 年代，当国外大多数大批量生产的工厂已经实现自动化后，人们 意识到大批量生产只是机械制造业的- - 4 部分，只占1 5 一2 5 的比重，而中、小批 量生产却占7 5 - - 8 5 。在国民经济生产部门中比重占绝对优势的多品种、小批量牛 产企业的劳动生产率极大的落后于大批量生产企业。同时随着国际贸易发展和技术交 流的发展，跨国产品和出口产品在生产中的比重大为增加。对于小批量、多品种的情 况，一般可采用单台数控机床，它具有灵活加工一族产品系列的能力。从一种类型的 工件转换到另一种类型的工件，不需要改变机床硬件，仅需要改变控制程序及夹具利 刀具。n c 程序是n c 机床的控制逻辑，表示为指令和加工步骤。用n c 机床加工产 品生产率低、成本高。其优点是灵活性较大。 对于中等批量、中等规模品种的生产情况，需要考虑一个折中方案。在金属品制 造中，这种生产情况是最主要的。根据美国统计资料，这类情况在金属加工工业中占 7 5 。因此，如何解决这种情况下的制造问题，对金属加工工业来说是十分关键的。 如果采用以上两种较为传统的生产方式，将会产生如下一系列不利因素： 1 ) 机床利用率太低。 2 ) 加工时间增长。 3 ) 中间缓冲库存增大。 4 ) 刀具利用率太低。 p e t r i 网在f m s 中的若干应用研究 5 ) 车间空降利用牢太低等。 这些都将导致成本的体高。所以要求人们寻找新的制造原理和生产方式，以解决 制造工业面临的新问题。思索和创造具有应变性好和生产效率高的制造系统就成为一 项迫切的任务。 从2 0 世纪6 0 年代开始到2 0 世纪7 0 年代，计算机技术得到了飞速的发展。计算 机控制的数控机床( c n c 机床) 在自动化领域中取代了机械式或液压式的自动机床。 在c n c 机床上，只要改变程序就可以加工新的工件，处理加工对象的灵活性很大， 而所需调整的时间却很少，它为柔性制造系统打下了很好的摹础。于是近十年来，人 们把自动化生产技术的发展重点转移到中、小批量生产领域。结合自动流水线与n c 机床的特点，将n c 机床与物料输送设备通过计算机联系起来，形成一个系统，来解 决中等批量、中等规模品种以及小批量生产领域的问题，就形成了所谓的“柔性制造 系统”。 f m s 的首创者是美国m a a l r o s e 公司，它于1 9 6 3 年制造了世界上第一条加工 多种柴油机工件的数控自动线。1 9 6 7 年英国m o l i nc o 公布“系统2 4 ”( m o l i n ss y s t e m - - 2 4 ) ，用计算机分散控制加工设备，每天工作2 4 小时，使f m s 的思想正式形成。 随着科学技术的迅速发展，新产品不断涌现，产品的复杂程度也随之增加，而产 品的市场寿命随之缩短，更新换代加速，中、小批量生产占有越来越重要的地位。面 临这一新的局面，必须大幅度提高柔性和生产效率缩短生产周期。保证产品质量， 降低能耗，从而降低生产成本，以获得更好的经济效益。柔性制造系统正是在这种形 式下应运而生的。 柔性制造系统的主要优点是：系统自动化程度高，可以减少机床操作人员。由于 配有质量检测和反馈控制装置，零件的加工质量很高。工序集中，可以有效减少生产 面积。与立体仓库相配合，可以实现2 4 小时连续工作。由于集中作业，可以减少加 工时间，易于和管理信息系统( m a n a g e m e n t i n f o r m a t i o ns y s t e m m i s ) ，技术信息系统 ( t e c h n i c a li n f o r m a t i o n s y s t e m t i s ) 及质量信息系统( q u a l i t yi n f o r m a t i o ns y s t e m q i s ) 结合形成更高级的自动化制造系统。 f m s 的发展来自于两方面的推动；市场竞争和技术进步。由于f m s 具有传统流 水生产线的高效率和单件作业车间的柔性，因此，特别适合用于多品种中，小批量产 品的生产。对于这一类产品的生产，f m s 能以较高的设备利用率，较低的生产成本， 较高的加工质量和较短的生产周期等特点适应快速变化和竞争激烈的市场需求。目 前，f m s 的发展已普遍受到各个工业化国家的高度重视。我国也己将f m s 的研究， 开发和应用列为国家重点攻关项目。 第章绪论 2 f m s 的定义 尽筒大家都对柔性制造系统感兴趣，但对它的定义却一直还没有达成一致。f m s 与传统的制造系统的主要差别就在于“柔性”。可是柔性本身就没有一个明确的定义。 f m s 一个最常见的定义：是r a n k y 2 m 作出的，他把f m s 定义为：“个关于高级分布式数 据处胖和自动物料流的系统，其中包括有计算机控制的机器、组装单元、工业机器人， 监视机器等等，以及计算机集成的物料处理和存储系统。” 一个柔性制造系统( f m s ) 一般由四部分组成】：两台以上的数控j 3 n t 设备，一 个自动化的物料及川具储运系统。若干台辅助设备( 如清洗机，测量机，摊屑装置， 冷却润渭装置等) 和一个由多级计算机组成的控制和符理系统。到目前为止，柔性制 造系统是最复杂自动化程度最高的单一性质的制造系统。柔性制造系统g , l 一般包括 两类不同性质的运动，一类是系统的信息流，另一类是系统的物料流，物料流受信息 流的控制。 3f m s 的特点 在柔性制造系统中数控机床由计算机来控制，工件由机器人来搬运：成品由a g v 小车来运到目的地。并采用了列具库和自动换刀系统，每当出现产品的工程或设计改 变时，它们将被合成到计算机程序或数据库中。 柔性制造系统是一种典型的离散事件动态系统( d e d s ) ，具有如下特点f 2 8 j ： ( 1 ) d e d s 的状态只能在离散事件点上发生跃变，在d e d s 中，状态演化是 由事件驱动的，即仅在驱动事件发生的瞬时，状态才能出现跃变，其它时刻则 保持不变，这是种固有的不连续性。f m s 状态的改变只有在特定的操作( 原 料到位、加工完成、机器就绪等等) 完成时才能够发生。 ( 2 ) d e d s 的状态变化具有异步性和并发性。在d e d s 中，由系统固有离散 性决定，演化过程中状态发生跃变时刻呈现异步性，在时间轴上状态跃变时刻 是异步的排列的。此外，一个离散事件的发生，可能会使状态变化呈现出并发 性。即同时导致些乃至全部状态变量的跃变。在f m s 中，如果满足资源约束， 对于不同工件的不同工作就可能同时进行，它们之间就有异步性和并发性。 ( 3 ) 实际d e d s 的状态变化往往呈现出不确定性。在d e d s 中，离散事件同 时受着状态内部和外部因素的约束，这些因素严格的说总是会包含某种不确定 性的，由此导致系统状态变化呈现出不确定性。在f m s 中，一个工件可以通过 不同的加工路径来完成，其中包含了多种不同的资源组合方式。 p e t r i 网在f m s 中的若干应用研究 ( 4 ) d e d s 服从的是人为的逻辑规则，而不是物理学定律及其衍生物，d e d s 通常不能采用传统的微分方程或差分方程来描述。f m s 的运行和控制遵守的当然是人 们所制定的那些规则，而不是一些物理学定律。 因为具有着以上特征，f m s 是一种非常复杂的系统，单纯将f m s 的硬件设备合 理的组成一个系统并不一定就能取得效果，在实践中，还必须以有效地系统运行管 理措施予以保证。f m s 的运行僻理是通过f m s 的计算机控制软件系统实现的，控制 软件的核心是f m s 生产计划与调度理论和决策技术。f m s 的运行管理从本质上是在 系统信息集成的基础上，制定出使f m s 能以最优方式运行的若干决策。 1 2 问题的提出 随着科学技术的迅速发展，新产品不断涌现，产品的复杂程度也随之增加，而产 品的市场寿命随之缩短，更新换代加速，中、小批量生产占有越来越重要的地位。面 临这一新的局面，企业必须大幅度提高柔性和生产效率，缩短生产周期，保证产品质 量，降低能耗，从而降低生产成本，以获得更好的经济效益。而f m s 正是我们达到 这一目标的有力工具。它能在保持对车间配置不做大的调整的情况下，通过给数控机 床安装不同软件s u j j 具的办法，实现多品种工件加工间的快速切换。但是，由于f m s 的复杂性，要充分发挥它们的性能，创造出应有的经济效益，必须要有一个很有效的 管理控制系统来对其进行控制，而这样一个控制系统软件的开发是离不开对f m s 本 身进行仔细分析和充分了解的。f m s 从本质上来说是一种典型的离散事件动态系统 ( d e d s ) ，符合离散事件系统的许多特征。有其固有的很多复杂特性，比如说加工路 径柔性、机器资源共享、缓冲资源有限、操作并行、对特定资源的争夺导致的冲突、 工序之间的优先级别以及潜在的死锁情况等等。我们用传统方法分析起来比较困难， 因为对于很多系统特性，传统方法如数学规划等，根本没法精确的表示出来，也就是 说光是给系统建立一个贴切的模型就已经是相当困难的事情了，更不用说对系统的性 能进行分析。因此我们借助那些d e d s 的专用分析方法来进行研究，而在这些方法中 p e t r i 网以其简单直观的图形界面，坚实深厚的数学基础，丰富多样的分析方法，众多 的支持工具而受到越来越多学者和工程技术人员的青睐，是一种相当有前景的方法， 所以本文选用p e t r i 网来对f m s 进行分析。 第一章绪论 1 3 国内外研究状况 f m s 是一种典型的d e d s 系统，对于d e d s 的研究一直属于学术界的一个前沿问 题，人们尝试用各种方法来进行。常见的研究方法有【3 0 】：正规语言与自动机( f o r m a l l a n g u a g ea n da u t o m a t a ) ；极大一加代数法( m a x p l u sa l g e b r a ) ：排队论( q u e u i n gt h e o r y ) ； 算术与布尔函数法( a t i t h m e t i ca n db o o l e a nf u n c t i o n s ) ；马尔可夫链( m a r k o vc h a i n ) ；摄 动分析( p e r t u r b a t i o na n a l y s i s ) ；p e t r i 网方法等。出于篇i 旧的考虑，在此我们不对其 一一进行介绍。由于p e t r i 网能准确的反映系统中的并行、冲突、竞争、死锁等行为， 并能直接在模型基础上通过托肯的流动来研究系统的动态性能，具有很多其它方法所 无法比拟的长处，因此它被广泛应用到各种d e d s 的研究当中，近几十年来受到各国学 者的重视，得到了较大的发展。具体至1 p e t r i 网在f m s 中的应用，国内外的学者也做了 不少的研究工作。根据研究的e 1 的和方法之不同，研究工作分成了一些不同的方向， 下面我们就其中的一些主要方向做一个简单的介绍。 3 1 对于建模工具的研究 要在系统中应用p e t r i 网，首要的任务当然是要先建立起系统的p e t r i 网模型。可 以这么说，对p e t r i 网在f m s 中应用的研究工作就是从用p e t r i 网对制造系统的建模研 究开始的。众所周知，复杂性问题一直是p e t r i 网应用的一个不利之处。也就是说， 当实际系统的规模中等或较大时，用普通方法得到的p e t r i 网模型都会大( 网中的节 点太多) 到难以分析。即问题的状态空间会随着网中节点的增多而呈指数级的增长， 出现所渭的“组合爆炸”。因此人们一直致力于p n 对f m s 系统建模方法的研究，其 目的是找出一类适合于工程应用的特殊子网( 其中很大一部分都是基于状态机而提出 ) 及其建模方法，能使得对某类特殊工程问题的建模和分析得到简化，这方面的研 究主要有：j e z p e l e t a i ”蝽提出的s 3 p r 网，m d j e n g t 6 l 等提出的r c n s 网，z h o u 7 】等 提出的一类共享资源系统，a r e y e s 【5 儿”1 等提出的b 一网。i b a b d a l l a h l 2 1 ，【3 1 等提出的s 4 尺 网等等。此类方法的共同特征是：针对某一类特殊问题提出一种满足某些约束条件的 子网，通过较严格的数学证明来保证用这类子网构建起来的系统模型能具有某些我们 所希望的性质，比如说无死锁、安全、有界、可逆等等。然而这些方法的局限性也是 很明显的，因为各种予网都是针对某一类较理想的工程问题提出的，需要系统满足很 多假设条件，当实际系统不满足这些假设条件时，这些方法的实用性就值得怀疑。当 然，到目前为止也没有人开发出能适合各种工程问题的p n 建模方法和简单有效的分 p e t r i 网在f m s 中的若干应用研究 析方法。因此，对于这方面的研究还是要继续进行下去。 1 3 1 对于合成方法的研究 各类有着特殊性质的了网只是构建整体模型的小部件，要让这些小部件和谐的工 作在一起，必须要有一定建模方法论的支撑，这就是对各种p n 模块的合成方法的研 究。其中比较重要的有a g e r w a l a 和c h o e d a m p h a i ，k r o g h 和b e c k 【8 】【9 1 等研究的自下 而上法，为每个r 系统单独建模。此时不考虑予系统间的相瓦作用。在每一个合成步， 通过融合这些了系统间的公用的库所和或变迁来将相应予系统结台成一个较大的了 系统。对每一步合成后的了系统立即进行分析，这样对最终结果的分析就得到简化了。 当合成完成后，我们就得到了撮终系统以及它的一些重要性质。v a l e t t e ，m u r a t a ，k o h 1 等提出或改进的自上而下法则一般从一个系统的总体模型开始，忽略具体底层的细 节。然后再一步一步的对模型进行细化，最终得到所需结果。库所扩展和变迁扩展是 两种常用的细化方法。该方法的优点就在于建模是从对系统的一个全局观点开始的。 而且很多学者的一些方法能够保证在细化过程中不丢失系统的一些重要特性，使得我 们可以简化甚至省略对最后模型的分析。z h o u i ”l ij 等提出的混合合成方法，使得我 们在建立系统模型时能够渐进的引入建模的细节部分，对系统的复杂度能够有所把 握。该方法在建模过程中能够保证最终模型的一些重要性质，从而使我们省去了对于 有界性、活性以及可逆性等的复杂的数学分析。 1 3 2 对于模型分析方法的研究 在正确建模理论的指导下，根据系统的特性建立起来的模型能够较准确的反映系 统的一些性能。因此，我们就可以通过对模型的分析来检查真实系统的相应性能，比 如说通过对模型有界性的检查来看系统是否会出现缓冲区溢出现象；通过对模型活性 的检查来看系统能否完成我们所设计各种操作：通过对导致死锁的变迁序列的分析来 看系统的何种操作过程会导致系统停止运行，如何来解决之等等。因而，对系统p n 模型的各种分析方法也就成了学者们研究的一个内容。在模型的分析方法上，可达图 ”3 1 方法是比较成熟的一种，通过构造系统完整的可达图，也就是把系统各种可 能出现的标志及其之间的关系都列举出来，我们可以很清楚的知道系统的任何特性和 行为，但是，对于中等以上规模的系统，要构造其可达图也不是一件很简单的事情， 因为系统的状态节点太多，要花费大量的计算时间。为此，引发了人们对p n 的简化 和分解方法的研究，如g b e r t h e l o t 和r t e r r a t ，g b e r t h e l o t 和r t e r r a 1 4 1 , 提出的转化 第一。章绪论 规则：l e e 和j f a v r e l 5 1 等提出的阶层化简化方法，j c ，m u g a r z a ，和h c a m u s 6 埂出的 利用转化规则来降低p n 调度问题的计算复杂性。这些方法都能保证系统在经过一次 或数次的简化后仍然保留活性、有界等系统特性，为我们分析复杂系统提供了方便。 另一种分析方法就是基于系统矩阵方程的方法，如j h 。l i u 2 0 1 ，y j s o n g 2 。1 等提出的通 过变迁矩阵来分析p n 模型等等。 1 3 3 对于调度方法的研究 利用p e t r i 网来对f m s 进行调度也是研究的一个重点，从最开始用于对调度方法 的测试 1 1 ，到后来通过p e t r i 网直接牛成调度方案，其中较有影响的有l e e 和 f d i c e s a r e 】的工作，他们把p e t r i 网和a + 算法相结合，利用肩发函数来控制对p e t r i 网状态兰；兰间的搜索范围，从而能在可接收的时间内生成较小系统的调度方案。 不过他们的方法因为算法较简单，且扁发函数不能充分利用p e t r i 网中的信息， 效率有限，对于节点更多的系统就很难在合理的时间内给出结果，因此很多学者继续 对这种方法进行扩展，工作从两个方面进行：一是开发出更有效率的启发函数，如 a r e y e s 5 i ，【3 3 1 等提出的基于r c r ( r e s o u r c ec o s tt e a c h a b i l i t y ) 矩阵的启发函数，m u d j 【4 1 【4 0 等提出的基于p n 的结构和动态性的肩发函数等，通过实例计算的结果都表明，一个 较好的启发函数能够较大的减少算法对p n 状态空间的搜索，提高算法的效率。 另一个方面就是对算法本身进行改进，比如h h x i o n g j s l 提出的将最好一优先的 启发式算法和受控回溯策略结合起来的混合搜索算法，使得我们能在最优化和搜索效 率上取得一个折中；还有t h s u n ”肄提出的有限扩展a 算法即在a 算法的基础上 通过对o p e n 列表长度的限定来控制算法的搜索空间，这样，虽然有可能丢失最优解， 但却能提高算法的搜索效率；y w k i m ”】等提出的将r t a ( 实时。算法) 和一个监 视器结合在一起的快速搜索算法，能通过监视器来改善r t a 所找到结果的质量； b c d a m a s c e n o 2 4 等则提出了一种利用动态规划方法结合启发式算法来实现一类无死 锁调度的方法，其中还用到了模拟退火等算法：为了能处理如半导体工业中的生产调 度等复杂的调度问题，很多学者研究利用c p n 和各种搜索算法相结合来产生最优调 度，如j p r e d d y l 3 2 】等提出的利用p n 和遗传算法相结合来产生对多模多资源约束的工 程调度问题；j h c h e n ”l 等运用遗传算法和c p n 来完成了对一个晶圆制造车间的建模 调度，取得了不错的效果：然而，当我们使用的工具越来越高级时，它们的开发成本 也随之增长，象这样复杂系统的开发工作，已经远非单独某一个科研人员可以胜任的 了。 p e t r i 网在f m s 巾的若干应用研究 1 3 4 对于仿真方法的研究 由于f m s 系统固所有的复杂性，以及p e t r i 网模型能通过直接运行来分析系统性 能这一特性开发基于各种p n 的汁算机仿真软件也成了一个研究的重要方向。使用 一个合适的专用仿真软件，能为我们省去很多不必要的重复工作，极大的提高我们的 效率。人们开发出来了各种各样的工具，从简单的t p n 仿真工具。到稍复杂的g s p n 仿真工具如t r i v e d i 等开发的s p n p 【3 4 】，l i n d e m a n n 等开发的d s p n e x p r e s s t ”1 等等：直 到各种功能强大的c p n 仿真工具平台，如t c p n t 妨】，d e s i g n c p n i ”1 等等。对于很多 的p n 工具d a i m i 大学的网站上都有专门的收集，其中很多都是免费软件，网站上还 有专门的邮件列表，供人们交流经验【3 8 1 。 以卜是本人在作论文期间所接触到的一些研究方向，由于条件有限加上自身能力 的原因，难免挂一漏万，难以反映当前p n 在f m s 应用研究的全貌，希望后来者能在 此基础上进行总结。 1 4 本文工作和组织结构 本文研究的是p e t r i 网在f m s 中的若干应用问题，第二章首先介绍了p n 的一些 基本概念，特别是那些在制造系统中有重要意义的p n 性质；第三章较系统的综述了 p n 对f m s 的建模问题，从面向具体制造过程的一般表示方法和习惯，到对于较大规 模系统的建模方法论的研究，都是本章的工作：第四章主要研究了p e t r i 网在f m s 中 的调度问题，重点是放在肩发式算法上，提出并实现了考虑机器资源成本和负载均衡 的多目标调度方法；最后一章利用了c p n 仿真工具( c p n t o o i s ) 对一个小型制造单 元进行了仿真分析，解决了其物流策略不当的问题。 第二章p e t r i 网理论基础 9 第二章p e t r i 网理论基础 p e t r i 网( p n ) 最早由西德的c a r lap e t r i 博士于1 9 6 2 年在他的博士论文中提出 ，。文中采用一网络( 用其名命名为p n ) 来描述计算机系统事件之间的因果关系。 他的研究工作口l 起了美国应用科学研究所( a p p l i e d r e s e a r c hi n c ) 的信息系统理论项 目研究组的h o l t 及其他人的注意。他们的研究工作说明了p n 能够描述与分析并行 系统。这些有关p n 的研究工作也引起d e n n i s 教授领导的美国麻省理工学院m i t 计 算结构研究室的注意。后来，于7 0 年代初发表了若干有关p n 的博士论文及研究报 告。1 9 8 1 年p e t e r s o n 出版了第一部关于p n 的书，书中罗列了1 9 8 0 年前发表的大 部分有关p n 的论文。1 9 8 5 年第二部有关p n 的书由r e s i g 出版，书中总结了欧洲 有关p n 的研究工作并罗列了所发表的文章。如今p e t r i 网已被广泛的应用于科研研 究和工业生产当中。在计算机学科中，p e t r i 网被应用于线路设计网络胁议分析，软 件工程，人工智能，形式语义，操作系统，并行编译，数据管理等等；在工业中，p e t r i 网被广泛用于产品结构设计，生产线布局仿真，生产调度，工业监控系统的设计等等。 2 1p e t r i 网的概念 p e t r i 网是一种特殊的两分图，由库所( p l a c e ) 、变迁( t r a n s i t i o n ) 和其间的有向 弧( d i r e c t e d a r c ) 三种基本元素组成。在图形中，用圆圈表示库所，短线或小矩形框 表示变迁，用带箭头的线条表示有向弧。除了以上三种元素外，还在库所中加入可以 沿着有向弧流动的托肯用以表示系统的动态特性，托肯一般用实心的小黑点来表示。 形式化定义m ，【1 5 7 】【t s - 【2 9 】 【3 0 一个标记p e t r i 网是一个五元组z = ( p t ，i ，0 ，m ) ，其中： p = p l , 岛，。见l 为有限库所集，n 0 ； t = ，l ，f 。 为有限变迁集，j 0 ，且尸n t a ，e u t o ； 1 ：p t j n 输入函数定义从p 到t 的有向弧集，n = f 0 ，1 ，2 ，l ； 0 ：p t j n 输出函数，定义从t 到p 的有向弧集： m ：p j n 标记，它的第i 个元素表示第i 个库所中的托肯数。初始标识记为。 四元组( p ，t ，i ，0 ) 被称为p n 的结构，它定义了一个有向图结构。在库所 中加入托肯及托肯通过变迁的流动，使得我们可以描述和研究p n 的离散动态表现， 1 0 p e l r i 网在f m s 中的若干应用研究 因而对系统建模。i 和0 表示两个非负的 x s 矩阵。连接矩阵c = 0 - - i 。p n 也可以定 义为( p , t ，f ，w ，m ) 其中f 是 p x t ) u f7 p 的个子集，表示所有弧的集合。如果 z ( p ，t ) = k ( o ( p ，) = k ) ，那么就存在k 条从p 到t ( 从t 到p 的) 的有向弧。如果 z ( p ，f ) = o ( o ( p ，) = 0 ) 那表示从p 到t ( 从t 到p ) 没有弧连接。当k = l 时使用条有 向弧，当k ) l 时，使用k 条平行的弧，或更一般的，使用一条弧加上其权重作为标记。 当m ( p ) = j 1 时，我们把j 写在库所中以代替j 个黑点来表示托肯。 例1 ：一个标记p n 如图2 1 ，它的形式化描述如下： p = p t ，p z ，庙，只，t = t f ，f 2 ) ，( a ，f i ) = 4 ，i ( p i ，f 2 ) = 0 ； o ( p l ，1 t ) = o ，o ( p i ，f 2 ) = o ； i ( p 2 ，1 ) = 1 ，z ( p 2 ，2 ) = 0 ； o ( p 2 ，1 ) = o ，o ( p 2 ，2 ) = 1 ； ，( 协，f 1 ) = 0 ，( 岛，2 ) = i ； o ( p 3 ，t 。) = l ，o ( p 3 ，f 2 ) = 0 ； ，( 只，t j ) = 0 ，l ( p 4 ，f 2 ) = o ； ( ) ( 矶，t 。) = 0 ，o ( p 3 ，：) = 2 ； m = ( 4 10 0 ) 7 一厂吣 稿弋 o 图2 1 。一个简单的标记p n 输入输出函数用矩阵表示如下 关联矩阵 卜觚 0，o 2 一 睥 和 第二章p e t r i 网理论基础 c = o i 一4o i一1 o 2 00 通过这些描述，我们就可以知道一个p n 的所有基本信息。 2 2 p e t r i 网的运行规则 p e t r i 网本身一般仅能描述d e d s 的静态结构，系统的动态性能只能用系统标志的 变化来描述，而系统标志的变化是由托肯通过变迁的触发沿有向孤的流动而引起的。 变迁的触发遵守如卜| 的规则p 叫： 规则1 使能规则变迁t 是使能的，如果t 满足： ( 1 ) 对于t 的每一个输入库所p ，l ( t ) ，有m ( 只) ( 只，) 。 ( 2 ) 对于t 的每一个输出库所p ，o ( t ) ，有k ( p ，) m ( p ，) + ( f ，p ，) 。 ( 3 ) 对于t 的每个既为输入又为输出的库所b i ( t ) f l o ( t ) ，同时满足 上述两个关系式。 其中w 为有向弧权重，k 为库所容量，m 为库所中托肯数。 规则2 触发规则使能变迁触发后，完成如下操作： ( 1 ) 从t 的输入库所中减去托肯。 ( 2 )向t 的输出库所中加入托肯。 变化的托肯在数量上满足式( 2 1 ) 。 m ( p ) = m ( p ) 一w ( p ，f ) ，p ，o ) p 仁0 ( r ) ； m ( p ) + g ( t ，p ) ，p d ( ，) ，p 盛m ) ； ，。，、 ，( p ) 一( p ，f ) + ( f ，p ) ，p 1 ( 0 n o ( t ) ； 。2 + m ( p ) ， 其他 例2 ( 继续例1 ) ：在图2 2 ( a ) 中，由于m ( p i ) = 4 = ，( p j ，t 。) 及m ( 见) = 1 _ ，( n ，t ) ；所以 此时t 是使能的 p e t r i 网在f m s 叶1 的若干戍片j 研究 l a l p 。，弋广、 ( h o 粕 l f ； o 二 i j i m 雌t z j ，队 o d 刊。相 图2 2 例1 中p n 的演化 又r e ( p 3 ) = 0 m 。用r ( z ，m o ) 来表示所有从出发的可达 标志集合。可达性用于检测系统是否可以到达某个具有特定功能表现的特殊状态。它 是一个行为性质。 有界性和安全性： 给出一个p n z 和它的可达集r ，如果对一个库所p p 有 m ( p ) b ，v m r ( z ，m 。) ，其中b 为正整数，则称p 为b 一有界的。如果p 中每个库所 都是b 一有界的，则称z 为b 一有界的。安全性是有界性的一种特殊情况，当b = l 时， p e t r i 网在f m s 中的若干应用研究 有界性又称为安全性。这两个也是行为性性质。结构性的性质如下：如果对于 千意的 初始标志帆，z 对某些b 都是b 一有界的，那么称z 为结构性有界。 在制造系统中库所经常用来表示工件、刀具、托盘及自动引导小车的存储区域。 有界性用来确定建模系统中是否存在溢出情况。当库所用以表示一个操作时，其安全 性能保证控制器不会对一个正在进行的操作初始化，亦即不会往一个正在操作的机器 上装入新的工件，因为我们在建模时一般假设机器在同一时刻只能进行一个操作。当 一个离散制造系统被建模成一个排队系统时，有界性的概念经常用以说明系统的稳定 性。 守恒性： 对于一个p e t r i 网z = ( p ，t ，0 月b ) 如果存在一个向量 甜= ( d i ，鸭，q ，n q o ，i = 1 ，2 ，月，使得7 1 1 1 = 0 3 7 o ，v r ( z ，t o o ) 则称z 是关于 守恒的。如果甜= ( 1 ，1 ，1 ) f 或m ( p ) = ( b ) ，v m r ( z ，) ，则称z 为严格守恒 的。守恒性与初始标志无关，所以它是结构性质。如果存在一个向量 山= ( i ，峨，甜。) 7 ，c - 0 r o ，i = l ，2 ，胛，且甜0 使得7 m = 7 m 0 ，v m r ( z ，m o ) 则称 z = ( p ，t ，0 ，m 。) 为部分守恒的。 守恒性表示各个标志的托肯加权和相同。严格的守恒性表示系统中托肯数量不随 变迁的触发而变化。这表示除了预先规定外，一个系统中的资源是不会增减的。当然 也有例外情况如果我们从制造系统中移除一个破损的a g v 小车，那么a g v 的可用数 量就要减一。 活性： 如果对于任何标志meg ( z ，m 0 ) ，都存在一个变迁序列，触发后得到一个标志使 得变迁t 成为使能的。则t 为活的。如果p n 中任何一个变迁都为活的，则称此p n 为 活的。 如果存在一个标志m r ( z ，m o ) 使得没有任何变迁序列能使t 在n l 下使能，则称 变迁t 是死的。如果存在m r ( z ，m o ) 使得其下没有任何变迁是使能的。则说此p n 包 含一个死锁。此标志m 称为死标志。 死锁是由资源的不正确分配或对某些或全部资源的过度使用造成的。例如，若干 机器可能公用机器人，若干不同或相同的加工共用机器，毛坯、中间件以及成品公用 缓冲区空间。在这样的资源共享系统中，下列4 个情况可能同时满足l l l l 【如1 ，从而导致 锁死： f n 互斥：一资源不可以为两个或两个以上过程同时使用，一过程排斥其它过程 第二章p e t r i 网理论基础 对于该资源的占用。 ( 2 ) 占用且等待：一过程已被许可占用某一或某些资源，同时又在请求占用其它 资源。 ( 3 ) 无抢占：已分配给某一过程的资源不能从该过程中抢走，除非该过程使用此 资源完毕后而释放。 ( 4 ) 循环等待：两个或更多过程排成一个链，链上每一过程都在等待一个正在被 链上下一个过程占用的资源。 如果对于任何从m 。可达的m 下的每一个变迁，都最终存在一个变迁序列使它使 能，则称此p s 是活的。很明显，如果一个p n 是活的那么其中就不会有死锁。如果 存在任意有限初始标志使得网为活的，就称其为结构活的。 可逆性和丰宿状态： p n 是可逆的，若对于每一标识m e r ( z ，m o ) ，都有m 。r ( z ，m ) 。标识m r ( z ，m 。) 称为手宿状态( i t o m es t a t e ) ，若对任意的m r ( z ，m 。) ，m 都是从m 可达的。 p e t r i 网的可逆性是指对于任意从卅0 可达的m 都可以回到r r ，。来。许多系统需要 能从错误状态恢复到之前的正确状态，因此可逆性对于制造系统的错误恢复是非常重 要的。而且，它还保证所有重复制造系统的周期特征。可逆性是主宿特征的一个特例， 就是说，如果主宿状态m 。m o ，那么网就为可逆的。这些性质为行为性的。而且，如 果一个网中包含有死锁，那么它就不是可逆的。如果有任意有限个初始标志使得一个 p e t r i 网为可逆的，那么它就是结构可逆的。 其他结构特征如下：如果存在一个初始标志及一个从它出发的变迁序列a ，所 有( 部分) 变迁无限的以序列a 出现，那么该p n 就称为( 部分) 重复的。如果存在 一个初始标志码及一个从它出发并回到它的变迁序列，使得所有或部分变迁触发至 少一次，那么该州就被称为( 部分) 一致的。一致性是重复性的一个特例。 例3 ：图2 1 所示的为一个4 一有界的网，给出初始标志( 4 10 0 ) 7 后，其每个库 所中最多只能容纳4 个托肯。它不是活的，因为其中包括一个死锁，在标志( 0 l02 ) 7 下，没有变迁是使能的了，这个死锁是由于舟中的托肯被耗尽而造成的。从初始标志 ( 4 1 0o ) 7 出发，只有( 0 0 l0 ) 7 和( 0 1 0 2 ) 7 是可达的；网不可逆；因为存在国= ( 1 15 2 ) 7 使得甜7 m = 印7 ，所以它是守恒的。 p e t r i 网在f m s 巾的若干应用研究 2 41 时间p e t r i 阔 4 3 1 ，【4 4 1 2 4p e t r i 网扩展 我们知道，由于网论中没有全局时间的观念，所以普通p e t r i 网不包括任何时间 概念。通过这类网，我们只能描述系统的逻辑结构和行为，却不能描述它随时间的演 化。出于对离散事件系统性能评价及动态系统调度等问题的需要，人们以各种方式把 时间概念引入到p e t r i 网中，因而产牛了时间p e t r i 网( t p n ) 的概念。 按照时间在刚中被引入的位置，我们可以把t p n 分为以下3 种： ( ”若用变迁表示历经一定时间的事件或操作，则将时间与变迁关联，得到时间 变迁p e t r i 网( t i m e dt r a n s i t i o np e t r in e t ，t t p n ) 。一旦变迁可实施，则从该变迁的每一 输入位置中移去一定数量的托肯，但变迁要延迟一定时间后再实施，并在输出位置中 放入一定数量的托肯。 ( 2 ) 若用库所表示历经一定时间的事件或操作，则将时间与库所关联，得到时间 库所p e t r i 网( t i m e dp l a c e p e t r i n e t ，t