排队论讲义

排队论一.概率论及随机过程回顾二.排队论的基本知识三.单服务台负指数分布排队系统分析四.多服务台负指数分布排队系统分析五.一般服务时间M/G/1模型分析六.经济分析___排队系统的最优化一、概率论及随机过程回顾随机变量离散型随机变量概率分布和概率分布图数学期望和方差常见离散型随机变量的概率分布二点分布?二项式分布?Poisson分布?1.1、随机变量与概率分布一、概率论及随机过程复习随机变量离散型随机变量概率分布和概率分布图数学期望和方差常见离散型随机变量的概率分布二点分布?二项式分布?Poisson分布?随机变量连续型随机变量概率密度函数概率分布函数数学期望和方差常见连续型随机变量的概率分布均匀分布指数分布？正态分布？k阶爱尔朗分布？一、随机变量与概率分布2/1)(,/1)()0(0,00,)(XDXExxexax随机变量X为时间间隔，如顾客到达的时间间隔、电话呼叫的时间、产品的寿命等。密度函数?爱尔朗分布211)(,1)(0,)!1()()(kTDTEtekktktbktkkkXXX,,,21k为k个相互独立的随机变量；服从相同参数的负指数分布；kXXXT21设，则T的密度函数为如k个服务台串联（k个服务阶段），一个顾客接受k个服务共需的服务时间T，T爱尔朗分布。1.2随机过程的有关概念随机过程(Randomprocess)的定义}),({TttX设，是一族随机变量，T是一个实数集，对是一个随机变量，则称为随机过程。)(,tXTt}),({TttXTt•T：参数集合•当T={0,1,…,n,…}时，称为随机序列•：随机过程的一个状态•状态空间E={X(t)全体可能取值，}ktX)(随机过程的基本类型二阶矩过程平稳过程平稳独立增量过程常见随机过程马尔可夫过程？Poisson过程？生灭过程？1.2随机过程的有关概念定义：若满足如下性质：对任意非负整数，只要就有则称具有马尔可夫性，或无后效性。马尔可夫过程马尔可夫链离散,...}2,1,0),({nnXttttr...21})()({})(,...,)(,)()({2211rrrritXjtXPitXitXitXjtXP0})(,...,)(,)({2211rritXitXitXP)}({nX1t2trt1rtt过去现在将来“将来”的情况与“过去”无关，只是通过“现在”与“过去”发生联系，若“现在”已知，“将来”与“过去”无关。)}({nX时齐的马氏链：马氏链若满足：则称为时齐马尔可夫链)(}{mPiXjXPijnmn,...}2,1,0),({nnX,...}2,1,0),({nnX)(mPij—系统由状态i经过m个时间间隔（或m步）转移到状态j的转移概率Poisson过程定义：设为时间内到达系统的顾客数，若满足下面三个条件：独立性：在任意两个不相交的区间内顾客到达的情况相互独立；平稳性：在内有一个顾客到达的概率为普通性：在内多于一个顾客到达的率为。则称为Poisson过程。)(tNt,0}0),({ttNttt',');(tt)(tttt','（1）只与区间长度与起点无关。（2）单位时间内一个顾客到达的概率为。Poisson过程与Poisson分布定理1：设为时间内到达系统的顾客数则为Poisson过程的充要条件是)(tNt,0}0),({ttN,...2,1!)(})({nentntNPtn数理统计方法容易初步判断:期望=标准差ttNDttNE)(,)(Poisson过程与负指数分布tTPsTstTP}{定理2：设为时间内到达系统的顾客数则为参数为的Poisson过程的充要条件是相继到达的时间间隔T服从相互独立的参数为的负指数分布。)(tNt,0}0),({ttN0,00,)(ttetatT负指数分布的性质:2/1)(,/1tNDTE马尔可夫性，或无后效性Poisson过程与Poisson分布的关系：定理1：设为时间内到达系统的顾客数则为Poisson过程的充要条件是)(tNt,0}0),({ttN,...2,1!)(})({nentntNPtn定理2：设为时间内到达系统的顾客数则为参数为的Poisson过程的充要条件是相继到达的时间间隔T服从相互独立的参数为的负指数分布。)(tNt,0}0),({ttN0,00,)(ttetatT对于Poisson流：——单位时间平均到达的顾客数——顾客相继到达的平均间隔时间/1定义：设为一个随机过程，若N(t)的概率分布具有以下性质：(1)假设N(t)=n，则从时刻到下一个顾客到达时刻止的时间服从参数为的负指数分布；(2)假设N(t)=n，则从时刻到下一个顾客离开时刻止的时间服从参数为的负指数分布；(3)同一时刻是只有一个顾客到达或离去。则称为一个生灭过程。}0),({ttN}0),({ttNnn生灭过程1001nn-1n+11nnn1n平稳生灭过程系统状态n平衡方程：“流入=流出”nnnnnnnppppp)(011111100系统达到平稳状态时：...)2,1,0(),(ntppnn)(tN的分布...)2,1,0(},)({)(nntNPtpn系统达到平稳状态时：100110210111......,...2,1,nnnnnnnnnnnCppCnpCp其中nnnnnnnppppp)(011111100平衡方程：当时才有意义1nnC...)2,1,0(},)({)(nntNPtppnn二、排队论的基本知识2.1排队模型2.2排队系统的组成和特征排队论研究的内容性态问题:排队系统的概率规律,如队长分布,等待时间分布等.最优化问题:排队系统的最优设计.统计推断:判定排队系统的类型.顾客源2.1、排队模型排队系统排队结构服务机构排队规则服务规则接受服务后离去——排队系统的的一般表示服务机构服务台(a)一个队列、单服务台（阶段）服务台1服务台2(b)一个队列、s个服务阶段服务机构服务台1服务台2服务机构(c)一个队列、s个服务台一个服务阶段服务台3服务台4服务台1服务台2服务机构(d)s个队列、s个服务阶段服务台3服务台4服务台1服务台2:1–2–4:2–4–3:3–2–1–4服务机构(e)混合型排队结构服务台(f)一个队列服务台(g)s个队列输入过程顾客总体:有限,无限.顾客到达方式:单个,成批.顾客到达间隔时间:确定的、随机的.顾客到达的独立性:独立,不独立.输入过程的平稳性:与时间无关(平稳的),与时间有关(非平稳的).2.2、排队系统的组成和特征顾客到达时间间隔的分布:：第n个顾客与第n-1个顾客到达的时间间隔；nXnT：第n个顾客到达的时刻；设nTTT100,,2,1,1nTTXnnn令1T2TnT1nT1nT0TnX顾客到达时间间隔的分布:假定是独立同分布，分布函数为，排队论中常用的有两种：}{nX)(tA}{nX（2）最简流（即Poisson流）（M）：顾客到达时间间隔为独立的，服从负指数分布，其密度函数为（1）定长分布（D）：顾客到达时间间隔为确定的。000)(ttetat因为负指数分布具有无后效性（即Markov性）排队及排队规则即时制(损失制)等待制先到先服务:FCFS后到先服务:LCFS随机服务优先权服务：PS队容量:有限,无限;有形,无形.队列数目:单列,多列.服务机构服务员数量:无,单个,多个.队列与服务台的组合服务方式:单个顾客,成批顾客.服务时间:确定的,随机的.服务时间和到达间隔时间至少一个是随机的.服务时间分布是平稳的.服务时间分布:设某服务台的服务时间为V，其密度函数为b（t），常见的分布有：（1）定长分布（D）：每个顾客接受服务的时间是一个确定的常数。（2）负指数分布（M）：每个顾客接受服务时间相互独立，具有相互的负指数分布：其中，为一常数。000)(ttetbt0μ--单位时间平均服务完成的顾客数1/μ--每个顾客的平均服务时间服务时间分布:（3）k阶爱尔朗（Erlang）分布：每个顾客接受服务时间服从k阶爱尔朗分布，其密度函数为：tkkektkktb)!1()()(1符号表示:X/Y/ZX--客到达间隔时间分布Y--服务时间分布Z--服务台个数X,Y可以是:M--负指数分布D--确定性的Ek--k阶Erlang分布GI--一般相互独立的到达时间间隔分布G--一般(General)时间分布排队系统的分类扩展符号表示:X/Y/Z/A/B/CA--系统容量B--顾客源中顾客的数量C--服务规则:FCFS,LCFS,等等.若省略后三项，即是指下面的情形：X/Y/Z///FCFS例：M/M/s/K表示？已知:顾客到达间隔时间分布,服务时间分布.求:队长:Ls--系统中的顾客数.排队长(队列长):Lq--队列中的顾客数.Ls=Lq+正在接受服务的顾客数逗留时间:WS--顾客在系统中的停留时间等待时间:Wq--顾客在队列中的等待时间.WS=Wq+服务时间忙期,损失率,服务强度.排队问题的求解三.单服务台负指数分布排队系统分析3.1M/M/1模型3.2M/M/1/N/模型(即系统的容量有限)3.3M/M/1//m模型（即顾客源为有限）顾客源排队系统排队结构服务机构排队规则服务规则接受服务后离去3.1M/M/1模型无限输入过程服从参数为的Poisson过程单队队长无限先到先服务服务时间服从参数为的负指数分布生灭过程求解：np:系统达到平稳后，系统有n个顾客的概率。1n0)(0n01110nnnPPPPP平衡方程：1n)1(10nnPP1:令，且当时01102101......,...2,1,ppCnpCpnnnnnnnnn其中关于的几点说明：)1(/1/1(2)01(3)p顾客平均到达率顾客平均服务率一个顾客服务时间一个顾客到达时间——服务强度,1)4(即顾客的顾客平均到达率小于顾客平均服务率时，系统才能达到统计平稳。•系统中至少有一个顾客的概率；•服务台处于忙的状态的概率；•反映系统繁忙程度计算有关指标101......)2(...)32()1(3232321n0nsnnsLnnPL队长队列长1)1()1(201n10nssnnnnqLPLPnPPnL计算有关指标逗留时间:可以证明,Ws服从参数为μ-λ的负指数分布.则:等待时间1sW1sqWW服务计算有关指标计算有关指标Little公式（相互关系）qsqsqqssLL小结1sWqWqLsL平均服务时间平均在忙的服务台数/正在接受服务的顾客数有效到达率平均忙期B,忙期出现的概率平均闲期I,闲期出现的概率(1-)忙期B:闲期I=:(1-)平均闲期I=1/闲期的分布与顾客到达时间间隔的相同----服从参数为的负指数分布计算有关指标忙期与闲期WHY?1-P0=平均忙期B,忙期