运筹学排队论1

《运筹学排队论1》由会员分享，可在线阅读，更多相关《运筹学排队论1（37页珍藏版）》请在金锄头文库上搜索。

1、,第十章 排队论,引 言 排队论是研究排队系统（又称随机服务系统）的数学理论和方法，是运筹学的一个重要分支。 有形排队现象：进餐馆就餐，到图书馆借书，车站等车，去医院看病，售票处售票，到工具房领物品等现象。 无形排队现象：如几个旅客同时打电话订车票；如果有一人正在通话，其他人只得在各自的电话机前等待，他们分散在不同的地方，形成一个无形的队列在等待通电话。 排队的不一定是人，也可以是物。如生产线上的原材料，半成品等待加工；因故障而停止运行的机器设备在等待修理；码头上的船只等待装货或卸货；要下降的飞机因跑道不空而在空中盘旋等。,当然，进行服务的也不一定是人，可以是跑道，自动售货机，公共汽车等。顾客

2、可以走向服务机构，也可以相反（如送货上门）。 顾客要求服务的对象。 服务员提供服务的服务者（也称服务机构）。 顾客、服务员的含义是广义的。 如果增添服务设备，就要增加投资或发生空闲浪费 ；如果 服务设备太少，排队现象就会严重，对顾客个人和对社会都会带来不利影响。因此，管理人员必须考虑如何在这两者之间取得平衡，经常检查目前处理是否得当，研究今后改进对策，以期提高 服务质量，降低成本。,2、排队系统类型：,单服务台排队系统,S个服务台，一个队列的排队系统,S个服务台， S个队列的排队系统,多服务台串联排队系统,随机聚散服务系统,随机性顾客到达情况与顾客接受服务的时间是随机的。 一般来说，排队论所研

3、究的排队系统中，顾客相继到达时间间隔和服务时间这两个量中至少有一个是随机的，因此，排队论又称随机服务理论。,3、排队系统的组成和特征 实际中的排队系统各不相同，但概括起来都由三个基本部分组成：输入过程，排队规则和服务机构。 输入过程即顾客到达排队系统。 顾客总体（顾客源）数：可能是有限，也可能是无限。河流上游流入水库的水量可认为是无限的；车间内停机待修的机器显然是有限的。 到达方式：是单个到达还是成批到达。库存问题中，若把进来的货看成顾客，则为成批到达的例子。,顾客（单个或成批）相继到达的时间间隔，可以是确定型的，也可以是随机型的。这是刻划输入过程的最重要内容。令T0=0，Tn表示第n顾客到达

4、的时刻，则有T0T1 T2 Tn 记Xn= Tn Tn-1 n=1,2,则Xn是第n顾客与第n-1顾客到达的时间间隔。对于随机型的，要知道其分布：一般假定Xn是独立（非关联）同分布，并记分布函数为A(t)。 Xn的分布A(t)常见的有： 定常分布（D）：顾客相继到达的时间间隔为确定的。如产品通过传送带进入包装箱就是定常分布。 最简流（或称Poisson)（M）：顾客相继到达的时间间隔Xn为独立的，同为负指数分布，其密度函数为：,a(t)=,e- t t0,0 t 0,排队规则 排队 有限排队排队系统中顾客数是有限的。有限排队还可以分成： 损失制排队系统：排队空间为零的系统，即不允许排队。（顾客

5、到达时，服务台占满，顾客自动离开，不再回来）（电话系统） 混合制排队系统：是等待制与损失制结合，即允许排队，但不允许队列无限长。,混合制排队系统： 队长有限。即系统等待空间是有限的。例：最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数（又称为队长）小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。等待时间有限。即顾客在系统中等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离开，不再回来。如易损失的电子元件的库存问题，超过一定存储时间的元器件被自动认为失效。 逗留时间（等待时间与服务时间之和）有限。例：用高射炮

