算法大全第06章排队论

1、第六章排队论模型排队论起源丁1909年丹麦电话工程师AK.爱尔朗的工作，他对电话通话拥挤问题进行了研究。1917年，爱尔朗发表了他的著名的文章一“自动电话交换中的概率理论的几个问题的解决”。排队论已广泛应用丁解决军事、运输、维修、生产.服务.库存、医疗卫生、教育.水利灌溉之类的排队系统的问题，显示了强人的生命力。排队是在口常生活中经常遇到的现彖，如顾客到商店购买物品、病人到医院看病常常要排队。此时要求服务的数危超过服务机构(服务台、服务员等)的容鼠。也就是说,到达的顾客不能立即得到服务，因而出现了排队现彖。这种现彖不仅在个人口常生活中出现，电话局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器的停机待修，水库的存贮调节等都是有形或无形的排队现彖。由顾客到达和服务时间的随机性。可以说排队现彖儿乎是不可避免的。排队论(QueuingTheory)也称随机服务系统理论，就是为解决上述问题而发展的一门学科。它研究的内容有下列三部分：(i) 性态问题，即研究各种排队系统的概率规律性，主要是研究队长分布.等待时间分布和忙期分布等，包括了瞬态和稳态两种情形。(ii) 最优化问题，又分静态最

2、优和动态最优，前者指最优设计。后者指现有排队系统的最优运营。(iii) 排队系统的统计推断，即判断一个给定的排队系统符合丁哪种模型，以便根据排队理论进行分析研究。这里将介绍排队论的一些基本知识，分析儿个常见的排队模型。1基本概念1.1排队过程的一般表示卜图是排队论的一般模型。图1井队模型图中虚线所包含的部分为排队系统。各个顾客从顾客源出发，随机地來到服务机构，按一定的排队规则等待服务，直到按一定的服务规则接受完服务后离开排队系统。凡要求服务的对彖统称为顾客，为顾客服务的人或物称为服务员，由顾客和服务员组成服务系统。対J：一个服务系统來说，如果服务机构过小，以致不能满足要求服务的众多顾客的需耍，那么就会产生拥挤现彖而使服务质杲降低。因此，顾客总希望服务机构越人越好，但是，如果服务机构过人，人力和物力方而的开支也就相应增加，从U会造成浪费，因此研究排队模型的目的就是要在顾客需要和服务机构的规模Z间进行权衡决策，使其达到合理的平衡。1.2排队系统的组成和特征一般的排队过程都由输入过程、排队规则、服务过程三部分组成，现分述如卜I1.2.1输入过程输入过程是指顾客到來时间的规律性，可能有下列不同

3、情况：(i) 顾客的组成可能是有限的，也可能是无限的。(ii) 顾客到达的方式可能是一个一个的，也可能是成批的。(iii) 顾客到达可以是相互独立的，即以前的到达情况对以后的到达没有影响；否则是相关的。(込)输入过程可以是平稳的，即相继到达的间隔时间分布及其数学期望、方差等数字特征都与时间无关，否则是非平稳的。1.2.2排队规则排队规则指到达排队系统的顾客按怎样的规则排队等待，可分为损失制，等待制和混合制二种。(1) 损失制(消失制)。当顾客到达时，所有的服务台均被占用，顾客随即离去。(ii) 等待制。当顾客到达时，所有的服务台均被占用，顾客就排队等待，直到接受完服务才离去。例如出故障的机器排队等待维修就是这种情况。(iii) 混合制。介丁损失制和等待制之间的是混合制，即既有等待又有损失。有队列长度有限和排队等待时间有限两种情况，在限度以内就排队等待，超过一定限度就离去。排队方式还分为单列、多列和循坏队列。1.2.3服务过程(i) 服务机构。主耍有以卜儿种类型：单服务台；多服务台并联(每个服务台同时为不同顾客服务)；多服务台串联(多服务台依次为同一顾客服务)；混合型。(ii) 服务规则

