排队论模型.docx

《排队论模型.docx》由会员分享，可在线阅读，更多相关《排队论模型.docx（15页珍藏版）》请在三一办公上搜索。

1、排队论模型排队论模型 排队论也称随机服务系统理论。它涉及的是建立一些数学模型，藉以对随机发生的需求提供服务的系统预测其行为。现实世界中排队的现象比比皆是，如到商店购货、轮船进港、病人就诊、机器等待修理等等。排队的内容虽然不同，但有如下共同特征： 有请求服务的人或物，如候诊的病人、请求着陆的飞机等，我们将此称为“顾客”。 有为顾客提供服务的人或物，如医生、飞机跑道等，我们称此为“服务员”。由顾客和服务员就组成服务系统。 顾客随机地一个一个来到服务系统，每位顾客需要服务的时间不一定是确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时候服务员又空闲无事。 排队论主要是对服务系统建立数学模型

2、，研究诸如单位时间内服务系统能够服务的顾客的平均数、顾客平均的排队时间、排队顾客的平均数等数量规律。 一、 排队论的一些基本概念 为了叙述一个给定的排队系统，必须规定系统的下列组成部分： 输入过程 即顾客来到服务台的概率分布。排队问题首先要根据原始资料，由顾客到达的规律、作出经验分布，然后按照统计学的方法确定服从哪种理论分布，并估计它的参数值。我们主要讨论顾客来到服务台的概率分布服从泊松分布，且顾客的达到是相互独立的、平稳的输入过程。所谓“平稳”是指分布的期望值和方差参数都不受时间的影响。 排队规则 即顾客排队和等待的规则，排队规则一般有即时制和等待制两种。所谓即时制就是服务台被占用时顾客便随

3、即离去；等待制就是服务台被占用时，顾客便排队等候服务。等待制服务的次序规则有先到先服务、随机服务、有优先权的先服务等，我们主要讨论先到先服务的系统。 服务机构 服务机构可以是没有服务员的，也可以是一个或多个服务员的；可以对单独顾客进行服务，也可以对成批顾客进行服务。和输入过程一样，多数的服务时间都是随机的，且我们总是假定服务时间的分布是平稳的。若以n表示服务员为第n个顾客提供服务所需的时间，则服务时间所构成的序列n，n=1，2，所服从的概率分布表达了排队系统的服务机制，一般假定，相继的服务时间1，2，是独立同分布的，并且任意两个顾客到来的时间间隔序列Tn也是独立的。 如果按服务系统的以上三个特

4、征的各种可能情形来对服务系统进行分类，那么分类就太多了。因此，现在已被广泛采用的是按顾客相继到达时间间隔的分布、服务时间的分布和服务台的个数进行分类。 研究排队问题的目的，是研究排队系统的运行效率，估计服务质量，确定系统参数的最优值，以决定系统的结构是否合理，设计改进措施等。所以，必须确定用来判断系统运行优劣的基本数量指标，这些数量指标通常是： 队长 指排队系统中的顾客数，它的期望值记为L系；排队长，指在排队系统中排队等待服务的顾客数，其期望值记为L队。 系统中的顾客数 = 等待服务的顾客数 + 正被服务的顾客数 所以L队越大，说明服务效率越低。 逗留时间 指一个顾客在排队系统中的停留时间，即

5、顾客从进入服务系统到服务完毕的整个时间。其期望值记为W系。等待时间，指一个顾客在排队系统中等待服务的时间，其期望值记为W队。 逗留时间 = 等待时间 + 服务时间 忙期 指从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度，即服务机构连续工作的时间长度。它关系到服务员的工作长度，即服务机构连续工作的时间长度。它关系到服务员的工作强度、忙期的长度和一个忙期中平均完成服务的顾客数，这些都是衡量服务效率的指标。 要计算以上这些指标必须知道系统状态的概率，所谓系统状态即时刻t时排队系统中的顾客数。如果时刻t时排队系统中有n个顾客，就说系统的状态是n，其概率一般用Pn(t)表示。求Pn(t)的方法

