? ? ? ? ? ?
后到先服务LIFO ； 随机服务GIRO ；
按优先级别服务—— 根据队列中实体的重要程度选择最优先服务者。 混合制 条件损失制
时间阈值制（等待时间＋服务时间）
5.1.5 队列的度量
??? 服务机构的业务量强度：
??? 服务设备利用率——得到服务的动态实体的到达速度与服务速度之比： ?? 正常情况是服务设备利用率小于1，这样每个动态实体才有希望得到服务。利用率越高，实体排队等待的时间越长。
u??n/Tn???ns/Tns5.2 排队模型的分类
针对并列服务情形，标志性的符号形式是：X/Y/Z 其中，X——动态实体到达间隔时间的分布； Y——服务时间的分布； Z——并列的服务设备数量。
表示到达间隔时间和服务时间分布的典型符号有： M——负指数分布； Ek——k阶爱尔郎分布；
D——确定性； GI——一般相互独立的随机分布； G——一般随机分布。
M/M/1——到达间隔时间为负指数分布，服务时间为负指数分布，单服务设备的模型；
D/M/2——确定的到达间隔时间，服务时间为负指数分布，两台并行服务设备的模型。 GI/G/1
5.3 排队系统的分析
对于随机排队系统，在给定的到达和服务条件下，研究的是系统的运行指标：
? 在系统中动态实体数量的期望值 L s ，在系统队列中等待的动态实体数量（队列长
度）的期望值 L；q
? 在系统中动态实体逗留时间的期望值 W s ，在队列中动态实体等待时间（排队时间）
的期望值 W q
5.3.1 单服务台M/M/1模型
标准的M/M/1模型是指适合下列条件的排队系统： ? 到达模式：服从泊松分布；
? 排队规则：单对，且队列长度没有限制，先到先服务； ? 服务机构：单服务台，服务时间服从指数分布 设 ? 否则队列将排至无限远），则系统的运行指标为：
???1 ?(3?38)? 系统的平均顾客数（系统的期望值） (3?39)? 等待的平均顾客数（队列长度的期望值） (3?41)? 顾客逗留时间的期望值
21
(3?42)? 顾客等待时间（排队时间）的期望值 ? 例3-1
5.3.2 多服务台M/M/c模型
? 假设各服务台工作是相互独立且平均服务速度相同，即整个服务机构的平均服务速
? 时队列才不会出现无限长的情况。 度为 c ? ，只有当 ???1?? 令 ? ? 为这个系统的服务强度或服务台的平均利用率。 c?
多服务台系统的运行指标：
? 生产设备空闲概率 ? 系统状态概率
? 平均队长和平均队列长度 ? 平均等待时间和逗留时间 ? 例3－2
c? (3?51a) (3?51b) (3?52) (3?53)5.3.3 M/M/c和M/M/1模型比较
两种模型比较： 生产设备空闲概率 工件必须等待概率 平均队列长度 平均队长 平均逗留时间 平均等待时间
从各指标的对比可以看出，同样三个服务机构，同样的平均服务速度和顾客到达间隔时间分布，总体进行单队列的模式比三个服务台各自进行独立的队列模式有显著的优越性。
M/M/3 0.0748 0.57 1.7 3.95 4.39 1.89 M/M/1 0.25 0.75 2.25 3.00 10 7.5
第6章 系统仿真算法
基本概念
成份和实体是同一概念
在描述系统时，用实体 在描述模型时，用成份
? 主动成份：可以主动产生活动的成份、工件
? 被动成份：本身不产生活动，只有在主动成份作用下才产生状态变化的成份。
仿真钟
仿真钟：用于表示仿真时间的变化。
? 由于引起状态变化的事件发生时间的随机性，仿真钟的推进步长则完全是随机的；
22
? 而且，两个相邻发生的事件之间系统状态不会发生任何变化，因而仿真钟可以跨过
这些“不活动”周期。从一个事件发生时刻推进到下一事件发生时刻，仿真钟的推进呈现跳跃性，推进速度具有随机性。
统计计数器
统计计数器
离散事件动态系统的状态随着事件的不断发生呈现出动态变化，这种变化过程是随机的，某一次仿真运行得到的状态变化过程只不过是随机过程的一次取样。需要统计多次仿真运行的数据才有意义。
仿真钟的推进与仿真策略
仿真钟的推进：
? 下一事件步长法：按下一最早发生事件的发生时间推进。 ? 固定增量法：按固定的时间增量推进 。 下一事件步长法
举例： 单泊位码头系统，设
? ti ＝ 第i条船舶到达的时间；
? Si＝码头为第i条船舶装卸的时间长度； ? Di＝第i条船舶排队等待的时间长度； ? Ci＝ti+Di+Si为第i条船舶离去的时间；
? Ai＝ti-ti-1为第i-1条与第i条船舶到达之间的间隔时间； ? bi ：仿真钟推进的时间； 举例： 单泊位码头系统 系统事件类型：
类型1 船舶到达事件；类型2 船舶接受服务事件；类型3 船舶接受服务完毕并离去事件。 程序事件：仿真运行到9000个时间单位(例如分钟)结束
一般说来，Ai，Si是随机变量，要根据其分布函数来产生，为了便于解释，假定我们已经得到了这些随机变量的样本值为 A1=900，A2＝1920，A3=1440，A4=2400，A5=1320 S1=2580，S2=2160，S3=2040，S4=1680，… 下一事件步长法仿真钟推进时间：
A1=900，A2＝1920，A3=1440，A4=2400，A5=1320 S1=2580，S2=2160，S3=2040，S4=1680，…
S1 D2 b1 b2 b3 C1 A1
t1
S2 D3 b4 b5 C2 A4 t3
S3 D4 b6 b7 C3 A5 t4
S4 D5 b8 b9 C4 A2 t2
A3 t5
23
单泊位码头系统的事件表 时间 0 900 2820 3480 3480 4260 5640 5640 ··· ··· 9000 事件 仿真开始 船舶1到达 船舶2到达 船舶1服务完毕 船舶2接收服务 船舶3到达 船舶2服务完毕 船舶3接收服务 ··· ··· 仿真结束 泊位 状态 0 1 1 0 1 1 0 ··· ··· 排队 0 0 1 1 0 1 1 0 ··· ··· 固定增量推进法 选择适当的时间单位T作为仿真钟推进时的增量，每推进一步进行如下处理： A. 该步内若无事件发生，则仿真钟再推进一个单位时间T；
B. 若在该步内有若干个事件发生，则认为这些事件均发生在该步的结束时刻。为便于进行各类事件处理，用户必须规定当出现这种情况时各类事件处理的优先顺序。 1.事件调度法
事件调度法是通过定义事件，并按时间顺序处理所发生的一系列事件。记录每一事件发生时引起的系统状态的变化来完成系统的整个动态过程的仿真。
仿真钟是按下一事件步长法来推进的。通过建立事件表，将预定的事件按时间发生的先后顺序放入事件表中。仿真钟始终推进到最早发生的时刻。
2.活动扫描法
活动开始和结束是系统状态变化的标志。
而活动开始与结束不仅取决于时间因素，还取决于其他的因素(条件因素)。 活动扫描法的步骤：
1. 设置系统仿真钟TIME，即控制系统仿真时间。
2. 设置成分仿真钟 —— ta 表示各成分活动持续的预定时刻。用来控制成分活动的持续时间。
其中ta ≤TIME表示成分活动可以或早该发生，是否发生唯一取决于条件是否满足。 3. 设置条件处理模块——成分活动开始与结束的条件是否满足。
4. 设置成分活动子程序——处理活动开始与结束时系统的状态变化。
系统仿真钟、成分仿真钟的关系
? ta >Time 表示该活动将来某一时刻可能发生； ? ta =Time 表示该活动如果条件满足，立即发生； ? ta 活动扫描法的处理过程： 1. 扫描所有的活动。 2. 对ta ≤TIME的成分进行条件检测，看其活动开始与结束的条件是否满足，满足则是可激活成分。 3. 对所有激活的成分，处理其相应的活动子程序，即修改系统的有关状态，并修改成分仿 24 真钟。 4. 推进系统仿真钟TIME到下一个最早发生的活动生成时刻。 5. 继续(1)一(4)的步骤，直至仿真结束。 3.进程交互法 进程由若干个有序事件及若干有序活动组成 。 一个成分进入系统，完成各项活动的过程可以由一个进程来描述。进程交互法是事件调度法与活动扫描法的结合。它是以模型的各个主动成分的活动为主线来调度事件生成的顺序的。 该法将模型中的主动成分历经系统时所发生的事件及活动，按时间顺序加以组合，形成进度表。一旦一个成份进入系统，在条件满足的情况下，它就完成该进程的全部活动。 进程交互法 的几个概念 ? 当前事件表CEL（Current Events List)： 它包括从当前时间开始，有资格执行的事件的记录。但是该事件是否发生的条件尚需要判断。 ? 将来事件表FEL (Future Events List)： 它包括将来某个时刻发生的事件的记录。每个事件记录中包含该事件的若干属性，其中之一是该事件在进程中的位置指针。 进程交互法 的处理过程 1. 执行初始化操作 ? 置初始时间t0 结束时间 t e ? 设置初始化事件，并置于FEL中 ? 将FEL中有关事件记录置于CEL中 ? 成份状态初始化S=（（ s ?1 t?1）… （s ?m t?m）… （s ?n t?n）) 2. 推进系统仿真钟 TIME ＝FEL中最早时间 3. 把满足ta ≤TIME的所有事件从FEL移至CEL中。 4. 取出CEL中的每一个事件，判断其所属的进程及在进程中的位置。 5. 判断该事件发生的条件是否满足。 6. 如果条件允许该进程尽可能连续推进，直到进程结束，该成分离开系统。 7. 该进程推进过程中，遇到条件不满足时，记录下进程的位置，并退出该进程。 8. 重复(4)～（7），CEL中的事件处理完毕。 9. 重复(2)～(8)，直到仿真结束。 三种仿真算法 上述所介绍的三种仿真策略，事件调度法、活动扫描法和进程交互法各有优缺点。在离散事件系统仿真中均得到广泛的应用。许多仿真语言允许用户在同一仿真语言中用不同的算法建模。 一般来说，如果系统中的成分相关性较少，宜采用事件调度法，相反则宜采用活动扫描法；如果系统成分的活动比较规则，则宜采用进程交互法。 25