4、。按为顾客服务的次序采用以卜几种规则： 先到先服务，这是通常的情形。 后到先服务，如情报系统中，最后到的情报信息往往最有价值，因而常被优先处理。 随机服务，服务台从等待的顾客中随机地取其一进行服务，而不管到达的先后。 优先服务，如医疗系统对病情严重的病人给予优先治疗。1.3排队模型的符号表示排队模型用六个符号表示，在符号之间用斜线隔开,即X/Y/Z/A/B/C.第一个符号%表示顾客到达流或顾客到达间隔时间的分布；第二个符号丫表示服务时间的分布；第三个符号Z表示服务台数目；第四个符号A是系统容鼠限制；第五个符号是顾客源数目；第六个符号C是服务规则，如先到先服务FCFS,后到先服务LCFS等。并约定，如略去后三项，即指X/y/Z/s/s/FCFS的情形。我们只讨论先到先服务FCFS的情形，所以略去第六项。表示顾客到达间隔时间和服务时间的分布的约定符号为：指数分布(M是Markov的字头，因为指数分布具有无记忆性，即Markov性)；D确定型(Deterministic)；Ekk阶爱尔朗(Erlang)分布：G般(general)服务时间的分布；GI般相互独立(GeneralIndepend

5、ent)的时间间隔的分布。例如，M/M/1表示相继到达间隔时间为指数分布、服务时间为指数分布、单服务台、等待制系统。D/M/c表示确定的到达时间、服务时间为指数分布、c个平行服务台(但顾客是一队)的模型。1.4排队系统的运行指标为了研究排队系统运行的效率，估计其服务质鼠，确定系统的最优参数，评价系统的结构是否合理并研究其改进的措施，必须确定用以判断系统运行优劣的基本数起指标，这些数駅指标通常是：(i) 平均队长：指系统内顾客数(包括正被服务的顾客与排队等待服务的顾客)的数学期望，记作(ii) 平均排队长:指系统内等待服务的顾客数的数学期望，记作q。(iii) 平均逗留时间：顾客在系统内逗留时间(包括排队等待的时间和接受服务的时间)的数学期望，记作W、.。(iv) 平均等待时间：指一个顾客在排队系统中排队等待时间的数学期望，记作(V)平均忙期：指服务机构连续繁忙时间(顾客到达空闲服务机构起，到服务机构再次空闲止的时间)长度的数学期塑，记为。还有由j:顾客被拒绝而使企业受到损失的损失率以及以后经常遇到的服务强度等,这些都是很重要的指标。计算这些指标的基础是表达系统状态的概率。所谓系统的状态