6、，首先要建立含Pn(t)关系式，因t为连续变量而n只取非负整数，所以建立的Pn(t)的关系式一般是微分差分方程，这时要求方程的解是不容易的，有时即使求出也很难利用。因此，往往只求稳态解Pn，求Pn并不一定求t时的Pn(t)极限，而只需由Pn(t)=0，用Pn代替Pn(t)即可。 下面分析几个排队系统。 二、 单通道等待制排队问题 对于单通道等待制排队问题主要讨论输入过程服从泊松分布，服务时间服从负指数分布，单服务台的情形。分两种模型来分析： 标准模型 所谓标准模型是指顾客源为无限，顾客单个到来，相互独立，一定时间的到达数服从泊松分布，到达过程是平稳的，排队为单队，队长没有限制，先到先服务，各顾

7、客的服务时间服从负指数分布，且相互独立。同时还假定顾客到达的时间间隔和服务时间是相互对立的。可以证明，顾客相继到达的时间间隔独立且为负指数分布的充要条件是输入过程服从泊松分布。 首先求出排队系统在任意时刻t的、状态为n的概率Pn(t)，不妨假设顾客到达规律服从参数为的泊松分布，服务时间服从参数为的负指数，由此决定了t，t+t时间间隔内： 1、有1个顾客到达的概率为t+o(t)，没有顾客到达的概率是1-t+o(t)。 2、当有顾客在接受服务时，1个顾客被服务完了的概率是t+o(t)，没有服务完的概率是1-t+o(t)。 3、多于一个顾客到达或服务完的概率为o(t)，均可忽略。 注1：因为单位时间

8、内顾客到达数XP，所以t时间间隔内顾客到达数Y P，因而在t时间间隔内有一个顾客到达的概率为：P Y=1 -t-t=te=t + o(t)，没有顾客到达的概率为PY=0= e=1-t + o(t)。 注2：由于服务时间TE，故在有顾客接受服务时，一个顾客被服务完的概率为PTt =1 - e-t=t + o(t)，没有被服务完的概率为1 -t + o(t)。 在t+t时刻，系统中有n个顾客的状态由t时刻的以下状态转化而来：t时刻系统中有n个顾客，没有顾客到达且没有顾客服务完毕，其概率为：1-t+o(t) 1-t+o(t)= (1-t-t)+o(t)；t时刻系统中有n+1个顾客，没有顾客到达且有一

9、个顾客服务完毕，其概率为：1-t+o(t)t+o(t)= t+o(t)；t时刻系统中有n-1个顾客，有一个顾客到达且没有顾客服务完毕，其概率为：t+o(t)1-t+o(t)= t+o(t)；其他状态的概率为o(t)。 因此，在t+t时刻，系统中有n个顾客的概率Pn(t+t)满足： Pn(t+t)= Pn(t)(1-t-t)+ Pn+1(t)t + Pn-1(t)t+o(t) Pn(t+t)- Pn(t)/t=Pn-1(t)+Pn+1(t)-(+)Pn(t)+o(t)/t 令t0，得到 dPn(t)=lPn-1(t)+mPn+1(t)-(l+m)Pn(t)dtn=1,2L n=0时，因为 P0(

10、t+t)= P0(t)(1-t)+ P1(t)(1-t) t+o(t) 所以，有 dP0(t)=-lP0(t)+mP1(t) dt对于稳态情形，与t无关，其导数为零。因此，得到差分方程 lP+mPn+1-(l+m)Pn=0,n1 n-1 -lP0+mP1=0求解此差分方程 Pn=(/)nP0 由概率的性质知Pn=0n=1，将上式代入/1时可得到 P0=1-/ Pn=(1-/)( /)n 因为顾客到达规律服从参数为的泊松分布，服务时间服从参数为的负指数分布，其期望值就分别为，1/。所以表示单位时间内平均到达的顾客数，表示单位时间内能服务完的顾客数。如果令=/，这时就表示相同区间内顾客到达的平均数

