离散系统仿真基础

《离散系统仿真基础》由会员分享，可在线阅读，更多相关《离散系统仿真基础（54页珍藏版）》请在金锄头文库上搜索。

1、 3.离散系统仿真基础离散事件动态系统(DEDS: Discrete Event Dynamic System) 是指受事件驱动、系统状态跳跃式变 化、系统状态迁移发生在一串离散时 间点上的动态系统。3.1 术语介绍l系统按照某些规律结合起来的，互相作用、 相互依存的所有元素的集合。l实体是对实际系统构成仿真模型所必须的、 不可略去的各种系统（元素）的抽象。l（实体）属性能描述该实体状态的一些量。 它们可以是时间的函数，也可以不随时间变 化。l系统状态系统中全部实体的属性在某时刻t 所取量值的集合S(t)定义为“系统状态”。 l事件当t在T上按某种序列t1,t2,取值 的过程中，系统状态发生了

2、变化，就定义系 统发生了某一“事件”。并把此时的ti值定义为 “事件时刻”。l活动任何引起系统状态改变的过程称为“ 活动”。因此“活动”的结果使系统发生“事件” 。而两个相邻“事件时刻”，可以看成是某一“ 活动”的过程。离散系统按照时间和事件关系的 分类 :l时间离散系统本身可能连续，但只在一 些特定的时刻，即T= t1,t2,上被考察。通 常为了方便，各时间间隔选定为整常数。S(t) S(t6)S(t1)0 t1 t2 t6 t 时间离散系统l时间连续而有离散事件这时，系统状态 的变化，即事件时刻是不连续的，跳跃式的 。S(t)1（亮）0 t1 t2 t3 t4 t5 t6 t 人工控制的红

3、绿灯系统离散系统例子系统统实实体属性事件急诊诊室护护士，病床，医 生， 病人病情类类型，护护士和 医生的服务务速 度，病人的发发 病类类型和发发病 率病人到达，离院， 护护士检查结检查结 束， 病人就诊诊银银行出纳员纳员 ，计计算 机，顾顾客帐户帐户 号，支票号， 信用卡号，出纳员纳员 的服务务速度， 顾顾客到达率， 存/取/其它操作出纳员纳员 服务务， 计计算机查询查询 ，顾顾客 到达， 离去不同实体可以分成两类：l静态实体这类实体在系统中往往处于被 动地位。它们为动态实体提供服务。因而起 设备作用。描述这类实体的最常见的属性有 ：忙、闲、数量、地点、速度、设备号、服 务时间等。l动态实体这

4、类实体在系统中总是要求得 到某些设备的服务。在系统的运行中，它们 不断得以某种到达率“生成”。当从某一设备 得到服务后，又流向其他设备以求服务。l系统环境能对系统产生影响的，属于系 统以外的元素集合。l仿真目的指仿真者希望通过仿真所获取 系统的哪些性能，信息。l仿真模型由系统数学模型根据仿真工具 （语言）的特点，进行必要的结构变换，建 立的合适算法。 对同一系统，仿真的目的不同，所建的模 型也将不同。 3.2 排队系统在日常生活中，人们常常会见到各种各 样的服务系统。例如：到食堂去买饭，炊 事员和买饭人员构成一个服务系统；在公 共汽车服务系统，由汽车、乘客和车站组 成。服务系统的主要特征是出现

5、排队。因 此也称其为“排队系统”。 用于研究排队系统的理论基础是“排队 论”排队论最早由A. K. Erlang 于1918 年提出,在管理通讯和各类服务系统中 有着广泛的应用,但是采用排队论方法 来为DEDS 建模服务却是近二十年来的 事。以排队论为基础的网络模型是离散 事件系统仿真中最常用的模型。随机排队系统的三个组成部分： 到达模式指含个类型的动态实体按怎样 的规律到达。 服务机构指同一时刻有多少服务设备可 以接纳动态实体；对它们的服务需要多少 时间。 排队规则到达的动态实体将按怎样的次 序接受服务。离散仿真要解决的基本问题如何通过已知的到达模式和服务时间 的概率分布，研究排队系统的队列

