运筹学18排队论

排队论(QueueingTheory)（随机服务系统）,排队论（QueueingTheory)，也称随机服务系统理论，是运筹学的一个重要分支之一。1909年，丹麦哥本哈根电子公司电话工程师A.K.Erlang的开创性论文“概率论和电话通讯理论”标志此理论的诞生。排队论的发展最早是与电话，通信中的问题相联系的，这些问题仍然是排队论传统的应用领域。近年来在计算机通讯、网络系统、交通运输、医疗卫生系统、库存管理、作战指挥等各领域中均得到了广泛的应用。,设备修理修理工人修理工人领取配件管理员病人就诊医生打电话通话交换台文件打印打印机飞机降落跑道指挥机构顾客就餐服务员汽车通过路口红绿灯,1.1排队系统的组成与特征三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。,1排队系统的基本概念,输入即为顾客的到达，可有下列情况：1）顾客源：有限的，或无限的。2）到达方式：成批到达，或单个到达。3）到达间隔时间：随机的，或确定的。4）到达关联性：相互独立的，或关联的。所谓独立指t时刻顾客的到达对t时刻以后顾客的到达无影响。5）输入过程可以是平稳的（stationary），也可以是非平稳的。平稳的，指顾客相继到达间隔时间分布及其参数（均值、方差）与时间无关；非平稳的则与时间相关，非平稳的处理比较困难。,1.输入过程,2.排队规则,1）队列数：单列，或多列。（多列时包括各列间可以相互转移、不能相互转移；中途可退出、中途不能退出等。）2）队列的空间：有容量限制，或无容量限制。也可分为有形的和抽象的。3）顾客到达后接受服务，服务分为即时制（损失制）和等待制。即时制不允许排队，不形成队列；而对于等待制将会形成队列，顾客可以按以下规则接受服务：先到先服务FCFS；后到先服务LCFS；随机服务RAND；有优先权服务PS。,3.服务机构,1）服务机构：单服务台，或多服务台。,2)服务方式：单个顾客服务，或成批顾客服务。3)服务时间：确定型(定长时间），或随机型。4)服务时间的分布：假定是平稳的。,我们研究的问题是：输入服从某种分布，顾客的到达是相互独立的平稳过程；各列间不能相互转移、中途不能退出；顾客单个到来，服务方式FCFS。,最主要的、影响最大的特征是：顾客相继到达间隔时间的分布服务时间的分布服务台数D.G.Kendall，1953提出了分类法，称为Kendall记号：X/Y/Z年又扩充为：X/Y/Z/A/B/C,1.2排队系统的模型分类,式中：X表示顾客相继到达间隔时间分布；Y表示服务时间分布；各种分布符号如下：M负指数分布（负指数分布具有无记忆性，即Markov性）；D确定型（Deterministic）分布；EkK阶爱尔朗分布Erlang；GI一般相互独立随机分布(GeneralIndependent)；G一般随机分布。,Z并列的服务台数A排队系统的最大容量NB顾客源数量mC排队规则（FCFS、LCFS等。本章仅研究FCFS排队规则）如M/M/1/FCFS即为顾客到达时间间隔为负指数分布，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统模型。,1.3排队论研究的基本问题1.排队系统的统计推断：即通过对排队系统主要参数的统计推断和对排队系统的结构分析，判断一个给定的排队系统符合哪种模型，以便根据排队理论进行研究。2.系统性态问题：即研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括瞬态、稳态两种情形。3.最优化问题：即包括最优设计(静态优化)，最优运营（动态优化）。,1.4排队问题求解,求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现有系统合理改进和对新建系统的最优设计等。认识系统；分析系统；改造系统；设计系统。排队问题的求解：1、确定或拟合排队系统顾客到达时间间隔分布和服务时间分布(可实测)。,2、根据排队系统对应的理论模型求解用以判断系统运行优劣的基本数量指标的概率分布或特征数。数量指标主要包括:队长：系统中的顾客数，它的数学期望记为Ls。队列长：系统中排队等待服务的顾客数，它的数学期望记为Lq。系统中顾客数Ls=系统中排队等待服务的顾客数Lq+正被服务的顾客数,逗留时间：指一个顾客在系统中的停留时间，它的数学期望记为Ws。等待时间：指一个顾客在系统中排队等待的时间，它的数学期望记为Wq。逗留时间=等待时间+服务时间,忙期：指从顾客到达空闲服务机构起到服务机构再次空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度）为了计算上述的数量指标，必须首先计算系统状态的概率。,系统状态：系统状态是指系统中顾客数。状态概率：用Pn(t)表示,即在t时刻系统中有n个顾客的概率，也称瞬态概率。它是表述系统的各种性能指标的基础。状态的可能值：队长没有限制时：n=1，2，队长有限制时：n=1，2，3，N即时制：服务台个数是c时，n=1，c,求解状态概率Pn(t)方法：建立含Pn(t)的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于对瞬态解求出确定值比较困难，即便求得一般也很难使用。因此我们常常使用它的极限(如果存在的话)：,称为稳态(steadystate)解，或称统计平衡状态(StatisticalEquilibriumState)的解。,稳态的物理意义见图2，系统的稳态一般都能很快达到，但实际中达不到稳态的现象也存在。,图2排队系统状态变化示意图,2到达间隔时间分布和服务时间分布,一个排队系统的最主要特征参数是顾客到达间隔时间分布与服务时间分布。要研究到达间隔时间分布与服务时间分布需要首先根据现有系统原始资料统计出它们的经验分布，然后与理论分布拟合，若能对应，即可得出上述分布情况。,2.1经验分布,经验分布是对排队系统的某些时间参数根据经验数据进行统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数的经验数据服从该假设分布。分布的拟合检验一般采用2检验。具体参见有关的概率统计教材内容。,随机变量：变量的取值随实验的结果的不同而变化离散型：的所有可能值有限或至多可列个连续型：（）取值于某个区间（a，b）,2.2概率论复习知识,分布函数(连续):,方差:,条件概率:,密度函数:(连续),2.3理论分布,式中为常数(0)，称x服从参数为的泊松分布。,1.泊松分布设随机变量为x，则有：,n=0,1,2,（1）,(2)式表示与时间有关的随机变量的概率，是一个随机过程，即泊松过程。,若在上式中引入时间参数t，即令t代替，则有：,t0，n=0,1,2,（2）,下面我们在一定的假设条件下，推导顾客的到达过程就是一个泊松过程。设N(t)表示在时间区间0,t)内到达的顾客数(t0)，Pn(t1,t2)表示在时间区间t1,t2)(t2t1)内有n(0)个顾客到达的概率。即：,（t2t1，n0）,无后效性（独立性）：各区间内的顾客到达数相互独立，即Markov性。,当Pn(t1,t2)符合于下述三个条件时，我们说顾客的到达过程是泊松过程或者说顾客的到达形成泊松流。,平稳性：即对于足够小的t，在时间区间t，t+t内有1个顾客到达的概率为,设表示单位时间内有一个顾客到达的概率,也就是在t,t+t内有一个顾客到达的概率与t无关,而与t成正比。0是常数，称为概率强度。,普通性：对充分小的t,在时间区间（t,t+t）内有2个或2个以上顾客到达的概率是t的高阶无穷小.即,由此知，在(t，t+t)区间内没有顾客到达的概率为:,为了求Pn(t)，即Pn(0,t)，需要研究它从时刻t到t+t时刻的改变量，也就是要建立Pn(t)的微分方程。区间0，t+t)可以分成0，t)和t，t+t)，其间顾客到达总数是n，不外有下列三种情况：,令t1=0,t2=t,则Pn(t1,t2)=Pn(0,t)=Pn(t),区间长度为t时有n个顾客的概率,代初始条件(t=0)有：,C=0,（3）式两端乘et并移项得：,由（）式得：,两边积分得：,将n=1,2,3代入（6）得：,(注意利用(5)式),如此继续递推下去得：,（n个顾客到达的概率）,即随机变量N(t)=n服从泊松分布。它的数学期望和方差为：,令k=n-1，则,由级数展开,即：,即：,没有顾客到达的概率为：(由（5）式而来),2.负指数分布当输入过程是泊松流时，我们研究两顾客相继到达时间间隔的概率分布。设T为时间间隔，分布函数为FT（t），即：FT（t）=PTt此概率等价于在0，t）区间内至少有1个顾客到达的概率.,由前知，表示单位时间内顾客平均到达数，这里1/表示顾客到达的平均间隔时间，两者是吻合的。间隔时间T独立且服从负指数分布与顾客到达形成泊松流是等价的。,即T服从负指数分布，由概率论知它的期望及方差为：,其中：表示单位时间内能被服务完成的顾客数，即平均服务率。1/表示一个顾客的平均服务时间。,，则,令，则称为服务强度。,下面我们再看服务时间的分布：对顾客的服务时间，实际是系统处于忙期时两顾客相继离开系统的时间间隔，一般地也服从负指数分布，即：,3.爱尔朗(Erlang)分布设v1,v2，,vk是k个独立的随机变量，服从相同参数k的负指数分布，那么：,的概率密度是,每一个服从k，因此E(Ti)=1/k，且Ti之间相互独立,则称T服从k阶爱尔朗分布，其特征值为:,串列的k个服务台，每台服务时间相互独立，服从相同的负指数分布（参数k），那么一顾客走完k个服务台总共所需要服务时间就服从上述的k阶Erlang分布。,当k=1时，Erlang分布即为负指数分布；当k增加时，Erlang分布逐渐变为对称的；当k30时，Erlang分布近似于正态分布；,练习：有易碎物品500件,由甲地运往乙地,根据以往统计资料,在运输过程中易碎物品按泊松流发生破碎,其概率为0.002,现求:1.破碎3件物品的概率;2.破碎少于3件的概率和多于3件的概率;3.至少有一件破损的概率.,3.单服务台负指数分布排队系统的分析,研究对象为单队、单服务台（服务台数为1），包括：（1）标准M/M/1模型（M/M/1/）；（2）系统容量有限制（M/M/1/N/）（3）有限顾客源（M/M/1/m）,以后各节将介绍几个常见的排队模型。对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标：(1)系统平均队长Ls(期望值)和平均队列长Lq(期望值)；(2)系统中顾客平均逗留时间Ws与平均等待时间Wq；本节只研究M/M/1模型，下面分三种情况讨论：,3.1标准的M/M/1模型,标准的M/M/1模型即为M/M/1/FCFS模型1、输入过程：顾客源无限，顾客单个到达，相互独立，服从泊松分布，平稳；2、排队规则：单队，队长无限制，FCFS。3、服务机构：单服务台，各顾客服务时间相互独立，服从负指数分布。此外：假设到达时间间隔和服务时间是相互独立的。,1.稳态概率Pn的计算为分析模型，首先要确定在任意时刻t，状态为n（系统中有n个顾客）的概率Pn(t)(瞬态概率)，它决定了系统的运行特征。已知顾客到达服从参数为的泊松过程，服务时间服从参数为的负指数分布。Pn(t)的计算仍然通过研究区间t，t+t）的变化来求解。在区间t，t+t），系统中有n个顾客不外乎有下列四种情况（到达或离去2个以上的没列入，是高阶无穷小）。,由于这四种情况是互不相容的，所以Pn(t+t)应是这四项之和，将所有的高阶无穷小和并，则有：,令t0，得关于Pn(t)的微分差分方程：,(1),当n=0时，只有表中的（A）、（B）两种情况，因为在较小的t内不可能发生（D）（到达后即离去），若发生可将t取小即可。,对方程(1)、(2)求解很麻烦，即便求得解也是瞬态解，无法应用。为此,我们只要求得稳态解即可。稳态时，Pn(t)与时间无关，可以写成Pn，它对时间的导数为0，所以由(1)、(2)两式得：,在时刻t系统处于无顾客状态，而在t+t时刻内又没有顾客来到系统（必然没有离去事件）,在时刻t系统有一个顾客接受服务，在t+t时刻内服务完毕离去，且在t+t时刻内又没有顾客来到系统,上式即为关于Pn的差分方程。由此可得该排队系统的状态转移图：,将其代入（3）式并令n=1,2,(也可从状态转移图中看出状态平衡方程)得：,n=1,n=2,以此类推，当n=n时，,(5),当=1时，似乎好象来一个顾客服务一个顾客，但这是在均衡条件下和所有的顾客的服务时间都相等时，才会出现不存在排队现象的这种理想的现象。在随机的情况下，这是不可能的。,由概率性质知,(6)式就是系统稳态概率，以它为基础可以计算系统的运行指标。,2.系统的运行指标计算(1)系统中的平均顾客数（队长期望值Ls）,(01),(8),(2)队列中等待的平均顾客数Lq（队列长期望值）,(3)顾客在系统中的平均逗留时间Ws顾客在系统中的逗留时间是随机变量，可以证明，它服从参数为-的负指数分布，分布函数和密度函数为：,(4)顾客在队列中的等待时间的期望值Wq顾客在队列中的等待时间应为Ws减去平均服务时间。,四个指标的关系为(Little公式)：,3.系统的忙期与闲期,系统处于空闲状态的概率：,系统处于繁忙状态的概率：,下标s表示系统下标q表示队列,3.2系统容量有限制的模型M/M/1/N/FCFS,当系统容量最大为N时，排队多于N个的顾客将被拒绝。当N=1时，即为瞬时制；N时，即为容量无限制的情况。,现在研究系统中有n个顾客的概率Pn(t).对于P0(t)，前面的（2）式仍然成立,(2),对于(1)式，当n=1,2,N-1时，也仍能成立。,(1),(n=1,2,N-1),但当n=N时，有下面两种情况：,(8),其状态转移图为:,解（9）式得：,而等比数列,下面计算其运行指标：,(1)平均队长Ls：,(1),（2）队列长（期望值）,有效到达率e的引入：Little公式可应用的条件是：其平均到达率是在系统有空时的平均到达率。当系统满员时，需要重新定义到达率，即有效到达率。,因为系统容量有限，当满员时，顾客将被拒绝，因此实际的顾客到达率为0，与不一样，为了求其他指标，需要求得有效到达率为e：,可以验证：,此种情况的公式与前类似，只有Ls不同，e与不同。求e必须先求得P0或Pn才行。,（3）顾