6、射击飞机，当敌机飞越射击有效区域的时间为t时，若这个时间内未被击落，也就不可能再被击落了。,损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台个数，则当k=s时，混合制即为损失制；当k=时，即成为等待制。 无限排队顾客数是无限，队列可以排到无限长（等待制排队系统）。 当顾客到达时，若所有服务台都被占有且又允许排队，则该顾客将进入队列等待。服务台对顾客进行服务所遵循的规则通常有： 先来先服务（FCFS） 后来先服务（LCFS）。在许多库存系统中就会出现这种情况，如钢板存入仓库后，需要时总是从最上面取出；又如在情报系统中，后来到达的信息往往更重要，首先要加以分析和利用。,具有优先权的服务

7、（PS）。服务台根据顾客的优先权的不同进行服务。如病危的病人应优先治疗；重要的信息应优先处理；出价高的顾客应优先考虑。 随机服务，指服务员从等待的顾客中随机地选取其一进行服务，而不管到达的先后。如电话交换台接通呼唤的电话就是如此。 从占有空间来看，队列可以排在具体的处所，也可以是抽象的；有的系统要规定容量的，有的容量没有限制。 从队列的数目来看，可以是单列的，也可以是多列的；在多列的情形中，各列的顾客有的是可以互相转移的，有的不能互相转移；有的可以中途退出，有的必须坚持到被服务为止。,服务机制：包括：服务员的数量及其连接方式（串联还是并联）；顾客是单个还是成批接受服务；服务时间的分布。记某服务

8、台的服务时间为V，其分布函数为B(t),密度函数为b(t),则常见的分布有： 定长分布（D）：每个顾客接受的服务时间是一个确定的常数。 负指数分布（M）：每个顾客接受的服务时间相互独立，具有相同的负指数分布： 其中0为一常数。,b(t)=,e- t t0,0 t0,K阶爱尔朗分布（Ek）：,b(t)=,k(kt)k-1 (K-1)!,= e- kt,当k=1时即为负指数分布；k 30,近似于正态分布。当 k 时，方差 0 即为完全非随机的。 排队系统的符号表示： “Kendall”记号：X / Y/ Z / A/B/C 其中：X表示顾客相继到达的分布； Y表示服务时间的分布； Z表示服务台个数

9、； A表示系统的容量，即可容纳的最多顾客数。 B表示顾客客源数目。 C表示服务规则。,例 13-1 M /M/ 1 / / M表示顾客相继到达的时间间隔服从负指数分布； M表示服务时间为负指数分布；单个服务台；系统容量为无限（等待制）的排队模型 。 例 13-2 M /M/ S / K/ 表示顾客到达的时间间隔服从负指数分布； 服务时间为负指数分布；S个服务台；系统容量为K的排队模型 。 当 K= S 时为损失制排队模型； 当 K= 时为等待制排队模型。,3、排队系统的主要数量指标： 系统状态：也称为队长，指排队系统中的顾客数（排队等待的顾客数与正在接受服务的顾客数之和）。它的期望值记作LS。

10、 排队长：系统中正在排队等待服务的顾客数。它的期望值记作Lq 系统中顾客数=在队列中等待服务的顾客数+正被服务的顾客数 逗留时间：指一个顾客在系统中停留的时间，它的期望值记作Ws。 等待时间：指一个顾客在系统中排队等待的时间，它的期望值记作Wq。 逗留时间=等待时间 +服务时间,4、排队论研究的基本问题： 通过研究主要数量指标在瞬时或平稳状态下的概率分布及数字特征，了解系统运行的基本特征。 统计推断问题：建立适当的排队模型是排队论研究的第一步，建立模型过程中，系统是否达到平稳状态的检验；顾客相继到达时间间隔相互独立性的检验，服务时间的分布及有关参数的确定等。 系统优化问题：又称为系统控制问题或