6、长度 和服务设备“忙”或“闲”的程度，就是离 散仿真要解决的基本问题。 几种常见的排队系统的结构：动态实体服务设备动态实体到达离去一线一服务设备排队系统结构动态实体服务设备1服务设备n动态实体到达 离去 ： ：一线并联服务设备排队系统结构3.3 到达模式确定型到达模式顾客有规则地按照一定的间隔时间到达 。 泊松到达模式满足4个条件l平稳性：在a, a+t时间内有k个顾客到来的概率与a无关，只与t, k 有关。记此概率为：Vk(t)在t时间间隔内到达k个顾客的概率。 (P(k,t)l无后效性：不相交区间内到达的顾客数是相互独立的。t1,t2到达 数与t0,t1的到达数无关。l普通性：令(t)表示

7、在长度为t的区间内至少到达两个顾客的概率， 则(t)=0 当t-0；l有限性：在任意有限时间区间内到达有限个顾客的概率之和为1。其中0为常数。令第i个顾客到达的 时刻为i(I=1,2,)，1=0，且ti=i-i-1 （i=1,2,），则顾客相继到达的间隔t 是相互独立相同分布的。其到达间隔的 分布为指数分布。指数分布：泊松分布到达模式实际上是指：到达间隔时 间为指数分布的到达模式。 l平均到达间隔时间Ta在考虑模型的总时间 T中，共到达了n个“顾客”的情况下的比值 T/n。l平均到达率单位时间内到达的“顾客” 数 。=1/Ta。 l到达间隔的分布函数A0(t)到达间隔时间大 于t的概率。 A0

8、(t)1F (t)A0(t)0t3.2.2 服务时间定长分布这是最简单的情况。对每个动态 实体的服务时间都是常数a，其分布函数为：指数分布当服务时间完全是随机的情况， 可以用指数分布来表示。其分布函数： 正态分布在服务时间近似于常数的情况下，因 多种随机因素的影响，使服务时间围绕这些常数 值随机波动的情况。其中：0，a均值。F(x) 记为：N(a, 2)。 当a=0，=1时，N(0,1)称为“标准正态分布”。 3.4 排队规则和队列的度量排队规则动态实体应依一定的次序和规则接受服务 。l损失制动态实体到达时，如所有的服务设备均被 占，则该实体就自动消失，永不再来。l等待制动态实体到达时，如所有

9、的服务设备均被 占，则它们就排成队伍，等待服务。服务次序可以采 用下列各种规则：l先到先服务l先到后服务l随机服务l优先权服务排队规则 在优先权服务时，必须考虑当一个比现在正 接受服务的实体具有更高优先权级别的动态实 体到达之后，系统将会做出怎样的处理：l优先权仅决定动态实体的排队先后。l立即停止当前服务，为新到的高优先权的实体服 务。 排队规则 3. 混合制l队长有限制l等待时间有限制l逗留时间队列的度量 设Ta为动态实体的平均到达间隔时间， =1/Ta为平均到达速度 Ts是设备的平均服务时间，=1/Ts是平均 服务速度。定义：l业务量强度在已知平均到达速度和平均 服务速度，业务量强度： u

10、=/=Ts/Tal设备利用率得到服务的动态实体的到达速 率与服务速度之比： =/对队列进行度量通常考察两个量 ： l队列长度l排队时间3.5 设备利用率和服务质量 对系统做假设：动态实体数量是无限的，其 到达速率不受排队长度的影响，并且所到达的 实体不会中途离去；到达模式为泊松分布，服 务设备利用率 0.75对第二个要求 如平均服务时间为10秒 = =1/10=0.1Pw(t) 1.00.8=0.8 0.6 =0.6 0.4=0.4 0.2=0.20 1 2 3 4 5 6 tt=30秒 = t=3。查曲线得 Pw(3) 0.2 =0.6 如果用更小的利用率，则会得到更低的概 率。所以要求0.

11、6。综合两个要求，可取0.6。为了使=0.6就要 求顾客的平均到达时间Ta=Ts/=10/0.6=16.7 （秒）。同样：对给定了到达间隔时间Ta时 ，也可求得Ts以达到满意的服务质量。 3.6 排队系统建模（1）以排队论方法为基础的仿真模型设计技术 主要适用于带时标的随机DEDS 系统。 对排队系统来说，它只有两个基本的操作 ：“入队”和“离队”操作。排队模型的确切形 式取决于服务设备的数量和排队线的数量。开始对到达的动态实体 做相关记录服务设备忙将实体挂 在排队线上排队线长度加1设置服务设备为“忙 ”状态确定（此次）服 务时间调度服务完成事件结束YN（时间）入队操作设置服务设备为“空 ”状

12、态排队线“空”按排队规则从队列中选出 一个实体记录，让设备为 它服务； 累计等待时间确定（此次）服务时间； 队列统计记录，队长度减1调度服务完成事件结束开始Y N离队操作(2) Petri 网络模型 Petri网模型最早在1962年 Carl Adam Petri的博士论文中提出来，主要特性是具有较 强的对并行、不确定性、异步和分布的描述能 力和分析能力。 Petri网是一个模型化的工具，它是设想来 用于模型化某一类问题：即有同时平行事件的 离散事件的系统的问题。Petri网模型化了系统 ，特别是系统的两个方面（事件和条件）及它 们之间的关系。(3)有限状态自动机模型 离散事件系统自动机及形式

13、语言理论最早是 由P. J .Ramadge 和W.M.Wonbarn 等人八十 年代中期提出的,现已成为DEDS 研究的重要方 法之一。 有限状态自动机模型描述方法主要适用于逻 辑定性模型和无时标确定性模型的建模。建立 有限状态自动机模型的关键是,基于适当的仿真 策略选用相应状态集合,建立正确的转移关系函 数和输出关系函数。4. 离散事件仿真策略与结构模型仿真过程的运行调度控制（特别是在用高级语言编程 时），是通过所谓的“仿真策略”来实现的。 例：对一个含有一些出纳员，一些顾客和对应每个出 纳员的银行（多）排队线的系统。 设：出纳员 数量5 服务速度 N(3,1)顾客 到达0.2, 0.8

14、统计 队列长度（平均，最大，最小，方差） 出纳员利用率（平均，最大，最小，方差） 顾客在银行的时间（平均，最大，最小，方差） 可以画出仿真程序的结构框图如下：预定仿真时间 TIME=0 预定第一个顾客到达时间开始TIME仿真预定时间有顾客到达选择排队线 将顾客插入排队线 *调度下一个顾客的到达时间输出统计结果结束在这一段时间内有事 务处理完（出纳空）顾客离去 选择排队线上的顾客给予服务 *调度为该顾客服务的完成时间TIME=TIME+1N Y N 到达事件 YNY这是种“面向时间”的时钟(TIME)处理。通过多次运行 程序（试验）统计得到结果。程序每做一次循环，就增加 一个时间单位。此时不论系

15、统是否有时间发生，程序总是 要查询系统状态，如发现没有时间发生就跳过该事件的处 理程序。 这种方法的特点是：能和连续模型（进行时间离散）混 合仿真。当事件子程序均能在一个时间单位内处理完成， 则TIME的+1操作可以在机器硬件时钟的控制下执行，即 仿真程序可以实时的（与机器时钟同步）运行。 缺点是：计算机做了很多不必要的空操作。因为在两个 相邻事件时刻之间，系统没有活动需要计算机处理。目前 很少使用此方法。 人们在研究了各种（离散）仿真调度方法的基础上，总 结出三种通用的仿真策略，即：事件预定，活动扫描和进 程互配。4.1 面向事件结构模型 面向事件结构模型是按事件独立预定策略 组建成的。对上述的银行系统为例，其仿真 程序结构框图： TIME仿真时 间开始调度第一次到达事件从事件表中选出最先要执行的事件作为当 前事件 将时间TIME拨到当前事件的发生时刻按当前事件类型分支选择排队线 将顾客插入该排队线 调度下一次到达事件的产生 时刻顾客离去 选排队线上某顾客接受服务 或“空闲”出纳员 调度本次服务完成（时间）输出统计结果