排队论

5.2排队论排队是日常生活和工作中常见的现象，它由两个方面构成，一是要求得到服务的顾客，二是设法给予服务的服务人员或服务机构（统称为服务员或服务台），顾客与服务台就构成一个排队系统，或称为随机服务系统。如图5.5所示。图5.5排队系统结构5.2.1排队论概述1.排队论研究的基本问题随机性是排队系统的共同特性，顾客的到达间隔时间与顾客所需的服务时间中，至少有一个具有随机性。排队论研究的首要问题是系统的主要数量指标（如：系统的队长（系统中的顾客数）、顾客的等待时间和逗留时间等）的概率特性，然后进一步研究系统优化问题。与这两个问题相关联的还有系统的统计推断问题。1)性态问题(即数量指标的研究)研究排队系统的性态问题就是通过研究系统的主要数量指标的瞬时性质或统计平衡下的性态来研究排队系统的基本特征。2)最优化问题排队系统的最优化问题涉及排队系统的设计、控制以及系统有效性的度量，包括系统的最优设计（静态最优）和已有系统的最优运行控制（动态最优），前者是在服务系统设置之前，对未来运行的情况有所估计，确定系统的参数，使设计人员有所依据；后者是对已有的排队系统寻求最优运行策略。其内容很多，有最小费用问题，服务率的控制问题等。3)统计推断问题排队系统的统计推断是通过对正在运行的排队系统多次观测、搜集数据，用数理统计的方法对得到的资料进行加工处理，推断所观测的排队系统的概率规律，建立适当的排队模型。2.排队系统的基本组成及特征实际中的排队系统是各种各样的，但从决定排队系统进程的因素看，它由3个基本部分组成：输入过程、排队规则和服务机构。由于输入过程、排队规则和服务机构的复杂多样性，可以形成各种各样的排队模型，因此在研究一个排队系统之前，有必要弄清楚这3部顾客总体排队结构服务机构顾客到达服务规则离去排队规则分的具体内容和结构。1)输入过程输入过程是说明顾客来源及顾客是按怎样的规律到达系统。它包括3方面内容：①顾客总体(顾客源)数：它可能是有限的，也可能是无限的。②到达的方式：是单个到达还是成批到达。③顾客相继到达的时间间隔的概率分布，分布的参数怎样，到达的间隔时间之间是否独立。令001nTTn，表示第n个（批）顾客的到达时刻，则01210nnTTTTT又令11nnnTTn，，则n表示第n个（批）顾客到达时刻与第1n个（批）顾客到达时刻之差，称序列｛n，1n｝为顾客相继到达的间隔时间序列。在排队论研究中，一般假定｛n，1n｝相互独立、同分布。经常用到的有：定长分布，即顾客是等距时间到达；最简流（Poisson流），即｛n，1n｝独立、同负指数分布；k阶埃尔朗分布；一般独立分布等。2)排队规则排队规则是指服务允许不允许排队，顾客是否愿意排队。在排队等待的情形下服务的顺序是什么等，分为：①损失制：顾客到达时，若所有服务台均被占，服务机构又不允许顾客等待，此时该顾客就自动离去。②等待制：顾客到达时，若所有服务台均被占，他们就排队等待服务。服务顺序的规则有：先到先服务（FCFS），即顾客接到达的先后顺序接受服务；后到先服务(LCFS、有优先权的服务(PS))以及随机挑选顾客进行服务的随机服务（SIRO）等。③混合制：损失制与等待制的混合，分为队长（容量）有限的混合制系统，等待时间有限的混合制系统（等待时间＜固定的时间0t，否则就离去），以及逗留时间有限制的混合制系统。3)服务机构服务机构主要包括：①服务台的数目。在多个服务台的情形下，是串联或是并联；②顾客所需的服务时间服从什么样的概率分布，每个顾客所需的服务时间是否相互独立，是成批服务或是单个服务等。常见顾客的服务时间分布有：定长分布、负指数分布、k阶埃尔朗分布、一般分布等。3.常用的排队系统符号表示一个排队系统是由许多条件决定的，为了简明起见，在经典排队系统中，常采用3～6个英文字母表示一个排队系统，字母之间用斜线隔开，形式为/////XYZABC：第一个字母X表示顾客相继到达时间间隔的分布，第二个字母Y表示服务时间的分布，第三个字母Z表示服务台的个数，第四个字母A表示系统的容量，即可容纳的最多顾客数；有时用第五个字母B表示顾客源数目，第六个字母C表示服务规则。若顾客源数目为和服务规则为FCFS，后两项可以略去不写。例如：///MMc表示输入过程是Poisson流，服务时间服从负指数分布，有c个服务台0c），容量为无穷，于是///MMc系统是等待制模型；//1/GIM表示输入过程为顾客独立到达且相继到达的间隔时间服从一般概率分布，服务时间是相互独立、服从负指数分布，1个服务台，容量为无穷的等待制模型；///DMcK表示相继到达的间隔时间独立、服从定长分布，服务时间相互独立、服从负指数分布，有c个服务台，容量为K（cK）的混合制模型，等等。4.排队系统的主要数量指标1)队长L与等待队长QL队长是指在系统中的顾客数（包括正在接受服务的顾客），而等待队长是指系统中排队等待的顾客数，它们都是随机变量，是顾客和服务机构双方都十分关心的数量指标，显然，队长等于等待队长加上正在被服务的顾客数。2)等待时间QW与逗留时间W顾客的等待时间是指从顾客进入系统的时刻起直到开始接受服务止这段时间，而逗留时间是顾客在系统中的等待时间与服务时间之和。在假定到达与服务是彼此独立的条件下，等待时间与服务时间是相互独立的。等待时间与逗留时间是顾客最关心的数量指标，应用中关心的是统计平衡下它们的分布及期望平均值。3)忙期与闲期从顾客到达空闲的服务机构起，到服务台再次变为空闲止，这段时间是系统连续工作的时间，我们称为系统的忙期，它反映了系统中服务员的工作强度。与忙期对应的是系统的闲期，即系统连续保持空闲的时间长度。在排队系统中，统计平衡下忙期与闲期是交替出现的。而忙期循环是指相邻的两次忙期开始的间隔时间，显然它等于当前的忙期长度与闲期长度之和。4)输出过程输出过程也称离去过程，是指接受服务完毕的顾客相继离开系统的过程。刻画一个输出过程的主要指标是相继离去的间隔时间和在一段已知时间内离去顾客的数目，这些指标从一个侧面也反映了系统的工作效率。此外，在不同的排队系统中，还会涉及其它数量指标，例如在损失制与混合制排队系统中，由于服务能力不足而造成的顾客的损失率及单位时间内损失的平均顾客数，在多服务台并行服务的系统中，某个时刻正在忙的服务台数目，以及服务机构的利用率（或称为服务强度）等。5.2.2排队论预备知识1.代价方程在排队论模型中，一些基本的令人感兴趣的量有：L——系统中顾客的平均数QL——系统中排队等待服务的顾客平均数W——顾客在系统中停留的平均时间QW——顾客在系统中排队等待的平均时间这几个量以及其它使人感兴趣的量的很多有用的关系可以由下面的思想获得：假定正在进入系统的顾客被迫支付费用(按某种规则)给系统。这样我们就有下面的基本代价方程：系统挣得费用平均速率＝a一个进入系统的顾客的平均花费（5-1）其中a定义为顾客的平均到达速率。即，若()Nt表示在t时间内到达的顾客数，则()limatNtt通过选取适当的花费规则，作为方程的特例，很多有用的公式都可以得到，比如，假设每个顾客在系统中单位时间内花费1元，由方程即得到所谓的Little’s公式：aLW（5-2）在该花费规则下，这个公式表明，系统挣得费用的速率就是系统中顾客数，顾客支付费用就是他在系统中的时间。类似地，若假设每个顾客在排队中单位时间花费1元，则（5-1）式变为：QaQLW（5-3）假定花费规则为每个顾客在服务时单位时间支付1元，则由（5-1）得到：受服务的顾客平均数＝a[]ES（5-4）其中[]ES定义为顾客被服务的平均时间。需要强调的是：（5-1）～（5-4）几乎对所有排队模型有效，而无论其到达过程、服务人员数或排队规律怎样。2.几个重要的概率分布1)定长分布（单点分布）定义5.1设随机变量X以概率1取常值a，即1PXa，则称X服从定长分布或单点分布。它的概率分布函数为0()1taFtPXtta，，（5-5）2)负指数分布定义5.2一个连续型随机变量X，若它的分布密度函数为0()00tetftt，，（5-6）其中(0)为常数，则称随机变数X服从参数的负指数分布，其概率分布函数为10()00tetFtt，，（5-7）可以求得其k阶原点矩为kkkEXk，方差为21[]DX。服从负指数分布的随机变量具有下面的基本性质——“无记忆性”或称“无后效性”。定理5.1设连续型随机变量X服从参数(0)的负指数分布，则(1)对任意00ts，，有{|}{}tPXtsXsPXte（5-8）(2)对任意一个与X相互独立的非负随机变量Y，和任意0t，在{}0PXY的条件下，有{|}{}tPXYtXYPXte（5-9）证明(1)由条件概率公式，有(){,}{|}{}{}{}tstsPXtsXsPXtsXsPXsPXtseePXse(2)由条件概率公式和全概率分解，有00{|}{|}{}{}ttPXYtXYPXytXydPYyedPYye3)k阶埃尔朗（Erlang）分布定义5.3如果连续型随机变量X的概率分布密度()ft为1(),0()(1)!0,0kttetftkt（5-10）则称X服从参数(0)的k阶埃尔朗分布，记为kE，其分布函数()Ft为10()()1,0!iktitFteti（5-11）期望平均值[],kEX方差2[]kDX。借用概率密度函数，用归纳法易证下面定理5.2：定理5.2设12kXXX，，是相互独立、服从相同参数(0)的负指数分布，则12kXXXX服从参数为的k阶埃尔朗分布。由定理5.2及中心极限定理，容易证明：定理5.3设随机变数X服从k阶埃尔朗分布，则对一切0x，有2221lim2txkkXPxedtk（5-12）注：当1k时，1E分布即为负指数分布；当k时，kE分布近似正态分布。4)超指数分布定义5.4若连续型随机变量X的概率密度函数为10()00iktiiietftt，，（5-13）其中0i，且11(0)kiii，均为常数(1,2,,ik),则称X服从超指数分布。其概率分布函数为1()10iktiiFtet，（5-14）它的期望平均值1[]kiiiEX，方差2211[]2kkiiiiiiDX。注：超指数分布是负指数分布的一种混合分布，其背景解释为：设有k个服务台独立地并行服务，第i个服务台提供的服务时间服从参数(0)i的负指数分布，到达的顾客以概率i选择第i个服务台接受服务（1,2,,ik），这样顾客的服务时间就是超指数分布。5)泊松（Poisson）分布定义5.5若离散型随机变量X的概率分布律为{}0,1,2,!nnpPXnenn，（5-15）其中(0)为常数，则称X服从参数的泊松（Poisson）分布，且[][]EXDX。5.2.3泊松过程（Poisson流）、马尔可夫链与生灭过程排队论的另一些基础性的重要描述就是泊松过程（Poisson流）、马尔可夫链与生灭程。1．泊松过程定义5.6考虑单个到达的输入过程，令()Nt表示在时间(0]t，内到达的顾客数，则{()0}Ntt，是连续时间参数的随机过程（计数过程）。如果满足：(1)(0)0N；(2){()0}Ntt，有独立增量，即对任取的n个时刻：120nttt，随机变量10()()NtNt、21()()NtNt。。。1()()nnNtNt是相互独立的；(3){()