6、即指系统中顾客数,如果系统中有个顾客就说系统的状态是“，它的可能值是(i) 队长没有限制时，“=0丄2,，(ii) 队长有限制，最大数为N时，h=,N,(iii) 损失制,服务台个数是c时,n=0,l,-,co这些状态的概率一般是随时刻/而变化，所以在时刻/、系统状态为“的概率用P(t)表示。稳态时系统状态为n的概率用Pn表示。2输入过程与服务时间的分布排队系统中的事件流包括顾客到达流和服务时间流。由J：顾客到达的间隔时间和服务时间不可能是负值，因此它的分布是非负随机变堂的分布。最常用的分布有泊松分布、确定型分布，指数分布和爱尔朗分布。2.1泊松流与指数分布设N(f)表示在时间区间0,0内到达的顾客数(f0),令代(GG)表示在时间区间心)内有“(no)个顾客到达的概率，即代(PN(fJ-N(t2tl9n0)当化J合于卜列三个条件时，我们说顾客的到达形成泊松流。这三个条件是：1击不相重叠的时间区间内顾客到达数是和互独立的，我们称这性质为无后效性。2对充分小的在时间区间/,/+)内有一个顾客到达的概率与f无关，而约与区间长/成正比，即片(/+/)=2d+o(d)(1)其中0(),当dTO

7、时，是关于M的高阶无穷小。久0是常数，它表示单位时间有一个顾客到达的概率，称为概率强度。3对充分小的/,在时间区间/,/+/)内有两个或两个以上顾客到达的概率极小，以致可以忽略，即土化,/+/)=0(h)(2)在上述条件卜，我们研究顾客到达数的概率分布。由条件2,我们总可以取时间由0算起，并简记代(0,f)=Pn(t)。由条件1和2,有4(f+0)=A(f)(d)化(/+卜)=化_卍)人(4),=1,2,k=0由条件2和3得Pq(/)=1-AAt+o(M)因而有乙(/+zf)-化(/)/一恥)+讐PQ_=PM)=_厲+砒T(f)+气2在以上两式中，取/趋丁零的极限，当假设所涉及的函数可导时，得到以卜微分方程组：at吗=一2化(/)+吧_(),“=1,2,.at取初值4(0)=1,代(0)=0(=1,2,)，容易解出p(f)=”；再令代(/)=“(/)幺7,可以得到/(/)及其它匕所满足的微分方程组，即d匕dt=久匕t()，匕(/)=0由此容易解得代(0=哼“，=1,2,.n正如在概率论中所学过的，我们说随机变量(/)=N(s+/)-N(s)服从泊松分布。它的数学期望和方差分别是EN(t

8、)=At；VarN(f)=2/当输入过程是泊松流时，那么顾客相继到达的时间间隔T必服从指数分布。这是由于PT/=POJ)内呼叫次数为零=P0(t)=eA,那么，以尸(f)表示T的分布函数，则有PTo0,t0对J泊松流，久表示单位时间平均到达的顾客数，所以丄就表示和继顾客到达平均2间隔时间，而这正和ET的意义相符。对一顾客的服务时间也就是在忙期相继离开系统的两顾客的间隔时间，有时也服从指数分布。这时设它的分布函数和密度函数分别是G(/)=l-严，我们得到vPTtvPtTt这表明，在任何小的时间间隔/+()内一个顾客被服务完了(离去)的概率是+“表示单位时间能被服务完成的顾客数，称为平均服务率，而丄表示一个顾客的平均服务时间。2.2常用的儿种概率分布及其产生2.2.1常用的连续型概率分布我们只给出这些分布的参数、记号和通常的应用范F乩更详细的内容参看专门的概率论书籍。(i) 均匀分布区间(。丄)内的均匀分布记作U,b)。服从(0、1)分布的随机变量又称为随机数，它是产生其它随机变量的基础。如若X为(0,1)分布，则Y=a+(b-a)X服从U(a,b)o(ii) 正态分布以为期羞，0为方差的

9、正态分布记作N(/ACT2)o正态分布的应用十分广泛。正态分布还可以作为二项分布一定条件卜的近似。(iii) 指数分布指数分布是单参数久的非对称分布，记作Exp(Q),概率密度函数为：r0r0它的数学期望为2,方差为2。指数分布是唯一具有无记忆性的连续型随机变最，即z才有P(X/+s|X/)=P(Xs),在排队论、可靠性分析中有广泛应用。(iv) Gamma分布Gamma分布是双参数Q,0的非对称分布，记作G(Q,0),期望是妙。Q=1时蜕化为指数分布。个相互独立、同分布(参数久)的指数分布之和是Gamma分布(Q=np=2)。Gamma分布可用丁服务时间，零件寿命等。Gamma分布又称爱尔朗分布。(v) Weibull分布Weibull分布是双参数Z0的非对称分布，记作W(Z0)。a=l时蜕化为指数分布。作为设备、零件的寿命分布在可靠性分析中有着非常广泛的应用。(vi)Beta分布分布是区间(0)内的双参数、非均匀分布，记作B(Z0)。2.2.2常用的离散型概率分布(i) 离散均匀分布(ii) Bernoulli分布(两点分布)Bernoulli分布是X=1,0处取值的概率分别是和1-p的两点分布，记作Bein(p)o用于基本的

《算法大全第06章排队论》由会员cl****1分享，可在线阅读，更多相关《算法大全第06章排队论》请在金锄头文库上搜索。