（交通信息工程及控制专业论文）基于Petri网的车站调度模型的研究.pdf

中文摘要 m f ll lli r l l lrl f lfljil l i l 17 8 9 312 列车运行调度是铁路运输f 1 常工作中的一项核心工作，涉及到众多的部门和专业技 术领域，列车在车站的运行调度是其中的一个重要组成部分。以列车在车站的运行调度 为背景，通过对列车在车站运行调度的特点进行分析，本文采用p e t r i 理论对列车在车 站的运行调度进行了研究，建立了列车在车站的运行调度模型并对调度计划可行性进行 了分析。主要研究工作内容如下： ( 1 ) 对p e t r i 网理论和列车在车站运行调度相关理论进行了研究，指出列车运行调 度是一个典型的离散事件系统。p e t r i 网作为离散事件系统建模、性能分析的一种有效工 具，适合用来对列车运行调度问题进行研究。 ( 2 ) 对列车在车站的运行调度模型进行研究。通过将着色p e t r i 网和赋时p e t r i 网相 结合，给出赋时着色p e t r i 网的形式化描述并建立列车在车站运行调度的层次模型。 ( 3 ) 仿真分析。采用c p nt o o l s 仿真工具对模型进行仿真分析，验证模型的有 效性。 本文通过对p e t r i 网理论和列车运行调度相关理论的研究，建立了列车在车站的运 行调度的层次模型。仿真结果表明了模型的有效性和正确性。该模型对验证列车在车站 运行调整方案的可行性具有重要的理论价值和实用价值。 关键词：离散事件动态系统；着色p e t r i 网；列车运行调度 - 一 a bs t r a c t t r a i n o p e r a t i o nd i s p a t c h i n gi s o n eo ft h ec o r ew o r k si nt h e r a i l w a y t r a n s p o r td a i l yw o r k s ，i n v o l v e sm a n yd e p a r t m e n t sa n dp r o f e s s i o n a lt e c h n o l o g y d o m a i n s ，t r a i no p e r a t i o nd i s p a t c hj o ba ts t a t i o ni sa ni m p o r t a n tp a r t f o rt h et r a i n o p e r a t i o nd i s p a t c h i n ga ts t a t i o n ，i ti ss t u d i e db yu s i n gp e t r in e tt h e o r y ，i t sm o d e l i se s t a b l i s h e da n dt h ef e a s i b i l i t yo ft h ea d j u s t i n gp l a ni sa n a l y z e di nt h i sp a p e r t h er e s e a r c hw o r k si n c l u d e s ： ( 1 ) s t u d y i n gt h et h e o r i e sa b o u t t h ep e t r in e ta n dt h et r a i no p e r a t i o nd i s p a t c h a ts t a t i o ni ti sp o i n t e do u tt h a tt h et r a i no p e r a t i o n d i s p a t c h i n gi sat y p i c a ld i s c r e t e e v e n ts y s t e m ，p e t r in e tb e i n ga ne f f e c t i v et o o lf o rd i s c r e t ee v e n ts y s t e m s m o d e l i n ga n dp e r f o r m a n c ea n a l y z i n gi ss u i t a b l et os t u d yt h ep r o b l e mo ft r a i n o p e r a t i o ns c h e d u l i n g ( 2 ) m o d e l i n gt h et r a i no p e r a t i o nd i s p a t c h i n ga ts t a t i o n t h r o u g hi n t e g r a t i n g c o l o r e dp e t r in e ta n dt i m e dp e t r in e t ，t h ef o r m a ld e s c r i p t i o no ft h et i m e dc o l o r e d p e t r in e ti sg i v e na n dt h eh i e r a r c h i c a lm o d e lo ft h et r a i no p e r a t i o nd i s p a t c ha t s t a t i o ni sb u i l t ( 3 ) t h es i m u l a t i o na n a l y s i s t h ec p nt o o l si s u s e dt o s i m u l a t et h e m o d e la n dt ov e r i f yi t sv a l i d i t y t h r o u g hs t u d y i n gt h et h e o r yo f p e t r in e ta n dt h er e l a t e dt h e o r yo ft h et r a i n o p e r a t i o nd i s p a t c h i n g ，t h eh i e r a r c h i c a lm o d e lo ft r a i no p e r a t i o nd i s p a t c h i n ga t s t a t i o ni sb u i l t t h es i m u l a t i o nr e s u l ts h o w st h ec o r r e c t n e s sa n de f f e c t i v e n e s so f t h em o d e l t h em o d e lh a st h ei m p o r t a n tt h e o r e t i c a lv a l u ea n dp r a c t i c a lv a l u ef o r v e r i f y i n gt h ef e a s i b i l i t yo ft r a i no p e r a t i o na d j u s t m e n tp r o g r a m s k e yw o r d s d i s c r e t ee v e n td y n a m i cs y s t e m ；c o l o r e dp e t r in e t ；t r a i n o p e r a t i o nd i s p a t c h i n g i v 目录 第一章绪论1 1 1 研究背景和目的1 1 1 1 研究背景l 1 1 2 研究目的2 1 2 列车运行调度系统国内外的发展概况3 1 2 1 国内状况3 1 2 2 国外状况4 1 2 3 车站列车运行调度问题的研究4 1 3p e t r i 网理论引入车站列车运行调度的研究5 1 4 本文研究内容6 第二章p e t r i 网基本理论9 2 1 基本p e t r i 网9 2 1 1p e t r i 网的发展历史9 2 1 2 经典p e t r i 网定义9 2 1 3 p e t r i 网的运行规则1 0 2 2 几科t 特另u 的p n 1 0 2 3 扩展p e t r i 网1 1 2 3 1 着色p e t r i 网1 l 2 3 2 赋时p e t r i 网1 2 2 3 3 着色赋时p e t r i 网1 3 2 4 小结1 4 第三章基于c p n 的车站调度层次模型建立与仿真1 5 3 1 列车在车站的运行调度分析1 5 3 2 基于c p n 的车站列车调度模型1 5 3 2 1 列车在区段上的运行模型1 5 3 2 2 列车在道分区段上的运行模型1 6 3 2 3 办理进路模型1 7 3 2 4 车站列车运行调度c p n 模型1 8 3 3 仿真及分析1 9 3 4 小结2 4 v 车站调度层次模型仿真及分析2 5 2 5 2 5 ：2 6 ：6 ：2 9 3 1 3 3 3 7 3 9 4 5 v i 第一章绪论 第一章绪论 1 1 研究背景和目的 1 1 1 研究背景 铁路运输以其客货运输量大、运行速度高、运输成本低、投资效果好、运输的持续 性及受气候条件影响小的特点构成国民经济活动中必不可少的重要组成部分。随着国民 经济的腾飞，我国大规模的客运专线相继建成。目前，由于我困的客运专线为多速度列 车共线，新旧线芪用的模式，车站接、发车作业频繁，使得车站有限的设备资源在客运 接、发高峰期时段显得十分紧张【。但靠新增车站设备，扩大基础投资，提高运输能力 是不够的。要想从根本上摆脱运力紧张困境，必须从系统的观点出发，用科学的手段把 列车、线路和运营管理综合起来考虑；采用先进技术，实行优化调度，挖掘现有线路的 潜力，实现对车站有限的设备资源的高效利用来提高车站的作业能力，协调车站各部门、 各工种更好、更快的完成车站各项作业，有节奏的进行同常运输生产。 在我国的铁路网上，拥有几万公里线路，配备了大量的技术设备，设有运输、机车、 车辆、工务、电务等业务部门。各部门与各工种之间必须密切配合，协同动作，贯彻高 度集中、统一指挥的原则。 铁路综合调度系统能够实现列车计划、运行、维修等一系列管理与控制，为日常运 输生产安全、高效的完成提供有力保障。其管理和指挥包括列车、机车、车辆运用计划 的制定，实施计划的调整，事故统计等一系列内容。自8 0 年代后期起，我国的铁路综 合调度方式逐渐由传统的“一张纸+ 一把尺子+ 一只铅笔+ 一部电话”的人工调度方式 转向由计算机完成调度信息的采集和处理的t d c s ( y u 车调度指挥系统) 。t d c s 集合了通 信、信号、计算机、网络、数据传输、多媒体等技术，构成铁路调度指挥系统网络，它 覆盖我国铁路调度信息点，形成三级三层集中式综合性现代化的运输指挥调度系统1 2 j 。 t d c s 系统集中式机构如图1 1 所示。 图1 1 中，铁道部调度指挥中心主要从宏观上制定调度策略，协调处理各铁路局间 的交接列车等事宜，着重在于监视列车的运行过程，不直接参与对列车群的运行过程控 制：铁路局调度指挥系统主要对所管辖范围内的列车群运行过程进行控制，是局管内的 运输组织调度指挥，行车指挥与运输调度的第一直接管理者，主要体现为制定阶段调整 计划和下达调度命令。车站是命令的执行者，调度任务主要是具体执行阶段调整计划和 调度命令，并将各种信息反馈于铁路局调度所。 基- j - p e t r i 网的下站调度模型的研究 图1 1 t i ) c s 系统结构图 f i g 1 is t r u c t u r ed i a g r a mo ft d c ss y s t e m 与路局调度相比，车站列车运行调度是三级三层集中式综合性现代化的运输指挥调 度系统的日常调度工作的基础和莺要内容，是实现车站接发车、调车等作业的技术性文 件。作为基层的车站列车运行调度虽然只是执行路局调度下达的阶段调整计划及调度命 令，根据阶段调整计划办理进路、开放信号灯和接发车等，不具体参与阶段调整计划的 制定，但是在整个列车运行调度过程中具有很重要的作用，它保证列车在车站安全运行。 车站列车运行调度涉及列车、车站、区问、调度员等各方面的参与，是铁路运输的 综合体现，具有相当的复杂性【3 7 1 。近年来，对于车站列车运行调整的理论与方法，有 关方面的专家学者作了大量深入的研究，取得了若干有价值的成果。例如，文献 8 运用 无延迟调度算法对列车运行调整问题进行研究；文献 9 的产生式规则表达列车运行调整 知识的专家系统；文献 1 0 的离散事件动态系统模型上的分层滚动调整方法等。然而， 当前设计的车站列车运行调度系统在对调度信息的采集、分析及处理后形成调度指令输 出方面不具有真正的“思考”能力【1 1 1 引，相当一部分信息只能由调度员完成。车站列车 运行调度系统在智能化发展方面是不完善的，这也成为整个铁路运输调度自动化发展的 瓶颈。本文即是在这一研究背景下，通过对列车在车站运行调度的特点及运行规则的分 析，对车站列车运行调度进行建模，并基于此模型对车站列车运行调度计划可行性进行 研究。 1 1 2 研究目的 车站列车运行调度是铁路运输的核心内容和关键技术，科学地制定车站列车运行调 度方案，对于提高铁路部门的运输生产效率起着至关重要的作用【1 9 1 。如何在车站有限运 输资源的约束下( 如车站股道、道岔、区段等) ，合理确定列车在车站的行车顺序，确 保列车的安全运行及按计划行车，是本文的主要研究目的。本文运用离散事件动态系统 中的着色赋时p e t r i 网的建模方法解决车站调度的分析问题，将p e t r i 网建模方法与车站 2 第一章绪论 调度相结合，从宏观和微观两个层次对列车在车站的运行调度进行建模。模型从宏观上 描述列车在车站的调度过程( 调度计划的自动执行) 和进路办理过程( 自动办理接、发 车进路、占用及取消) ；从微观上描述列车在轨道区段、道俞区段、股道与站线上的运 行过程。运用c p nt o o l 仿真工具对系统模型分别采用两种仿真方法进行仿真实现与分 析。方法一采用单纯c p nt o o l 建模方法仿真实验；方法二采用层次化c p nt o o l 建模方 法仿真实验。通过仿真实验与分析，比对两种仿真方法在描述车站调度系列事件系统的 静态结构及动态结构时的优劣性；分析系统模型的冲突、互斥、非确定及系统锁死等行 为特性及运行规则；验证系统模型各变迁触发事件的先后、并行、同步与异步特征的逻 辑控制关系及反映系统操作表示信息的正确性。在对基于c p n 的车站调度层次系统模 型进行仿真实验与分析中，引入时问问题。在时间约束条件下，采用c p nt o o l 仿真工 具，提高了对系统的描述和分析能力，对于验证列车运行调整方案的可行性，合理确定 列车在车站的行车顺序，确保列车按计划安全、高效、f 点运行具有理论价值与实践应 用价值。 1 2 列车运行调度系统国内外的发展概况 1 2 1 国内状况 列车运行调度是实现铁路智能运输的关键环节之一，涉及到车、机、工、电、辆、， 客、货、建设、安全检查等许多部门以及许多规章制度。为了规范车站的作业流程，发 挥技术设备的效能，改善车站调度人员的工作手段和减轻工作压力，我国自八十年代后 期，经过长期和广泛的研究，借鉴国外很过成功经验，集合计算机技术、通信技术、网 络技术和现代控制技术等先进技术相继开发了以t m i s ( 铁路运输管理信息系统) 、d m i s ( 铁路调度指挥信息系统) 为代表的一系列产品。 t m i s 系统通过建立全路计算机网络，将全路部、局及主要站段的计算机设备联成 一个整体，实现了对全路列车、货车、机车、集装箱等实施追踪管理，从而为铁路调度 指挥人员提供及时、准确、完整的动态信息和决策方案。d m i s 系统是我国铁路运输调 度指挥系统现代化建设的标志，它由铁道部、各铁路局、以及基层车站、枢纽等构成的 三级网络。t d c s 融合现代化先进技术与铁路信号的特点，将以车站为单位的分散信号 系统逐步改造成全国统一的网络信号系统。它实现了全国铁路系统内有关列车运行、数 据统计、运行调整、信息自动处理与查询等功能。d m i s 系统的实施大幅度提高了铁路 运输生产效率、改善了车站调度指挥人员的二f ：作条件。 为进一步集中调配使用铁路运输资源，提高我国铁路运输生产效率，铁道部在2 0 0 5 后，相继将t m i s 和d m i s 进行系统集成，建立了以c t c ( c e n t r a l i z e dt r a f f i cc o n t r 0 1 ) 基tp e t r i 网的下站调度模型的研究 为技术核心的t d c s ( t r a i nd i s p a t c hc o n t r o ls y s t e m ) 系统，并在全路推广。目前，我 国的列车运行调度在车次追踪、实绩运行图自动绘制、计算机辅助列车运行计划系统等 方面取得了很大进展【l 】，但车站列车运行调度中心在列车运行指挥、列车运行管理及设 备管理与维护等方面的自动化水平还不高，有待进一步研究。 1 2 2 国外状况 经过长期和广泛的研究，发达国家已从主要依靠修建更多的道路、扩大路网的规模 来解决r 益增长的交通需求，逐渐转移到利用高新技术来改造现有的道路运输系统和管 理体系，从而大幅度地提高了路网的通行能力和服务质量。其中以日本、德国和法国的 铁路调度管理系统为代表化分为三种类型【2 0 1 。 1 、r 本模式 日本是世界上第一条高速铁路诞生国，为适应其高速铁路新干线的管理需求，在充 分考虑高速铁路行车所伴随的高风险及其行车安全对调度系统的依赖性，r 本综合了行 车调度、通信信号及安全监控等有关的各专业内容，秉承“安全第一 的思想，构建了 以运输计划为基础，以列车运行管理为核心各专业综合的高度自动化的调度指挥系统。 2 、德国方式 德国路网结构特点是客货列车混跑，新建线与既有线混用。调度系统实行区域控制， 其新建高速线调度指挥根据所在的区域纳入既有调度系统。调度管理模式从上向下实行 三级管理，即中央调度中心、区域指挥中心、基础车站值班员。每个区域指挥中心采用 c t c ( 调度集中) 技术控制管辖范围内铁路沿线各站的信号设备，监视区段内信号设备 状态和列车运行情况。 3 、法国模式 法国的铁路线路包括：东南线和地中海线( 东南轴线) ，北方线和大西洋线。调度 指挥系统控制中心的建立以线路为目标，指挥形式不一，有两级管理和三级管理两种， 基本保持传统的控制模式【2 l 】。高速铁路调度指挥是按照三级管理设置，其调度指挥模式 相对独立于既有线，调车作业只包含客运组织、行车组织以及机车车辆方面的调度2 2 1 。 1 2 3 车站列车运行调度问题的研究 目前国内外铁路调度系统虽都有“计划台 ( 供调度员进行计算机辅助计划编制的 计算机平台) ，但基本上都足辅助调度员绘制运行图的工具，缺少辅助系统决策的功能， 仅在少数简单路段( 如封闭性强的城市地铁系统) 实现了半无人化的调度管理。而这类 调度管理算法也因为系统模型相对简单，并且基本无外界干扰，而不具备普遍适用性。 针对车站列车运行调度问题，我国也已进行了相应的研究2 3 2 卯。就行车指挥算法而 4 第一章绪论 言，早期的行车指挥算法都是基于传统的最优化理论之上的。这些方法在实际应用中存 在许多缺陷，如：这些数学模型无法反映列车群运行的真实情况；计算量很大，无法满 足实时性要求，组合爆炸等。除此之外，这些传统的方法无法反映调度员的知识和他们 的那些行之有效的经验性策略，不具备调度员所具有的智能。这也是人工智能、知识工 程等学科在行车指挥方面开始得到应用及调度系统向智能化发展的原因。 铁路是一个庞大复杂的巨大系统，包含多方面因素，各个环节紧密联系，有许多领 域涉及到时间知识的分析处理。由于p e t r i 网可描述时间的顺序或并发等性质，且具有 多种有效的推理分析方法 2 6 - - 2 8 1 ，基于p e t r i 网进行时间知识的分析处理在近几年引起了 学者们的很大兴趣。文献【2 9 】在p e t r i 的基础上，提出了一种着色赋时p e t r i 网的行车指 挥系统模型，并与遗传算法相结合对列车运行调整问题进行求解；文献 3 0 禾t j 用分层有 色p e t r i 网( c p n ) 对c b t c ( 基于通信的列车控制系统) 系统移动闭塞条件下的列车追 踪过程进行建模和仿真来描述列车运行过程；文献【3 1 】采用面向对象p e t r i 子网对列车群 运行系统进行了建模和问题分析等。因此，针对列车运行调度，本文结合时间p e t r i 网 对列车在车站运行的调度进行建模和分析处理的研究，具有很强的代表性和实用性。： 1 3p e t r i 网理论引入车站列车运行调度的研究 在铁路的实际生产工作中，列车调度员指挥有关部门按列车运行计划图组织列车运。 行。在理想情况下( 没有任何意外事件发生) ，列车运行调度工作的主要内容是在各个 车站办理接车进路和发车进路，只要当天的列车运行计划图不发生变化，就不存在制定 列车运行的阶段调整计划。与路局调度相比，作为基层的车站调度虽然只是执行路局调 度下达的阶段调整计划及调度命令，不具体参与阶段调整计划的制定，但是在整个列车 运行调度过程中具有很重要的作用，它保证列车在车站安全运行。在车站，列车运行调 度的主要工作是执行路局下达的调度命令、根据阶段调整计划办理进路、开放信号灯和 接发车等。和列车在区间运行过程相比，列车在车站的运行过程要复杂的多。 列车运行调整过程所发生的事件序列主要为：列车进站一办理接车进路一开放进路 信号灯一办理发车进路一丌放发车信号灯- - y i j 车出站一。由于这些事件的发生时问均 在列车计划运行图中得到体现，因而，此工作易于用设备进行控制，如铁路行车调度c t c 系统的一项主要功能就是按照计划自动办理接车进路和发出进路。 在铁路的实际生产工作中，由于列车的运行过程不可避免受到众多意外因素的影 响，而导致列车运行秩序发生紊乱，如列车故障、临时专列的丌放、作业延误、设备故 障以及自然灾害等。在此情况下，一列列车的晚点往往会影响一条线上的列车，进而影 响到一片，甚至会发生行车事故。针对列车在运行过程中出现的突发情况，如何及时做 基于p e t r i 网的车站调度模型的研究 出调整策略，保证列车安全准点运行或尽量避免列车晚点是列车运行调度的主要工作和 内容。在实际的列车运行调度过程中，所发生的事件可分为三类，一类是不可控事件， 如设备故障、列车故障、自然灾害等。该类事件的发生是不以人的意志而转移的；第二 类事件是可控事件，如办理接车进路、发车进路、信号灯开放、列车停运等，该类事件 完全可由人进行控制；第三类事件是主动事件，如调度员发布的调度命令，以及阶段调 整计划等。从事件的角度来讲，列车运行调度的本质是当不可控事件发生时，通过发布 主动事件对可控事件进行控制，从而保证列车安全运行，避免行车事故的发生。 列车运行调度是铁路运输部门组织列车运输的一项关键性工作，涉及到列车、车站、 区问以及铁路运输的各个部门。有效的列车运行调度就是通过制定阶段调整计划，对路 网内的列车群运行过程进行控制，保证按图行车。列车运行调度从分类上看，是一个典 型的调度问题，而调度问题又是一个典型的离散事件系统3 2 35 1 。离散事件系统建模的方 法有因果图、p e t r i 网等，其中p e t r i 网作为离散事件系统建模、性能分析及控制的一种 数学和图形工具，近年来已广泛应用于柔性制造系统( f m s ) 。铁路运输系统( i 玎s ) 与 f m s 有许多类似之处，例如都是典型的离散事件系统，都存在一个调度问题，所不同的 是两种生产部门产生的产品不同。p e t r i 网在f m s 的应用将为r t s 的应用提供成功的典 范。 在本文后面的章节中，将详细介绍p e t r i 网的基本概念及相关理论，以及详细描述 采用着色p e t r i 网对车站调度进行建模研究的过程。 1 4 本文研究内容 本文以铁路系统中的车站调度研究为背景，运用离散事件动态系统中的着色赋时 p e t r i 网的建模方法解决车站调度的分析问题。文中涉及基于p e t r i 网的建模方法，建立 车站调度模型，以及运用c p nt o o l 对模型的仿真实现与分析。本文的主要研究内 容如下： 1 对p e t r i 网( p n ) 的相关理论及建模方法进行研究，对铁路运行调整问题进行分 析研究。 介绍基本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 网的定义、运行规则及其建模方法进行研究。分析列车运行调度工 作流程及列车在车站的运行行为。 2 基于c p n 对列车运行调度进行建模仿真。 基于p e t r i 网的列车运行调度系统的建模过程，分为以下步骤： 6 第一章绪论 1 ) 运用c p n 的建模方法，分析列车在车站内的无翁区段、道岔区段的运行过程及 车站办理进路过程，建立列车在车站的运行调度层次模型： 2 ) 利用c p nt o o l 仿真工具对基于c p n 的车站调度层次模型进行仿真实验，在不 考虑时问因素的前提下，验证模型的逻辑摔制关系及操作表示信息的正确性，分析模型 的基本性质。 3 对基于c p n 的车站调度层次模型进行带时问约束的仿真实验，验证给定列车阶 段调整计划的可实施性及模型的可行性。 论文具体内容安排如下： 第二章介绍基本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 网( c p n ) 的建模方法对车站调度进行建模仿真； 第四章利用c p nt o o l 仿真工具，对系统模型进行带时间约束的仿真实验。验证给 定列车阶段调整计划的可实施性及模型的可行性； j ； 一 第五章是本文的结论与展望。 基丁p e t r i 网的车站调度模型的研究 8 第二章p e t r i 网基本理论 第二章p e t r i 网基本理论 2 1 基本p e t r i 网 2 1 1p e t r i 网的发展历史 p e t r i 网是对计算机系统事件之间的因果关系的数学表示。最早由卡尔a 佩特里博 士于19 6 2 年在他的博士论文中提出。4 0 多年来，大批科学研究者与工程研究人员长期 致力于p n 的理论及应用研究，不断的充实与发展p n 理论，如今，p e t r i 网的应用领域 广泛拓展至计算机、自动化、通信、交通、电力与电子、服务以及制造等f 3 6 1 。p e t r i 网是 一种结构化的d e d s 描述工具，适合于描述异步的、同步的、并行的计算机系统模型。 p e t r i 网由简单的圆、线、弧所构成，但能够描述系统活动之间复杂的逻辑关系；p e t r i 网通过直观的图形描述系统组成的行为特性，但却被形式化的数学方法所支持，表达离 散事件动态系统( d i s c r e t ee v e n td y n a m i cs y s t e m ，d e d s ) 的静态结构和动态变化，p e t r i 网已经成为描述、分析和控制d e d s 最有效和应用最广泛的方法。 2 1 2 经典p e t r i 网定义 经典p e t r i 网是简单的过程模型，由库所、变迁、有向弧以及令牌等元素组成的。 一个过程的状态是由在场所中的令牌建模的，状态的变迁是由变迁建模的。p n 的结构 是由四要元( 库所，变迁，输入函数，输出函数) 描述的有向图。 刚s = ( p ，t ，d )( 2 1 ) 此处： ( 1 ) p = 气，p 2 ，易) 是库所的有限集合，z 0 为库所的个数； ( 2 ) 丁= t 2 ，锄 是变迁的有限集合，m 0 为变迁的个数； ( 3 ) p n 丁：囝，p w t o ( 集合p 和集合丁不同时为空) ； ( 4 ) ，：p x t j 是输入函数，它定义了从t 到p 的有向弧的重复数或权( w e i g h t ) 的集合，这罩n = 0 ，i ，1 ) 为非负整数集； ( 5 ) o ：t x p _ 是输出函数，它定义了从t 到p 的有向弧的重复数或权的集合。 如图2 1 所示。 图2 1 基本p e tr i 网模型 f i 9 2 1b a s i cp e t r in e t sm o d e l 图2 1 中，p e t r i 网的元素定义如下：库所( p l a c e s ) p 1 、p 2 ，p 3 、p 4 以椭圆表示， 9 基- j - p e t r i 网的币站调度模型的研究 表库所、通道或地理位置；变迁( t r a n s i t i o n s ) t 1 、t 2 、t 3 以长方形或粗实线表示， 表事件、转化或传输；令牌以黑色实心小圆点表示，代表事物( 人，货物，机器) 、 息、条件、或对象的状态；有向弧( c o n n e c t i o n ) 是库所和变迁之阳j 的弧，它是有方 的，两个库所或变迁之间不允许有弧；如果一个变迁的每个输入库所都拥有令牌，该 迁即为被允许的。一个变迁被允许时，变迁将发生，输入库所的令牌被消耗，同时为 出库所产生令牌。两个变迁都有被允许的可能，但是一次只能发生一个变迁。若出现 个变迁，其收入库所的个数与输出库所的个数不相等，令牌的个数将发生变化。 1 3 p e t r i 网的运行规则 ( 1 ) 变迁t 的使能规则定义如下： 变迁t t 在标识m 下使能，当且仅当： v p + t ：m ( p ) i ( p ，f )( 2 2 ) 有前提条件得以满足的变迁的发生，将“消耗”输入库所的令牌，同时为输出库所产 令牌。在p n 中，用使能的变迁的激发( f i r e ) 来描述事件的发生，所消耗的令牌及 次数通过变迁的输入函数来定义。并以从输入库所中移去相应数量的托肯来表示，所 尘的结果状态及其次数由输出函数确定，并用输出库所中增加的托肯表示。 ( 2 ) 在标识m 下使能的变迁t 的激发将产生新标识m 、，现定义如下： 印p ：m 、= 聊( p ) 一l ( p ，f ) + o ( p ，t )( 2 3 ) 具体地 v p t ：m 、= 聊( p ) 一，( p ，)( 2 4 ) 坳f + ：m 、= 所( p ) + d ( p ，f )( 2 5 ) v p lr 、t + ：m 、( p ) = m ( p ) - i ( p ，f ) + d ( p ，f ) ( 2 6 ) v p 萑+ t p 正f ( 既不是t 的输入又不是输出库所) ：研、( p ) = m ( p )( 2 7 ) 若标识m 、是( 通过t 的激发) 直接从m 可达的，则记为州f 所、 ( 2 8 ) 2 2 几种特别的p n 若p n 的所有变迁至多有1 个输入弧或输出弧，即 i ：pxt j o ，1 ) ，o ：t p 。 o ，l ( 2 9 ) 贝0 此p n 称为普通p n ( o r d i n a r yp e t r in e t ) 。 若p n 无自闭环，即不存在某一库所同时是某一变迁的输入与输出库所的情况，则 此p n 称为纯p n ( p u r ep e t r in e t ) 。 若p n 的每一库所都恰好有1 个输入变迁与1 个输出变迁，即 v p p ：r p i = pi = 1( 2 1 0 ) l o 第二二章p e t r i 网基本理论 则该p n 称为标示图( m a r k e dg r a p h s ) 。 若p n 的每一个变迁都恰好有1 个输入库所与1 个输出库所，即 v ，丁：1 f | = i f i = 1 ( 2 1 1 ) 则该p n 称为状态机( s t a t em a c h i n e ) 。 2 3 扩展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 网、着色p e t r i 网、面向对象p e t r i 网、混合p e t r i 网及变结构p e t r i 网。 2 3 1 着色p e t r i 网 着色p e t r i 网常简记为c p n ( c o l o r e dp e t r in e t ) ，其特点是把系统中具有类同行为 特性的元素归属到一个位置节点或一个变迁节点中，并通过对所属“托肯”的不同颜色 来进行区别，从而使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 ) 对不同属性的“托肯”着以不同的颜色，称着了颜色的“托肯 为“有色托 肯”或色点。在c p n 中，一种颜色的“有色托肯”用来表征一类具有相同行为特性的 元素。而在基本形式p e t r i 中，一个“托肯”仅仅只是表示一个元素或一个资源。 ( 2 ) 托肯的发射不同于基本形式p e t r i 网的发射规则。c p n 中，在任一两个节点间 的路径弧上，都标识一个相应的线性函数，每个线性函数明确地舰定了相应的发射条件， 包括为使变迁节点使能，其输入位置节点中所应有的色点的颜色，以及变迁节点在完成 发射后应清除的和应产生的色点的颜色。 与经典p e t r i 网相比，着色p e t r i 网并不具备更强的建模能力，但可以压缩模型中的 基本元素。着色p e t r i 网可定义为一个六元组： c p n = ( 尸，丁，f ，c ，w ，m ) ( 2 1 2 ) 其中： 1 l 基于p e t r i 网的乍站调度模型的研究 1 ) p = 暑，昱，巴) 为有限库所集合，p 为库所数量且p 0( 2 13 ) 2 ) 丁= 互，疋，乙 为有限变迁集合，q 为变迁数量且q 0( 2 14 ) 3 ) p nt = 囝，pu t 囝( 集合丁和集合p 不同时为空)( 2 15 ) 4 ) f ( p t ) u ( t p ) & p f 为有向弧的集合 ( 2 1 6 ) 5 ) c 是k 种颜色的集合：c = 口l ，a 2 ，口女)( 2 17 ) 6 ) w ：fj o ，1 ，2 ，一) 庀为有向弧集合到k 维向量集合的映射，其中k 维向量中的每一 个分量表示一种颜色的数量( 2 1 8 ) 7 ) m ：p 寸 0 ，1 ，2 ，) 庀，为库所集合到k 维向量集合的映射，其中k 维向量中的每一 个分量表示一种颜色的数量。 着色p e t r i 网的运行规则如下： 1 ) 变迁使能条件 在标识m 下，对v t t 被认为是具有发射权的， 砌f ，m ( p ) w ( p ，t ) ，其中 。，= p i ( p ，f ) ，) 2 ) 标谚 变化规则 ( 2 1 9 ) 即变迁f 为使能，如果满足条件： ( 2 2 0 ) 若v t t 在标识m 下使能，则变迁，发射后按如下规则变化到新的状态标识m ： m ( p ) = 2 3 2 赋时p e t r i 网 赋时p e t r i 网( t i m e dp e t r in e t s ) 常简记为t p n 。t p n 的一个基本特点是，在基本形 式p e t r i 网的变迁节点中引入表征时间的参量，使其不仅能够用来描述系统在逻辑层次 上的关系，而且能够适度地表征系统在时问层次上的关系。 一个赋时佩特利网t p n 可表示为一七元组： 卯= ( p n ，伊) = ( 尸，t ，f ，w ，m ，m o ，0 )( 2 2 2 ) 其中，p n 为一个基本形式p e t r i 网，0 = ( 舅，岛，氏) 为一组与变迁节点或位置节点 相联系的时延参量，对时延参量引入于变迁节点的t p n 。按照约定，当具有发射权即使 能的一个变迁节点t ；具备发射条件时，还需经过0 i 的时延后才能实现真正的发射。对时 间参量引入位置节点的t p n ，时延的含义对应地变为当“托肯 由一个位置节点转移到 另一个位置节点中时，后者需要经过伊的时延后才可接受到，而“托肯”只有在被接收 1 2 22 、 rn f ， f p p p es谨行行d 、，p f l 肜+ 、，、，、， h p h p 以 p l，ll 形矿矿 一 + 一 、，、，、夕、， p p p p，llll m m m m 第二章p e t r i 网基本理论 到后才能对变迁节点具有诱发发射的可能性。 通常，t p n 的各个时延参量臼，( j = 1 ，2 ，m ) 被认为是一组确定性的常数，在分析和 综合方法上，赋时p e t r i 网同于基本形式p e t r i 网，但分析的复杂性增加。 2 3 3 着色赋时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 网的模型中，通过用圆圈表示库所，用方框表 示变迁，用t o k e n 表示变迁发生所需要的资源分布标识，不同颜色的t o k e n 表示不同种 类的资源，变迁表示实际的活动，库所表示工作流网当前的状态。当变迁具备发生权时， 还需要判断其是否在相应的时间区间内。由于库所中不同颜色的t o k e n 代表不同性质过 程发生所需的资源，因而变迁的实施时间是个变量，它的赋值取决于变迁发生前的t o k e n 的颜色。 ( 1 ) t c p n 的定义 t c p n 定义为一六要元 t c p n = l p ，t ，c ，l 。o ，d 、 这里p ，t ，c ，i ，o 定义与c p n 相同，而d 为库所或变迁的时延函数，有 d ：c ( 尸) 寸r 十( 正实数) 对于变迁的时延函数，有 d ：c ( 丁) jr + 具体的，库所尸时延函数表示为： d ( b ) = 谚，l ，谚，埘) ，= i d ( b ) i = i c ( 只) i ，i = 1 ，咒 这里q ，矗为库所p 的第h 个色彩a i 。所对应的时延，记为 d 珊= d ( a 啪) ，h = 1 甜， 类似地，变迁t 的时延函数表示为： d ( ，沪d ，勺，巧) ，v j = d ( ，川= | c ( f 刊，= 卜一，聊 这罩嘭，。为库所f 的第k 个色彩色，。所对应的时延，记为 d 似= d 【6 叫) ，k = 1 i ， ( 2 ) 对于时间与变迁关联的t c p n ，变迁使能的条件与c p n 完全相同。 分两步进行： 变迁0 一开始激发，立即执行： v p ，木f ：m 、a i , h ) = m ( 口，。) 一，( 口，。，b ，。) ( 2 2 3 ) ( 2 2