离散事件仿真模型设计与实现算法

物流系统仿真

——从理论到实践第三章离散事件仿真模型设计与实现算法第三章离散事件仿真模型设计与实现算法3.1离散事件系统仿真建模方法3.1.1离散事件仿真模型的组成与构造3.1.2实体流图法3.1.3活动周期图法3.1.4实体流图与活动周期图的比较3.2离散事件系统仿真实现的三种算法3.2.1事件调度法3.2.2活动扫描法3.2.3进程交互法3.3离散事件系统仿真模型设计3.3.1面向事件的仿真模型3.3.2面向活动的仿真模型3.3.3面向进程的仿真模型3.4离散事件系统仿真的基本要素3.4.1基本要素3.4.2仿真钟3.5排队系统与库存系统3.5.1排队系统3.5.2库存系统3.5.3排队系统与库存系统仿真比较第三章离散事件仿真模型设计与实现算法3.1离散事件系统仿真建模方法离散事件仿真模型的组成与构造仿真模型系统状态

仿真钟事件列表统计计数器初始化程序时间推进程序事件发生程序随机观测生成程序库报告生成器主程序第三章离散事件仿真模型设计与实现算法3.1离散事件系统仿真建模方法离散事件仿真模型的组成与构造变步长时间推进机制下的控制逻辑第三章离散事件仿真模型设计与实现算法3.1离散事件系统仿真建模方法离散事件仿真模型的组成与构造实体流图法

实体流程图方法采用与计算机程序流程图相类似的图示符号和原理，建立表示临时实体产生、在系统中流动、接受永久实体“服务”以及消失等过程的流程图。借助实体流程图、可以表示事件、状态变化及实体间相互作用的逻辑关系。第三章离散事件仿真模型设计与实现算法3.1离散事件系统仿真建模方法离散事件仿真模型的组成与构造实体流图法建模可以按一下思路进行：

（1）辨识组成系统的实体及属性。（2）分析各种实体的状态和活动，及其相互间的影响。（3）考察有哪些事情导致了活动的开始或结束，或者可以作为活动开始或结束的标志，以确定引起实体状态变化的事件，并合并条件事件。（4）分析各种事件发生时，实体状态的变化规律。（5）在一定的服务流程下，分析与队列实体有关的特殊操作(如换队等)。（6）通过以上分析，以临时实体的流动为主线，用约定的图示符号画出被仿真系统的实体流程图。（7）给出模型参数的取值、参变量的计算方法及属性描述变量的取值方法。（8）给出队列的排队规则。第三章离散事件仿真模型设计与实现算法3.1离散事件系统仿真建模方法离散事件仿真模型的组成与构造活动周期图法

活动周期图以直观的方式显示了实体的状态变化历程和各实体之间的交互作用关系，便于理解和分析。活动周期图可以充分反映各类实体的行为模式，并将系统的状态变化以“个体”状态变化的集合方式表示出来，因此可以更好地表达众多实体的并发活动和实体之间的协同。第三章离散事件仿真模型设计与实现算法3.1离散事件系统仿真建模方法离散事件仿真模型的组成与构造活动周期图法活动周期图建模过程如下：（1）辨识组成系统的实体及属性.（2）辨识组成系统的永久实体和临时实体，队列不作为实体考虑。（3）分别画出各实体的活动周期图。第三章离散事件仿真模型设计与实现算法3.1离散事件系统仿真建模方法离散事件仿真模型的组成与构造实体流程图与活动周期图比较哪些不同点？第三章离散事件仿真模型设计与实现算法3.2离散事件系统仿真实现的三种算法事件调度法

事件调度法（EventScheduling）是面向事件的方法。仿真方法主要是研究系统状态变化，有事件发生就会有状态变化。事件调度法是通过定义事件，并按照时间顺序处理所发生的一系列事件。由于事件都是预定的，状态变化发生在明确的预定时刻，所以这种方法适合于活动持续时间比较确定的系统。第三章离散事件仿真模型设计与实现算法3.2离散事件系统仿真实现的三种算法事件调度法事件调度法程序结构第三章离散事件仿真模型设计与实现算法3.2离散事件系统仿真实现的三种算法事件调度法事件调度法的步骤是：（1）初始化：需要初始化的对象包括时间、事件表、系统初始时间和成分状态。（2）将仿真钟设置为系统初始事件的时间。（3）执行事件子程序，修改事件表。（4）取出

