（计算机软件与理论专业论文）基于活动资源时间图模型的过程仿真系统研究.pdf

兰竖堕生二兰生查兰篁堕塑王堡垫堕塑堕囹堕堡型盟垫矍堕塞墨竺竺塞一生坐查兰堡主笙苎! 唑 基于活动资源时间图模型的过程仿真系统研究 计算机软件与理论 硕士生：刘洪涛 指导老师：李磊教授 摘要 企业的业务流程是非常复杂的，在为企业设计与流程相关的软件的失败率很 高，原因在于所设计的软件处理的流程与企业实际运行的流程不相符合。针对该 问题，本文采用一阶逻辑形式化的描述了一个过程仿真系统模型，使得该过程仿 真系统具有一定的通用性。并根据该逻辑模型开发了一个过程仿真系统，用于检 验所仿真的流程是否与实际流程相符合。通过将企业实际运行结果数据与仿真系 统的输出数据进行比较，可以判断流程是否符合企业实际业务处理过程。该过程 仿真系统采用了本文提出的活动资源时间图模型，用于描述企业业务流程；采 用融合事件调度法和活动扫描法的仿真策略进行仿真；采用推理机处理业务流程 的逻辑关系；并且在其中应用v a d ( v a l u e - a s s i g n m e n t d e l a y ) 启发式、优先级指导冲 突活动的调度，以此实现了一个离散事件过程仿真系统。本文提出的活动资源 时间图模型是本文提出的一种新的离散事件系统建模方法，能够很好地描述业务 处理流程，有效地解决了复杂流程的描述问题。最后于以上原理，完成了基于 活动资源时间图模型的过程仿真原型系统的设计与开发。 关键字：活动资源时间图模型，过程仿真系统，v a d 启发式 型堡堡皇些查兰竺生堕 墨主堡垫! 童塑! 堕塑圈堡型箜塾垄堕塞至竺旦窒! 生查兰堡圭笙壅! 塑! p r o c e s ss i m u l a t i o n s y s t e m b a s e do n a c t i v i t y r e s o u r c e t i m e g r a p h c o m p u t e r s o f t w a r ea n d t h e o r y n a m e ：l i u ，h o n 【g t a o s u p e r v i s o r ：p r o f e s s o r l i ，l e i a b s t r a c t e n t e r p r i s eb u s i n e s sp r o c e s s si sv e r yc o m p l e x ，a n dt h ef a i l u r er a t eo fd e v e l o p i n g s o f t w a r ef o re n t e r p r i s ei sv e r yh i 曲t h er e a s o ni st h en oc o n s i s t e n c yo fb u s i n e s s p r o c e s so fs o f t w a r ed e a l e da n de n t e r p r i s et u n e d f o rt h ep r o b l e m ，t h et h e s i su s e dt h e l o g i ct of o r m a l l yd e s c r i b eae n t e r p r i s eb u s i n e s sp r o c e s sm o d e l ，a n d m a d et h em o d e lt o h a v eau n i v e r s a lp r o p e r t y a tt h es a m et i m e ，ae n t e r p r i s eb u s i n e s sp r o c e s ss y s t e mw a s d e v e l o p e di nt h eb a s eo fl o g i cm o d e lt o v e r i f i e sw h e t h e rt h es i m u l a t e dp r o c e s si s c o n s i s t e n tw i t h e n t e r p r i s e r e a l p r o c e s s t h r o u g h t h e c o m p a r e o fr e a l e n t e r p r i s e r u n n i n gd a t aa n d t h es y s t e mo u t p u td a t a , w ec o u l dv e r i f yw h e t h e rt h ei n p u tb u s i n e s s p r o c e s sa c c o r dw i t ht h e r e a l e n t e r p r i s e b u s i n e s sp r o c e s s t h ep r o c e s ss i m u l a t i o n s y s t e ma d o b e dt h ea c t i v i t y r e s o u r c e t i m eg r a p hm o d e li n t i d d u c e db yt h e t h e s i s w h i c hd e s c r i b ee n t e r p r i s eb u s i n e s sp r o c e s s ，a d o b e das i m u l a t i o ns t r a t e g yb a s e do n c o m b i n a t i o no fe v e n t s c h e d u l i n g a n d a c t i v i t ys c a n n i n g m e c h a n i s m ，a d o b e d a r e a s o n i n g m a c h i n et od e a lw i t hb u s i n e s s l o g i c i n t h es a m e t i m e ， v a d ( v a l u e - a s s i g n m e n td e l a y ) h e u r i s t i cw a sa p p l i e d t od i r e c tc o n f l i c ta c t i v i t i e s s c h e d u l i n gp r o b l e m b a s e do nt h i sm e t h o d ，ad i s c r e t ee v e n ts i m u l a t i o ns y s t e mw a s b u i l t t h ei n t r o d u c e da c t i v i t y r e s o u r c e t i m eg r a p hm o d e l i n gm e t h o di s an o v e l m e t h o do nd i s c r e t ee v e n td y n a m i cs y s t e m i tc a nd e s c r i b eb e t t e rc o m p l e xb u s i n e s s p r o c e s sa n de f f e c t i v e l yr e s o l v e dt h ed e s c r i b i n gp r o b l e m o fc o m p l e xp r o c e s s a tl a s t ， t h ed e s i g na n dd e v e l o p m e n to ft h eo b j e c to r i e n t e dp r o c e s ss i m u l a t i o np r i m i t i v es y s t e m i sf i n i s h e d k e yw o r d s ：a c t i v i t y r e s o u r c e t i m eg r a p h 、p r o c e s s s i m u l a t i o n 、v a dh e u r i s t i c i l 刘洪涛 中山大学软件所 基于活动资源时间图模型的过程仿真系统研究中山大学硕士论文2 0 0 4 0 1 论文主要内容 - j l 刖 吾 企业的业务流程是非常复杂的，在为企业设计与流程相关的软件的失败率很 高，原因在于所设计的软件处理的流程与企业实际运行的流程不相符合。针对该 问题，本文采用一阶逻辑形式化的描述了一个过程仿真系统模型，使得该过程仿 真系统具有一定的通用性。并根据该逻辑模型开发了一个过程仿真系统，用于检 验所仿真的流程是否与实际流程相符合。通过将企业实际运行结果数据与仿真系 统的输出数据进行比较，可以判断流程是否符合企业实际业务处理过程。该过程 仿真系统采用了本文提出的活动资、源时间图模型，用于描述企业业务流程：采 用融合事件调度法和活动扫描法的仿真策略进行仿真；采用活动推理机处理业务 流程的逻辑关系；并且在其中应用v a d ( v a l u e a s s i g n m e n td e l a y ) 启发式、优先级 指导冲突活动的调度，以此实现了一个离散事件过程仿真系统。本文提出的活动 资源时间图模型是本文提出的一种新的离散事件系统建模方法，能够很好地描 述业务处理流程，有效地解决了复杂流程的描述问题。最后基于以上原理，完成 了基于活动资源时间图模型的过程仿真原型系统的设计与开发。 0 2 论文组织 全文共分七个章节。 本文第1 章首先介绍仿真技术历史背景、概念与发展，以及本文所研究的问 题的背景及其意义。 第2 章介绍了离散事件系统仿真原理、以及本文在过程仿真系统中采用的仿 真策略： 第3 章对企业过程仿真模型一活动资源时间图模型和基于v a d 启发式的资 源分配算法进行了详细的阐述，并将该模型与一些其它模型进行了比较。 第4 章采用一阶谓词逻辑形式化给出了过程仿真系统逻辑模型。 第5 章给出了基于活动资源时间图模型的过程仿真系统的详细设计、仿真 策略算法及体系结构。 第6 章以中山华帝e r p 系统的实际制造流程作为实例，检测该系统的验证 能力和实用性。 最后第7 章，对所做的工作进行了总结，介绍了下一步将要做的工作。 v 型堂塑坐查兰竺堡垦茔于活动，资源肘问图模型的过程仿真系统研究中山大学硕士论文2 0 0 4 第1 章背景 1 1 系统仿真历史、基本概念及分类 系统仿真历史【1 】 早期仿真技术主要采用模拟计算机，它出现于2 0 世纪5 0 年代。5 0 年代末， 由于导弹技术和卫星技术发展的需要，出现了混合模拟机和混合计算机系统。自 7 0 年代末期起，数字仿真机已逐渐占领仿真计算机的主要市场。进入8 0 年代以 后，个人计算机的出现，再配上高性能的建模与仿真软件，已经受到仿真界的极 度重视。历史上第一个仿真软件是由塞尔弗里奇f r g s e l f r i d g e ) 在1 9 5 5 年开 发的。他完成了利用辛普森方法进行数值积分的仿真程序设计工作。从那之后， 仿真软件的发展经历了四个阶段： 第一阶段是从5 0 年代到6 0 年代初期，以f o r t r a n 语言为代表的通用程序设 计语言阶段。f o r t r a n 语言是达到成熟的第一个高级程序设计语言，当时几乎所 有用于求解数学表达式的程序都是用f o r t r a n 语言编写成的。即使在目前，也有 许多大型的通用仿真语言是基于f o r t r a n 语言编制的。 第二阶段是6 0 年代到7 0 年代，出现了多种仿真程序包及初级仿真语言。这 个时期仿真软件主要解决的问题是利用数字仿真方法求解常微分方程组。例如 1 9 6 1 年由贝尔实验室开发的用于实现数据采集系统仿真的面向框图的程序 b l o d i ( b l o c kd i a g r a mc o m p i l e r ) ，1 9 6 2 年为了工业动力学系统仿真专门开发的 语言d y n a m o ( d y n a m i cm o d e l s ) 。1 9 6 3 发表的用于求解常微分方程组的仿真 程序m i d a s ( m o d i f i e di n t e g r a t i o nd i g i t a la n a l o gs i m u l a t o r ) 等等。直到1 9 6 7 年， 为了促进已有的几十种数字仿真语言的标准化，美国计算机仿真学会s c s 提出 了c s s l ( c o n t i n u o u ss y s t e ms i m u l a t i o nl a n g u a g e ) 标准。在此阶段的仿真语言中， 比较典型的还有1 9 6 0 年由i b m 公司的g 戈登( g o r d o n ) 开发的对排队问题进行 仿真的仿真语言g p s s ( g e n e r a lp u r p o s e s i m u l a t i o ns y s t e m ) 。 第三阶段在7 0 年代到8 0 年代初期，出现了高级完善的商品化仿真语言。这 个阶段仿真语言比早期的仿真语言更加成熟和全面。 模型的表达能力 数值性能和算法 语言的结构特征 模型验证 型堂堕! 坐查兰软件所基于活动，资源时间图模型的过程仿真系统研究中山大学硕士论文2 0 0 4 程序执行方式 数据管理和处理能力 输入输出特性 例如在7 0 年代中期推出的算法全面，功能强大的求解常微分方程和差分方 程问题的仿真语言q s s l 一和a c s “a d v a n c dc o n t i n u o u ss i m u l a t i o n l a n g u a g e ) ，以及1 9 7 1 年推出的用于离散事件仿真的可以用类似自然语言自由格 式描述系统模型的仿真语言s i m s c r i p ti i 5 和应用广泛的随机网络建模的s l a m 仿真语言。 第四阶段是8 0 年代中期开始的体化建模与仿真环境研究。其背景是： 随着建模与仿真工作要求的提高，已开发的各种仿真软件经常不能协调 地工作 对仿真语言的要求越来越复杂 存在大量的数据处理及文档化工作 不同的用户( 建模者，仿真实验人员，决策者) 对仿真工具有不同的要求 计算机网络技术和数据库技术有较大的发展 一体化建模与仿真环境的主要性能表现在； 支持建模与仿真的全生命周期活动 集成化程度高 方便友好的用户接口 初步的知识处理能力 模型与仿真的质量保证措施 美国的p r i t s k e r 公司于1 9 8 4 年推出集成化建模仿真语言环境t e s s ，第一次 通过数据库系统将建模、仿真和输出结果分析有机地组成了一个完整的系统。 系统仿真基本概念【1 】 系统( s y s t e m ) 系统就是一些具有特定功能的、相互间以一定规律联系着的物体所组成的一 个总体。系统具有明确的整体性，各个部分不可分割；系统内部各部分之间相互 以一定规律联系着，它们的特定关系形成了具有特定性能的系统：系统具有有序 性和动态性。本文研究的企业过程系统是一个具有严密组织和时序关系的系统， 过程的各个组成活动的执行需要资源子系统的支持，其执行的先后时序受到业务 规则的控制。 模型( m o d e l ) 2 刘洪涛中山大学软件所 基于活动资源时间图模型的过程仿真系统研究中山大学硕：t 论文2 0 0 4 模型是人们为了研究和解决客观世界中存在的种种问题而对客观现实经过 思维抽象后用文字、图表、符号、关系式以及实体模样描述所认识到的客观对象 的一种简化的表示形式。简单的说，模型就是所描述客观对象的抽象表示。本论 文提出的活动资源时间图模型将企业过程各个静态部分抽象的分为活动和资源 两部分，活动的执行依靠资源的支持，在业务规则和时间的推动下，研究企业过 程的动态行为。 仿真( s i m u l a t i o n ) 系统仿真，是设计一个实际系统的模型，对它进行实验，以便理解及评价系 统的各种运行策略，其基础是建立在系统的数学模型上，并以计算机为工具对系 统进行实验研究的一种方法。仿真，就是模仿真实事物，也就是用一个模型来模 仿真实系统，两者不可能完全等同，但是最基本的内容应该相同，即模型至少必 须反映系统的主要特征。本论文提取出活动的状态、时间参数、功能参数，互连 参数，资源需求参数和资源的数量、可重用性、共享性、独占性等主要特征，再 根据业务控制规则，建立了业务流程的活动资源，时间图模型。将该模型和企业 的实际运行数据输入仿真系统，对其进行仿真。通过将得到的仿真数据与实际系 统的数据进行比较，评价输入仿真系统的业务流程是否符合企业实际的业务处理 过程。 系统的分类 根据所研究的系统的状态变化是否连续，系统主要分为连续系统和离散系统 两大类。连续系统是指系统状态随时间连续变化的情况，如钢铁、电力等工程系 统。这类系统的动态特性可以用微分方程或一组状态方程来描述，也可以用差分 方程或一组离散状态方程来描述。离散事件系统则是指系统状态变化是离散的， 其主要特征是引起状态变化的行为亦即“事件”往往发生在随机时间上，所以离 散系统仿真也叫离散事件系统仿真。如通信系统、交通运输系统、计算机网络、 库存系统、社会经济系统等。图1 1 表示该连续系统的状态变量，即暴雨后，雨 水流入坝后湖中的水头变化状况。图1 2 表示银行服务顾客的顾客数改变状况。 兰型塑生! 些苎兰型型塑苎王堕垫堕堡! 堕塑望堡型塑塾矍堕塞墨竺! 壅! 些查兰堡圭堡塞! ! 坚 术 * g 监 晷 o 图1 1 连续系统状态变量 图1 2 离散系统状态变量 本文将企业业务过程分解成前后有相互关系的一组活动( a c t i v i t y ) ，这些活动 是企业的基本功能单元，这些活动的执行与否改变了企业系统的状态。由于它们 的执行发生在一些离散的时间点上，所以将这些活动定义为一个个的“事件”， 这样企业业务过程就是一个离散事件系统，本文采用离散事件仿真系统对企业业 务过程进行仿真。 1 2 仿真技术的研究与发展 早期计算机仿真的对象是对工程技术领域中的实际物理过程进行仿真，该领 域中的问题( 例如系统控制和优化) 涉及机械、电子、制造、航空等诸多背景，这 些问题的特点是可以建立起以时间为基准的数学模型，即连续时间模型和离散时 间模型，包括常微分方程。偏微分方程和差分方程等。利用实际工程背景中的原 理和定理可以推导出所研究问题的时间微分或差分方程模型，而根据系统自身的 特征和试验数据可以确定模型中的参数。在5 0 年代至6 0 年代，在差分方程和微 分方程模型的结构特征化和参数辨识方面花费了相当的精力并取得了很大的成 果；此同时，对求解这些方程的算法的研究也在不断发展，产生了能够满足快速 4 八 一 3 2 l 0 籁锋餐g球蹬辎目铽g靶船平矗惮 型竖堕! 山大学软件所 基于活动，资源时间图模型的过程仿真系统研究 中山大学硕士论文2 0 0 4 和实时等多种不同要求的仿真算法和仿真软件。 进人7 0 年代，仿真逐步向政治、经济、军事等社会科学领域渗透，出现了 许多用于求解这些领域中间题的数学模型。而随着对这些问题的深入分析和了 解，数学模型从早期的微分方程和差分方程模型逐渐向能够反映问题离散和随机 特点的离散事件逻辑流图和网络图模型过渡。同时，从求解静态模型的蒙特卡罗 f m o n t ec a r l o ) 法到研究系统动态模型的以事件调度法、活动扫描法和进程交互法 为代表的仿真策略，离散事件系统建模仿真方法研究取得了很大的发展。 7 0 年代中期，b p 齐格勒( b e z e i g l e r ) 提出了模型的规范化和形式化描述理 论，使得建模方法学前进了一大步。从那时起，结合计算机软件方法学的发展， 系统建模理论中引入了层次化模块化方法和面向对象的思想，为建立集成化交互 式建模环境提供了良好的基础。 s c s c 2 0 0 4 ( t h e2 0 0 4s u m m e rc o m p u t e rs i m u l a t i o nc o n f e r e n c e ，2 0 0 4 年夏 季计算机仿真会议) 4 】根据当前计算机建模与仿真技术的发展状况，提出以下几 个专题进行了讨论： 仿真方法学 建模与仿真语言 建模与仿真系统体系结构 并行与分布式建模与仿真 高层体系结构口i 曲l e v e la r c h i t e c t u r e ，h l a ) 实时系统建模与仿真技术 仿真生命周期演化 仿真软件工程 虚拟现实、虚拟环境 基于w e b 体系结构与实现 基于知识的系统与人工智能。 计算机仿真技术在工业与商业上的应用：包括合作环境：基于仿真的获 取；机器人与自治系统；基于仿真的辨识、控制及优化；工艺学；规划； 标准化；校核、验证及确认；材料；生物医学科学；教育：经济建模与 仿真；教育建模与仿真：未来建模与仿真；信息系统；基础设计规划与 设计；交通运输；后勤学；管理科学。 仿真技术在军事中的应用：包括训练仿真器；防御系统仿真技术；模型 提取技术；导弹防御系统与战争管理、指挥、控制及通讯系统；仿真在 武器系统中的应用。 上述主要课题可以归纳为三个方面：第一方面是建模与仿真方法学的研究， 型堡堕! 些查堂堑壁所 基于活动愤源时间图模型的过程仿真系统研究中山大学硕士论文2 0 0 4 包括建模方法、仿真模型的规范化、形式化，建模与仿真语言等；第二方面是仿 真技术的研究，包括仿真过程与仿真工具，仿真语言与仿真环境，先进分布仿真 技术 5 1 1 6 1 1 7 1 1 8 9 ，模型提取技术等；第三方面是仿真技术的应用，包括在各个 不同领域的应用f 1 0 1 。 从这些专题可以看出，仿真技术的应用领域己达到了前所未有的广度与深 度，并将继续朝着更广、更深的方向发展；各国政府对仿真技术在军事、国防上 的重要性认识正在逐步提高，特别是美国，目前已成立了“国家导弹防御联合规 划办公室”，专门组织技术专家小组研究仿真技术在导弹防御系统以及战争管理、 指挥、控制与通讯系统中的应用；仿真技术在工业和商业中的应用也非常广泛， 极大地提高了工业生产中产品的产量与质量，使生产中的原材料、资金以及人力 物力分配更趋优化。 1 3 本论文所研究问题的背景及其意义 9 0 年代初期，美国的g a r t n e rg r o u p 公司提出e r p o i n t e r p f i s er e s o u r c e p 】a 加i n 曲 1 1 】 1 2 这一管理思想得到极大的流行。作为企业管理思想，它是一种 新型的管理模式：而作为一种管理工具，它同时又是一套先进的计算机管理系统。 为此，在不到十年的短暂时间内，它很快就被人们认同和接受，并为许许多多的 企业带来了丰厚的收益。但同时也有相当多的企业使用e r p 失败的记录。企业 上e r p 系统失败的原因有很多，其中软件选择不当比例高达6 7 ，如图1 3 。软 件选择不当有非常多的原因，比如企业小，人员配置不齐，业务量不大，所上的 e r p 系统利用率不高，造成e r p 系统功能没有完全发挥作用，以至上不上e r p 管理的意义不大。但根据综合分析，造成浪费的最主要的一个原因就是软件的业 务处理流程与企业实际业务处理流程不符，从而影响企业的正常运行，最终导致 上e r p 系统的失败。 图1 3 e r p 失败原因 本文研究的过程仿真系统的目的就是建立一个能够将软件业务处理流程与 6 型墨堕些查兰墼壁堕基于活动，资源哆旦里! 壅型的过程仿真系统研究中山大学硕士论文2 0 0 4 实际企业业务处理流程进行比较的一个平台。通过输入软件业务处理流程和企业 实际运行的业务处理流程数据到系统中进行仿真，再将仿真系统输出的数据与企 业实际数据进行对照、分析，验证二者是否相一致。如果相一致，则证明输入的 业务处理流程是符合企业实际的业务处理流程，如果不一致，则证明二者不相符 合，而不至于造成企业的重大损失。 图1 4 e r p 实旌状况 同时从图1 4 中可以看出，企业上的e r p 系统有2 3 1 6 是委托开发的，委 托的对象也就是一些公司、高校、研究所等具备实力的单位。但是它们在开发 e r p 系统时，虽然和客户有紧密的联系，但也常常遇到所开发的软件业务处理流 程可能与企业实际的业务处理流程不一致，因此需要将正在开发的业务处理流程 与企业实际业务处理流程进行仿真比较。从而可以在开发中就发现流程的错误， 而不至于到软件开发完毕才发现流程处理的错误，因此可以大量节省开发成本， 降低软件开发风险。 在实际应用中，由中山大学软件研究所正在开发的中山华帝e r p ) ) 1 3 】系 统正需要一个能够仿真软件所处理的流程，以检测其软件处理流程的过程仿真系 统，本论文研究内容的提出正是基于此处。 当前本文的过程仿真系统可以应用在以下一些领域：业务流程再造( b u s i n e s s p r o c e s sr e e n g i n e e r i n g ) 1 4 j 1 5 1 6 、敏捷制造( a g i l em a n u f a c t u r i n g ) 1 1 7 j 1 1 8 1 、并行 工程( c o n c u r r e n te n g i n e e r i n g ) j 1 9 、虚拟制造( v m u a lm a n u f a c t u r i n g ) 2 0 、供应链 管理( s u p p l yc h a i nm a n a g e m e n t ) 2 1 等a 第2 章离散事件系统仿真原理 离散事件系统仿真原理【1 】涉及系统仿真模型和系统仿真策略两部分。本章 介绍了一般离散事件系统仿真模型原理，并在此基础上：介绍了本文仿真系统采 用的仿真技术。 型堡堡! 些查兰墼壁所 基于活动，资源，时甸图模型的过程仿真系统研究中山大学硕士论文2 0 0 4 2 1 离散事件系统仿真模型 离散事件系统的状态是只在离散的时间点上发生变化，且状态在一段时间内 保持不变，而且这些离散的时间点是不确定的。因此在建立离散事件系统模型时， 只需考虑系统内部状态发生变化的时间点以及产生这些状态变化的原因，而不用 描述系统内部状态发生变化的过程。 一般离散事件系统模型通常由以下六部分组成 3 ：随机离散事件、仿真时 钟、未来事件表、随机数发生器、统计数据汇集以及事件安排事件推进的仿真 控制器。以下将分别予以简单介绍。 1 _ 随机离散事件 随机离散事件是一系列按时序、随机发生的具体事实，它们只在离散的可数 时刻上发生，这些事实一旦出现，将使系统中一个或若干个状态变量发生瞬时跃 变。由于这些事实的发生具有离散性和随机性，因此称为随机离数事件。这些事 件发生的时刻往往服从一定的概率分布。 2 仿真时钟及其推进方式 离散事件系统的仿真是动态仿真，需要不断地记录各类离散事件发生的时 刻，并进行时间统计。仿真时钟是离散系统仿真中的基本组成部分，它是随仿真 的进程而不断更新的时间推进机构。通常，在仿真开始时将仿真时钟置零，随后， 仿真时钟按一定的推进方式，不断给出仿真时间的当前值。仿真时间是仿真模型 中的时间指示，它表示仿真运行的系统时间。在离散系统仿真中有两种不同的时 钟推进方式。 面向事件的仿真时钟 在这种时钟推进方式下，仿真时钟按照下一离散事件预计将要发生 的时刻，以不同的时间间隔向前推进的，即仿真时钟每次都跳跃性地推 进到下一事件发生的时刻，为此，必须将各事件按发生时间的先后次序 进行排列，仿真时钟则按事件顺序发生的时刻推进。每当某一事件发生 时，系统开始处理相应的“活动”，并计算出由该事件触发产生的未来事 件的发生时刻。经过一定活动处理时间后，仿真时钟将推进到下一事件 发生的时刻上。这个过程不断地重复，直到仿真运行满足规定的终止条 件时为止。 面向时间间隔的仿真时钟 这种时钟推进方式中，仿真时钟按足够小的时间间隔等距推进，使 得在每个时间间俑中基本上不会出现两个或两个以上的离散事件。每次 时钟推进都需要扫描所有活动的完成时刻，以检查在此时间闯隔中有无 事件发生，若有事件发生则记录此时间区间，从而更新由此事件引起的 8 皇些望至! 些i 燮竺里一萎主重型堑塑堕塑望堡型竺望望堕墨墨堕翌塞! 些查兰塑主堕兰! 塑 状态变量的变化。这种推进方式要求每次时钟推进都必须扫描所有正在 执行的活动。 3 未来事件表 离散系统仿真的核心是随机离散事件的发生和由此引起对相应活动的执行。 随着仿真时钟的推进，某一随机事件的出现，必将引起新的未来事件，并使系统 的状态发生变化，从而使仿真进程得以持续。 由事件发生时间大于当前仿真时钟时刻的事件所构成的时序列表称为未来 事件表。表中各离散事件都按照发生时刻的先后次序排列，每当仿真时钟推进到 某事件的发生时刻时，由此触发引起的新的未来离散事件，将按其发生时刻的 先后次序排入或推入未来事件表的适当位置。 未来事件表既是仿真时钟推进的依据，即仿真时钟总是推进到未来事件表中 最早发生事件的时刻，同时，它也是保证系统中的未来事件严格按时问顺序正确 排列的工具。未来事件表是离散系统仿真的基本组成部分。 未来事件表中包含由已发生事件触发的所有未来事件及其发生时刻，当仿真 时钟推进到下一个紧接事件( h i n e n te v e n ) 时刻时，该事件就发生，同时也表示 一项或多项活动的开始。 未来事件表不仅是仿真时钟推进的依据，同时也是控制仿真运行的依据。通 常终止仿真运行有两种方法： 规定仿真运行时间长度t e 规定某个未来事件 e 4 随机数发生器 在离散系统仿真中，由于所反映的实际系统都包含多种随机因素的交互作用 和影响，属于复杂随机系统，在仿真过程中需要处理大量的随机因素。无论是各 种随机离散事件的发生时刻，或是被仿真实体的到达及其在服务台的逗留时间 等，都是各种概率分布的随机变量，每次仿真运行都要从这些概率分布中进行随 机抽样，作为该次运行的实际参数。当进入系统的实体数量很多，每个实体流经 的环节也较多时，仿真过程中就需要成千上万次地进行随机抽样，使每个实体在 每个环节上触发产生的离散事件都能得到规定概率分布的抽样时同，从而使系统 在仿真运行中的随机因素和相互关系得以复现，并得到一次运行的综合样本参 数。因此，任何离散系统仿真过程都必须具备比较完善的、能够产生多种概率分 布随枫变量的随机数发生器，这是仿真中不可或缺的组成部分。各种仿真语言通 常都包含十余种标准概率分布的随机数发生器，当用户在程序赋予某一随机变量 以规定参数的概率分布时，仿真器即可自动调用和生成相应的随机数，以保证系 统的随机特征在仿真中复现。 9 刘洪涛中山大学软件所 基于活动资源时间图模型的过程仿真系统研究中山大学硕士论文2 0 0 4 5 采集和输出统计数据 在仿真过程中要对每一事件的发生时刻进行记录，计算事件发生后系统状态 变量的变化，并对进入系统的实体数量、在各环节中的延迟时间以及系统综合性 能参数进行统计计算，从而给出多次仿真运行后系统参数的数学期望、方差、最 大值与最小值、变量的峰态和偏态系数以及相应的样本分布曲线或直方图等。一 般离散系统仿真软件都应具有自动汇集各种统计数据的功能，并能打印输出标准 格式的系统参数，或按用户定义的格式给出所需要的数据和图形，以提供决策部 门参考。 6 事件安排事件推进的仿真控制器 在系统仿真模型中安排和处理离散事件和仿真时钟的推进是整个仿真过程 的核心部分，因此，离散事件系统仿真必须具有事件安排和时间推进的基本仿真 机制。这种机制的结构如图2 1 所示。 | j 定义仿真模型l l 输入仿真数据i 随机数发生器 产生规则分布 的随机数 仿真横型初始化 t n o ；o ，景诗统计置零 产生初始事件，定冀系统初始状态 事件安捧 事件排序，建立表来事件表 时间推进 扫描当前紧接事件 置t n o = 紧接事件发生时刻 事件娃理 执行当前紧接事件 更新系统当前变量 产生薪前未来事件 仿真数据统计计算 打印仿真输出报告 否 ! 一。 竺室 ! 图2 1 事件安排时间推进的仿真机制 离散事件仿真就是在仿真控制器的控制下“产生事件、安排事件、处理事件、 1 0 型堂堕些查兰塾梦所基于活动，资源，时间圈模型的过程仿真系统研究中山大学硕士论文2 0 0 4 时间推进，再产生新的事件”这样的循环过程中实现的。 2 2 离散事件系统仿真策略 要将系统模型转换为计算机模型，首先要从总体上确定仿真模型的控制逻辑 和仿真时钟推进机制，即确定仿真策略。仿真策略是仿真模型的核心，反映了仿 真模型的本质。从根本上决定了仿真模型的结构。现在离散事件系统基本的仿真 策略一般分为三种，即事件调度法( e v e n ts c h e d u l i n g ，e s ) 、活动扫描法( a c t i v i t y s c a n n i n g ，a s ) 略和进程交互法( p r o c e s si n t e r a c t i o n ，p i ) 1 】。其它仿真策略均是以 这三种仿真策略为基础的。 1 事件调度法 事件调度法最早出现在1 9 6 3 年兰德公司的m a r k o w i t z 等人提出的 s i m s c r i f t 语言的早期版本中。在美国广泛采用，欧洲则不那么流行。它的基 本思想是，将事件倒程作为仿真模型的基本模型单元，按照事件发生的先后顺序 不断执行相应的事件例程。每一事先可预知其发生时间的确定事件都带有一个事 件例程，用以处理事件发生后对实体状态所产生的影响，并安排后续事件；条件 事件不具有事件例程。对它的处理隐含在某一确定事件的例程中。因此，事件调 度法中所说的事件是指确定事件。实体流程法建立的仿真模型，采用的就是事件 调度法。 事件调度法的仿真策略如下： ( 1 ) 初始化； 置仿真的开始时间t o 和结束时间t f ； 置实体的初始状态； 置初始事件及其发生时间t s 。 f 2 1 仿真时钟t i m e = t s ； ( 3 ) 确定在当前时钟t i m e 下发生的事件类型e i ，i 一1 ，2 ，n ，并按解 决规则排序； f 4 ) 如果t i m e - - - - f f ，执行 c a s e e i o f e 1 ：执行e 1 的事件例程；产生后续事件类型及发生时间； e n ：执行e n 的事件例程；产生后续事件类型及发生时间。 e n d c a s e 否则，转( 6 ) ； ( 5 )将仿真时钟t i m e 推进到下一最早事件发生时刻；转( 3 ) ； 刘洪涛中山大学软件所 基于活动资源，时间图模型的过程仿真系统研究中山大学硕士论文2 0 0 4 ( 6 ) 仿真结束。 事件调度法的仿真时钟的推进机制，是将仿真时钟推进到下一最早事件的发 生时刻，也即前一节的面向事件的仿真时钟。它与连续系统仿真中的时间推进方 法一固定时间增量法不同，反映了离散事件系统状态仅在离散时刻点上发生变 化的特点。 2 活动扫描法 活动扫描法在英国很流行，最早出现在1 9 6 2 年b u x t o n 和l a s k i 发布的c s l 语言中。活动扫描法与活动周期模型有较好的对应关系。活动扫描法中的任一活 动都可以由开始和结束两个事件来表示，每一事件都有相应的活动例程。例程中 的操作能否进行取决于一定的测试条件。该条件一般与时间和系统的状态有关， 而且时间条件须优先考虑。确定事件的发生时间事先可以确定，因此其活动例程 的测试条件己与时间有关；条件事件的例程测试条件与系统状态有关。一个实体 可以有几个活动例程；协同活动的活动例程，只归属于参与的一个实体( 一般为 永久实体) 。在活动扫描法中，除设置系统仿真时钟外，每一实体都带有标志自 身时钟值的时间元( t i m ec e l l ) 。时间元的取值由所属实体的下一确定事件刷新。 活动扫描法的基本思想是，用各实体时间元的最小值推进仿真时钟；将时钟 推进到一个新的时刻点后，按优先序执行可激活实体的活动例程，使测试通过的 事件得以发生并改变系统的状态和安排相关确定事件的发生时间；因此，与事件 调度法中的事件例程相当，活动例程是活动扫描法的基本模型单元。 事件调度法的仿真策略如下： ( 1 1 初始化； 置仿真的开始时间t o 和结束时间t f ； 置实体的初始状态； 置初始事件及其发生时间t s 。 ( 2 )仿真时钟m e = t s ； ( 3 ) 确定在当前时钟t i m e 下发生的事件类型e i ，i = l ，2 ，n ，并按解 决规则排序； ( 4 ) 如果t e v i e = t f ，执行 c , a s e e io f e 1 ：执行e 1 的事件例程；产生后续事件类型及发生时间； - e n ：执行e n 的事件例程；产生后续事件类型及发生时间。 e n d c a s e ) 否则，转( 6 ) ； 2 苎壁墅里! 些苎兰竺型! 堕兰王至垫! 鎏篓! 盟塑堕塑型塑垄堡堕塞墨竺里窒! 坐查兰堡堡塞! ! 竺 ( 5 ) 将仿真时钟t i m e 推进到下一最早事件发生时刻：转( 3 ) ； ( 6 ) 仿真结束。 3 三段扫描法 由于活动扫描法将确定事件和条件事件的活动例程同等对待，都要通过反复 扫描来执行，因此效率较低。1 9 6 2 年，t o c h e r 借鉴事件调度法的某些思想，对 活动扫描法进行了改进，提出了三段扫描, 法c l h r e ep h a s e ，t p ) 。三段扫描法兼有 活动扫描法简单和事件调度法高效的优点，因此被广泛采用，并逐步取代了最初 的活动扫描法。 同活动扫描法一样，三段扫描法的基本模型单元也是活动例程。但是在三段 扫描法中，活动例程被分为两类： b 类活动例程描述确定事件的活动例程，在某一排定时刻必然会被执 行。也称确定活动例程。 c 类活动例程描述条件事件的活动例程，在协同活动开始f 满足状态条 件1 或满足其它特定条件时被执行。也称条件活动例程或合作活动例程。 显然，b 类活动例程像事件调度法中的事件例程一样可以在排定时刻直接执 行，只有c 类活动例程才需要扫描执行。 基于这种思想，给出三段扫描法仿真策略如下： ( 1 1 初始化； 置仿真开始时间t o 和结束时间m 置实体的初始状态； 置初始b 类活动例程及其调用时间t s 。 ( 2 ) 仿真时钟t i m e = t s ； f 3 1 确定在当前时钟t i m e 下调用的b 类活动例程a i ， i = l ，2 ，3 ，n ； ( 4 ) b 类例程调用； 如果t i m e t f ，按优先序执行 c a s e a i o f a 1 ：执行活动例程a 1 ； a n ：执行活动例程a n e n d c a s e 否则，转( n 。 f 5 1c 类例程扫描； f o r 浮1 ，m ( 优先序从高到低) 执行活动例程i j ； 趔竖塑! 些查芋软件所基于活动资源肘问图模型的过程仿真系统研究中山大学硕士论文2 0 0 4 若a j 的测试条件d j = t r u e ，则 退出当前循环，重新开始扫描 ： e n d f o r 。 ( 6 ) 推进仿真时钟t i m e 到下一最早b 类例程调用时刻；转( 3 ) ； ( 7 ) 仿真结束。 4 进程交互法 事件调度法和活动扫描法的基本模型单元分别是事件例程和活动例程，这些 例程都是针对事件而建立的；而且在e s 和a s 策略中，各个例程都是独立存在 的。进程交互法的基本模型单元是进程。进程与例程的概念有着本质的区别，它 是针对某类实体的生命周期而建立的，因此一个进程中要处理实体流动中发生的 所有事件( 包括确定事件和条件事件) 。 进程交互法的一种建模观点是将系统的演进过程归结为临时实体产生、等待 和被永久实体处理的过程。最早发布于1 9 6 1 年的g p s s 语言，是由m m 公司的 g o r d o n 等人研制的一种采用进程交互法的仿真语言，它就采用了上述建模观点。 也有一些进程交互型仿真语言，如挪威的d a b l 等人提出的s i m u l a 语言，临时 实体和永久实体都可建立进程。 进程交互法的基本思想是，通过所有进程中时间值最小的无条件延迟复活点 来推进仿真时钟；当时钟推进到一个新的时刻点后，如果某一实体在进程中解锁， 就将该实体从当前复活点一直推进到下一次延迟发生为止。进程交互法兼有事件 调度法和活动扫描法的特点，但其算法比二者都复杂。 ( 1 ) 初始化； 置仿真开始时间t o 和结束时间t f ； 置各进程中每一实体的初始复活点及相应的时间值t i ，j 】，i = 1 ， 2 ，m ：j = 1 ，2 ，n q ，i n 是进程数，n 【i 】是第i 个进程中的实 体数。 ( 2 ) 推进仿真时钟t i m e = m l n t i ，j | j 处于无条件延迟 ； ( 3 ) 如果t i m e 一 f f ，转( 4 ) ；否则转( 5 ) ； ( 4 ) f o ri = l ，m ( 优先序从高到低) f o r j = l ，n i 】 i f ( t 【i j = t i m e ) t h e n 从当前复活点开始推进实体j 的进程i ，直至下一次延迟发 生为止： 如果下一延迟是无条件延迟，则 设置实体j 在进程i 中的复活时间t 【i ，j 】) ； 1 4 望堡壁蔓主! 生堑整竺堕苎主垩垫! 塞塑! 堕塑里堡型塑塾堡堑塞委竺里壅 主坐查兰堡圭笙苎! ! 坐 e n d i f i f ( t i ，j - n 墅i ；! ! i v a l u c v a l t t c v a l u ： n u m b e ro f t i m eu n i t s n u m b e ro f t i m cu n i b n u m b e ro f t i m cu n i