1
第十三章 排队论
? 排队过程的组成部分
? 单服务台泊松到达、负指数服务时间的排队模型
? 多服务台泊松到达、负指数服务时间的排队模型
? 排队系统的经济分析
? 单服务台泊松到达、任意服务时间的排队模型
? 单服务台泊松到达、定长服务时间的排队模型
? 多服务台泊松到达、任意的服务时间、损失制排队
模型
? 顾客来源有限制排队模型
2
§ 1 排队过程的组成部分 (1)
一, 基本概念
? 一些排队系统的例子 。
排队系统 顾 客 服务台 服 务
电话系统 电话呼叫 电话总机 接通呼叫或取消呼叫
售票系统 购票旅客 售票窗口 收款、售票
设备维修 出故障的设备 修理工 排除设备故障
防空系统 进入阵地的敌机 高射炮 瞄准、射击直至敌机被击落或离开
? 排队的过程可表示为:
排队系统
顾客到达 排队 服务机构服务 顾客离去
3
§ 1 排队过程的组成部分 (2)
? 考虑要点:
1、服务台个数:单服务台、多服务台
2、顾客到达过程:本教材主要考虑顾客泊松到达情况。
满足以下四个条件的输入流称为泊松流(泊松过程)
*平稳性:在时间区间 [t,t+?t)内到达 k个顾客的概率与 t无关,只与 ?t有关。记为 pk(?t)。
*无后效性:不相交的时间区间内到达的顾客数互相独立。
*普通性:在足够短的时间内到达多于一个顾客的概率可以忽略;
*有限性:任意有限个区间内到达有限个顾客的概率等于 1。
泊松分布 ? 为单位时间平均到达的顾客数
P (x) = ?x e-? / x! (x = 0,1,2,……)
3、服务时间分布,服从负指数分布 ? 为平均服务率,即单位时间服务的顾客数。
P(服务时间 ≤ t ) = 1- e-? t
4、排队规则分类
(1)等待制:顾客到达后,一直等到服务完毕以后才离去;
先到先服务,后到先服务,随机服务,有优先权的服务。
(2)损失制:到达的顾客有一部分未接受服务就离去;
5、平稳状态,业务活动与时间无关。
4
§ 2 单服务台泊松到达、负指数
服务时间的排队模型
? 记号,M / M / 1 / ∞ / ∞
? 条件,单位时间顾客平均到达数 ?
单位平均服务顾客数 ?
? 关心的项目,
1、系统中无顾客的概率 P0
2、系统中平均排队的顾客数 Lq
3、系统中的平均顾客数 Ls
4、系统中顾客平均的排队等待时间 Wq
5、系统中顾客的平均逗留时间 Ws
6、系统中顾客必须排队等待的概率 Pw
7、系统中恰好有 n 个顾客的概率 Pn
5
§ 3 多服务台泊松到达、负指数
服务时间的排队模型
? 记号,M / M / C / ∞ / ∞
? 条件,单位时间顾客平均到达数 ?
单位平均服务顾客数 ?
? 关心的项目,
1、系统中无顾客的概率 P0
2、系统中平均排队的顾客数 Lq
3、系统中的平均顾客数 Ls
4、系统中顾客平均的排队等待时间 Wq
5、系统中顾客的平均逗留时间 Ws
6、系统中顾客必须排队等待的概率 Pw
7、系统中恰好有 n 个顾客的概率 Pn
6
§ 4 排队系统的经济分析
? 公式,TC = cw Ls + cs c
? 其中,
cw 一个顾客在排队系统中逗留单位时间付出的费用
Ls 在排队系统中的平均顾客数
cs 每个服务台单位时间的费用
c 服务台个数
7
§ 5 单服务台泊松到达、任意服
务时间的排队模型
? 记号,M / G / 1 / ∞ / ∞
? 条件:
单位时间顾客平均到达数 ? 单位平均服务顾客数 ?
一个顾客的平均服务时间 1 / ? 服务时间的均方差 ?
? 关心的项目,
1、系统中无顾客的概率 P0
2、系统中平均排队的顾客数 Lq
3、系统中的平均顾客数 Ls
4、系统中顾客平均的排队等待时间 Wq
5、系统中顾客的平均逗留时间 Ws
6、系统中顾客必须排队等待的概率 Pw
7、系统中恰好有 n 个顾客的概率 Pn
8
§ 6 单服务台泊松到达、定长服
务时间的排队模型
? 记号,M / D / 1 / ∞ / ∞
? 注:是 M / G / 1 / ∞ / ∞ 的特殊情况 ? = 0
? 关心的项目,
1、系统中无顾客的概率 P0
2、系统中平均排队的顾客数 Lq
3、系统中的平均顾客数 Ls
4、系统中顾客平均的排队等待时间 Wq
5、系统中顾客的平均逗留时间 Ws
6、系统中顾客必须排队等待的概率 Pw
7、系统中恰好有 n 个顾客的概率 Pn
9
§ 7 多服务台泊松到达、任意的
服务时间、损失制排队模型
? 记号,M / G / C / C / ∞
? 注,不存在平均排队的顾客数 Lq 和顾客平均的排队等待时间 Wq
? 关心的项目,
系统中的平均顾客数 Ls
系统中恰好有 n 个顾客的概率 Pn
10
§ 8 顾客来源有限制的排队模型
? 记号,M / M / 1 / ∞ / m
? 条件,单位时间顾客平均到达数 ?
单位平均服务顾客数 ?
? 关心的项目,
1、系统中无顾客的概率 P0
2、系统中平均排队的顾客数 Lq
3、系统中的平均顾客数 Ls
4、系统中顾客平均的排队等待时间 Wq
5、系统中顾客的平均逗留时间 Ws
6、系统中顾客必须排队等待的概率 Pw
7、系统中恰好有 n 个顾客的概率 Pn
第十三章 排队论
? 排队过程的组成部分
? 单服务台泊松到达、负指数服务时间的排队模型
? 多服务台泊松到达、负指数服务时间的排队模型
? 排队系统的经济分析
? 单服务台泊松到达、任意服务时间的排队模型
? 单服务台泊松到达、定长服务时间的排队模型
? 多服务台泊松到达、任意的服务时间、损失制排队
模型
? 顾客来源有限制排队模型
2
§ 1 排队过程的组成部分 (1)
一, 基本概念
? 一些排队系统的例子 。
排队系统 顾 客 服务台 服 务
电话系统 电话呼叫 电话总机 接通呼叫或取消呼叫
售票系统 购票旅客 售票窗口 收款、售票
设备维修 出故障的设备 修理工 排除设备故障
防空系统 进入阵地的敌机 高射炮 瞄准、射击直至敌机被击落或离开
? 排队的过程可表示为:
排队系统
顾客到达 排队 服务机构服务 顾客离去
3
§ 1 排队过程的组成部分 (2)
? 考虑要点:
1、服务台个数:单服务台、多服务台
2、顾客到达过程:本教材主要考虑顾客泊松到达情况。
满足以下四个条件的输入流称为泊松流(泊松过程)
*平稳性:在时间区间 [t,t+?t)内到达 k个顾客的概率与 t无关,只与 ?t有关。记为 pk(?t)。
*无后效性:不相交的时间区间内到达的顾客数互相独立。
*普通性:在足够短的时间内到达多于一个顾客的概率可以忽略;
*有限性:任意有限个区间内到达有限个顾客的概率等于 1。
泊松分布 ? 为单位时间平均到达的顾客数
P (x) = ?x e-? / x! (x = 0,1,2,……)
3、服务时间分布,服从负指数分布 ? 为平均服务率,即单位时间服务的顾客数。
P(服务时间 ≤ t ) = 1- e-? t
4、排队规则分类
(1)等待制:顾客到达后,一直等到服务完毕以后才离去;
先到先服务,后到先服务,随机服务,有优先权的服务。
(2)损失制:到达的顾客有一部分未接受服务就离去;
5、平稳状态,业务活动与时间无关。
4
§ 2 单服务台泊松到达、负指数
服务时间的排队模型
? 记号,M / M / 1 / ∞ / ∞
? 条件,单位时间顾客平均到达数 ?
单位平均服务顾客数 ?
? 关心的项目,
1、系统中无顾客的概率 P0
2、系统中平均排队的顾客数 Lq
3、系统中的平均顾客数 Ls
4、系统中顾客平均的排队等待时间 Wq
5、系统中顾客的平均逗留时间 Ws
6、系统中顾客必须排队等待的概率 Pw
7、系统中恰好有 n 个顾客的概率 Pn
5
§ 3 多服务台泊松到达、负指数
服务时间的排队模型
? 记号,M / M / C / ∞ / ∞
? 条件,单位时间顾客平均到达数 ?
单位平均服务顾客数 ?
? 关心的项目,
1、系统中无顾客的概率 P0
2、系统中平均排队的顾客数 Lq
3、系统中的平均顾客数 Ls
4、系统中顾客平均的排队等待时间 Wq
5、系统中顾客的平均逗留时间 Ws
6、系统中顾客必须排队等待的概率 Pw
7、系统中恰好有 n 个顾客的概率 Pn
6
§ 4 排队系统的经济分析
? 公式,TC = cw Ls + cs c
? 其中,
cw 一个顾客在排队系统中逗留单位时间付出的费用
Ls 在排队系统中的平均顾客数
cs 每个服务台单位时间的费用
c 服务台个数
7
§ 5 单服务台泊松到达、任意服
务时间的排队模型
? 记号,M / G / 1 / ∞ / ∞
? 条件:
单位时间顾客平均到达数 ? 单位平均服务顾客数 ?
一个顾客的平均服务时间 1 / ? 服务时间的均方差 ?
? 关心的项目,
1、系统中无顾客的概率 P0
2、系统中平均排队的顾客数 Lq
3、系统中的平均顾客数 Ls
4、系统中顾客平均的排队等待时间 Wq
5、系统中顾客的平均逗留时间 Ws
6、系统中顾客必须排队等待的概率 Pw
7、系统中恰好有 n 个顾客的概率 Pn
8
§ 6 单服务台泊松到达、定长服
务时间的排队模型
? 记号,M / D / 1 / ∞ / ∞
? 注:是 M / G / 1 / ∞ / ∞ 的特殊情况 ? = 0
? 关心的项目,
1、系统中无顾客的概率 P0
2、系统中平均排队的顾客数 Lq
3、系统中的平均顾客数 Ls
4、系统中顾客平均的排队等待时间 Wq
5、系统中顾客的平均逗留时间 Ws
6、系统中顾客必须排队等待的概率 Pw
7、系统中恰好有 n 个顾客的概率 Pn
9
§ 7 多服务台泊松到达、任意的
服务时间、损失制排队模型
? 记号,M / G / C / C / ∞
? 注,不存在平均排队的顾客数 Lq 和顾客平均的排队等待时间 Wq
? 关心的项目,
系统中的平均顾客数 Ls
系统中恰好有 n 个顾客的概率 Pn
10
§ 8 顾客来源有限制的排队模型
? 记号,M / M / 1 / ∞ / m
? 条件,单位时间顾客平均到达数 ?
单位平均服务顾客数 ?
? 关心的项目,
1、系统中无顾客的概率 P0
2、系统中平均排队的顾客数 Lq
3、系统中的平均顾客数 Ls
4、系统中顾客平均的排队等待时间 Wq
5、系统中顾客的平均逗留时间 Ws
6、系统中顾客必须排队等待的概率 Pw
7、系统中恰好有 n 个顾客的概率 Pn