排队论随机服务系统

1、1,排队论(Queueing Theory)（随机服务系统,第一节,第二节,第三节,2,大纲要求： 掌握排队论的基本概念、常见的到达时间间隔分布和服务时间分布特性，生灭过程及稳态概率。 单服务台负指数分布排队模型；多服务台负指数排队模型；排队系统设计的最优化 重点：掌握M/M/1模型及其应用 难点：到达流的稳态概率和系统状态转移概率及其优化服务设计 自学：M/G/1模型,3,排队论（Queueing Theory)，也称随机服务系统理论，是运筹学的一个重要分支之一。 1909年，丹麦哥本哈根电子公司电话工程师A. K. Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生。排队论的

2、发展最早是与电话，通信中的问题相联系的，这些问题到现在仍是排队论传统的应用领域。 近年来在计算机通讯、网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到了广泛的应用。 各种排队问题,4,机械坏了 修理 修理工人 修理工人 领取配件 管理员 病人 就诊 医生 打电话 通话 交换台 文件 打印 打印机 飞机降落 降落 跑道指挥机构 顾客 就餐 服务员 汽车 路口 红绿灯,5,1.1 排队系统的组成与特征 首先看一下一般排队系统的组成示意图，不难发现排队系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。现分别说明,1 排队系统的基本概念,6,输入即为顾客的到达，

3、可有下列情况： 1）顾客源可能是有限的，也可能是无限的。 2）顾客是成批到达或是单个到达。 3）顾客到达的间隔时间可能是随机的或确定的。 4）顾客到达可能是相互独立的或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。 5）输入过程可以是平稳的（stationary），也可以是非平稳的。输入过程是平稳的是指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比较困难,1. 输入过程,7,2. 排队规则,1）顾客到达后接受服务，服务分为即时制（损失制）和等待制。即时制不允许排队，不形成队列；而对于等待制将会形成队列，顾客可以按下规则接收服务： (

4、1)先到先服务 FCFS ;(2)后到先服务 LCFS (3)随机服务RAND; （4）有优先权服务 PS。 2）从队列的空间可分为有容量限制和无容量限制。也可分为有形的和抽象的。 3）从队列数可分为单列和多列。（多列时包括各列间可以相互转移、不能相互转移；中途可退出、中途不能退出等。,8,3. 服务机构,1）服务机构分为单服务台和多服务台。不同的输入形式与排队规则和服务机构联合后形成不同的排队服务机构，如,9,2)服务方式分为单个顾客服务和成批顾客服务。 3)服务时间分为确定型(定常时间）和随机型。 4)服务时间的分布在这里我们假定是平稳的,我们研究的问题是：输入是服从某种分布，顾客的到达是

5、相互独立到达的平稳过程；各列间不能相互转移、中途不能退出；单个单个地服务方式，服务服从某种分布， FCFS,10,最主要的、影响最大的是： 顾客相继到达的间隔时间分布 服务时间的分布 服务台数 D.G.Kendall，1953提出了分类法，称为Kendall记号(适用于并列服务台),1971又扩展成为： X/Y/Z/A/B/C,1.2 排队系统的模型分类,11,式中： X 或Y 表示顾客相继到达时间间隔分布和服务时间分布的各种分布符号： M负指数分布（负指数分布具有无记忆性，即Markov性）； D确定型（Deterministic）分布； EkK阶爱尔朗分布Erlang； GI 一般相互独立

6、随机分布(General Independent)； G 一般随机分布,12,Z填写并列的服务台数 A排队系统的最大容量N B顾客源数量m C排队规则（FCFS、LCFS等。本章仅研究FCFS的排队规则） 如 M/M/1/FCFS即为顾客到达时间间隔为负指数分布，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统模型,13,1.3 排队论研究的基本问题 1.排队系统的统计推断:即通过对排队系统主要参数的统计推断和对排队系统的结构分析，判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。 2.系统性态问题:即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布

