随机服务系统理论排队论课件

1、1排队论主要知识点排队论的基本概念排队系统的组成与特征排队系统的模型分类顾客到达间隔时间和服务时间的经验分布与理论分布稳态概率Pn的计算M/M/1模型标准的M/M/1模型(M/M/1:/FCFS)系统容量有限制的模型M/M/1:N/FCFS顾客源有限模型M/M/1/M/ FCFS 牛牛文库文档分享2M/M/C模型标准的M/M/C模型M/M/C:/FCFSM/M/C型系统和C个M/M/1型系统系统容量有限制的多服务台模型(M/M/C/N/)顾客源为有限的多服务台模型(M/M/C/M)一般服务时间的（M/G/1）模型Pollaczek-Khintchine(P-K) 公式定长服务时间 M/D/1模

2、型爱尔朗服务时间M/Ek/1模型排队系统优化M/M/1 模型中的最优服务率u标准的M/M/1Model系统容量为N的情形M/M/C模型中最优服务台数C 牛牛文库文档分享3排队系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。1 排队论的基本概念1.1 排队系统的组成与特征 牛牛文库文档分享4输入即为顾客的到达，可有下列3种情况：1）顾客来源。顾客总体(称为顾客源)的组成可能是有限的，也可能是无限的。如，上游河水流入水库可以认为总体是无限的，工厂内停机待修的机器显然是有限的总体。2）顾客到达方式。顾客到来的方式可能是一个一个的，也可能是成批的。如，到餐厅就餐就有单个到来的顾客

3、和受邀请来参加宴会的成批顾客。 1. 输入过程 牛牛文库文档分享53）顾客流的概率分布。顾客随机一个(批)个(批)来到排队系统，顾客流的概率分布用来描述相继到达的顾客之间的间隔时间分布是确定的还是随机的，分布参数是什么，到达的间隔时间是否独立，分布是随时间变化的还是平稳的。 当输入过程是泊松流时，两顾客相继到达的时间间隔T独立且服从负指数分布。（等价） 牛牛文库文档分享6 1）损失制。顾客到达时，如果所有的服务台都被占用，且服务机构又不允许顾客等待，顾客只能离去，这种服务规则就是损失制。2）等待制。当顾客到达时，如果所有服务台都被顾客占用而无空闲，这时该顾客自动加入队列排队等待服务，服务完才离

4、开。 （1）先到先服务 FCFS （2）后到先服务 LCFS（3）随机服务RAND （4）有优先权服务 PR。 2. 排队规则 牛牛文库文档分享7 1）服务机构可以是单服务员和多服务员服务，这种服务形式与队列规则联合后形成了多种不同队列，不同形式的排队服务机构，如：3. 服务机构 牛牛文库文档分享8上述特征中最主要的、影响最大的是：顾客相继到达的间隔时间分布服务时间的分布服务台数 2)服务方式分为单个顾客服务和成批顾客服务。 3)服务时间分为确定型和随机型。 4)服务时间的分布在这里我们假定是平稳的。1.2 排队系统的模型分类 牛牛文库文档分享9式中：X填写顾客相继到达间隔时间分布。 M负指数

5、分布Markov， D确定型分布Deterministic， EkK阶爱尔朗分布Erlang， G 一般随机分布。Y填写服务时间分布（与上同）Z填写并列的服务台数A排队系统的最大容量B顾客源数量 C排队规则 如 M/M/1:/FCFS即为顾客到达为泊松过程，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统模型。D.G.Kendall，1953提出了分类法，称为Kendall记号(适用于并列服务台)即：X/Y/Z:A/B/C 牛牛文库文档分享10系统指标(1)队长:指在系统中的顾客数，它的期望值记Ls；(2) 排队长:指在系统中排队等待服务的顾客数，它的期望值记作Lq。 系统中

