排队论

关; 与系统当前状态n有关，而与以前的状态无关； ——马尔可夫性质
(三) 排队系统的生灭过程 (1)生灭过程示意 • 顾客到达——“生”； • 顾客离开——“灭”
顾客聚 顾客到达
服务机构
顾客散 顾客离去
n ，
n ，
(2)生灭过程定义 若排队系统具有下列性质: (1) 顾客到达为泊松流，时间间隔服从参 数为n的负指数分布;(n ：平均每小时 到达顾客数) (2) 顾客服务时间服从参数为 n的负指 数分布; 则排队系统的随机过程{N(t),t>=0}具有马 尔可夫性质, 为一个生灭过程.
二、排队系统的状态转移方程 (一) 排队系统状态的概率及其分布 (1)瞬态概率Pn(t) ——表示时刻系统状态N(t)=n的概率; (2) 稳态概率Pn ——Pn= Pn(t) ; 一般，稳态概率Pn的分布，是分析计算 排队系统运行优劣的基础。
(二) 排队系统状态概率的微分差分方程 ——求解可得瞬态概率Pn(t)
• 对泊松流，在时间t系统内有n个顾客的概 率服从如下泊松分布
• E[N(t)]=t ;
Var [N(t)]=t ;
——单位时间平均到达的顾客数；
推导过程：P 319-320
(二)泊松流到达间隔服从负指数分布 • 若顾客到达间隔T的概率密度为
则称T服从负指数分布，分布函数如下：
• 若顾客流是泊松流时，顾客到达的时间间隔 显然服从上述负指数分布(WHY);
p
n 0

n
1

p0 Cn p0 (1 Cn ) p0 1
k (k t ) k t b(t ) e (k 1)!
k 1
称T服从k阶爱尔朗分布。
(2)
E[T]=1/ ; Var [T]=1/( k2)
(3) T的意义之一: k个串联服务台的总服务时间！
6.4 排队系统的生灭过程与状态转移方程 一、排队系统的生灭过程 (一)生灭过程的背景与定义
顾客到达时刻i
（2）排队结构与排队规则
顾客排队方式：等待制/即时制(损失制); 排队系统容量：有限制/无限制; 排队队列数目: 单列/多列; 是否中途退出: 允许/禁止; 是否列间转移: 允许/禁止; (仅研究禁止退出和转移的情形)
（3）服务机构与服务规则 服务台(员)数目;单个/多个; 服务台(员)排列形式;并列/串列/混合; 服务台(员)服务方式;逐个/逐批;(研究逐个情形) 服务时间分布;随机型/确定型; 服务时间分布是否平稳:平稳/非平稳;(研究平稳情形) 1 1 2 … c 1 2 … c 1 2 … c
(二)系统运行指标参数
——评价排队系统的优劣。
1、队长与排队长 (1)队长: 系统中的顾客数（n）； 期望值 Ls= n*Pn (2)排队长: 系统中排队等待服务的顾客数; 期望值 Lq =
n c 1
(n c) P

