第14章--排队论

管理运筹学1第十四章排队论§1排队过程的组成部分§2单服务台泊松到达、负指数服务时间的排队模型§3多服务台泊松到达、负指数服务时间的排队模型§4排队系统的经济分析§5单服务台泊松到达、任意服务时间的排队模型§6单服务台泊松到达、定长服务时间的排队模型§7多服务台泊松到达、任意的服务时间、损失制排队模型§8顾客来源有限制排队模型§9单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型§10多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型*§11生灭过程及生灭过程排队系统管理运筹学2一、基本概念•一些排队系统的例子排队系统顾客服务台服务电话系统电话呼叫电话总机接通呼叫或取消呼叫售票系统购票旅客售票窗口收款、售票设备维修出故障的设备修理工排除设备故障防空系统进入阵地的敌机高射炮瞄准、射击，敌机被击落或离开•排队的过程可表示为：排队服务机构服务服务后顾客离去排队系统顾客到达§1排队过程的组成部分管理运筹学3考虑要点：1、服务台（或通道）数目：单服务台（单通道）、多服务台（多通道）。2、顾客到达过程：本教材主要考虑顾客的泊松到达情况。满足以下四个条件的输入流称为泊松流（泊松过程）。*平稳性：在时间区间[t,t+t)内到达k个顾客的概率与t无关，只与t有关，记为pk(t）；*无后效性：不相交的时间区间内到达的顾客数互相独立；*普通性：在足够短的时间内到达多于一个顾客的概率可以忽略；*有限性：任意有限个区间内到达有限个顾客的概率等于1。泊松分布为单位时间平均到达的顾客数P(x)=xe-/x!(x=0,1,2,……)§1排队过程的组成部分管理运筹学4§1排队过程的组成部分3、服务时间分布：服从负指数分布，为平均服务率，即单位时间服务的顾客数，P（服务时间≤t)=1-e-t。4、排队规则分类(1)等待制：顾客到达后，一直等到服务完毕以后才离去，先到先服务，后到先服务，随机服务，有优先权的服务；(2)损失制：到达的顾客有一部分未接受服务就离去。5、平稳状态：业务活动与时间无关。管理运筹学5排队系统的符号表示:一个排队系统的特征可以用五个参数表示，形式为：A／B／C／D／E其中A––顾客到达的概率分布，可取M、D、G、Ek等；B––服务时间的概率分布，可取M、D、G、Ek等；C––服务台个数，取正整数；D––排队系统的最大容量，可取正整数或；E––顾客源的最大容量，可取正整数或。例如M/M/1//表示顾客到达过程服从泊松分布，服务时间服从负指数分布，一个服务台，排队的长度无限制和顾客的来源无限制。§1排队过程的组成部分管理运筹学6M/M/1/∞/∞单位时间顾客平均到达数，单位平均服务顾客数()数量指标公式:1.系统中无顾客的概率P0=1/2.平均排队的顾客数Lq=2/()3.系统中的平均顾客数Ls=Lq+/4.顾客花在排队上的平均等待时间Wq=Lq/5.顾客在系统中的平均逗留时间Ws=Wq+1/6.顾客得不到及时服务必须排队等待的概率Pw=/7.系统中恰好有n个顾客的概率Pn=(/)nP0§1排队过程的组成部分§2单服务台泊松到达、负指数服务时间的排队模型管理运筹学7§2单服务台泊松到达、负指数服务时间的排队模型在上面的公式中，我们都认定,即到达率小于服务率，如果没有这个条件，则排队的长度将无限制地增加，服务机构根本没有能力处理所有到达的顾客，也就是/1,我们称/为服务强度。例某储蓄所只有一个服务窗口。根据统计分析，顾客的到达过程服从泊松分布，平均每小时到达顾客36人；储蓄所的服务时间服从负指数分布，平均每小时能处理48位顾客的业务。试求这个排队系统的数量指标。解平均到达率=36/60=0.6，平均服务率=48/60=0.8。P0=1/=10.6/0.8=0.25,Lq=2/()=(0.6)2/0.8(0.80.6)=2.25(个顾客),管理运筹学8Ls=Lq+/=2.25+0.6/0.8=3(个顾客),Wq=Lq/=2.25/0.6=3.75（分钟）,Ws=Wq+1/=3.75+1/0.8=5（分钟）,Pw=/=0.6/0.8=0.75,Pn=(/)nP0=(0.75)n×0.25,n=1,2,…。通过计算，可知储蓄所的排队系统里有n个顾客的概率，见表14-1。§2单服务台泊松到达、负指数服务时间的排队模型系统里的顾客数概率系统里的顾客数概率00.250040.079110.187550.059320.140660.044530.105570.1335表14-1管理运筹学9§2单服务台泊松到达、负指数服务时间的排队模型通过计算数据与表中数据，可知储蓄所的排队系统并不尽如人意，到达储蓄所有75%的概率要排队等待，排队的长度平均为2.25个人，排队的平均时间为3.75分钟，是1.25分钟的3倍，而且储蓄所里有7个或更多的顾客的概率为13.35%，这个概率太高了。而要提高服务水平，减少顾客的平均排队时间和平均服务时间，一般可采用两种措施：第一，减少服务时间，提高服务率；第二，增加服务台即增加服务窗口。如采取第一种方法，不增加服务窗口，而增加新型点钞机，建立储户管理信息系统，可以缩短储蓄所每笔业务的服务时间，使每小时平均服务的顾客数目从原来的48人提高到60人，即每分钟平均服务的顾客数从0.8人提高到1人，这时仍然为0.6，为1，通过计算得到的结果如表14-2所示：管理运筹学10§2单服务台泊松到达、负指数服务时间的排队模型系统里没有顾客的概率0.4平均排队的顾客人数0.9人系统里的平均顾客数1.5人一位顾客平均排队时间1.5分钟一位顾客平均逗留时间2.5分钟顾客到达系统必须等待排队的概率0.6系统里有7个或更多顾客的概率为0.027从上表我们可以看出由于把服务率从0.8提高到1，其排队系统有了很大的改进，顾客平均排队时间由3.75分钟减少到1.5分钟，顾客平均逗留时间从5分钟减少到2.5分钟，在系统里有7个或更多顾客的概率有大幅度的下降，从13.35%下降到2.79%。如果采用第二种方法，再设一个服务窗口，排队的规则为每个窗口排一个队，先到先服务，并假设顾客一旦排了一个队，就不能再换到另一个队上去（譬如，当把这个服务台设在另一个地点，上述假设就成立了）。这种处理方法就是把顾客分流，把一个排队系统分成两个排队系表14-2管理运筹学11§2单服务台泊松到达、负指数服务时间的排队模型统，每个排队系统中有一个服务台，每个系统的服务率仍然为0.8，但到达率由于分流，只有原来的一半了，=0.3，这时我们可求得每一个排队系统的数量指标如表14-3所示：系统里没有顾客的概率0.6250平均排队的顾客人数0.2250人系统里的平均顾客数0.6人一位顾客平均排队时间0.75分钟一位顾客平均逗留时间2.000分钟顾客到达系统必须等待排队的概率0.375系统里有7个或更多顾客的概率为0.0074表14-3我们比较表14-1和14-3，知道采用第二个方法的服务水平也使得原来的服务水平有了很大的提高，采用第二种方法顾客平均排队时间减少到了0.75分钟，顾客平均逗留时间减少到了2分钟，第二种排队系统为两个M/M/1排队系统。如果在第二种方法中把排队的规则变一下，在储蓄所里只排一个队，这样的排队系统就变成了M/M/2排队系统。管理运筹学12M/M/C/∞/∞单位时间顾客平均到达数，单位平均服务顾客数。1.系统中无顾客的概率2.平均排队的顾客数3.系统中的平均顾客数Ls=Lq+/,4.顾客花在排队上的平均等待时间Wq=Lq/,)(!)/(!)/(1100cccnpccnn02)()!1()/(PccLcq§3多服务台泊松到达、负指数服务时间的排队模型管理运筹学135.顾客在系统中的平均逗留时间Ws=Wq+1/,6.系统中顾客必须排队等待的概率7.系统中恰好有n个顾客的概率0)()(!1pcccpcw0!)/(pnpnn当n≤c时0)(!)/(pccpcnnn当nc时§3多服务台泊松到达、负指数服务时间的排队模型管理运筹学14例在前例的储蓄所里多设一个服务窗口，即储蓄所开设两个服务窗口。顾客的到达过程仍服从泊松分布，平均每小时到达顾客仍是36人；储蓄所的服务时间仍服从负指数分布，平均每小时仍能处理48位顾客的业务，其排队规则为只排一个队，先到先服务。试求这个排队系统的数量指标。解C=2，平均到达率=36/60=0.6，平均服务率=48/60=0.8。P0=0.4545,Lq=0.1227(个顾客),Ls=Lq+/=0.8727(个顾客),Wq=Lq/=0.2045（分钟）,Ws=Wq+1/=1.4545（分钟）,Pw=0.2045,P1=0.3409,P2=0.1278,P3=0.0479,P4=0.0180,P5=0.0067。系统里有6个人的概率或多于6个人的概率为0.0040。§3多服务台泊松到达、负指数服务时间的排队模型管理运筹学15在储蓄所里使用M/M/2模型与使用两个M/M/1模型，它们的服务台数都是2，服务率和顾客到达率都一样，只是在M/M/2中只排一队，在2个M/M/1中排两个队，结果却不一样。M/M/2使得服务水平有了很大的提高，每个顾客的平均排队时间从0.75分钟减少到0.2045分钟，每个顾客在系统里逗留时间从2分钟减少到1.4545分钟，平均排队的人数也从0.2250人减少到0.1227人，系统里平均顾客数也从0.6*2=1.2人减少到0.8727人。如果把M/M/2与原先一个M/M/1比较，那么服务水平之间的差别就更大了。当然在多服务台的M/M/C模型中，计算求得这些数量指标是很繁琐的。管理运筹学软件有排队论的程序，可以由它来计算。我们在第二节与第三节发现公式有三个公式是完全相同的，实际上这三个公式表示了任一个排队模型（不仅仅是M/M/1或M/M/2）中，Ls,Lq,Ws,Wq之间的关系，也就是说：§3多服务台泊松到达、负指数服务时间的排队模型管理运筹学16,(14.5),(14.6)1,(14.7)sqqqsqLLL§3多服务台泊松到达、负指数服务时间的排队模型对任一个排队模型成立，这里Ls,Lq,Ws,μ的定义如上所述，而应为实际进入系统平均到达率，对于排队长度有限制的模型，我们设因排队长度的限制顾客被拒绝的概率为PN，则实际进入系统平均到达率应为这时，原来公式中的应改为。1NP1NP管理运筹学17我们把一个排队系统的单位时间的总费用TC定义为服务机构的单位时间的费用和顾客在排队系统中逗留单位时间的费用之和。即TC=cwLs+csc其中cw为一个顾客在排队系统中逗留单位时间付出的费用；Ls为在排队系统中的平均顾客数；cs为每个服务台单位时间的费用；c为服务台的数目。例在前两例中，设储蓄所的每个服务台的费用cs=18，顾客在储蓄所中逗留一小时的成本cw=10。这样，对储蓄所M/M/1模型可知Ls=3，c=1，得TC=cwLs+csc=48元/每小时。对储蓄所M/M/2模型可知Ls=0.8727，c=2，得TC=cwLs+csc=44.73元/每小时。§4排队系统的经济分析管理运筹学18M/G/1/∞/∞单位时间顾客平均到达数，单位平均服务顾客数，一个顾客的平均服务时间1/，服务时间的均方差。数量指标公式:1.系统中无顾客的概率P0=1/2.平均排队的顾客数3.系统中的平均顾客数Ls=Lq+/4.顾客花在排队上的平均等待时间Wq=Lq/5.在系统中顾客的平均逗留时间Ws=Wq+1/6.系统中顾客必须排队等待的概率Pw=/7.系统中恰好有n个顾客的概率Pn)/1(2)/(222qL§5单服务台泊松到达、任意服务时间的排队模型管理运筹学19例1某杂货店只有一名售货员，已知顾客的到达过程服从泊松分布，平均到达率为每小时2