8-1排队论概述

第8章排队论概述本章要点：1.排队系统的组成；2.排队模型的研究方式；3.典型排队系统模型结构及应用。内容框架：输入过程排队规则服务台排队系统分类符号表示研究方式典型模型及其应用明确系统意义画状态转移速度图→Λ→状态概率方程计算基本数量指标应用举例注释：大小写8.1排队系统的特征与基本排队系统一、引言1、什么是排队论？排队论是研究拥挤现象的一门学科。它是在研究各种排队系统概率规律性的基础上，解决有关排队系统的最优设计（静态）和最优控制（动态）问题。2、排队论的起源与应用领域&20世纪初——Bell电话公司为减少用户呼叫，研究电话线路合理配置问题；&1909年丹麦工程师A.K.Erlang受热力学统计平衡概念启发论文“概率论与电话交换”，解决了上述问题；&应用于：通讯系统、交通运输、机器维修、库存控制、计算机设计……二、排队系统的特征及其组成1、排队系统的特征即拥挤现象的共性:有请求服务的人或物（统称为顾客）；有为顾客服务的人或物（统称为服务台）；具有随机性；（各种排队系统中，顾客相继到达的间隔时间以及对每一位顾客的服务时间是随机的）随机性是排队系统的一个重要特征。2、排队系统的基本组成顾客源等待队列顾客离去（输出）服务机构排队规则？（1）输入过程：描述顾客到达排队系统的规律。排队系统123顾客到达（输入）服务机构顾客总体数（顾客源）有限或无限；顾客到达方式是单个到达或成批到达；顾客相继到达的间隔时间服从什么样的概率分布；（2）服务规则：描述顾客到达排队系统后接受服务的先后次序，一般可分为损失制、等待制和混合制三类：损失制(Losingsystem)——当顾客到达排队系统时，若所有的服务台均被占用(正在进行服务)，则离开系统，另求服务；等待制(Waitingsystem)——顾客到达系统时，所有的服务台均被占用（正在进行服务），顾客就加入排队行列等待服务，服务台可按照下面的规则进行排序服务：①先到先服务（FCFS）FirstComeFirstserve②后到先服务（LCFS）LastComeFirstserve③随机服务（SIRO）ServeInRandomOrder④有优先权的服务（PR）Preference混合制(LosingsystemandWaitingsystem)——损失制和等待制的结合，主要有以下两种情况：①队长有限制；②排队等待时间有限制；（3）服务机构（服务台）：数量及布置形式——见下页图某一时刻接受服务的顾客数——单个服务还是成批服务；服务时间的分布——最常见的有定常分布、负指数分布、k阶爱尔朗分布、一般分布等；。。。。。。12┇n。。。。。。。。。12┇n（a）单队单台。。。。。。12312(d)混合多服务台。。。。。。。。。12…n(e)串联多服务台排队系统服务台布置形式(b)多队多台(c)单队多台三、排队模型的符号表示——肯道尔分类方法(D.G.kendall)表示为：A/B/C/D/E/F或[A/B/C]：[d/e/f]A表示输入过程——顾客相继到达的间隔时间的分布；B表示服务时间服从的分布；C表示服务台的个数；D表示系统容量；E表示顾客源包含的全部个体数量；F表示服务规则；举例：M/M/1/∞/∞/FCFS表示泊松输入、服务时间服从负指数分布、1个服务台、系统容量无限制（即等待制）、顾客源无限、先到先服务的排队系统；GI/EK/1/N/∞/FCFS表示一般独立输入（顾客到达的间隔时间服从一般独立分布）、服务时间服从K阶爱尔朗分布、1个服务台、系统容量为N、顾客源无限、先到先服务的排队系统。常用的各种分布符号：M——负指数分布(兼指泊松输入)；D——定长分布；EK——K阶爱尔朗分布；GI——一般独立随机分布；G——一般随机分布；四、排队系统研究的问题1、排队系统的数量指标(特征量)（1）研究的目的是：了解系统的基本特征和性态，揭示其表现的概率规律性，以便对系统作出评价。（2）主要的数量指标：队长（Ls）——排队系统中顾客的平均数（期望值），包括正在接受服务和等待接受服务的顾客总数期望值。已知队长分布，就能计算队长超过某个数量的概率，据此可以考虑是否应改变服务方式、设计合理的等待空间等；队列长（Lq）——系统中排队等待接受服务的顾客数期望值；逗留时间（Ws）——顾客在系统内停留时间（包括排队等待时间和接受服务的时间）的期望值；等待时间（Wq）——顾客从到达系统的时刻到开始接受服务的时刻止的时间段；忙期和闲期分布——忙期指从有顾客到达空闲服务台接受服务开始到服务台再度空闲为止的这段时间，即服务台连续工作的时间。“忙期”是一个随机变量，可以表征服务台的工作强度；服务台连续保持空闲的时间长度称为闲期。在排队系统中忙期和闲期是交替出现的。服务设备利用率——指服务设备工作时间占总时间的比例。该指标可以衡量服务设备的工作强度、磨损和疲劳程度。顾客损失率——由于服务能力不足而造成的顾客流失的概率称为顾客损失率。该指标过高会造成服务系统利润减少，因此损失制和混合制排队系统均会重视对该指标的研究。2、统计推断问题的研究对实际问题建立排队模型时，必须判断该系统适合建立何种排队模型，从而进一步用排队理论进行分析研究。首先必须进行现实数据的收集、处理；进而研究相继到达的间隔时间是否独立分布、确定其分布类型和有关参数，研究服务时间与相继到达的间隔时间之间的独立性以及服务时间的分布等；判断该系统适合建立何种类型的排队模型，再用排队理论进行分析研究。3、排队系统的优化研究排队系统最优设计的静态优化和研究排队系统最优控制的动态优化。最优设计：通常是在输入和服务参数给定的条件下，确定系统的设计参数（如服务台数量），以求系统运行指标达到最优。最优控制：在系统运行的参数可以随时间或状态而变化的情况下（如服务率随顾客数的变化而改变）根据系统的实际情况假设一个合理或实际可行的控制策略，然后分析确定系统运行的最佳参数或者是对一个具体系统研究一个最佳的控制策略。研究排队系统的目的就是通过对该系统概率规律的研究，达到系统的最优设计和最优控制，以最少的费用实现系统的最大效益。即使服务系统既能在适当的程度上满足顾客需求，同时又使所需费用达到最小。服务费用等待费用费用服务水平总费用费用优化示意图1、泊松分布（Poisson）也称为泊松流，在排队论中常称为最简单流。概率分布：,2,1,0!)()(kektktNPtk其中，λ0为一常数，t≥0。求N(t)的数学期望得:tektkktNkPtNEtkkk11!)(})({)]([则λ=E[N(t)]/t。因此，λ表示单位时间内到达系统的平均顾客数,又称平均到达率。五、排队系统中常见的几种典型理论分布最简单流的4个基本性质：平稳性：在时间段t内，恰有n个顾客到达系统的概率P{N(t)=n}仅与t的长短有关,而与该时间段的起始时刻无关；无后效性：在不相交的时间区间内到达的顾客数是相互独立的。如：在[a，a+t]时段内到达K个顾客的概率与时刻a之前到达多少顾客无关；普通性：在充分小的间隔时间内至少到达两个顾客的概率ψ(Δt)=o(t),Δt→0,即0)(0ttLimt有限性：在任意有限的时间区间内，到达有限个顾客的概率为1，即1)(1kktNP泊松流在排队论中的意义：实际问题中最常见；数字处理简单；当实际流与泊松流有较大出入时，经过一定的变换，结果也可达到一定的精度；2、负指数分布密度函数和分布函数：数学期望和方差：0001)(,000)(ttetFttetptt21)(,1)(tDtE定理6-1顾客到达服从参数为λ的泊松分布等价于顾客相继到达的间隔时间是独立的且同为负指数分布。参数μ0表示单位时间内完成服务的顾客平均数,称为平均服务率。3、爱尔朗分布当顾客在系统内所接受的服务可以分为K个阶段，每个阶段的服务时间T1，T2，…，Tk为服从同一分布（参数为kμ的负指数分布）的k个相互独立的随机变量，顾客在完成全部服务内容并离开系统后，另一个顾客才能进入服务系统，则顾客在系统内接受服务时间之和T=T1+T2+…+Tk服从k阶爱尔朗分布Ek，其分布密度函数为：tkektf)(1()(),0,0,1(1)!kkktkktftetkk相应的数学期望和方差为：21)(,1)(kTDTE当k=1时，爱尔朗分布归结为负指数分布，当k增大时，图形逐渐变为对称的，当k≥30时，近似于正态分布，当k→∞，由D(T)=0可知,爱尔朗分布归结为定长分布(顾客接受服务的时间是一个确定的常数)。因此，爱尔朗分布类可以看成完全随机（k=1）与完全确定(k=∞)的中间型，能对现实问题提供更广泛的模型类。k=∞k=3k=2k=1)(tfkto