6、顾客 数在队列中等待服务的顾客数正被服务的顾客数+=一般情形，Ls(或Lq)越大，说明服务效率越低。 牛牛文库文档分享11(3) 逗留时间，指一个顾客在系统中的停留时间，它的期望值记作Ws；(4) 等待时间，指一个顾客在系统中排队等待的时间，它的期望值记作Wq；等待时间服务时间+逗留时间= 牛牛文库文档分享121.排队系统的统计推断:即通过对排队系统主要参数的统计推断和对排队系统的结构分析，判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。 2.系统性态问题:即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。 3.最优化

7、问题：即包括最优设计(静态优化)，最优运营（动态优化）。 1.3 排队论研究的基本问题 牛牛文库文档分享131.4 排队问题求解(主要指性态问题) 求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现有系统合理改进和对新建系统的最优设计等。 排队问题的一般步骤： 1. 确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布(可实测)。 2. 研究系统状态的概率。系统状态是指系统中顾客数。状态概率用Pn(t)表示,即在t时刻系统中有n个顾客的概率，也称瞬态概率。 牛牛文库文档分享14 求解状态概率Pn(t)方法是建立含P

8、n(t)的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此我们常常使用它的极限(如果存在的话)：稳态的物理意义见右图，系统的稳态一般很快都能达到，但实际中达不到稳态的现象也存在。值得注意的是求稳态概率Pn并不一定求t的极限,而只需求Pn(t)=0 即可。过渡状态稳定状态pnt图3 排队系统状态变化示意图 称为稳态(steady state)解，或称统计平衡状态 (Statistical Equilibrium State)的解。 牛牛文库文档分享152 到达间隔时间分布和服务时间的分布 一个排队系统的最主要特征参数是顾客的到达间隔

9、时间分布与服务时间分布。要研究到达间隔时间分布与服务时间分布需要首先根据现存系统原始资料统计出它们的经验分布，然后与理论分布拟合，若能照应，我们就可以得出上述的分布情况。 牛牛文库文档分享162.1 经验分布 经验分布是对排队系统的某些时间参数根据经验数据进行统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数的经验数据服从该假设分布。 分布的拟合检验一般采用2检验。由数理统计的知识我们知：若样本量n充分大(n50)，则当假设H0为真时，统计量总是近似地服从自由度为k-r-1的 2分布，其中k为分组数，r为检验分布中被估计的参数个数。

10、 牛牛文库文档分享172.2 理论分布 式中为常数(0)，称X服从参数为的泊松分布，若在上式中引入时间参数t，即令t代替，则有： 1.泊松分布 在概率论中，我们曾学过泊松分布，设随机变量为X，则有：n=0,1,2, （1） 与时间有关的随机变量的概率，是一个随机过程，即泊松过程。 t0，n=0,1,2, （2） 牛牛文库文档分享18（t2t1，n0） 若设N(t)表示在时间区间0,t)内到达的顾客数(t0),Pn(t1,t2)表示在时间区间t1,t2)(t2t1)内有n(0)个顾客到达的概率。即： 在一定的假设条件下 顾客的到达过程就是一个泊松过程。 当Pn(t1,t2)符合下述三个条件时，顾

11、客到达过程就是泊松过程(顾客到达形成泊松流)。 牛牛文库文档分享19 无后效性：各区间的到达相互独立,即Markov性。 也就是说过程在t+t所处的状态与t以前所处的状态无关。平稳性：即对于足够小的t，有：泊松流具有如下特性： 在t,t+t内有一个顾客到达的概率与t无关,而与t成正比。 0 是常数，它表示单位时间到达的顾客数，称为概率强度。 牛牛文库文档分享20 普通性：对充分小的t,在时间区间（t,t+t）内有2个或2个以上顾客到达的概率是一高阶无穷小.由此知，在(t，t+t)区间内没有顾客到达的概率为： 令t1=0,t2=t,则P(t1,t2)=Pn(0,t)=Pn(t)即P0+P1+P2

