物流系统仿真 ——从理论到实践,第三章 离散事件仿真模型设计与实现算法,刘亮,第三章 离散事件仿真模型设计与实现算法,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 离散事件系统仿真实现的三种算法事件调度法 事件调度法（Event Scheduling）是面向事件的方法仿真方法主要是研究系统状态变化，有事件发生就会有状态变化事件调度法是通过定义事件，并按照时间顺序处理所发生的一系列事件由于事件都是预定的，状态变化发生在明确的预定时刻，所以这种方法适合于活动持续时间比较确定的系统第三章 离散事件仿真模型设计与实现算法,3.2 离散事件系统仿真实现的三种算法事件调度法,事件调度法程序结构,第三章 离散事件仿真模型设计与实现算法,3.2 离散事件系统仿真实现的三种算法事件调度法事件调度法的步骤是：（1）初始化：需要初始化的对象包括时间、事件表、系统初始时间和成分状态。
2）将仿真钟设置为系统初始事件的时间3）执行事件子程序，修改事件表4）取出 的事件记录，推进仿真钟 ，修改事件表第三章 离散事件仿真模型设计与实现算法,3.2 离散事件系统仿真实现的三种算法活动扫描法 活动扫描法（Activity Scanning）是面向活动的活动开始和结束是系统状态变化的标志而活动的开始与结束不仅取决于时间因素还取决于其他的因素活动扫描法在英国很流行．最早出现在1962年Buxton和Laski发布的CSL语言中 活动扫描法建立在设立系统仿真钟、成分仿真钟和条件测试模块的基础之上第三章 离散事件仿真模型设计与实现算法,3.2 离散事件系统仿真实现的三种算法活动扫描法三段扫描法的步骤是：（1）初始化①置仿真开始时间t0和结束时间tf；②置实体的初始状态；③置初始B类活动例程及其调用时间ts；（2）仿真时钟TIME= ts3）确定在当前时钟TIME下调用的B类活动例程 ，i=1，2，···，n4）B类例程调用,第三章 离散事件仿真模型设计与实现算法,3.2 离散事件系统仿真实现的三种算法活动扫描法如果 ，按优先序执行 { A1：执行活动例程A1； ······ An：执行活动例程An。
Endcase} 否则，转（7）第三章 离散事件仿真模型设计与实现算法,3.2 离散事件系统仿真实现的三种算法活动扫描法（5）C类例程扫描 for j=1，m（优先序从高到低） 执行活动Aj； 若Aj的测试条件 ，则 {退出当前循环，重新开始扫描}； Endfor（6）推进仿真时钟TIME到下一最早B类例程调用时刻，转（3）7）仿真结束第三章 离散事件仿真模型设计与实现算法,3.2 离散事件系统仿真实现的三种算法进程交互法 进程交互法（Process Interaction）面向进程进程交互法的基本模型单元是进程进程与例程的概念有着本质的区别，它是针对某类实体的生命周期而建立的，因此一个进程中要处理实体流动中发生的所有事件(包括确定事件和条件事件)进程是由若干个有序的事件，以及由相邻事件组成的若干活动组成的过程一个成分进入系统，完成各项活动的过程可以有一个进程来描述进程交互法是事件调度法与活动扫描法的结合第三章 离散事件仿真模型设计与实现算法,3.2 离散事件系统仿真实现的三种算法进程交互法进程交互法的处理过程如下：（1）推进仿真时钟TIME；（2）把满足 的所有事件从FEL移至CEL中；（3）取出CEL中的每一个事件，判断其所属的进程及在进程中的位置；（4）判断该事件发生的条件是否满足；（5）如果条件允许该进程尽可能连续推进，直到进程结束，该成分离开系统；（6）该进程推进过程中，遇到条件不满足时，记录下进程的位置，并退出该进程；（7）重复3~6，CEL中的事件处理完毕；（8）重复1~7，直到仿真结束。
第三章 离散事件仿真模型设计与实现算法,3.2 离散事件系统仿真实现的三种算法进程交互法,第三章 离散事件仿真模型设计与实现算法,3.2 离散事件系统仿真实现的三种算法三种算法的比较,第三章 离散事件仿真模型设计与实现算法,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 离散事件系统仿真的基本要素基本要素事件、活动与进程的关系,,第三章 离散事件仿真模型设计与实现算法,3.4 离散事件系统仿真的基本要素仿真钟 我们把一个仿真模型中用来记录仿真当前时刻的变量称为仿真钟 仿真钟是用于表示仿真时间变化的时间标识仿真钟所记录的时间，和我们运行模型所耗费的计算机运行时间没有必然的相关关系。
第三章 离散事件仿真模型设计与实现算法,3.4 离散事件系统仿真的基本要素仿真钟 在仿真模型运行过程中，仿真时钟从0逐步增大到仿真结束时间，离散事件系统仿真的仿真时钟推进方法有两种1）面向时间间隔的仿真时钟推进（2）面向事件的仿真时钟推进,,,,,,,第三章 离散事件仿真模型设计与实现算法,3.5 排队系统与库存系统排队系统 排队系统式离散事件系统仿真应用的一类经典系统排队系统是指物、人及信息等流量元素在流动过程中，由于服务台不足而不能及时为每个顾客服务，产生需要排队等待服务（加工）的一类系统排队系统的基本参数,,排队系统的结构,第三章 离散事件仿真模型设计与实现算法,3.5 排队系统与库存系统排队系统排队系统的性能指标平均等待时间服务台利用率平均逗留时间平均队长系统中平均顾客数忙期（闲期）,第三章 离散事件仿真模型设计与实现算法,3.5 排队系统与库存系统库存系统 库存系统也是物流系统中常见的一类系统在日常的生产和经营活动中，不论工厂对它生产所需的原材料、半成品、成品仓库库存，还是商场对所需的商品库存，都需要进行严格的控制和管理库存过多会造成资金积压，过少会影响生产和销售。
库存系统的特征①补给模式②需求模式③成本代价,第三章 离散事件仿真模型设计与实现算法,3.5 排队系统与库存系统库存系统库存系统常用的输出参数①保管费②订货费③缺货损失费,第三章 离散事件仿真模型设计与实现算法,3.5 排队系统与库存系统排队系统与库存系统仿真比较 排队系统与库存系统在进行仿真时，存在一定的差异，具体表现在要素、目标、主要性能指标、评价等几个方面排队系统的要素是服务台和顾客，而库存系统主要处理的是订货和需求；排队系统的目标是提高服务台、顾客效率，以最少的资源服务于最多的顾客，既提高客户满意度也能降低成本库存系统的目标是保证供应的前提下降低库存，库存虽然是生产销售必不可少的，但却占压大量的资金，所以，要把库存水平维持在一个较合理的位置排队系统的主要性能指标是排队队长、平均等待时间、平均滞留时间、平均实体数等，主要是从时间和实体数方面考察；而库存系统的指标是订货费、月平均保管费、月平均缺货损失费等，主要从费用考核排队系统主要通过效率指标（时间）评价，而库存系统主要通过效益指标（费用）评价。