的事件记录，推进仿真钟

，修改事件表。第三章离散事件仿真模型设计与实现算法3.2离散事件系统仿真实现的三种算法活动扫描法活动扫描法（ActivityScanning）是面向活动的。活动开始和结束是系统状态变化的标志。而活动的开始与结束不仅取决于时间因素还取决于其他的因素。活动扫描法在英国很流行．最早出现在1962年Buxton和Laski发布的CSL语言中。

活动扫描法建立在设立系统仿真钟、成分仿真钟和条件测试模块的基础之上。第三章离散事件仿真模型设计与实现算法3.2离散事件系统仿真实现的三种算法活动扫描法三段扫描法的步骤是：（1）初始化①置仿真开始时间t0和结束时间tf；②置实体的初始状态；③置初始B类活动例程及其调用时间ts；（2）仿真时钟TIME=ts。（3）确定在当前时钟TIME下调用的B类活动例程

，i=1，2，···，n。（4）B类例程调用第三章离散事件仿真模型设计与实现算法3.2离散事件系统仿真实现的三种算法活动扫描法如果

，按优先序执行{ A1：执行活动例程A1；

······An：执行活动例程An。 Endcase}

否则，转（7）。第三章离散事件仿真模型设计与实现算法3.2离散事件系统仿真实现的三种算法活动扫描法（5）C类例程扫描 forj=1，m（优先序从高到低）

执行活动Aj；

若Aj的测试条件

，则 {退出当前循环，重新开始扫描}； Endfor（6）推进仿真时钟TIME到下一最早B类例程调用时刻，转（3）。（7）仿真结束。第三章离散事件仿真模型设计与实现算法3.2离散事件系统仿真实现的三种算法进程交互法

进程交互法（ProcessInteraction）面向进程。进程交互法的基本模型单元是进程。进程与例程的概念有着本质的区别，它是针对某类实体的生命周期而建立的，因此一个进程中要处理实体流动中发生的所有事件(包括确定事件和条件事件)。进程是由若干个有序的事件，以及由相邻事件组成的若干活动组成的过程。一个成分进入系统，完成各项活动的过程可以有一个进程来描述。进程交互法是事件调度法与活动扫描法的结合。第三章离散事件仿真模型设计与实现算法3.2离散事件系统仿真实现的三种算法进程交互法进程交互法的处理过程如下：（1）推进仿真时钟TIME；（2）把满足

的所有事件从FEL移至CEL中；（3）取出CEL中的每一个事件，判断其所属的进程及在进程中的位置；（4）判断该事件发生的条件是否满足；（5）如果条件允许该进程尽可能连续推进，直到进程结束，该成分离开系统；（6）该进程推进过程中，遇到条件不满足时，记录下进程的位置，并退出该进程；（7）重复3~6，CEL中的事件处理完毕；（8）重复1~7，直到仿真结束。第三章离散事件仿真模型设计与实现算法3.2离散事件系统仿真实现的三种算法进程交互法第三章离散事件仿真模型设计与实现算法3.2离散事件系统仿真实现的三种算法三种算法的比较时间调度法活动扫描法进程交互法系统描述主动成分可施加作用主动成分、被动成分均可施加作用主动成分、被动成分均可施加作用建模要点对事件建模，事件子程序对活动建模，条件子程序进程分步，条件测试于执行活动仿真钟推进系统仿真钟系统仿真钟，成分仿真钟依据CEL，最早发生的事件时间执行活动执行控制选择最早发生的时间记录扫描全部活动，执行可激活成分扫描CEL，执行Da(S)=true记录断点第三章离散事件仿真模型设计与实现算法3.3离散事件系统仿真模型设计面向事件的仿真模型使用事件表后，面向事件仿真模型总控程序的算法结构如下：（1）时间扫描①扫描事件表，确定下一事件发生时间；②推进仿真时钟至下一事件发生时间；③从事件表中产生当前事件表CEL，CEL中包含了所有当前发生事件的事件记录。（2）事件执行

依序安排CEL中的各个时间的发生，调用相应的事件例程。某一时间一旦发生，将其事件记录从当前事件表中移出。