12、=1在上述假设下，t时刻系统中有n个顾客的概率pn(t)： 牛牛文库文档分享21根据排队系统的状态转移图：整理后可得：n-1nn+12012n+1012n-2n-1n13n-1nn+1n+2稳态时， 它对时间的导数为0，所以由(12.5)、(12.6)两式得：Pn(t)与时间无关,可以写成Pn,(12.7)(12.8) 牛牛文库文档分享22 表示单位时间内顾客平均到达数。 1/表示顾客到达的平均间隔时间。2.负指数分布 可以证明当输入过程是泊松流时，两顾客相继到达的时间间隔T独立且服从负指数分布。（等价）（n个顾客到达的概率）（4） 牛牛文库文档分享23 对排队模型，在给定输入和服务条件下，主

13、要研究系统的下述运行指标： (1)系统的平均队长Ls(期望值)和平均队列长Lq(期望值)； (2)系统中顾客平均逗留时间Ws与队列中平均等待时间Wq； 本节只研究M/M/1模型，下面分三种情况讨论：3. M/M/1模型 牛牛文库文档分享243.1 标准的M/M/1模型 系统中有n个顾客M/M/1:/FCFS模型 1.稳态概率Pn的计算 在任意时刻t，状态为n的概率Pn(t)（瞬态概率），它决定了系统的运行特征。 已知顾客到达服从参数为的泊松过程，服务时间服从参数为的负指数分布。现仍然通过研究区间t，t+t）的变化来求解。在时刻t+t，系统中有n个顾客不外乎有下列四种情况（ t，t+t）内到达或

14、离开2个以上没列入）。 牛牛文库文档分享25由此可得该排队系统的状态转移图：由（4）得：其中服务强度 将其代入（3）式并令n=1,2,(也可从状态转移图中看出状态平衡方程)得：关于Pn的差分方程n-1nn+1201稳态时， 它对时间的导数为0，所以由(1)、(2)两式得：Pn(t)与时间无关,可以写成Pn,(3)(4) 牛牛文库文档分享26n=1n=2 牛牛文库文档分享27以此类推，当n=n时，(5)以及概率性质知：(数列的极限为 )(6)否则排队无限远系统稳态概率系统的运行指标 牛牛文库文档分享282. 系统的运行指标计算 (1) 系统中的队长Ls（平均队长）(01)即:(7)期望 牛牛文库

15、文档分享29(2) 队列中等待的平均顾客数Lq(8) 牛牛文库文档分享30(Little 公式)： 顾客在系统中的平均逗留时间Ws 顾客在队列中的平均逗留时间Wq 牛牛文库文档分享31 (4)顾客在队列中的平均逗留时间Wq 利用公式（12.26）可求出Ws (3) 顾客在系统中的平均逗留时间Ws 利用公式（12.27）可求出Wq 牛牛文库文档分享32 3. 系统的忙期与闲期系统处于空闲状态的概率：系统处于繁忙状态的概率：服务强度 牛牛文库文档分享33例： 某医院手术室根据病人来诊和完成手术的时间记录，任意抽查100个工作小时，每小时来就诊的病人数n的出现次数如表9-4。又任意抽查了100个完成

16、手术的病历，所用时间v(小时)出现的次数如表9-5。计算手术室的各项指标。 牛牛文库文档分享34到达的病人数n出现次数fn010128229316410566以上1合计100为病人完成手术时间v(小时)出现次数fv0.00.2380.20.4250.40.6170.60.890.81.061.01.251.2以上0合计100表9-4表9-5 牛牛文库文档分享351.参数的确定算出每小时病人平均到达率 2.1(人/小时) 每次手术平均时间 0.4(小时/人)每小时完成手术人数(平均服务率)2.5(人/小时)2.取2.1，2.5，可以通过统计检验的方法(例如2检验法)，认为病人到达数服从参数为2.

