第三章
通信网结构
3.1.
图论基础
3.1.1.
基本定义
3.1.2.
图的联结性
3.2.
最短径问题
3.2.1.
最短主树
3.2.2.
端间的最短径问题
3.2.3.
最佳流问题
第四章
网内业务分析
4.1.
排队论基础
− 概述
≡ 排队系统的构成
∆ 要求服务的顾客
∆ 提供服务的服务员
∆ 排队规则
∆ 如图
顾客源
队列
排队规则
顾客到达
服务机构
服务规则
离去
排队系统
≡ 排队论也称为随机服务系统理论
∆ 主要研究三方面的内容
• 性能问题
即研究各种排队系统的概率规律性
队列长度的分布
等待时间的分布
忙期分布等
包括瞬态情形和稳态情形两种
• 最优化问题
静态最优化
即研究最优设计
动态最优化
即研究现有排队系统的最优运营
• 排队系统的统计推断
判断一个实际排队系统符合哪种模型
以便根据排队理论进行分析研究
4.1.1.
基本概念
− 排队系统的特征
= 输入过程
≡ 输入
指顾客达到排队系统
≡ 顾客源
即顾客的总体 可能是有限的 也可能是无限的
≡ 顾客到来的方式
可能是一个一个的 也可以是成批的
≡ 顾客相继到达的间隔时间
可以是确定型的 也可以是随机型的
≡ 顾客的到达可以是相互独立的
也可以是相关联的
≡ 输入过程可以是平稳的
或称为对时间是齐次的
= 排队规则
≡ 即时制或损失制
∆ 顾客到达时
若所有服务台都已被占用 则顾客随即离去
≡ 等待制
∆ 顾客到达时
若所有服务台都已占用 则顾客排队等候
∆ 在等待制中
为顾客服务的次序可以有如下一些规则
• 先到先服务
• 后到先服务
• 随机服务
• 优先级服务
≡ 队列长度
∆ 限长队列
∆ 无限队列
≡ 队列数目
∆ 单列队列
∆ 多列队列
= 服务机构
≡ 服务机构可以没有服务员
∆ 也可以有一个服务员
∆ 还可以有多个服务员
服务台 通道 窗口等
≡ 在多个服务台的情况下
∆ 各服务台可以是并列的
∆ 各服务台可以是串列的
∆ 各服务台可以是串并混合排列的
≡ 服务方式
∆ 对单个顾客进行服务
∆ 对成批顾客进行服务
≡ 服务时间
∆ 确定型服务时间
∆ 随机型服务时间
≡ 服务过程通常假定是平稳的
− 排队模型的分类
= Kendall 分类法
1
顾客相继到达的间隔时间的分布
2
服务时间的分布
3
服务台个数
∆ 按照这三个特征分类
并用符号形式表示
X/Y/Z
• X
表示相继到达的间隔时间的分布
• Y
表示服务时间的分布
• Z
表示并列的服务台的数目
≡ 间隔时间和服务时间的各种分布有
∆ M
负指数分布
∆ D
确定型分布
∆ E
k
k 阶爱尔朗 Erlang
分布
∆ GI
一般相互独立的时间间隔分布
∆ G
一般服务时间的分布
∆ H
R
R 阶指数分布
≡ 排队模型举例
∆ M/M/1
表示相继到达的间隔时间为负指数分布
服务时间为负指数分布
单服务台的排队模型
∆ D/M/C
表示确定的到达的间隔 负指数分布的服务时间
C 个服务台
但顾客排一队 的排队模型
∆ M/M/1 问题称为初级问题或基本问题
∆ G/M/1 和 M/G/1 问题称为中级问题
∆ G/G/1 和 G/G/m 问题称为高级问题
• 其中包括 E
r
/G/1 G / E
r
/1 E
r
/ E
k
/1 等成批到达/离开问题
≡ 在 1971 年一次关于排队论符号标准化会议上
∆ 决定对 Kendall 符号进行扩充
∆ X/Y/Z /A/B/C
• 前三项意义不变
• A 处填写系统容量限制 N
即队长限于 N 个以内
• B 处填写顾客源数目 m
• C 处填写服务规则
如 先到先服务 FCFS 后到先服务 LCFS
等
∆ 并约定
如果略去后三项 则意味着
X/Y/Z /∞/∞/FCFS
− 排队问题的求解
= 一个实际问题作为排队问题求解时
≡ 首先要研究它属于哪个模型
≡ 其中
只有顾客到达的间隔时间分布和服务时间的分布 需要根据
实际测量的数据来确定
≡ 其它因素都是在问题提出时给定的
= 求解排队问题的目的
≡ 是研究排队系统运行的效率
≡ 估计服务质量
≡ 确定系统参数的最优值
≡ 判断系统结构的合理性
≡ 研究
设计改进的措施等
= 排队系统运行的基本指标
≡ 系统队长
在系统中的顾客数 其期望值记为 L
s
≡ 队列长
在系统中 排队等待服务的顾客数 期望值为 L
q
∆ 系统中的顾客数
排队等待服务的顾客数 正被服务的顾客数
≡ 逗留时间
一个顾客在系统中停留的时间 期望值记为 Ws
≡ 等待时间
一个顾客在系统中排队等待的时间期望值记为 Wq
∆ 逗留时间
等待时间 服务时间
∆ 列德尔
Little
公式 适用于任何排队系统
• W
s
L
s
≡ 忙期
∆ 从顾客到达空闲服务机构起
直到服务机构再次空闲为止 这段
时间长度
∆ 忙期和一个忙期中平均完成服务的顾客数是衡量服务机构效率的
指标
≡ 系统效率 η
∆ 即平均服务台占用率
∆ 设共有 m 个服务台
∆ 某时刻有 r 个服务台被占用
∆ 则占用率为
r/m
• 它是一个随机变量
∆ 其统计平均值即为系统效率
m
r
=η
∆ 对于单服务台系统 η
忙期效率
∆ η 越大
服务资源的利用率越高
≡ 损失率
∆ 在即时制或队长有限制的系统中
∆ 由于拒绝顾客进入系统而带来的损失
≡ 系统强度 ρ
∆ 定义为顾客到达率
与服务率 μ 之比
ρ /μ
• 当 ρ 大于服务台数 m 时
系统变得不稳定
• 当 ρ 小于服务台数 m 时
系统是稳定的
∆ 对于截止型系统
• 由于队长被人为地限制
即使 ρ > m 系统仍能稳定地工作
= 这些指标的计算基础