11、与能被服务的平均数之比，它是刻画服务效率和服务机构利用程度的重要标志，称为服务强度。上面在1，可以证明排队长度将是无限增加的，即使=1的情况下，P0(t)也是随时间而变化的，系统达不到稳定状态。因此，这里只讨论1时情况，从上面的推导知 Pn=(1-) n n=0,1,2, 下面计算出系统的运行指标 L系=npn=n(1-r)rn=r/(1-r)n=0n=1=l/(m-l)L队=(n-1)pn=(n-1)rn(1-r)n=1n=1=r2/(1-r)=rl/(m-l)可以证明，顾客在系统中逗留时间服从参数为的负指数分布。因此，有 W系=1/(-) W队=W系-1m=r/(m-l) 由以上结论可以看

12、出，各指标之间有如下关系： L系=W系； L队=W队 W系=W队+1/, L系=L队+/ 在指标的计算过程中，一般只要计算其中一个，其它的指标便可随之导出。 例1 病人候诊问题 某单位医院的一个科室有一位医生值班，经长期观察，每小时平均有4个病人，医生每小时平均可诊5个病人，病人的到来服从泊松分布，医生的诊病时间服从负指数分布。试分析该科室的工作状况。如果满足99%以上的病人有座，此科室至少应设多少个座位？如果该单位每天24h上班，病人看病1h因耽误工作单位要损失30元，这样单位平均每天损失多少元？如果该科室提高看病速度，每小时平均可诊6个病人，单位每天可减少损失多多少？可减少多少个座位？ 解

13、 由题意知=4，=5，=4/5，=4/5=0.81，从而排队系统的稳态概率为： Pn=0.20.8n n=0，1，2 该科室平均有病人数为： L系=/=0.8/=4 该科室内排队候诊病人的平均数为： L队=L系-/=4-0.8=3.2 看一次病平均所需的时间为： W系=L系/=4/4=1h 排队等候看病的平均时间为： W队=W系-1/=1-1/5=0.8h 为满足99%以上的病人有座，设科室应设m个座位，则m应满足： P医务室病人数m0.99 rn(1-r)=1-rm+10.99 n=0mrm+10.01 ln0.01m-1=20lnr所以该科室至少应设20个座位。 如果该单位24h上班，则每

14、天平均有病人244=96人，病人看病所花去的总时间为961=96 h。因看病平均每天损失3096=2880元。 如果医生每小时可诊6个病人，=2/3，则 L系=2，L队=4/3 W系=0.5h，W队=1/3h 这样单位每天的损失费为960.530=1440元，因而单位每天平均可减少损失2880-1440=1440元，这时为保证99%以上的病人有座，应设座位数mln0.01/ln(2/3)-1=11个，比原来减少了9个。 下面举一个与决策有关的排队问题。 例2 修理工录用问题 某工厂平均每天有一台机器发生故障而需要修理，机器的故障数服从泊松分布。修理一台机器平均花费20元。现有技术水平不同的修理

15、工人A和B，A种修理工平均每天能修理1.2台机器，每天工资3元；B种修理工平均每天能修理1.5台机器，每天工资5元，两种修理工修理机器的时间为负指数分布。问工厂录用哪种工人较合算？ 解 用N 表示每天发生故障机器的平均数，包括正在修理和等待修理的机器数，即等于排队L系，C1和C2分别表示修理一台机器的费用和工人的工资，则工厂每天平均损失费用为： R=NC1+NC2 若录用A种修理工，据题意知=1，A=0.2，A=/A=5/6，L系A=A/(1-A)=5台，则若录用A种修理工，工厂每天平均损失费用为： RA=520+3=103元 若录用B种修理工，据题意知=1，B=1.5，b=2/3，L系B=2