上述两个步骤反复进行，直到仿真结束。第三章离散事件仿真模型设计与实现算法3.3离散事件系统仿真模型设计面向活动的仿真模型面向活动的仿真模型中，每一活动例程都由两部分构成：（1）探测头：活动例程中所带的测试条件（2）动作序列：活动例程所要完成的具体操作，只有在测试通过后才被执行。时间元的取值方法有两种：（1）绝对时间法。将时间元的时钟值设定在相应实体的确定事件发生时刻。（2）相对世间法。将时间元的时钟值设定在相应实体确定事件发生的时间间隔上。面向活动仿真模型总控程序的算法结构包括：（1）时间扫描；（2）活动例程扫描。第三章离散事件仿真模型设计与实现算法3.3离散事件系统仿真模型设计面向进程的仿真模型面向进程仿真模型的总控程序包含三个步骤：（1）将来事件表扫描：从FEL的实体记录中检出复活时间最小的实体，并将仿真时间推进到该实体的复活时间。（2）移动记录：将FEL中当前时间复活的实体记录移至CEL中。（3）当前事件表扫描。第三章离散事件仿真模型设计与实现算法3.4离散事件系统仿真的基本要素基本要素

系统由某些相互关联或相互作用的要素组成，离散系统仿真模型是对真实系统关键要素的抽象和组合，抽象和组合的过程必须遵循一定的规律进行。任何一个系统都可以分为个体、活动、资源与控制等要素。第三章离散事件仿真模型设计与实现算法3.4离散事件系统仿真的基本要素基本要素事件、活动与进程的关系进程活动1活动2活动3事件1事件2事件n-1事件n·······第三章离散事件仿真模型设计与实现算法3.4离散事件系统仿真的基本要素仿真钟

我们把一个仿真模型中用来记录仿真当前时刻的变量称为仿真钟。

仿真钟是用于表示仿真时间变化的时间标识。仿真钟所记录的时间，和我们运行模型所耗费的计算机运行时间没有必然的相关关系。第三章离散事件仿真模型设计与实现算法3.4离散事件系统仿真的基本要素仿真钟

在仿真模型运行过程中，仿真时钟从0逐步增大到仿真结束时间，离散事件系统仿真的仿真时钟推进方法有两种。（1）面向时间间隔的仿真时钟推进（2）面向事件的仿真时钟推进（仿真钟）(a)面向时间间隔的仿真时钟推进(b)面向事件的仿真时钟推进第三章离散事件仿真模型设计与实现算法3.5排队系统与库存系统排队系统

排队系统式离散事件系统仿真应用的一类经典系统。排队系统是指物、人及信息等流量元素在流动过程中，由于服务台不足而不能及时为每个顾客服务，产生需要排队等待服务（加工）的一类系统。排队系统的基本参数顾客源服务台服务台服务台服务台队列离去排队系统的结构第三章离散事件仿真模型设计与实现算法3.5排队系统与库存系统排队系统排队系统的性能指标平均等待时间服务台利用率平均逗留时间平均队长系统中平均顾客数忙期（闲期）第三章离散事件仿真模型设计与实现算法3.5排队系统与库存系统库存系统

库存系统也是物流系统中常见的一类系统。在日常的生产和经营活动中，不论工厂对它生产所需的原材料、半成品、成品仓库库存，还是商场对所需的商品库存，都需要进行严格的控制和管理。库存过多会造成资金积压，过少会影响生产和销售。库存系统的特征①补给模式②需求模式③成本代价第三章离散事件仿真模型设计与实现算法3.5排队系统与库存系统库存系统库存系统常用的输出参数①保管费②订货费③缺货损失费第三章离散事件仿真模型设计与实现算法3.5排队系统与库存系统排队系统与库存系统仿真比较

排队系统与库存系统在进行仿真时，存在一定的差异，具体表现在要素、目标、主要性能指标、评价等几个方面。排队系统的要素是服务台和顾客，而库存系统主要处理的是订货和需求；排队系统的目标是提高服务台、顾客效率，以最少的资源服务于最多的顾客，既提高客户满意度也能降低成本。库存系统的目标是保证供应的前提下降低库存，库存虽然是生产销售必不可少的，但却占压大量的资金，所以，要把库存水平维持在一个较合理的位置。排队系统的主要性能指标是排队队长