n
Lq= Ls-[正被服务的顾客数]
2、逗留时间与等待时间 (1)逗留时间: ——指一个顾客在系统中的全部停留时间； 期望值，记为 Ws (2)等待时间: ——指一个顾客在系统中的排队等待时间； 期望值，记为 Wq Ws = Wq + E[服务时间]
2、系统状态概率： (1)瞬态概率Pn(t) ——表示时刻系统状态 N(t)=n 的概率; (2) 稳态概率Pn ——Pn= lim Pn(t) ; t ——一般，排队系统运行了一定长的时 间后，系统状态的概率分布不再随时间 t变化，即初始时刻（t=0）系统状态的 概率分布(Pn(0) ，n》0）的影响将消失。
n ，n ，t ( ？)
设某系统具有状态集S={0,1,2,…},或S={0,1,2,…,k}, N(t)表示系统在时刻 t (t>=0) 的状态。 若在N(t)=n的条件下，随机过程{N(t),t>=0}满足 以下条件: (1) N(t+t)转移到“n+1”的概率为n(t ) ; (2) N(t+t)转移到“n-1”的概率为n(t ) ; (3) N(t+t)转移到 其他状态“S-{n+1,n-1}”的概 率为o(t )(高阶无穷小) ; 则称随机过程{N(t),t>=0}为生灭过程。
第六章 排队论及排队系统优化
排队现象与排队系统; 排队模型与系统参数; 排队系统时间参数分布规律; 排队系统的生灭过程与状态转移方程; 排队系统分析; 单服务台负指数分布模型 多服务台负指数分布模型 排队系统优化分析;
• 排队论发源于本世纪初。 • 当时美国贝尔电话公司发明了自动电话， 以适应日益繁忙的工商业电话通讯需要。 这个新发明带来了一个新问题，即通话线 路与电话用户呼叫的数量关系应如何妥善 解决，这个问题久久未能解决。 • 1909年，丹麦的哥本哈根电话公司A.K.埃 尔浪(Erlang)在热力学统计平衡概念的启 发下予以解决了。
(二)生灭过程状态变化的性质 (1) 在无穷小t内,系统或生长1个;或灭亡1个;或既 不生长又不灭亡（概率:1- n(t ) -n(t ) ）; (2)系统生长一个的概率n(t )与t有关，而与t无 关; 与系统当前状态n有关，而与以前的状态无关；
(3)系统灭亡一个的概率n(t )与t有关，而与t无
0
0 1
1
2
2
n 2 n 1
n-1 n
n n 1
1
2
3
n1
n
0 p0 2 p2 (1 1 ) p1
0
0 1
1
2
2
n 2 n 1
n-1 n
n n 1
1
2
3
n1
n
1 p1 3 p3 (2 2 ) p2
三、 排队系统稳态概率Pn的求解
0 10 p1 p0 , p2 p0 1 2 1 n 1n 2 10 pn p0 n n 1 2 1
记
n 1n 2 10 Cn n n 1 2 1
则 p n C n p0 , n 1,2,
6.3 排队系统时间参数分布规律 一、顾客到达时间间隔分布 (一)泊松流与泊松分布 如果顾客到达满足如下条件,则称为泊松流: (1) 在不相互重叠的时间区间内，到达顾客数 相互独立(无后效性). (2) 对于充分小的时间间隔 成正比 (平稳性)： (3) 对于充分小的时间间隔 ，2个及以 上顾客到达的概率可忽略不计 (普通性)。 内，到达 1个顾客的概率与t无关，仅与时间间隔
,t 0
FTs (t ) {
1 e t ,t 0 0 ,t 0
则 E[Ts]=1/ ; Var [Ts]=1/ 2 ; [Ts]=1/ (2) E[Ts]=1/ ：每个顾客的平均(期望)服务时间； :单位时间服务的顾客数，平均(期望)服务率；
(二)爱尔朗(Erlang)分布 (1) 设v1,v2,…,vk是k个相互独立的随机变量,服从 相同参数1/ k的负指数分布,则:T= v1+v2+…+vk的 概率密度为
dP0 (t ) 0 P0 (t ) 1P t 0, n 0 1 (t ); dt
dPn (t ) n1Pn1 (t ) n1Pn1 (t ) (n n ) Pn (t ); t 0, n 0 dt
推导过程：P 323
(三) 排队系统状态转移方程 ——求解可得稳态概率Pn 令
2、国际排队论标准化会议(1971)表示法 X / Y / Z / A / B / C （1） A 系统容量限制； （2） B 顾客源（总体）数目； （3） C 服务规则（FCFS，LCFS等）； ——略去后三项，即指 “X/Y/Z///FCFS”； ——这里仅研究FCFS的情形；
(二)到达间隔和服务时间典型分布
dP0 (t ) 0 dt
dPn (t ) 0 ; dt
则
0 P0 (t ) 1P1 (t ) 0
n1Pn1 (t ) n1Pn1 (t ) (n n ) Pn (t ); n 0
——排队系统状态转移方程
(四) 排队系统状态转移图
0
0 1
1
2
2
n 2 n 1
n-1 n
n n 1
1
2
3
n1
n
在任意状态n达到稳态平衡的条件：
产生该状态的平均速率 =该状态转变成其他状态的平均速率 （流入=流出）
0
0 1
1
2
2
n 2 n 1
n-1 n
n n 1
1
2
3
n1
n
1 p1 0 p0
• E[T]=1/ ; Var [T]=1/2 ; [T]=1/
二、顾客服务时间分布 (一)负指数分布 (1) 对一个顾客的服务时间Ts，等价于相邻两个顾客 离开排队系统的时间间隔。若Ts服从负指数分布， 其概率密度和分布函数分别为
fTs (t ) {0
e t ,t 0
服务台(员)为顾客服务的顺序: a)先到先服务(FCFS); b)后到先服务(LCFS); c)随机服务;
d)优先服务;
6.2 排队模型与系统参数 一、排队模型 (一)排队模型表示方法
1、D.G.Kendall(1953)表示法 X / Y / Z ——依据排队系统3个主要特征： （1） X 顾客到达间隔时间分布； （2） Y 服务台（员）服务时间分布； （3） Z 服务台（员）个数（单个或多个并列）；
（1 ） （2 ） （3 ） （4 ） （5 ）
泊松分布 负指数分布 k阶爱尔朗分布 确定型分布 一般服务时间分布
M ； M ； Ek； D； G；
(三)排队模型示例 ——M/M/1，M/D/1，M/ Ek /1； ——M/M/c， M/M/c//m， ——M/M/c/N/ ，。。。