当前位置:文档之家› 排队论课件ppt

排队论课件ppt


到达间隔为负指数分布,服务时间也为负指数分 布,1个服务台,顾客源无限,系统容量也无限, 先到先服务。 若只讨论先到先服务的情况,可略去第6项。
描述一个排队系统运行状况的主要数量指标有:
排队 系统 的主 要数 量指 标和 记号
1. 队长和排队长 2. 等待时间和逗留时间 3. 忙期和闲期 上述一些主要数量指标的常用记号: N(t): 时刻t系统中的顾客数(又称为系统的状态),即队长; Nq(t): 时刻t系统中排队的顾客数,即排队长; T(t): 时刻t到达系统的顾客在系统中的逗留时间; Tq(t): 时刻t到达系统的顾客在系统中的等待时间。


排 队 论

引言 生灭过程和Poisson过程 M/M/s等待制排队模型 M/M/s混合制排队模型 其他排队模型简介 排队系统的优化 分析排队系统的模拟方法
M/M/s 等 待 制 排 队 模 型
一、 单服务台模型
单服务台等待制模型M/M/1/∞是指: 顾客的相继到达时间服从参数为λ的负指 数分布,服务台个数为1,服务时间V服从 参数为μ的负指数分布,系统空间无限, 允许无限排队。
1. 队长的分布
单 服 务 台 模 型
记pn=P{N=n}(n=0,1,2,…)为系统达到平稳状态后队 长N的概率分布,并注意到λn=λ,n=0,1,2,…和μn=μ, n=1,2,…记 ρ=λ/μ
设ρ<1,则

Cn ( ) n
Pn n P0
1

(n=1,2,...) (n=1,2,...)
生 灭 过 程 和 Poisson 过 程
二、 Poisson过程和负指数分布 定义2
设N(t)为时间[0,t]内到达系统的顾客数,如果满 足下面三个条件: (1) 平稳性: 在[t,t+Δt]内有一个顾客到达的概率 为λt+o(Δt); (2) 独立性: 任意两个不相交区间内顾客到达情况 相互独立; (3) 普通性: 在[t,t+Δt]内多于一个顾客到达的概 率为o(Δt)。 则称{N(t),t≥0}为Poisson过程。
排队 系统 的主 要数 量指 标和 记号
记pn(t)为时刻t时系统处于状态n的概率,即系 统的瞬时分布。我们将主要分析系统的平稳 分布,即当系统达到统计平衡时处于状态n的 概率,记为pn。又记
N:系统处于平稳状态时的队长,其均值为L, 称为平均队长; Nq:系统处于平稳状态时的排队长,其均值 为Lq,称为平均排队长; T:系统处于平稳状态时顾客的逗留时间,其 均值记为W,称为平均逗留时间; Tq:系统处于平稳状态时顾客的等待时间, 其均值记为Wq,称为平均等待时间;
W E (T ) E (Tq ) E (V ) Wq

可得平均等待时间Wq为:
Wq W ( )
1
平均队长L与平均逗留时间W的关系:
单 服 务 台 模 型
L=λW 平均排队长Lq与平均等待时间Wq有如下关系: Lq=λWq 这两个式子通常称为Little公式,是排队论中一 个非常重要的公式。
顾客到达
队列 ……… …
队列 …………
服务台1 服务完成离去
服务台2
图4 多个服务台的串联排队系统
排队 系统 的特 征及 排队 论
上述形式都可概括为:
聚 (输入) 散 (输出)
服务机构
图5 随机服务系统
1. 输入过程
排 队 系 统 的 描 述
(1)顾客总体(顾客源)数: • 无限

(如来商店购物的顾客数量)
另外,记忙期为B,闲期为I,平均忙期和平均闲期分 别记为和,记s为系统中并行的服务台数。
排 队 论 研 究 的 基 本 问 题
排队论研究的基本问题:
(1) 通过研究主要数量指标在瞬时或平稳状态下的概率 分布及其数字特征,了解系统运行的基本特征。 (2) 统计推断问题,建立适当的排队模型是排队论研究 的第一步,建立模型过程中经常会碰到如下问题: 检 验系统是否达到平稳状态;检验顾客相继到达时间间 隔的相互独立性;确定服务时间的分布及有关参数等。 (3) 系统优化问题,又称为系统控制问题或系统运营问 题,其基本目的是使系统处于最优或最合理的状态。 系统优化问题包括最优设计问题和最优运营问题,其 内容很多,有最少费用问题、服务率的控制问题、服 务台的开关策略、顾客(或服务)根据优先权的最优排 序等方面的问题。
第十章 排队论
Operational Research ( OR )


本 章 内 容