11、系统运营问题，其基本目的是使系统处于最优的或最合理的状态。包括：最优设计问题和最优运营问题。,5、M/M/1/排队模型 标准的M/M/1/模型是指适合下列条件的排队系统： 输入过程顾客源是无限的，顾客单个到来，相互独立，一定时间的到达数服从泊松分布，到达过程已是平衡的。 排队规则单队，且对 队长没有限制，先到先服务。 服务机构单服务台，各顾客的服务时间是相互独立的，服从相同的负指数分布。 此外，还假定到达间隔时间和服务时间是相互独立的。,例13-3：考虑一个铁路列车编组站。设待编列车到达时间间隔服从负指数分布，平均每小时到达2列；服务台是编组站，编组时间服从负指数分布，平均每20分钟可编一组。

12、已知编组站上共有2股道，当均被占用时，不能接车，再来的列车只能停在站外或前方站。求在平衡状态下系统中列车的平均数；每一列车的平均逗留时间；等待编组的列车平均数。如果列车因站中2股道均被占用而停在站外或前方站时，每列车每小时费用为a元，求每天由于列车在站外等待而造成的损失。,解：本例可看成一个M/M/1/排队问题。 其中 =2， =3，=/=2/31 系统中列车的平均数 Ls= / (1-)=(2/3)/(1-2/3)=2（列） 列车在系统中的平均停留时间 Ws=Ls/= 2/2=1（小时） 系统中等待编组的列车平均数 Lq=Ls-= 2-2/3=4/3（列）,列车在系统中的平均等待编组时间 W

13、q = Lq/ =(4/3)/(1/2)=2/3（小时） 每列车平均延误（由于站内2股道均被占用而不能进站）时间为W0 则W0 = WPN2=W1-P0-P1-P2 =W1-(l-)- (l-) 1 -(l-) 2 =1* 3= 3=(2/3)3=0.296（小时） 故每天列车由于等待而支出的平均费用E=24W0a=24*2*0.296*a=14.2a元,例13-4：某修理店只有一位修理工，来修理的顾客到达过程为Poisson流，平均每小时4人；修理时间服从负指数分布，平均需要6分钟。试求：修理店空闲的概率；店内恰有3位顾客的概率；店内至少有一位顾客的概率；在店内平均顾客数；每位在店内平均逗留

14、时间；等待服务的平均顾客数；每位顾客平均等待服务时间。,解：本例可看成一个M/M/1/ /排队问题. 其中 =4， =1/0.1=10(人/小时）， = /=2/51 修理店内空闲的概率 P0= 1-= (1-2/5)=0.6 店内恰有3个顾客的概率 P3= 3(1-)=(2/5)3(1-2/5)=0.038 店内至少有1位顾客的概率 P N1=1-P0=1- (1-)= =2/5=0.4,在店内平均顾客数 L= / (1-)=(2/5)/(1-2/5)= 0.67(人） 每位顾客在店内平均逗留时间 W=L/=0.67/4=10分钟 等待服务的平均顾客数 Lq=L-=0.67-2/5=0.27

15、(人) 每个顾客平均等待服务时间 Wq = Lq/ =0.27/4=0.0675小时 =4分钟,6、M/M/1/N/ /排队模型 如果系统的最大容量为N，对于单服务台的情形，排队等待的顾客最多为N-1，在某时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被的拒绝进入系统。,7、 M/M/1/M 等待制排队模型,8、 M/M/C/ 排队模型,7、 M/M/1/M 等待制排队模型 多服务台问题，又表示为M/M/S/ ：顾客相继到达时间服从参数为的负指数分布；服务台数为S；每个服务台的服务时间相互独立，且服从参数为的负指数分布。当顾客到达时，若有空闲服务台马上被进行服务，否则便排成一队列等待，等待空间为无限。,队长的分布 记Pn=pN=n,n=0,1,2.为系统达到平衡状态后队长N的概率分布，对多服务台有 n=； n=0,1,2. n= n n=0,1,2.s n= s n=s,s+1,s+2.,s= /s= /s, 当s1时，有,Cn=,(/)n n!,(/)s s!,(/s)n-s=,(/)n s!sn-s,n=1,2,s,ns,pn=,(p)n n!,n=1,2,s,n s!sn-s,n s,p0,p0,其中： p0=0s-1pn/n!+ s/s!(1- s)-1 当n s时，顾客必