第二篇 离散事件系统仿真
第十章 离散事件系统仿真基础
10.1 基本概念
刘军，剡昌锋
兰州理工大学
机电学院 裂纹所
2006/09/20
离散事件动态系统
? CVDS(连续变量动态系统）,
1）本质上属于物理世界范畴；
2）动态过程服从物理学或广义物理学规律；
3）数学模型：微分或差分方程。
? DEDS(离散事件动态系统）,
1）本质上属于人造系统范畴；
2）系统状态在离散时间点上发生跃变，状态变化具有
异步性和并发性、不确定性；
3）服从人为的逻辑规则，通常不能用传统的微分或差
分方程描述。
（离散事件触发并决定系统进程；排队论、网络分析、计
划评审、调度排序等研究的对象都可纳入到 DEDS的范
畴）
一个例子
单人理发馆系统,设上午 9:00开门,下午 5:00关
门,
? 顾客到达时间一般是随机的,为每个顾客服
务的时间长度也是随机的。
? 系统的状态：服务台的状态 (忙或闲 )、顾客
排队等待的队长。
? 状态量的变化也只能在离散的随机时间点
上发生。
几个仿真基础概念
? 实体 （临时实体及永久实体）,
永久实体是系统处于活动的必要条件 ；临时实体按一
定规律不断地到达（产生）,在永久实体作用下通过系
统,最后离开系统,整个系统呈现出动态过程。
? 事件 （引起系统状态发生变化的行为）,
,顾客到达” ；“顾客离去”；
系统事件,系统固有事件，“程序事件”,用于控制仿
真进程
? 事件表
对系统中的事件进行管理，记录每一发生了的或将要
发生的事件 及其相关属性等 。
几个仿真基础概念
?活动 （ 表示两个可以区分的事件之间的过程,
它标志着系统状态的转移 ）,
顾客的到达事件
与该顾客开始接
受服务事件之间
可称为一个活动。
? 进程 （ 由若干个事件及若干活动组成）,
一个进程描述了它所包括的事件及活动间的相互逻辑关
系及时序关系。
进 程
排队
活动
服务
活动
顾客到达事件 服务开始事件 服务结束事件
图 10.1 事件、活动、进程三者关系示意图
几个仿真基础概念
?仿真钟 （临时实体及永久实体）,
1）离散事件动态系统的状态本来就只在离散时间点上
发生变化,因而不需要进行离散化处理 ；
2）由于引起状态变化的事件发生时间的随机性,仿真钟
的推进步长则完全是随机的 ；
3）两个相邻发生的事件之间系统状态不会发生任何变
化，因而仿真钟可以跨过这些“不活动”周期,仿真钟
的推进呈现跳跃性，推进速度具有随机性 ；
4）时间控制部件 是必不可少的,以便按一定规律来控制
仿真钟的推进。
?统计计数器
在仿真模型中,需要有一个 统计计数部件,以便统计系统
中的有关变量。
10.2 仿真钟的推进
? 事件调度法,
按下一最早发生事件的发生时间推进；
? 固定增量时间推进,
选择适当的时间单位 T做为仿真钟推进时的增量,每推
进一步进行如下处理,
(1) 该步内若无事件发生,则仿真钟再推进一个单位时间
T;
(2) 若在该步内有若干个事件发生,则认为这些事件均发
生在该步的结束时刻。
事件调度法 (Event Scheduling)
例 10.2 单服务台排队系统,如单窗口的售票站。设,
事件调度法 (Event Scheduling)
?,22,40,24,32,15 54321 ????? AAAAA
S S S S1 2 3 443 36 34 28? ? ? ?,,,,?
q Z0 00 0? ?,
1）假定已经得到到达时间间隔随机变量的样本值为,
系统初始状态,
时间 事件 服务员状态 排队长度
0 仿真开始 0 0
15 顾客 1到达 1 0
47 顾客 2到达 1 1
58 顾客 1服务完毕 0 1
58 顾客 2接受服务 1 0
71 顾客 3到达 1 1
94 顾客 2服务完毕 0 1
94 顾客 3接受服务 1 0
...,..,..,.,
150 仿真结束
2）事件列表
事件调度法 (Event Scheduling)
3）程序框图
顾客到达 (时间间隔 (Ai )
服务员空闲否
开始服务
服务完毕
顾客离去
排队等待
经过 Si
是
否
图 10.2 单服务台仿真模型
事件调度法 (Event Scheduling)
4)分析仿真钟的推进过程,
初始值, TIME=
00 tb ?
下一最早发生事件,为第 1号顾客到达,发生时刻为 b1
t b
1 1? t t A1 0 1 15? ? ?
即,
,
因 （ 1） 仿真钟推进到
t1 150? t
1
然后处理该事件。
到达事件,且 Z
0 0?
,立即服务,即 D1 0? 服务台状态由 Z
0 0?变为
Z
0 1?
预定该顾客的离去时间,服务时间为 S
1 43?
,则其为,
C t S Dt ? ? ? ? ? ? ?1 1 1 15 43 0 58
事件调度法 (Event Scheduling)
下一最早发生事件,仍是到达事件,因为
t t A C2 1 2 115 32 47? ? ? ? ? ?,从而 b t2 2 47? ?
（ 2）仿真钟推进到 t
2
,处理该到达事件,
因,顾客排队等待，队长 Z1 1? q q
2 1 1 1? ? ?
,该顾客开始等待时间为 t2
下一最早发生事件,
应是第 1号顾客离去事件,因下一到达事件发生时间为,
t t A C3 2 2 147 24 71? ? ? ? ? ?,从而 b C3 1?
（ 3）仿真钟推进到 58
1 ?C
,处理第 1号顾客的离去事件,包括,
事件调度法 (Event Scheduling)
统计服务人数 ; 观察队列中是否有顾客等待等。
目前,则该顾客进入服务,同时要计算其排队等待的时间 q2 1?
D C t2 1 2? ? ；修改队长 q q
3 2 1 0? ? ?
预定该顾客的离去时间,因服务时间为 S2 36?,其离去时间
C C S2 1 2 94? ? ?
下一最早发生事件,由
32 tC ?
,因而下一事件应是到达事件,
（ 4）仿真钟推进到 ?
34 tb ?
依次下去,直到下一事件为仿真结束的程度事件为止。
事件调度法 (Event Scheduling)
固定增量时间推进
缺点,
1)仿真钟每推进一步,均要检查事件表以确定是否有事
件发生,增加了执行时间 ;
2)每步：任何事件的发生均认为发生在这一步的结束
时刻,如果 T选择过大,则会引入较大的误差 ;
3)要求事先确定各类事件的处理顺序,增加了建模的复
杂性。
主要用于系统事件发生时间具有较强周期性的模型
选择适当的时间单位 T做为仿真钟推进时的增量
10.3 排队系统
(1) 实体 (顾客 )到达模式
确定性到达及随机性到达
平稳 poisson过程可描述为,
?在 (t,t+s) 内到达的实体数 k的概率为,
P N t s N t k e sk
s k
{ ( ) ( ) } ( )!? ? ? ?
? ? ?
Nt( ) (,)0 t其中 表示在 区间内到达实体的个数,
t s k? ? ?0 0 0 1 2,,,,,,? ?为到达速率。
?平稳过程的到达时间间隔服从指数分布,其密度函数为,
f t e et t( ) /? ?? ?? ?? ?1
??? /1其中 为到达时间间隔均值。
10.3 排队系统
(2) 服务模式
描述服务台为顾客服务的时间：可以是 确定性 的,
也可 能是 随机 的。
(3) 排队规则
表示服务台完成当前的服务后,从队列中选择下一实体的
原则,一般有,
FIFO——先到先服务 ; LIFO——后到先服务 ;
按优先级别服务 ——根据队列中实体的重要程度选择
最优先服务者。
10.3 排队系统
(4) 服务流程
（多个服务台,多个队列,如何从某一个队列中选择某一
个实体服务,包括实体可否换队及换队规则等 ）
排队系统中的上述四个特征,一般用符号 GI/G/S来表示,
EK K
D
GI(General Independent)----到达模式。到达时间间隔服从 指
数分布,用 M表示,Erlang分布用 表示,
的维数 ;确定性时间间隔 用 表示。
表示 Erlang分布
G(General)----服务时间的分布,分布函数的符号与 GI相同。
S----单队多服务台的数目,且按 FIFO规则服务。
10.3 排队系统
（ 5）排队系统性能指标,
10.3 排队系统
10.4 库存系统
1,库存系统的基本概念
“需求,与,订货,,生产,与,需求,
由于需求与订货的不断发生,库存量 呈现动态变化。
确定性库存系统,
需求量是确定性的,需求发生时间也是确定性的,同
时,订货量与订货发生时间是确定性的,且从订货到货
物入库的时间都是确定性的。
随即库存系统,
一般只有通过仿真才有可能进行较深入的研究。
10.4 库存系统
2、研究目的
一般是要确定或比较各种库存策略,它包括在不同的需求情
况下,何时订货,订多少货为宜等。
3、库存策略的评价 一般则采用,费用” 高低来衡量库存策略的优劣,
(1) 保管费（存储费） (2) 订货费（生产费）
(3) 缺货损失费
10.4 库存系统
4,确定性库存系统
10.4 库存系统
10.4 库存系统
注,
1） 如果考虑 订货滞后,对确定性货物到达存在滞后时间
的库存系统来说，仍可采用上述模型，只需要确定订货的
提前期 (1-?)T。在考虑提前期的情况下，订货发生的时刻为
?T，此时的库存水平用 R来表示，称为 订货点 。
2） 在这两种情况下，平均库存量均为 0.5Q。 --------采
用 安全库存订货策略 。
10.4 库存系统
如果在某一提前期下所订货物不能在 nT(n=1,2,…)
时刻到达，则可能出现两种情况,
（ 1）发生缺货 （ 2）库存加大
若 允许缺货,设一周期内非缺货时间的百分比为 ?,Q
（考虑提前期）的库存模型可用图 10,7 表示,
10.4 库存系统
10.4 库存系统
平均缺货量 Qq，平均库存量 Q 及总费用 C如下,
其中,C2表示每件缺货引起的损失费。
10.4 库存系统
10.4 库存系统
5、随机库存系统,
随机,提前期（ 1-?） T, 单位时间的需求量。
最简单的随机库存系统：每次订货量 Q不变，订货点 R不变,
10.4 库存系统
问题：总费用最小的最优订货点、每次最优订货量及总费用。
设每周期期望库存量为 I，则
)y(EQRI ??? 2
其中,R＋ 0.5Q,无提前期时每周期的期望库存量,y为
提前期内的随机需求量,E(y)是 y的期望值。设每周期期
望缺货数为 S,
S y R h y
y R
? ?
?
?
? ( ) ( )
其中 h(y)是提前期需求量 y的速度函数,每年所需费用为 C，则
C C DQ C I C DQ S? ? ?0 1 2
10.4 库存系统
将 I,S表达式代入，可得
C C DQ C R Q E y C DQ y R h y
y R
? ? ? ? ? ??
?
?
?
?
?
?
??
0 1 22( ( )) ( ) ( )
求最佳订货点 R,
10.4 库存系统
6、仿真举例
10.4 库存系统
10.4 库存系统
10.4 库存系统
问题,现需要比较如下 9种订货策略,以便确定何种策略费
用最少,
l 20 20 20 20 40 40 40 60 60
S 40 60 80 100 60 80 100 80 100
10.4 库存系统
离散事件系统仿真研究的一般步骤,
1,系统建模,
2,确定仿真算法,
3,建立仿真模型
4,设计仿真程序
5,仿真结果分析
10.4 库存系统
10.4 库存系统
一库存系统，一年的总订货量为 3000件，初始值
为 100件，每月的消耗量相等（按 25天计算），消耗速
度相同，按月订货，每月缺货的天数允许为 3天，提前
期为 5天，试画出库存随时间变化的曲线；若每件货物
的保管费为 1元，每次订货费为 5元，每件货物短缺引
起的损失费为 2元，试解析计算出全年的总费用及订货
点库存水平。
习 题
第十章 离散事件系统仿真基础
10.1 基本概念
刘军，剡昌锋
兰州理工大学
机电学院 裂纹所
2006/09/20
离散事件动态系统
? CVDS(连续变量动态系统）,
1）本质上属于物理世界范畴；
2）动态过程服从物理学或广义物理学规律；
3）数学模型：微分或差分方程。
? DEDS(离散事件动态系统）,
1）本质上属于人造系统范畴；
2）系统状态在离散时间点上发生跃变，状态变化具有
异步性和并发性、不确定性；
3）服从人为的逻辑规则，通常不能用传统的微分或差
分方程描述。
（离散事件触发并决定系统进程；排队论、网络分析、计
划评审、调度排序等研究的对象都可纳入到 DEDS的范
畴）
一个例子
单人理发馆系统,设上午 9:00开门,下午 5:00关
门,
? 顾客到达时间一般是随机的,为每个顾客服
务的时间长度也是随机的。
? 系统的状态：服务台的状态 (忙或闲 )、顾客
排队等待的队长。
? 状态量的变化也只能在离散的随机时间点
上发生。
几个仿真基础概念
? 实体 （临时实体及永久实体）,
永久实体是系统处于活动的必要条件 ；临时实体按一
定规律不断地到达（产生）,在永久实体作用下通过系
统,最后离开系统,整个系统呈现出动态过程。
? 事件 （引起系统状态发生变化的行为）,
,顾客到达” ；“顾客离去”；
系统事件,系统固有事件，“程序事件”,用于控制仿
真进程
? 事件表
对系统中的事件进行管理，记录每一发生了的或将要
发生的事件 及其相关属性等 。
几个仿真基础概念
?活动 （ 表示两个可以区分的事件之间的过程,
它标志着系统状态的转移 ）,
顾客的到达事件
与该顾客开始接
受服务事件之间
可称为一个活动。
? 进程 （ 由若干个事件及若干活动组成）,
一个进程描述了它所包括的事件及活动间的相互逻辑关
系及时序关系。
进 程
排队
活动
服务
活动
顾客到达事件 服务开始事件 服务结束事件
图 10.1 事件、活动、进程三者关系示意图
几个仿真基础概念
?仿真钟 （临时实体及永久实体）,
1）离散事件动态系统的状态本来就只在离散时间点上
发生变化,因而不需要进行离散化处理 ；
2）由于引起状态变化的事件发生时间的随机性,仿真钟
的推进步长则完全是随机的 ；
3）两个相邻发生的事件之间系统状态不会发生任何变
化，因而仿真钟可以跨过这些“不活动”周期,仿真钟
的推进呈现跳跃性，推进速度具有随机性 ；
4）时间控制部件 是必不可少的,以便按一定规律来控制
仿真钟的推进。
?统计计数器
在仿真模型中,需要有一个 统计计数部件,以便统计系统
中的有关变量。
10.2 仿真钟的推进
? 事件调度法,
按下一最早发生事件的发生时间推进；
? 固定增量时间推进,
选择适当的时间单位 T做为仿真钟推进时的增量,每推
进一步进行如下处理,
(1) 该步内若无事件发生,则仿真钟再推进一个单位时间
T;
(2) 若在该步内有若干个事件发生,则认为这些事件均发
生在该步的结束时刻。
事件调度法 (Event Scheduling)
例 10.2 单服务台排队系统,如单窗口的售票站。设,
事件调度法 (Event Scheduling)
?,22,40,24,32,15 54321 ????? AAAAA
S S S S1 2 3 443 36 34 28? ? ? ?,,,,?
q Z0 00 0? ?,
1）假定已经得到到达时间间隔随机变量的样本值为,
系统初始状态,
时间 事件 服务员状态 排队长度
0 仿真开始 0 0
15 顾客 1到达 1 0
47 顾客 2到达 1 1
58 顾客 1服务完毕 0 1
58 顾客 2接受服务 1 0
71 顾客 3到达 1 1
94 顾客 2服务完毕 0 1
94 顾客 3接受服务 1 0
...,..,..,.,
150 仿真结束
2）事件列表
事件调度法 (Event Scheduling)
3）程序框图
顾客到达 (时间间隔 (Ai )
服务员空闲否
开始服务
服务完毕
顾客离去
排队等待
经过 Si
是
否
图 10.2 单服务台仿真模型
事件调度法 (Event Scheduling)
4)分析仿真钟的推进过程,
初始值, TIME=
00 tb ?
下一最早发生事件,为第 1号顾客到达,发生时刻为 b1
t b
1 1? t t A1 0 1 15? ? ?
即,
,
因 （ 1） 仿真钟推进到
t1 150? t
1
然后处理该事件。
到达事件,且 Z
0 0?
,立即服务,即 D1 0? 服务台状态由 Z
0 0?变为
Z
0 1?
预定该顾客的离去时间,服务时间为 S
1 43?
,则其为,
C t S Dt ? ? ? ? ? ? ?1 1 1 15 43 0 58
事件调度法 (Event Scheduling)
下一最早发生事件,仍是到达事件,因为
t t A C2 1 2 115 32 47? ? ? ? ? ?,从而 b t2 2 47? ?
（ 2）仿真钟推进到 t
2
,处理该到达事件,
因,顾客排队等待，队长 Z1 1? q q
2 1 1 1? ? ?
,该顾客开始等待时间为 t2
下一最早发生事件,
应是第 1号顾客离去事件,因下一到达事件发生时间为,
t t A C3 2 2 147 24 71? ? ? ? ? ?,从而 b C3 1?
（ 3）仿真钟推进到 58
1 ?C
,处理第 1号顾客的离去事件,包括,
事件调度法 (Event Scheduling)
统计服务人数 ; 观察队列中是否有顾客等待等。
目前,则该顾客进入服务,同时要计算其排队等待的时间 q2 1?
D C t2 1 2? ? ；修改队长 q q
3 2 1 0? ? ?
预定该顾客的离去时间,因服务时间为 S2 36?,其离去时间
C C S2 1 2 94? ? ?
下一最早发生事件,由
32 tC ?
,因而下一事件应是到达事件,
（ 4）仿真钟推进到 ?
34 tb ?
依次下去,直到下一事件为仿真结束的程度事件为止。
事件调度法 (Event Scheduling)
固定增量时间推进
缺点,
1)仿真钟每推进一步,均要检查事件表以确定是否有事
件发生,增加了执行时间 ;
2)每步：任何事件的发生均认为发生在这一步的结束
时刻,如果 T选择过大,则会引入较大的误差 ;
3)要求事先确定各类事件的处理顺序,增加了建模的复
杂性。
主要用于系统事件发生时间具有较强周期性的模型
选择适当的时间单位 T做为仿真钟推进时的增量
10.3 排队系统
(1) 实体 (顾客 )到达模式
确定性到达及随机性到达
平稳 poisson过程可描述为,
?在 (t,t+s) 内到达的实体数 k的概率为,
P N t s N t k e sk
s k
{ ( ) ( ) } ( )!? ? ? ?
? ? ?
Nt( ) (,)0 t其中 表示在 区间内到达实体的个数,
t s k? ? ?0 0 0 1 2,,,,,,? ?为到达速率。
?平稳过程的到达时间间隔服从指数分布,其密度函数为,
f t e et t( ) /? ?? ?? ?? ?1
??? /1其中 为到达时间间隔均值。
10.3 排队系统
(2) 服务模式
描述服务台为顾客服务的时间：可以是 确定性 的,
也可 能是 随机 的。
(3) 排队规则
表示服务台完成当前的服务后,从队列中选择下一实体的
原则,一般有,
FIFO——先到先服务 ; LIFO——后到先服务 ;
按优先级别服务 ——根据队列中实体的重要程度选择
最优先服务者。
10.3 排队系统
(4) 服务流程
（多个服务台,多个队列,如何从某一个队列中选择某一
个实体服务,包括实体可否换队及换队规则等 ）
排队系统中的上述四个特征,一般用符号 GI/G/S来表示,
EK K
D
GI(General Independent)----到达模式。到达时间间隔服从 指
数分布,用 M表示,Erlang分布用 表示,
的维数 ;确定性时间间隔 用 表示。
表示 Erlang分布
G(General)----服务时间的分布,分布函数的符号与 GI相同。
S----单队多服务台的数目,且按 FIFO规则服务。
10.3 排队系统
（ 5）排队系统性能指标,
10.3 排队系统
10.4 库存系统
1,库存系统的基本概念
“需求,与,订货,,生产,与,需求,
由于需求与订货的不断发生,库存量 呈现动态变化。
确定性库存系统,
需求量是确定性的,需求发生时间也是确定性的,同
时,订货量与订货发生时间是确定性的,且从订货到货
物入库的时间都是确定性的。
随即库存系统,
一般只有通过仿真才有可能进行较深入的研究。
10.4 库存系统
2、研究目的
一般是要确定或比较各种库存策略,它包括在不同的需求情
况下,何时订货,订多少货为宜等。
3、库存策略的评价 一般则采用,费用” 高低来衡量库存策略的优劣,
(1) 保管费（存储费） (2) 订货费（生产费）
(3) 缺货损失费
10.4 库存系统
4,确定性库存系统
10.4 库存系统
10.4 库存系统
注,
1） 如果考虑 订货滞后,对确定性货物到达存在滞后时间
的库存系统来说，仍可采用上述模型，只需要确定订货的
提前期 (1-?)T。在考虑提前期的情况下，订货发生的时刻为
?T，此时的库存水平用 R来表示，称为 订货点 。
2） 在这两种情况下，平均库存量均为 0.5Q。 --------采
用 安全库存订货策略 。
10.4 库存系统
如果在某一提前期下所订货物不能在 nT(n=1,2,…)
时刻到达，则可能出现两种情况,
（ 1）发生缺货 （ 2）库存加大
若 允许缺货,设一周期内非缺货时间的百分比为 ?,Q
（考虑提前期）的库存模型可用图 10,7 表示,
10.4 库存系统
10.4 库存系统
平均缺货量 Qq，平均库存量 Q 及总费用 C如下,
其中,C2表示每件缺货引起的损失费。
10.4 库存系统
10.4 库存系统
5、随机库存系统,
随机,提前期（ 1-?） T, 单位时间的需求量。
最简单的随机库存系统：每次订货量 Q不变，订货点 R不变,
10.4 库存系统
问题：总费用最小的最优订货点、每次最优订货量及总费用。
设每周期期望库存量为 I，则
)y(EQRI ??? 2
其中,R＋ 0.5Q,无提前期时每周期的期望库存量,y为
提前期内的随机需求量,E(y)是 y的期望值。设每周期期
望缺货数为 S,
S y R h y
y R
? ?
?
?
? ( ) ( )
其中 h(y)是提前期需求量 y的速度函数,每年所需费用为 C，则
C C DQ C I C DQ S? ? ?0 1 2
10.4 库存系统
将 I,S表达式代入，可得
C C DQ C R Q E y C DQ y R h y
y R
? ? ? ? ? ??
?
?
?
?
?
?
??
0 1 22( ( )) ( ) ( )
求最佳订货点 R,
10.4 库存系统
6、仿真举例
10.4 库存系统
10.4 库存系统
10.4 库存系统
问题,现需要比较如下 9种订货策略,以便确定何种策略费
用最少,
l 20 20 20 20 40 40 40 60 60
S 40 60 80 100 60 80 100 80 100
10.4 库存系统
离散事件系统仿真研究的一般步骤,
1,系统建模,
2,确定仿真算法,
3,建立仿真模型
4,设计仿真程序
5,仿真结果分析
10.4 库存系统
10.4 库存系统
一库存系统，一年的总订货量为 3000件，初始值
为 100件，每月的消耗量相等（按 25天计算），消耗速
度相同，按月订货，每月缺货的天数允许为 3天，提前
期为 5天，试画出库存随时间变化的曲线；若每件货物
的保管费为 1元，每次订货费为 5元，每件货物短缺引
起的损失费为 2元，试解析计算出全年的总费用及订货
点库存水平。
习 题