16、台，则若录用B种修理工，工厂每天平均损失费用为： RB=220+3=43元 比较可知，工厂录用B种修理工较为合算。如果计入机器停工损失费用，这一选择更为上算。 系统容量有限的模型 因为是单服务台，设排队系统的容量为N，即是排队等待的顾客最多为N-1，在某时刻一顾客到达时，如系统中已有N个顾客，那么这个顾客就被拒绝进入系统。在研究系统中有n个顾客的概率Pn(t)时，和标准模型研究方法相同，当n=N时有 PN(t)=lPN-1(t)-mPN(t) 在稳态情形下，并令r=l，得 mP1=rP0 Pn+1+rPn-1=(1+r)Pn,n=1,2,L,N-1 P=rPN-1N在条件Pi=1下解上式得到

17、i=0N1P=PL=P=,r=101NN+1 1-rPn=rnnN,r1N+11-r这里，不假设1，下面给出系统的各种指标的计算结果： L系=nPn=n=0n=0NNnN=,r=1 N+12n(1-r)rnL系=npn=N+1n=1n=01-rNN=Nr1-r-(N+1)r1-rN+1N+1,r1 L队=(n-1)Pn= L系-(1-P0) n=1NN-,r=12N+1= N+1rNr-r-,r1N+11-r1-r W系= L系/(1-P0) W队= W系 -1m应该指出，W系，W队的导出过程中不是采用平均达到率，而是采用有效到达率效。这主要是由于当系统已满时，顾客的实际到达率为零，因为正在被

18、服务的顾客的平均数为1-P0=效/，于是效=。 例3 单人理发馆有6个椅子，当6个椅子都坐满时，后来到的顾客不进店就离开。顾客平均到达率为3人/h，理发平均需15min，试分析该服务系统。 解 由题意知N=7，=3人/h，=4人/h，因此，某顾客一到达就能理发的概率为： P0=8）=0.2778 平均需要等待的顾客数量为： 3/48(3/4)8 L系 =-=2.11人 81-(3/4)1-(3/4) L队= L系-(1-P0) =2.11-(1-0.2778)=1.39人 有效到达率为： 效=4=2.89人/h 顾客在理发馆平均逗留时间为： 2.11=0.73h=43.8min W系= L系/

19、效=1.89 多通道等待制排队问题 多通道就是服务台。对于这种排队问题只讨论标准模型，其特征与单通道标准模型特征完全相同。假定有m个服务台，每个服务台相互独立工作，平均服务个数相同，则整个服务机构的平均服务率为m，显然只有当/m1时才不会排成无限长的队列，下面不加证明的给出稳定状态概率Pn和系统指标。 令r=l，则 mmm-1k1l11lm-1 P0=+ m!1-rmk=0k!m1lnnmn!(m)P0 Pn=1(l)nP,nfm0n-mmm!m(mr)mrL系= L队+m, L队=P 20m!(1-r) W队= L队/, W系= W队+1m=L系/ 例4 某火车站售票处有三个窗口，顾客的到达

20、服从泊松分布，平均每分钟有0.9人到达，服务时间服从负指数分布，平均每分钟可服务0.4人。现假设排成一队，依次向空闲的窗口购票，试分析该排队系统。 解 据题意知m=3，=0.9，=0.4,则 r=l0.9=0.75 m30.40.910.9210.931+-1 0.42!0.43!0.41-0.75 =0.0743 即整个售票处空闲的概率为0.0743。 平均队长： P0=1+(0.9/0.4)33/4 L队=0.0743=1.7 3!(1/4)2 平均等待时间： W队=1.7/0.9=1.89min 平均逗留时间： W系=1.89+1/0.4=4.39min 总之，排队论是具有特殊实用价值的现代应用数学分支之一，其内容十分丰富，像单通道顾客数有限，多通道容量有限，多通道顾客数目有限等情形这里未予介绍，有兴趣的读者可参阅有关资料。