引言 生灭过程和Poisson过程 M/M/s等待制排队模型 M/M/s混合制排队模型 其他排队模型简介 排队系统的优化 分析排队系统的模拟方法
排队系统特征及排队论 服 务 机 构
排队 系统 的特 征及 排队 论
1
(10 4) 1 1 1 4 (8) P ( W ) 1 P ( W ) 1 F ( ) e e 1.5 0.223。 4 4 4
前提: 单队、并列服务台
多 服 务 台 模 型
……
1 2



C

( / / G ) : 标准的 模型仍可分为 ( N / / G ) ( / m / G )
L npn n(1 ) n
n 0 n 1


( 2 2 3 3 …) ( 2 2 3 3 4 …) 2 3 …=
平均排队长Lq为:
1-
Lq (n 1) pn L (1 p0 )
① 损失制排队系统
② 混合制排队系统,具体说来,又分为以下三 种:
(i) 队长有限
(ii) 等待时间有限
(iii) 逗留时间(等待时间与服务时间之和)有限
排 队 系 统 的 描 述
(2) 排队规则,当顾客到达时,若所有 服务台都被占用且又允许排队,则该顾 客将进入队列等待。服务台对顾客进行 服务所遵循的规则通常有: ① 先来先服务(FCFS) ② 后来先服务(LCFS) ③ 具有优先权的服务(PS)
正在接受服务的顾客
图1 单服务排队系统
顾客到达
队列
服务台1 服务台2 服务完成后离去

...
服务台s
图2 s个服务台,一个队列的排队系统
队列1

服务台1 服务台2
服务完成后离去 服务完成后离去
排队 系统 的特 征及 排队 论
顾客到达
队列 …2 队列s
... …
服务台s 服务完成后离去
图3 s个服务台,s个队列的排队系统
=4人/小时 1 = 人/分钟=10人/小时
6
2 5。
3 (1) P0 1 ; 5
单 服 务 台 模 型
2 3 (2) P3 3 (1 ) ( ) 3 ( ) 0.0384; 5 5 2 (3) 1 P0 ; 5 4 2 (4) Ls (人/小时) ; 6 3 1 1 (5) W s Ls (小时/人) ; 6 2 2 4 (6) Lq Ls (人/小时) ; 3 5 15 1 1 1 1 (7) W q W s (小时/人) ; 6 10 15
排队 系统 的主 要数 量指 标和 记号
λn: 当系统处于状态n时,新来顾客的平均到达率(单 位时间内来到系统的平均顾客数); μn: 当系统处于状态n时,整个系统的平均服务率(单 位时间内可以服务完的顾客数); 当λn为常数时,记为λ;当每个服务台的平均服务率 为常数时,记每个服务台的服务率为μ,则当n≥s时, 有μn=sμ。因此,顾客相继到达的平均时间间隔为1/λ, 平均服务时间为1/μ。令ρ=λ/sμ,称ρ为系统的服务强 度。

2 2 L 1 ( )
n 1
关于顾客在系统中的逗留时间T,可说明它服从参 数为μ-λ的负指数分布,即
单 服 务 台 模 型
PT t e( )t
因此,平均逗留时间W为:
t≥0
1 W E (T )
因为,顾客在系统中的逗留时间为等待时间和接受 服务时间之和,即T=Tq+V。其中,V为服务时间, 故由 1
3. 忙期和闲期
单 服 务 台 模 型
忙期的平均长度和闲期的平均长度之比是:
B I 1
平均忙期为:
1 B 1
不难发现,一个顾客在系统内的平均逗留时 间等于服务员平均连续忙的时间。

1
例10-1 某修理店只有一个修理工人,来修理的顾客
单 服 务 台 模 型
排 队 系 统 的 描 述
3. 服务机制
排队系统的服务机制主要包括: 服务员 的数量及其连接形式(串联或并联);顾 客是单个还是成批接受服务;服务时间 的分布。记某服务台的服务时间为V, 其分布函数为B(t),密度函数为b(t),则 常见的分布有: (1) 定长分布(D) (2) 负指数分布(M) (3) k阶爱尔朗分布(Ek):
排 队 系 统 的 符 号 表 示
排队系统的符号表示 “Kendall记号”,其一般形式为:X/Y/Z/A/B/C,其中 XX:顾客到达时间间隔的分布 YY:服务时间的分布 Z Z:服务台个数 A :系统容量 B B:顾客源数量
C C:服务规则
例 (M / M / 1 /
/
引言 生灭过程和Poisson过程 M/M/s等待制排队模型 M/M/s混合制排队模型 其他排队模型简介 排队系统的优化 分析排队系统的模拟方法
生 灭 过 程 和 Poisson 过 程
一、生灭过程简介
定义1
设{N(t),t≥0}为一个随机过程。若N(t)的概率分布具有以 下性质:
相关主题