（机械设计及理论专业论文）基于flexsim的自动化立体仓库仿真与优化.pdf

摘要 在介绍自动化立体仓库系统和离散事件动态系统建模方法的基础上，作者提 出了将p e t r i 网建模方法用于立体仓库建模的研究，并采用f l e x s i m 物流仿真软 件对立体仓库系统进行仿真分析。 根据自动化立体仓库基本组成和作业流程，将自动化立体仓库剖析为入库、 存取、出库等三个子系统。通过对自动化立体仓库物流系统的整体分析，结合各 个子系统的机械配置及作业特点，提出了基于p e t r i 网的分层建模方法，建立了 入库、存取、出库三个子系统以及自动化立体仓库整体的p e t r i 网模型。本文构 建了上述子系统的变迁事件表，并采用p e t r i 网工作流的可达树法分析了各子系 统的一般模型。 本文借助f l e x s i m 物流仿真软件，完成了此自动化立体仓库叉车作业系统的 计算机仿真。作者通过对叉车作业模型的3 d 仿真，找出了该系统作业过程的“瓶 颈”所在，并提出了改进措施。通过对优化后模型的仿真分析，验证了改进措施 的有效性。 作者提出的将p e t r i 网法和f i e x s i m 物流仿真软件用于自动化立体仓库作业 流程的研究方法，同样适用于物流研究领域中其他具有随机动态特征的系统，为 物流系统的设计与评估提供参考依据。 关键词：自动化立体仓库；p e t r i 网；f l e x s i m ；建模；仿真；优化 a b s t r a c t b a s e do ni n t r o d u c i n gt h ea s r s ( a u t o m a t i cs t o r a g ea n dr e t r i e v a ls y s t e m ) a n d t h em o d e l i n gm e t h o d so ft h ed e 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 ) ，t h ea u t h o r b u i l d st h em o d e lo ft h ea s r su s i n gt h ep e t r in e t ，a n da d o p t ss i m u l a t i o ns o f t w a r eo f t h ef l e x s i mt oa n a l y z et h ea s r s b a s e do nt h ec o n s t i t u t ea n dt h et a s kf l o w , t h ea s r si sd i v i d e di n t os o m e s u b s y s t e m ss u c ha ss t o c k i n g ，p i c k i n g ，s t o c k - o u to p e r a t i o ns y s t e m a c c o r d i n gt ot h e r e s u l to ft h ea n a l y s i s ，t h ec h a r a c t e r i s t i ca n dt h ee q u i p m e n t so fi t ，t h el a y e r i n g b u i l d i n gm o d e li sp u tf o r w a r d a n dt h es u b s y s t e mm o d e l so ft h es t o c k i n g 、t h e p i c k i n ga n dt h es t o c k o u to p e r a t i o nw e r eb u i l t t h ea u t h o rt a l l i e du pt h ec h a n g e a f f a i r - f o r m so fe a c hs u b s y s t e m ，a n da n a l y z e dt h ec o m m o n l ym o d e lo ft h es y s t e m u s i n gt h ew o r k f l o wo ft h ep e t r i - n e ta n dt h er e s e a r c ht r e e s o m eo p e r a t i o np r o c e d u r e si na s r sa r es i m u l a t e do nt h r e e d i m e n s i o n a la n i m a t i o n u s i n gt h el o g i s t i c ss i m u l a t i o ns o f t w a r e 一一f l e x s i m a c c o r d i n gt ot h er e s u l to fs i m u l a t i o n ， t h e b o t t l e - n e c k p h e n o m e n o ni sd i s c o v e r e d m a n ym e a s u r e st h a tc a ne l i m i n a t et h i s p h e n o m e n o ni sp u tf o r w a r d i tp r o v e st h a tt h ei m p r o v e dm e a s u r e sa r ev a l i d i t yb y s i m u l a t i n ga n da n a l y z i n gt h ei m p r o v e dm o d e la f t e ro p t i m i z a t i o n t h ea u t h o rp u t sf o r w a r dt h er e s e a r c ha p p r o a c hu s e dt os t u d yt h ea s r so p e r a t i o n p r o c e d u r eb yp e t r i n e ta n df l e x s i m t h i sm e t h o di s s u i t a b l ef o rs t u d y i n gt h eo t h e r d y n a m i ca n ds t o c h a s t i cs y s t e m sa tl o g i s t i c sf i e l d ，a n dp r o v i d e sat h e o r yr e f e r e n c e a n dp r a c t i c a lf o u n d a t i o nf o rd e s i g n i n ga n de v a l u a t i n gl o g i s t i c ss y s t e m k e y w o r d s ：a s r s ；p e t r in e t ； f l e x s i m ； m o d e l i n g ；s i m u l a t i o n ；o p t i m i z a t i o n 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下进行的研究工作 所取得的成果。尽我所知，除文中已经特别注明引用的内容和致谢的地方外，本 论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做 出重要贡献的个人和集体，均已在文中以明确方式注明并表示感谢。本人完全意 识到本声明的法律结果由本人承担。 学位论文作者( 本人签 劳多月7 日 | 学位论文版权使用授权书 本学位论文作者完全了解南京林业大学有关保留、使用学位论文的规定，同 意学校保留并向国家有关部门或机构送交论文的复印件和电子版( 中国科学技术 信息研究所；国家图书馆等) ，允许论文被查阅和借阅。本人授权南京林业大学 可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以汇编和综合 为学校的科技成果，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论 文全部或部分内容。 保密口，在年解密后适用本授权书。本学位论文属于不保密口。 ( 请在以上方框内打“ ”) 学位论文作者c 本人签名晒渤辨 指导 教师( 本人签名) ：z 方锹 哆年 日 目 7 7 月 月 厂d r 致谢 在本文完成之际，向曾给予我帮助和支持的人们表示衷心的感谢。 感谢导师张沂泉教授在我读研期间的谆谆教诲和悉心指导。从课题的选择到论文的完 成始终得到导师的精心指导和不懈支持，论文的字里行间凝聚着导师大量的心血和汗水。 导师渊博的学识、严谨的学风、高尚的师德、科学的治学态度以及孜孜不倦的敬业精神深 深鼓舞着我，使我终身受益。 感谢林机教研室的各位老师对我的关心、支持和帮助； 感谢学弟葛坤明j 王旭焘在论文构思上所给予的帮助； 感谢同学余沛云、师弟谢锁文、师妹朱雯在课题研究和论文撰写过程中给予的帮助； 感谢实验室的沈仙法、王红星、王月梅等在学习、生活方面给予的帮助； 感谢读研期间关心、支持、帮助过我的老师、同学、朋友们； 最后，谨以此文献给我的父母和家人，他们一直以来对我的关心、支持和鼓励使我能 在学业生涯中百尺竿竞、扬帆远航，在此向他们表示最真挚的感谢。 作者：胡学刚 二o o 九年六月 1 1 研究背景和意义 1 1 1 自动化立体仓库概述 1 绪论 自动化立体仓库( a s r s a u t o m a t i cs t o r a g ea n dr e t r i e v a ls y s t e m ) 又称为自 动化高架仓库或自动存储系统，是一种基于高层货架，采用计算机进行控制管理， 采用自动化存取输送设备自动进行存取作业的仓储系统【l 】。自动化立体仓库由高 层货架、托盘或货箱、巷道堆垛机、输送机、a g v 自动导向小车、自动控制及仓 库管理系统( w m s ) 等组成。目前全国自动化立体仓库的保有量在3 0 0 座左右， 主要集中在烟草、医药保健品、食品、通信和信息、家具制造业、机械制造业等 传统优势行业。由于其具有存储量大、存储效率高、自动化和信息化水平高等优 点，越来越得到人民的广泛认同和普遍使用。 自动化仓库作为物流系统的一个核心和枢纽，是物流系统实现物流合理化的 关键所在。通常，一种产品要从原材料做成成品，再把成品作为商品，送到消费 者手中，需经过两个基本物流环节。前者是物流生产过程，如加工流水线，自动 生产线；后者是把商品送到消费者手中的物流流通过程。目前立体仓库系统主要 有两大应用领域，一是各种自动化生产线中的在线立体仓库系统；其二是各种物 资配送中心。货物从一个地方转移到另一个地方，单件运输是不经济的，成批的 和大量的组织运输有助于减少成本，而货物的等待就必须要由仓库来实现。自动 化立体仓库在物流中就充当这样一个货物储存的角色。 1 1 2 自动化立体仓库的建模与仿真 自动仓储系统是典型的离散事件系统。离散事件系统是指系统的状态仅在离 散的时间点上发生变化的系统，而且这些离散时间点一般是不确定的1 2 】。这类系 统中引起状态变化的原因是事件，通常状态变化与事件的发生是一一对应的。对 于自动立体仓库系统如将其分解成若干个相对独立又相互作用的实体，首先建立 这些实体的局部模型，然后按实体间的相互联系，连接局部模型来组成总体模型， 则相对容易。 现在被广泛使用物流系统建模方法主要有：g r a i 法、i d e f 法、g i m 法、s i m 法、a r i s 方法、p e t r i 网等。p e t r i 网是由德国的c a r la d a mp e t r i 博士于19 6 2 年 在他的博士论文中首次提出的，后来由p e t e r s o 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 理论的模型在物流系统的描述方面具有广 泛的应用前景。 仿真( s i m u l a t i o n ) 是对现实世界的过程或系统随时间运行的模仿，其应用 领域已经非常的广泛，已成为现代科学技术研究的主要内容，已渗透到各学科和 工程技术领域，物流学与物流技术领域也不例外1 3 】。在自动化立体仓库的筹建过 程中，如何对项目的可行性进行论证，如何寻求最佳设计方案，以及对预期建成的 项目如何进行总体性能评价，如何发现其中可能存在的问题等等，这些都可以通 过计算机仿真获得答案，从而节省大量的人力、物力、财力。利用计算机对立体 仓库进行建模与仿真，透过系统的三维动画，对系统进行实时跟踪与分析，是构 建自动化仓储系统的快捷有效手段。 在进行系统仿真时，首先要确定仿真的目标，也就是仿真要解决的问题：然 后是系统调研阶段，调研的目的是为了深入了解系统的总体流程、各种建模参数， 以便建立系统模型：最后进入实际建模阶段【2 】。总的说来可以将仿真过程分为三 个部分：系统分析阶段：仿真模型建立：仿真结果输出及分析。如图 卜1 所示： 仿真结构输出及分析 图1 - 1 建模过程 f i g u r e1 - 1m o d e l l i n gp r o c e s s 目前，比较有代表性的物流仿真软件有：a u t o m o d 、s i m a n i m a t i o n 、 s h o w f l o w 、f l e x s i m 、e x t e n d 、w i t n e s s 、p r o m o d e l 、a r e n a 、q u e s t 、e f a c t o r y 等。 这些软件不仅包括建模、仿真运行和结果输出，还包括模型分析、系统规划设计 和统计分析等功能。 2 f l e x s i m 是一套系统仿真模型设计、制作与分析工具软件。它集计算机三维 图像处理技术、仿真技术、人工智能技术、数据处理技术为一体，专门面向制造、 物流等领域。运用f l e x s i m 系统仿真软件，可在计算机内建立研究对象的系统三 维模型，然后对模型进行各种系统分析和工程验证，最终获得优化设计或改造方 案。f l e x s i m 是新一代离散事件系统仿真的有效工具。在f l e x s i m 的支持下，建 模过程变得十分简便。只需通过图形的拖动和必要的附加程序就可以快速的建立 系统的模型。软件提供了处理器、操作员、吸收器、堆垛机、货架、暂存器等多 种物理单元，用户可根据仿真对象的构成选取其中的物理单元，方便的建立起系 统的物理模型。物理模型可以用三维动画表现出来。 1 1 3 自动化立体仓库的优化 优化是科学研究、工程技术和经济管理等领域的重要研究工具，它所研究的 问题是讨论在众多的方案中寻找最优方案。例如，工程设计中怎样选择设计参数， 使设计方案既满足设计要求又能降低成本；资源分配中，怎样分配有限资源，使 分配方案既能满足个方面的基本要求，又能获得好的经济效益；在人类活动的各 个领域中，诸如此类，不胜枚举。优化正是为这些问题的解决，提供了基础和求 解方法。 仿真模型只是对问题的直观描述，系统仿真方法不是一种系统优化的方法， 仿真结果仅提供一定策略下的可行方案，它并不是问题的最优解。但是，系统仿 真可以让人们依据对系统模型动态运行的效果，多次修改参数，反复仿真，或者 说，系统仿真是一种间接的系统优化方法。但对于多目标、多因素、多层次的系 统来说，优化只是相对的，因此，我们不单纯追求最优解，而是寻求改善系统行 为的途径和方法，而系统仿真正是提供了这种环境。对于多参数的系统，单纯靠 人工修改参数的方法来达到系统的优化是非常困难的，因此，需要将某些优化方 法引入仿真系统，形成一个独立的优化模块，使仿真的结果不断得到改进1 7 j 。 通过对自动化立体仓库的仿真输出的研究，找出影响系统运行效率的因素， 优化系统的配置，提高系统的效率。 1 2 国内外研究现状 1 2 1 国外研究现状 相对来说，国外对物流的研究时间更长，已经形成一个比较完整的体系，目 前研究的重点主要集中于整个供应链或者物流链的管理和控制。j a c k ( 2 0 0 0 ) 提 出了对食物供应链的动态行为进行建模分析的方法，应用离散事件系统仿真方法 对供应链设计方案进行了系统评价，其建模方法基于企业过程的概念，仿真模型 则是基于时序有色p e t r i 网进行构造【8 】。e j a c kc h e n ( 2 0 0 2 ) 等人运用离散事件 建模的方法研究了化工企业的物流行为，通过对系统的仿真，测定出允许化工制 造业连续作业的物流作业能力1 9 】。m a r c oa d u r a n ( 2 0 0 4 ) 等人设计了一种用于 决策支持物流系统的建模仿真算法。这种方法可以研究和改善存储运输系统的 最优化问题，此算法将离散事件建模和随机优化控制相结合，统一的建模构架使 建模模型和控制器一体化。采用这种算法可以使决策者了解动态随机系统的行 为，是评价不同策略系统的有力工具【l0 1 。a o y a m a y u k o 等( 2 0 0 5 ) 分析了物流 产业的模式和最近发展趋势，特别强调了企业到企业的电子商务的影响，建立了 一个包含物流以及信息流两个内部连接网络的最优化模型，应用蒙特卡洛仿真法 突出了物流产业中对企业到企业的电子商务影响反应较大的环节，并且通过仿真 找到了在物流企业中影响信息和运输费用的因素【l1 1 。a n ap a u l ai a n n o n i ( 2 0 0 6 ) 采用离散系统建模的方法对农产品加工业中原材料的运输问题进行研究，着重分 析了车辆在多种队列情况下的等待时间，并以甘蔗作物为例，分析了系统的作业 进程，研究了作业过程中设备的配置【l2 。 在配送方面，对配送中心，特别是配送中心各个子系统的研究也越来越多。 新加坡国立大学的t e o c h u n gp i a w 等( 2 0 0 1 ) 用建模分析的方法研究了当多个 配送中心合并成为一个配送中心时，设备投资和库存成本方面受到的影响，同时 指出如果需求是恒定而独立的，那么合并会导致整体设备投资和库存成本下降并 且按不恒定的p o i s s o n 分布变化【l 引。p e t e r s e n c h a r l e s g 等( 2 0 0 4 ) 对物流分拣 系统研究时，为了提高拣选效率采用分类储存的方法，把货物分为几个等级，并 把储存地点分为几个面积块，同时应用仿真方法验证了这种储存方法在实际应用 中的可靠性【l4 1 。c h i n c h i a j a n e 在分析配送中心的分拣系统时，为了平衡每个分 拣者的工作负担，保证整个分拣系统能连续运行，提出了基于消费定单启发式的 储存方法，并应用经验公式和仿真实验给予验证，通过仿真来调整不合理的储存 位置来平衡每个分拣者的工作负担提高分拣效率引。f r a n c e s c op a r o l a 和a n n a s c i o m a c h e n ( 2 0 0 5 ) 介绍了一种适用于研究港口物流系统的离散事件建模仿真方 法，基于这种方法对意大利西北港的物流联合运输网络进行研究，通过对模型的 分析，估测出集装箱物流量的增长速度，此外还对模型中元素的配置以及参数设 置问题进行讨论【l9 1 。d e m e t r i ol a g a n f i 等( 2 0 0 6 ) 对集装箱码头物流系统进行研 究，采用基于网格计算的方法对系统进行最优化的模拟，得到了物流过程的排队 网络模型，此外还设计了分配系统进程的并行处理机【2 o 。 1 2 2 国内研究现状 当前，国内的学者大多采用建立基于p e t r i 网的网络模型的方式来研究物流 系统，研究对象还主要是生产物流，其基本思想是用库所集p 代表系统中实体和 活动的状态，用变迁集t 代表系统中的事件。昆明理工大学的詹跃东( 2 0 0 1 ) 等 应用p e t r i 网理论，对烟草行业的卷接包车间的a g v s 构造了p e t r i 网模型，并 进行了仿真研究 2 1 】。山东大学控制科学与工程学院的田国会( 2 0 0 1 ) 基于面向 对象着色p e t r i 网模型和时态逻辑方法，对自动化仓库输送系统运行过程的调度 问题进行研究，建立了系统的面向对象着色网模型，并讨论了该过程的死锁问题， 4 给出了系统行为的时态逻辑规范和死锁避免的最大允许反馈控制策略 2 2 - 2 4 】。南 京师范大学的彭晨等( 2 0 0 3 ) 应用p e t r i 网对供应链物流及供应流运行过程进 行建模，用于分析煤炭供应链存在的问题，最后供应链决策过程的可视化仿真， 找出煤炭供应链运营瓶颈【2 5 1 。山东大学的李歧强等( 2 0 0 3 ) 提出了一种三色p e t r i 网，给出了三色p e t r i 网的基本定义，分析了该种p e t r i 网的性质及建模方法，并 对自动分拣系统中的物流控制进行了建模，作了一致性、活性、有界性和安全性 分析1 2 引。上海交通大学自动化研究所李霄峰等( 2 0 0 1 ) 针对宝钢炼钢连铸物流 系统及制造业的复杂物流系统，提出用分层有色p e t r i 网对物流系统进行建模， 并运用组件对象模型( c o m ，c o m p o n e n to b j e c tm o d e l ) 技术实现仿真子模型，使 得物流仿真系统具有很好的灵活性和可扩展性，为企业生产计划调度( p r o d u c t i o n p l a n n i n g a n d s c h e d u l i n g ) 、资源调度等物流管理提供了一种很好的仿真设计模 式【2 6 - 29 1 。 在现代物流系统中，仓储系统是集物流、信息流和资金流于一体的流通型节 点，是现代物流的重要组成部分，对于仓储系统，特别是仓储系统内部具体作业 环节的研究也越来越多。上海海事大学的李纬韬( 2 0 0 4 ) 研究了仿真技术在物流 仓储系统设计中的应用，对仓储规模的确定、仓储作业区的规划、储位管理系统、 拣货管理系统进行了设计、仿真及优化【3 0 】。山东科技大学的李宝顺( 2 0 0 4 ) 在 其硕士论文中采用遗传算法对自动化仓储系统中的库位优化问题和堆垛机优化 调度问题进行了优化研究】。武汉理工大学的王薇( 2 0 0 4 ) 对华中物流公司的 仓储系统进行研究分析，提出仓库储区规划和货物储放的原则和方法，建立了新 的仓库货位管理模型，并对储位进行优化设计；分析了仓库现有组织作业流程和 运营模式，提出由于其信息技术运用不足所产生的总体效率不高等问题”2 1 。东 华大学的初玲玲( 2 0 0 5 ) 以宝钢化工有限公司的仓储业务为实例，针对化工行业 独特的特点，对仓储业的几个关键要素进行分析并建立数学模型【3 3 】。武汉理工 大学的陈思云等( 2 0 0 5 ) 运用p e t r i 网对一个简化的仓库系统作业情况进行建模 仿真，并简单地分析了仿真的运行结果【3 4 1 。武汉理工大学的刘大平( 2 0 0 5 ) 通 过研究物流自动化存取过程中的交互控制，实现了仓库存取的自动化、提高了设 备的可靠性 3 5 1 。大连海事大学的邵琳( 2 0 0 5 ) 在其硕士论文中对立体仓库中堆 垛机作业循环时间的数学计算进行了推导，在自动化仓库的货位指派问题中，将 货位的优化与指派问题相结合，建立相应的数学模型，并给出了解法【36 1 。山东 大学的田国会，刘长有等( 2 0 0 6 ) 针对某自动化主体仓库的实际运行过程，提出 了影响立体仓库运行效益的若干优化调度问题，分别采用p e t r i 网、时态逻辑、 模拟退火、遗传算法、神经网络等方法结合计算机仿真技术进行了研究，给出了 新近研究进展【37 1 。山东大学的朱耀明( 2 0 0 6 ) 在其硕士论文中根据立体仓库货 位的特点，建立了货位网格结构模型，该模型实现了货位稳定、出入库频率、作 业时间三方面优化的合理组合，并运用遗传算法实现多目标的优化【38 1 。 基于f l e x s i m 的研究现状，北京邮电大学肖江波，杨福兴( 2 0 0 7 ) 在基于 f l e x s i m 仿真的物流配送中心优化探讨中以某物流配送中心为例，探讨了物流配 5 送中心规划中的规模确定、功能布置方案以及装卸工作对配送中心仓库布局的要 求，配送中心仓库建筑物的位置布局等要求p 引。常鹏( 2 0 0 7 ) 基于f l e x s i m 对 散货码头物流系统建立了散货码头设备的三维模型并对其进行了仿真研究1 4 叭。 武汉理工大学于蒙，王少梅，肖峰( 2 0 0 7 ) 利用三维离散事件仿真软件f l e x s i m 建立集装箱码头装卸作业仿真模型，为生产管理者提供视觉上的决策支持，利用 其核心机制一任务序列驱动设备模型，实现装卸作业过程的三维动态仿真h 。李 俊等( 2 0 0 7 ) 从企业仓储作业中出入库调度策略的需求出发，利用面向对象建模 理论和f l e x s i m 仿真软件进行入库策略的建模。给出一种将复杂策略结果映射到 仿真模型的方法并将其应用与仿真实例中。最后比较两种策略下的仿真运行结 果，并进行比较分析得到两种策略的适用范围为企业选择调度策略提供依据1 4 2 。 1 3 本文研究的主要内容和技术路线 1 3 1 本文的主要内容 本文在对南京某电器物流中心立体仓库实况调研的基础上，明确了自动化立 体仓库系统的运作模式，内部各设备的作业工况及系统的运行效率。采用p e t r i 网理论建立了该自动化立体仓库系统运行的模型，使用f l e x s i m 物流仿真软件完 成局部建模仿真，并依据仿真结果分析找出配置不合理的因素，优化系统配置， 提高了仓储系统的合理性。 ( 1 ) 以南京某自动化立体仓库为载体，分析立体仓库出入库作业过程，以及 各设备之间的逻辑关系，建立入库作业、存取作业和出库作业p e t r i 网模型，及 立体仓库总体模型。 ( 2 ) 使用f l e x s i m 仿真软件建立该自动化立体仓库叉车作业系统的3 d 模型， 并对其运行结果进行分析；以此进一步探讨使用f l e x s i m 建模仿真的一般方法。 ( 3 ) 以仿真输出的系统性能指标为依据，找出配置不合理的因素，优化系统 配置，提高系统的运行效率。 1 3 2 技术路线 本文结合南京某电器物流中心立体仓库平面布置、商品资料、仓库设施设备 布置、仓库区位分配、进出库作业流程等情况，采用p e t r i 网理论及f l e x s i m 仿 真软件对自动化立体仓库进行建模仿真，分析立体仓库现状，指出其中不合理之 处，提出可行的优化方案。通过与优化之前的方案比较，验证优化方案的合理性。 技术路线如图1 - 2 所示 6 图1 - 2 技术路线图 f i g u r e1 - 2t e c h n i c a lr o a dm a p 7 2 离散事件系统及p e t ri 网 2 1 离散事件系统及其建模方法 2 1 i 离散事件系统 当系统的状态空间描述为诸如 0 ，1 ，2 ，) 或者 高，中，低 这样的离散 集，状态转移仅仅发生在离散的时间点上，我们将状态的转移与“事件”( e v e n t ) 相联系，从而导致所谓的“离散事件动态系统”( d i s c r e t ee v e n td y n a m i c s y s t e m d e d s ) 或者“离散事件系统”( d i s c r e t ee v e n ts y s t e m d e s ) 1 4 7 严格的说，对于离散时间为动态系统，至今还没有一个具有概括性地和普遍 性并被一致认同的定义。粗略地说，d e d s 是有离散事件驱动，并有利于事件按 照一定运行规则相互作用，导致状态演化的一类动态系统。 在立体仓库系统中，“货物到达”和“货物离开”就是一些典型的离散事件。 在d e d s 中，一个离散事件的发生驱动系统状态发生变化，同时还会按照系统的 运行规则在系统中激发新的离散事件，从而形成系统状态的演化过程。例如，“货 物到达”事件会改变入库台的状态及激发入库活动开始，入库活动的开始会引起 各种搬运装卸机械工作，而搬运装卸机械工作又会改变货位、库存的状态。事件 持续传递和变换，演绎着仓储系统的动态行为。由此可见，物流仓储系统是典型 的离散事件动态系统。 不同于连续变量动态系统( c o n t i n u o u sv a r i a b l ed y n a m i cs y s t e m s ，c v d s ) ， d e d s 的系统状态是由一批符号和离散变量表征，而且状态只能在离散时间点上 瞬时发生变动；状态的转换或事件的发生具有一定的序列性；事件或过程的发生 具有异步性和并发性：存在冲突、互斥、死锁现象，状态演化过程中具有不确定 性【49 1 。在特性表征上，离散事件动态系统与连续变量动态系统存在着明显的差 异，但是在研究方法上对d e d s 的研究也需要建立模型，通过对所建立模型的分 析，了解系统内部的运行规律，发现系统运行过程中的各种要素之间的相互关系， 分析系统的行为和效果，找出改进系统的途径和方法，并对改进后的系统进行评 价。 2 1 2 离散事件系统的建模方法 正如连续系统一样，研究d e d s 需要建立模型，模型反映了系统主要行为特 征的变量与系统结构参数之间的一种关系【5 0 1 。模型可采用数学方程、曲线、图 表、计算机程序等多种形式表征。基于系统的模型，可分析系统的行为性能及其 与系统结构和参数的关系，研究系统的控制和优化。不同于通常的c v d s ，d e d s 的动态特性无法用微分方程或差分方程来描述。系统的分析模型主要建立在随机 8 过程、运筹学、控制论、人工智能与自然语言等多学科的基础之上。 在d e d s 的研究中，常把d e d s 的模型和分析分为三个基本的层次，即统计 性能层次、代数层次和逻辑层次【5 。从统计性能层次研究d e d s 过程性能的研 究方法有：广义马尔柯夫过程、排队网络、摄动分析等；从代数层次研究d e d s 的运动过程及其特性的建模方法有：极大极小代数、有限递归过程、通讯序贯过 程等；从逻辑层次研究d e d s 中事件状态相互作用的序列的建模方法主要有：形 式语言与自动机、马尔柯夫链、p e t r i 网等。在研究过程中，一般用事件和状态 两个基本因素表征d e d s 。状态常用一些离散符号标记，状态空间不需要任何的 拓扑结构。事件则按系统以外的因素所确定的某种机制离散地瞬时地发生，并导 致状态的转移。 d e d s 模型和分析的性能统计层次，着眼于在性能层次上研究随机情况下 d e d s 的各种平均性能及其优化。从统计层次研究d e d s ，主要集中于d e d s 随 机品质分析和优化。通常采用随机分析法、仿真分析法和扰动分析法，以及运行 分析法、平均值分析法和近似分析法等方法分别来研究排队网络、广义马尔柯夫 过程等随机模型。其中，排队网络是在单级随机服务系统的排队模型基础上发展 起来的，两者统称排队论或随机服务系统。它是由若干个服务中心按一定的网络 结构所组成的一个系统。服务中心由顾客和服务台所构成，通常一个服务中心拥 有一个或多个服务台。19 7 7 年s o l b e r g 首次将排队网络理论用于d e d s 的建模， 其模型假定服务台的服务时间为指数分布，被服务对象是同一类型。与d e d s 的其他类型的模型相比，排队网络的优点是能够考虑系统中的各随机因素，并能 够较为细致地描述系统内部的各种复杂关系，基于排队网络的模型，易于从概率 和统计的角度分析和优化d e d s 的过程性能，它还具有解析形式的解，能得到定 量的结果。排队网络方法的主要局限性是所研究的排队系统引入的假设条件过 强，且只能描述系统的稳态性能和平均性能【52 1 ，而且对所用的概率模型有很大 的限制。 d e d s 模型和分析的代数层次，着眼于在物理时间层次上来研究d e d s 的代 数特性和运动过程，采用的主要数学工具有极大代数法等。极大代数法是由q c o h e n 等人于19 8 5 年提出的，以极大代数为工具，将制造系统视为确定性系统， 根据系统的运行关系建立起一系列事件发生的时间状态方程，分析其特征值，得 出加工设备、运输设备的工作周期、利用率等指标。极大代数法主要研究的是系 统的稳定性和周期性稳态问题。它的优点在于模型的线性形式易于处理物理时 间，理论体系严格完整，比较适合于串行生产线的d e d s 的建模和分析。缺点是 处理问题的范围较窄，当系统比较复杂时，系统模型的维数较大，计算困难。 d e d s 模型和分析的逻辑层次，着眼于在逻辑层次上研究d e d s 中事件和状 态的符号序列关系。在逻辑层次上，基本问题归结为研究事件和状态按逻辑时间 的序列，而不涉及物理时间问题。这样p e t r i 网、有限自动机【53 】等这些具有很强 逻辑功能表征能力的工具，对于描述和研究这些要素以及逻辑序列，无疑是非常 恰当的手段。其中，p e t r i 网是由德国学者c a p e t r i 于19 6 2 年提出的一种用令 9 牌( t o k e n ) 流动描述系统动态过程的网络。用p e t r i 网对d e d s 进行描述时以图 形方式描述系统，可使系统的复杂逻辑关系形象化，利于理解；可以分层次建立 p e t r i 网模型，适合描述d e d s 的分布式递阶结构；不仅可以描述d e d s 的静态 特征，而且可以描述d e d s 的动态行为；既可以描述系统内部的数据流，又可以 描述系统内部的物质流；通过变迁发生的机制，可以描述系统内部的并发性、竞 争性。p e t r i 网法的主要局限性是当d e d s 为一个复杂的大系统时，p e t r i 网规模 庞大、描述混乱，并可能引起“状态组合爆炸”问题，给分析带来困难。 利用p e t r i 网可对d e d s 进行性能分析，基于事件图，可以分析一类制造系 统的运行性能，如稳定性、运行周期、生产节奏的协调性等。利用可达树方法， 可讨论系统出现不希望状态( 如死锁) 的可能性。采用不变量技术，可研究系统 运行过程中错误的检测与局部或全局各子过程( 操作) 间的相关性等问题。对 p e t r i 网有界性( 安全性) 的分析，可反映系统是否会出现缓冲区“溢出、工件 发生“碰撞”等现象。回归性体现了系统运行的重复性( 周期性) ，而活性分析 表示了系统是否可以正常连续运行的问题。对含有反馈控制的闭环系统进行活性 分析，则反映了控制机制是否会影响系统正常运行的问题。利用一些化简或细化 规则，可以通过一些局部子系统的性能分析及子系统间相互连结方式的讨论，近 而直接评估整个系统的全局性能，避免了同时分析整个系统性能可能遇到的复杂 结构、维数灾难和计算复杂性等问题。由于p e t r i 网的通用性和随意性，它几乎 可应用于一切可用图形表示的系统。它比有限自动机形式语言模型更好地描述 了系统内部的逻辑关系，特别适用于描述并发、异步和冲突等现象。鉴于以上优 点，它作为系统建模和分析的一种有效工具越来越受到重视，基于p e t r i 网模型 的计算机仿真方法引起人们越来越大的兴趣。 2 2p e t r i 网理论 p e t r i 网是德国学者c a r la p e t r i 于19 6 2 年在其博士论文中提出的一种用于 描述事件和条件关系的网络。p e t r i 网是一种用简单的图形表示的组合模型，具 有直观、易懂和易用的优点，它能够较好的描述系统的结构，表示系统中的并行、 同步、冲突和因果依赖等关系，并以网图的形式，简洁、直观的模拟离散事件系 统，分析系统的动态性质【5 4 1 。p e t r i 网有严格而准确定义的数学对象，可以借助 数学工具，得到p e t r i 网的分析方法和技术，并可以对p e t r i 网系统进行静态的结 构分析和动态的行为分析。目前p e t r i 网已成功地应用于有限状态机、数据流计 算、通信协议、生产系统等的建模中，成为离散事件系统的主要建模工具。 2 2 1p e t r i 网概述 2 2 1 1 基本术语 资源( r e s o u r c e ) 资源指的是与系统状态发生变化有关的因素。例如原料、 零部件、产品、工具、设备、数据以及信息。 状态元素( e l e m e n t s ) 资源按照在系统中的作业分类，每一类放在一起，则 这一类抽象为一个相应的状态元素。 库所( p l a c e ) 状态元素就称为库所。它表示一个场所，而且在该场所存放 了一定的资源。 变迁( t r a n s i t i o n ) 变迁指的是资源的消耗、使用以及对应状态元素的变化。 条件( c o n d i t i o n ) 如果一个库所只有两种状态：有标记和无标记，则该库所 称为条件。 事件( e v e n t ) 涉及条件的变迁成为事件。 容量( c a p a c i t y ) 库所能够存储资源的最大数量称为库所的容量。 2 2 1 2p e t r i 网的数学定义 p e t r i 网是由节点和有向弧组成的一种有向图。用圆圈“o 表示库所，用 段竖线“l 或矩形框“口表示变迁，用有向弧表示从库所到变迁的序偶( p ，t ) ， 或从变迁到库所的序偶( t ，p ) 。 定义1 一个p e t r i 网是一个三元组n = ( 只乃力，式中， 尸和丁分别是库所和变迁的有限集，满足尸n 产函和p u 降圆，a 表示空集； 尸是由一个p 元素和一个丁元素组成的有序偶的集合，叫做流关系，满足 f e 尸丁u 丁只是两个的集合的直积运算； 令f 所含有序偶的第一个元素和第二个元素所组成的集合分别为d o m ( 尸) 和c o d ( 尸) ，满足d o m ( ，) uc o d ( 尸) = p u 乃不属于d o m ( 尸) 和c o d ( 尸) 的元 素叫做孤立元素。一个p e t r i 网可以表示成如图2 1 所示的图形，图中的p e t r i 网包括5 个库所和3 个变迁。 p l n ( 、一广一 p 2 t 2 p 4 1 图2 - 1 一个简单的p e t r i 网模型 f i g u r e2 - 1as i m p i ep e t r in e tm o d e l 定义2 设p c 丁和芒乃令。护 p l ( p ，手) 月为变迁t 的输入库所集， 方。= p i ( 芒，p ) 月为变迁t 的输出库所集。图2 1 所示的p e t r i 网用公式可写 成胆( 只乃尸) 。其中，库所集卢 a ，见，胁，p 4 ，协) ；变迁集产 芒。，乙，芒。) ；流关系 户 ( p 。，舌。) ，( t 。，乜) ，( f 。，p 3 ) ，( 见，t z ) ，( p 3 ，如) ，( p 3 芒3 ) ，( 乙，p 4 ) ，( p 4 ，t s ) ，( 芒s ，p 5 ) ) 。 定义3 设胪( 只乃尸) 为有向图， ( 1 ) 记为上的容量函数，它是库所到正整数集的映射瓜卜 1 ，2 ，) ； ( 2 ) 记为的一个标识，它是一个从库所到非负整数集的映射胚尸_ 1 ， 2 ，) ，且满足v p 尸，p ( p ) k ( p ) ； ( 3 ) 映射厩卜 l ，2 ，) 称为n 的权函数，它对各弧线赋权，用甜( p ，f ) 或甜( f ，p ) 表示由p 指向t 或t 指向p 的有向弧的权重。弧线都用其权重来标 注，如果弧线的权重等于1 ，则标注可以省略。 定义4 ( 变迁条件) 设六元组= ( 只乃只丘彬肋为一p e t r i 网系统。对于 t 乃如果在标识彤下，有 p e 。t ，肜( 力甜( p ，t ) p et 。，肜( p ) ( d 一( f ，p ) p et 。，八p et 。，( 力 ( 力+ u ( n 手) 一甜( t ，力 则称t 在下有效，记作所t 0 。 定义5 ( 变迁规则) 若t 在下有效，则t 就能发生。发生后，变成如下 定义的新标识，对v p p ， f肜( p ) 一甜( p ，芒) p e 。t l肜( p ) + 甜( 芒，p ) p e 舌。 肛 l肜( p ) + 甜( t ，p ) 一翻( p ，f ) p e 。芒入p et 。 i( p )其它 这里，t 的发生把标识变成，记作觚 ，叫做的后继标识。 2 2 1 3p e t r i 网的类型及特点 ( 1 ) p e t r i 网的类型 基本p e t r i 网。在最简单的p e t r i 网系统中，规定网中每一个库所的容量为 1 其库所也可以称为条件，变迁称为事件，所以基本的p e t r i 网又称为条件事件 系统，简称为c e 系统。 低级p e t r i 网。如果网中每一个库所的容量和权重为大于等于l 的任意整 数，这样的p e t r i 网称为库所变迁网，简称为p 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 网可以简化复杂的网络模型，表达更多的信息。 ( 2 ) p e t r i 网的特点 能够很好的描述和表达离散事件动态系统( d e d s ) 建模中经常