7、和忙期分布等统计指标,包括了瞬态和稳态两种情形。 3.最优化问题：即包括最优设计(静态优化)，最优运营（动态优化,14,统计推断,性态问题,排队系统研究问题阶段示意图,15,1.4 排队问题求解(主要指性态问题,求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现有系统合理改进和对新建系统的最优设计等。 认识系统：系统分析；改造系统：设计系统。 排队问题的求解： 1、确定或拟合排队系统顾客到达时间间隔的时间分布和服务时间分布(可实测,16,2、根据排队系统对应的理论模型求出用以判断系统运行优劣的基本数量指标的概率分布或

8、特征数。 数量指标主要包括: (1) 队长：系统中的顾客数，它的数学期望记为Ls 。 队列长：系统中排队等待服务的顾客数，它的数学期望记为Lq 。 系统中顾客数Ls =系统中排队等待服务的顾客数Lq +正被服务的顾客数 (2) 逗留时间：指一个顾客在系统中的停留时间，它的数学期望记为Ws,17,等待时间：指一个顾客在系统中排队等待的时间，它的数学期望记为Wq 。 逗留时间=等待时间+服务时间 (3)忙期：指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度） 为了计算上述的数量指标，必须首先计算系统状态的

9、概率 系统状态：系统状态是指系统中顾客数,18,状态概率：用Pn(t)表示,即在t时刻系统中有n个顾客的概率，也称瞬态概率。它是表述系统的各种性能指标的基础。 状态的可能值： 队长没有限制时：n=0 ，1，2， 队长有限制时：n= 0，1，2，3，N 即时制：服务台个数是c时，n=0 ，1，c,求解状态概率Pn(t)方法：是建立含Pn(t)的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此我们常常使用它的极限(如果存在的话,19,稳态的物理意义见右图，系统的稳态一般很快都能达到，但实际中达不到稳态的现象也存在。值得注意的是求稳态概

10、率Pn并不一定求t的极限,而只需求Pn(t)=0 即可,称为稳态(steady state)解，或称统计平衡状态 (Statistical Equilibrium State)的解,20,1.5 排队论主要知识点,排队系统的组成与特征 排队系统的模型分类 顾客到达间隔时间和服务时间的经验分布与理论分布 稳态概率Pn的计算 标准的M/M/1模型(M/M/1/FCFS) 系统容量有限制的模型M/M/1/N/FCFS 顾客源有限模型M/M/1/M/ FCFS 标准的M/M/C模型M/M/C/FCFS,21,M/M/C型系统和C个M/M/1型系统 系统容量有限制的多服务台模型(M/M/C/N/) 顾客

11、源为有限的多服务台模型(M/M/C/M) 一般服务时间的（M/G/1）模型 Pollaczek-Khintchine(P-K) 公式 定长服务时间 M/D/1模型 爱尔朗服务时间M/Ek/1模型 排队系统优化 M/M/1 模型中的最优服务率 标准的M/M/1 Model 系统容量为N的情形 M/M/C模型中最优服务台数C,22,2 到达间隔时间分布和服务时间的分布,要解决排队问题，首先要确定排队系统的到达间隔时间分布与服务时间分布。要研究到达间隔时间分布与服务时间分布需要首先根据现有系统原始资料统计出它们的经验分布（见P315319），然后与理论分布拟合，若能对应，我们就可以得出上述的分布情况

12、,23,2.1 经验分布,经验分布是对排队系统的某些时间参数根据经验数据进行的统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数的经验数据服从该假设分布。 分布的拟合检验一般采用2检验。具体参见有关的概率统计教材内容,24,随机变量：数 随着实验的结果的不同而变化 离散型：的所有可能只有限或至多可列个 连续型：（）取值于某个区间（a，b） 分布函数（连续,2.2 概率论复习知识,25,条件概率,26,2.3 理论分布,式中为常数(0)，称X服从参数为的泊松分布。 若在上式中引入时间参数t，即令t代替，则有,1.泊松分布 在概率论中，

13、我们曾学过泊松分布，设随机变量为X，则有,n=0,1,2, （1,t0，n=0,1,2, （2,27,2)式所表示的是与时间有关的随机变量的概率，这已不是简单的概率论的知识了，而是一个随机过程，即泊松过程。 下面我们在一定的假设条件下，推出顾客的到达过程就是一个泊松过程。 若设N(t)表示在时间区间0,t)内到达的顾客数(t0)，Pn(t1,t2)表示在时间区间t1,t2)(t2t1)内有n(0)个顾客到达的概率。即,t2t1，n0,28,无后效性（独立性）：各区间内的顾客到达数相互独立，即Markov性,平稳性：即对于足够小的t，在时间区间t，t+t)内有1个顾客到达的概率为,当Pn(t1,

14、t2)符合于下述三个条件时，我们说顾客到达过程就是泊松过程或者说顾客到达形成普阿松流。 普阿松流的三个特性,设表示单位时间内有 一个顾客到达的概率,29,普通性：对充分小的t,在时间区间t,t+t）内有2个或2个以上顾客到达的概率是t一高阶无穷小,令t1=0,t2=t, 则Pn(t1,t2)=Pn(0,t)=Pn(t,也就是在t,t+t内有一个顾客到达的概率与t无关,而与t成正比。 0 是常数，称为概率强度,即,由此知，在(t，t+t)区间内没有顾客到达的概率为,区间长度为t时有 n个顾客的概率,30,为了求Pn(t)，即Pn(0,t)，需要研究它在时刻t到t+t时刻的改变量，也就是要建立Pn

15、(t)的微分方程。 对于区间0，t+t)可以分成0，t)和t，t+t)，其到达总数是n，不外有下列三种情况：所以有,31,32,令t0取极限（并注意初始条件）得,当n=0时，没有B，C两种情况，则,33,代初始条件(t=0)有,C = 0,3）式两端乘 et 并移项得,由上式得,两边积分得,一阶台劳展开为1-t,34,将n=1,2,3代入（6）得,注意利用(5)式,35,如此继续递推下去得,n个顾客到达的概率,即随机变量N(t)=n服从泊松分布。它的数学期望和方差为,36,由高等数学知，若设,即,令k=n-1，则,37,即,同理方差为,38,其概率密度函数为,t0,没有顾客到达的概率为： (由

16、（5）式而来,2.负指数分布 当输入过程是泊松流时，我们研究两顾客相继到达的时间间隔的概率分布。 设T为时间间隔，分布函数为FT（t），即： FT（t）=PTt 此概率等价于在0，t）区间内至少有1个顾客到达的概率,39,由前知，表示单位时间内顾客平均到达数，这里1/表示顾客到达的平均间隔时间，两者是吻合的。 可以证明，间隔时间T独立且服从负指数分布与顾客到达形成泊松流是等价的,下面我们再谈一下服务时间的分布： 对顾客的服务时间，实际是系统处于忙期时两顾客相继离开系统的时间间隔，一般地也服从负指数分布，即,即T服从负指数分布，由概率论知它的期望及方差为,40,其中：表示单位时间内能被服务完成的

17、顾客数，即平均服务率。 1/表示一个顾客的平均服务时间,3.爱尔朗(Erlang)分布 设v1, v2，, vk是k个独立的随机变量，服从相同参数k的负指数分布，那么,则,令 ，则称为服务强度,41,串列的k个服务台，每台服务时间相互独立，服从相同的负指数分布（参数k），那么一顾客走完k个服务台总共所需要服务时间就服从上述的k阶Erlang分布,则称T服从k阶爱尔朗分布，其特征值为,的概率密度是(可以证明,当k=1时， Erlang分布即为负指数分布； 当k增加时， Erlang分布逐渐变为对称的； 当k30时， Erlang分布近似于正态分布,每一个服从k，因此E(Ti)=1/ k，且Ti之

18、间相互独立,42,例:有易碎物品500件,由甲地运往乙地,根据以往统计资料,在运输过程中易碎物品按普阿松流发生破碎,其概率为0.002,现求:1.破碎3件物品的概率;2.破碎少于3件的概率和多于3件的概率;3.至少有一件破损的概率. 解:1.求破碎3件物品的概率: =0.002500=1 则 P(k=3)=(3/3！)e-=(13/3！)e-1=0.0613 即物品破碎3件的概率为6.13 2.破碎物品少于3件的概率,43,破碎物品少于3件的概率为91.97 破碎物品多于3件的概率为,3.至少有一件破碎的概率为 Pk1=1-(1k/k!)e-=1-(10/0!)e-1=0.632,44,3.单

19、服务台负指数分布排队系统的分析,研究对象为单队、单服务台（服务台数为1），包括： （1）标准M/M/1模型（M/M/1/）； （2）系统容量有限制（M/M/1/N/） （3）有限顾客源（M/M/1/m,45,以后各节将介绍几个常见的排队模型。对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标： (1)系统的平均队长Ls(期望值)和平均队列长Lq期望值； (2)系统中顾客平均逗留时间Ws与队列中平均等待时间Wq； 本节只研究M/M/1模型，下面分三种情况讨论,46,3.1 标准的M/M/1模型,1.稳态概率Pn的计算 为分析模型，首先要确定在任意时刻t，状态为n（系统中有n个顾客）的

20、概率Pn(t)(瞬态概率)，它决定了系统的运行特征。 已知顾客到达服从参数为的普阿松过程，服务时间服从参数为的负指数分布。现仍然通过研究区间t，t+t）的变化来求解。在间刻t+t，系统中有n个顾客不外乎有下列四种情况（到达或离去2个以上的没列入，是高阶无穷小,1、输入过程：顾客源无限，顾客单个到达，相互独立，服从普阿松分布，平稳； 2、排队规则：单队，队长无限制，FCFS。 3、服务机构：单服务台，各顾客服务时间相互独立，服从负指数分布。 此外：假设到达时间间隔和服务时间是相互独立的,标准的M/M/1模型即为M/M/1/FCFS模型,47,48,由于这四种情况是互不相容的，所以Pn(t+t)应

21、是这四项之和，将所有的高阶无穷小合并，则有,49,令t0，得关于Pn(t)的微分差分方程,1,当n=0时，只有表中的（A）、（B）两种情况，因为在较小的t内不可能发生（D）（到达后即离去），若发生可将t取小即可,50,对于方程(1)、(2)求解很麻烦，即便求得解也是瞬态解，无法应用。为此,我们只要求得稳态解即可。 稳态时，Pn(t)与时间无关，可以写成Pn， 它对时间的导数为0，所以由(1)、(2)两式得,在时刻t系统处于无顾客状态，而在t+t时刻内又没有顾客来到系统（必然没有离去事件,在时刻t系统有一个顾客接受服务，在t+t时刻内服 务完毕离去，且在t+t时刻内又没有顾客来到系统,51,上式

22、即为关于Pn的差分方程。由此可得该排队系统的状态转移图,将其代入（3）式并令n=1,2,(也可从状态转移图中看出状态平衡方程)得,这种系统状态(n)随时间变化的过程就是生灭过程（Birth and Death Process），它可以描述细菌的生灭过程,52,n=1,n=2,53,以此类推，当n=n时,5,以及概率性质知,当=1时，似乎好象来一个顾客服务一个顾客，但这是在均衡条件下和所有的顾客的服务时间都相等时，才会出现不存在排队现象的这种理想的现象。在随机的情况下，这是不可能的,54,上式就是系统稳态概率，以它为基础可以 算出系统的运行指标。 2. 系统的运行指标计算 (1) 系统中的平均顾

23、客数（队长期望值Ls,01,55,8,3) 顾客在系统中的平均逗留时间Ws 顾客在系统中的逗留时间是随机变量，可以证明，它服从参数为-的负指数分布，分布函数,2) 队列中等待的平均顾客数Lq（队列长期望值,56,和密度函数为,4)顾客在队列中的等待时间的期望值Wq 顾客在队列中的等待时间应为Ws减去平均服务时间,57,四个指标的关系为(Little 公式,3. 系统的忙期与闲期,系统处于空闲状态的概率,系统处于繁忙状态的概率,下标s表示系统 下标q表示队列,58,3.2 系统容量有限制的模型 M/M/1/N/FCFS,当系统容量最大为N时，排队系统中多于N个的顾客将被拒绝。当N=1时，即为瞬时

24、制；N时，即为容量无限制的情况,59,现在研究系统中有n个顾客的概率Pn(t). 对于P0(t)，前面的（2）式仍然成立,2,对于(1)式，当n=1,2,N-1时，也仍能成立,1,n=1,2,N-1,但当n=N时，有下面两种情况,60,8,其状态转移图为,61,在稳态情况下有,解（9）式得,而等比数列,62,注：当=1时，试讨论其概率Pn 下面计算其运行指标,1) 平均队长Ls,1,试证=1时,Ls=N/2,63,2）队列长（期望值,有效到达率e的引入： Little公式可应用的条件是：其平均到达率是在系统有空时的平均到达率。当系统满员时，就不能再应用了。要用就应该应用有效到达率。 因为系统容量有限，当满员时，顾客将被拒绝，因此实际的顾客到达率