17、1的普阿松分布，手术时间服从参数为2.5的负指数分布。3.它说明服务机构(手术室)有84的时间是繁忙(被利用)，有16的时间是空闲的。 牛牛文库文档分享364.依次算出各指标：在病房中病人数(期望值) 排队等待病人数(期望值) 病人在病房中逗留时间(期望值) 病人排队等待时间(期望值) 牛牛文库文档分享373.2 系统容量有限制的模型 M/M/1：N/FCFS 当系统容量最大为N时，排队多于N个的顾客将被拒绝。当N=1时，即为损失制，N时，即为容量无限制的情况。 牛牛文库文档分享38 现在研究系统中有n个顾客的概率Pn(t)。(2)对于(1)式，当n=1,2,N-1时，也仍能成立。(1)(n=

18、1,2,N-1)但当n=N时，有下面两种情况：对于P0(t)，前面的（2）式仍然成立。 牛牛文库文档分享39(8)其状态转移图为: 牛牛文库文档分享40在稳态情况下有：(9)解（9）式得： 而等比数列 牛牛文库文档分享41(1,nN)(10)(1) 平均队长Ls：(1)其运行指标： 牛牛文库文档分享42 (2) 有效到达率e 系统容量有限，当满员时，顾客将被拒绝，实际的顾客到达率与不一样，还可验证： 此种情况的公式与前类似,只有Ls不同,e与 不同。求e必须先求得P0或PN才行。有效到达率为e。 可以证明：Ls 牛牛文库文档分享43例2某单人理发馆共有六把椅子接待顾客排队，无座时将离去，顾客平

19、均到达率为3人/h，理发时间平均为15分钟，求：(1) 求某一顾客到达就能理发的概率;(2) 求需要等待的顾客数的期望值;(3) 求有效到达率;(4) 求一顾客在系统中的逗留时间和排队时间平均值;(5) 在可能到来的顾客中，有百分之几不等待就离开？解：N=?N=6+1=7，=3，=4 牛牛文库文档分享44(1) 求某一顾客到达就能理发的概率:(2) 求需要等待的顾客数的期望值:(3) 求有效到达率:(4) 求一顾客在系统中的逗留时间和排队时间平均值: 牛牛文库文档分享45P0=0.27780P1=0.20836P2=0.15627P3=0.11720 = 0.9629=96.29%P4=0.0

20、8790 故拒绝的概率为3.71%P5=0.06593P6=0.04944(5) 在可能到来的顾客中，有百分之几不等待就离开？顾客为何不等待就离去？因为系统已经满员 牛牛文库文档分享463.3 顾客源有限的模型 M/M/1/m 以机器修理模型为例，设有m台机器(总体)，故障待修表示机器到达，修理工是服务员。机器修好后有可能再坏，形成循环。虽然系统没有容量限制，但系统中的顾客也不会超过m，故又可写成：M/M/1/m/m 牛牛文库文档分享47 对于有限源应按每个顾客单独考虑，求出其有效到达率e。 这样e是随系统内顾客数而变化的。其状态转移图为：设系统内顾客数为Ls，则系统外的顾客为m-Ls。设每个

21、顾客的平均到达率是相同的。 (这里的含义是单台机器在单位时间里发生故障的概率或平均次数) 牛牛文库文档分享481nm-10状态n状态m状态 这样e是随系统内顾客数而变化的。其状态转移方程为： 牛牛文库文档分享49 用递推方法解此差分方程，并注意条件，可以得到如下公式：10=miiP(1nm)各项运行指标为： 牛牛文库文档分享50例3 某车间有5台机器，每台机器的连续运转时间服从负指数分布。平均连续运转时间15分钟，有一个修理工，修理时间服从负指数分布，平均每次12分钟。求：(1) 修理工空闲时间解:(1) m=5,=1/15,=1/12,=4/5=0.8 牛牛文库文档分享51台台(3) 出故障的平均台数(4) 等待修理的平均台数(5) 平均停工时间分钟(2) 五台机器都出现故障的概率 牛牛文库文档分享52分钟 机器等待过长，忙期长，应增加维修工人或提高效率。(6) 平均等待修理时间(7) 评价这些结果 牛牛文库文档分享534.多服务台的情形M/M/C即：M/M/C: /FCFS 标准的M/M/C模型与标准的M/M/1模型的各特征规定相同，另外，各服务台工作是相互独立且平均服务率相同，即1=2=3=c=，整个服务机构的平均服务率为：c(nc时) 或n(nc时)令 ，只有当 时，才不会形成无限队列。4.1标准的M/M/C模型 牛牛文