数模排队理论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,排队论,张慧增,排队论的基本概念,在现实世界中，经常会发生为了获得某种服务而排队的现象,顾客到商店去买东西,病人到医院去看病,汽车去加油站加油,旅客到车站购票,当要求服务的对象的数量超过服务机构的容量就会出现排队现象。,出现排队现象的原因：顾客到达人数和服务时间的随机性。,排队论的基本概念,问题的解决：,增加服务设施能减少排队现象，但这样势必增加投资且可能出现因供大于求而使得设施经常闲置、导致浪费，这通常不是一个最经济的解决问题的办法。,作为管理人员来说，研究排队问题就是把排对的时间控制在一定的限度内，在服务质量的提高和成本的降低之间取得平衡，找到最适当的解。,排队论的基本概念,排队论的应用：,广泛用于解决电话局的通信线路的占线问题；,车站、码头、机场等交通的枢纽的堵塞和疏导；,故障机器的停机待修；,水库的储存调节等有形无形的排队现象的问题。,本章内容,排队论的基本知识；,常见的排队模型；,讨论排队论系统的经济分析与最优化问题。,排队论的基本概念,排队过程的一般模式,各个顾客由顾客源（总体）出发，到达服务机构前排队等候接受服务；,某些顾客在看到等候队列的长度以后，决定不进入服务系统；,部分排在队列里的顾客，在排了一段时间队以后也变得不耐烦，在接受服务之前离开了队列，留在队列里的顾客得到的服务后变离去。,排队系统的组成,一般排队系统都有,3,个基本组成部分：输入过程、排队与服务规则和服务机构。,输入过程：说明顾客按怎样的规律到达系统。要完全刻画一个输入过程，需要以下,3,个方面：,顾客总体数。可能是有限的，也可能是无限的。如车间内出现的故障待修的机器显然是有限的总体，而河流上游流入水库的水量可以认为是有限的。,顾客到达的方式。是单个到达还是成批到达。例如在一场球类比赛中，进入场地的团体单位的观众就是成批的。,顾客（单个或者成批）相继到达的间隔时间。可以是确定的，也可以是随机的。本章只研究最简单的模型，即顾客流的到达服从泊松分布为最简单流。,排队系统的组成,排队规则与服务规则,损失制：当顾客到达时，若所有的服务台均被占用，该顾客随即离去，这种排队规则也称为即时制；,等待制：当顾客到达时，若所有服务台均被占用，顾客并不离去而是排队等待服务；,混合制：允许排队，但是不允许队列无限的长下去。,服务规则,：（,1,）,先到先服务；,（,2,）,后到先服务；,（,3,）,随机服务；,（,4,）,有优先权的服务；,排队系统的组成,服务机构,服务台的数量及结构的形式。从数量上来看，服务台有单台和多台之分。从结构上来看，服务台,：（,1,）单队单服务台；（,2,）多队多服务台并列式；（,3,）单队多服务台并列式；（,4,）单队多服务台串联式；（,5,）多服务台混合式。,服务方式：在某一个时刻接受服务的顾客数，它有单个服务和成批服务两种。,服务时间：确定型和随机型。,排队系统的运行指标,研究排队系统的目的：通过了解系统的组成，对系统进行调整和改进，使系统处于最优或者满意的运行状态。,为了此目的，必须判断用以判断服务系统运行优劣的主要数量指标，这些指标通常为：,绝对通过能力,A,，即单位时间内被服务顾客的数学期望。,相对通过能力,Q,，即被服务顾客的顾客数与请求服务的顾客数的比值。,系统损失概率,P,损,，即服务系统满员的概率，或者说，服务员都忙着，排队位置满座的概率。,排队系统的运行指标,队长,L,系,，即系统内顾客数的数学期望。,排队长,L,队,，系统内排队顾客数的数学期望。,逗留时间,W,系,，顾客在系统内逗留时间的数学期望。,排队时间,W,队,，系统内顾客排队等待服务时间的数学期望。这里的逗留时间等于排队时间加服务时间。,计算上述指标的基础是系统状态的概率，这些状态概率的一般跟时刻,t,有关。用,P,n,(t,),表示时刻,t,的系统状态为,n,（即系统内有,n,个顾客）的概率。一般说来，求出与,t,有关的瞬态概率,P,n,(t,),是不容易的，即使求出也很难利用。而实际上很多系统运行一段时间后，系统的状态概率分布不再随时间变化，即当,t,充分大时，,P,n,(t,),接近一个常数,P,n,，这时称系统到达稳定或者统计平衡状态，称,P,n,为稳定概率。本章只研究稳定状态。,排队系统的运行指标,1971,年国际排队符号标准会上将排队模型的符号扩充为,6,项，记为,X/Y/Z/A/B/C.,X,表示顾客到达流或者顾客到达间隔时间的分布率；,Y,表示服务时间的概率分布；,Z,表示并列的服务员的数目；,A,表示顾客排队的容许长度或者系统内顾客的容量。,A=0,，表示损失制系统,;A=,，表示等待制,;A,为有限量时，为混合制。,B,表示顾客源的数目；,C,表示服务规则。,损失制排队模型算法,多通道损失制系统,模型：设系统内有,n,个服务员，顾客来到服务系统时如果服务员正在忙，顾客不能立即得到服务，则顾客离去，另求服务。,多通道损失制系统的各项效率指标：,损失概率,P,损，,其中,/,为单位时间来的顾客数即顾客流强度，,为单位时间内一个服务台服务的顾客数即服务台能力,损失制排队模型算法,系统的相对通过能力,Q=1-,P,损,系统的绝对通过能力,A=,Q,占用服务员的平均数,K,Q,通道的占用率,k/n,实例：某电话总机有,3,条中继线，平均每分钟有,0.8,次呼唤。如果每次通话时间平均为,1.5,分钟，试求：绝对通过能力、相对通过能力、损失概率、通道的占用率和占用通道的平均数。,解：,n,3,=0.8,=1/1.5=0.667,编程得到为,损失制排队模型算法,损失制排队模型算法,损失制排队模型算法,单通道损失系统,单通道损失系统是多通道损失系统的一种特殊情况，即当,n=1,时，系统即为单通道损失制系统,(M/M/1/0),效率指标为：,损失概率,系统的相对通过能力,Q=1/(1+,).,系统的绝对通过能力,A=,Q,损失制排队模型算法,实例：某电话总机有,1,条中继线，平均每分钟有,0.8,次呼唤。如果每次通话时间平均为,1.5,分钟，试求：中继线的相对通过能力，绝对通过能力和损失概率。,解：,n,1,=0.8,=1/1.5=0.667,损失制排队模型算法,练习,某电话总机有,3,条中继线，每小时平均,60,次呼唤，平均通话时间为,2,分钟，求系统运行效率指标。,电话总机有,1,条中继线，每分钟平均,2,次呼唤，平均通话时间为,4min,，求系统运行效率指标。,等待制排队模型算法,多通道等待制系统,模型：顾客到达流为泊松流，其强度为,。系统内有,n,个服务员，服务员具有相同服务时间，该服务时间服从指数分布，其强度为,。当顾客到达时，如果服务员忙着，顾客排队的等待服务，一直等到有服务员为他服务为止。,效率指标：,等待制排队模型算法,系统损失概率,P,损,0,。,系统的相对通过能力,Q=1.,系统的绝对通过能力,A=,系统内排队顾客的平均数,顾客的平均排队时间,等待制排队模型算法,占用服务员的平均数,k=,系统内顾客的平均数,L,系,L,队,单通道等待制系统的效率指标,P,0,=1-,系统内排队顾客的平均数,L,队,2,/(1-,),顾客排队的平均时间,W,队,2,/,(1-,),系统内顾客的平均数,L,系,L,队,顾客在系统中平均逗留时间,W,系,L,系,/,.,等待制排队模型实例,某临时架设的公路简便桥，桥上不容许同时有两辆汽车通过。若汽车到达流为泊松流，其强度为,2.1,辆,/,分钟,.,通过时间是指数分布，平均每辆的通过时间为,0.4,分钟,试求系统的效率指标。,解：,2.1,，,1/0.4=2.5,/,=2.5,m=1,等待制排队模型实例,某理发店有两个理发员，顾客平均到达的间隔时间为,20min,，每剃一个头需要,25min,，两种时间均服从负指数分布。试求理发店的经营效率。,某修理店只有一个修理工人；来修理的顾客到达次数服从泊松分布，平均每小时,4,人，修理时间服从负指数分布，平均需,6,分钟，试求系统的效率指标。,等待制排队模型练习,混合制排队模型算法,多通道混合制系统,模型：系统中有,n,个服务员。顾客按最简单流来到服务系统，其强度为,。服务员相同的能力为,，服务时间服从指数分布。系统内有,m,个位置供顾客排队。当顾客到达时，系统满员，顾客离去，另求服务。,系统的各项效率指标：,系统的损失概率,系统的相对通过能力,系统的绝对通过能力,混合制排队模型算法,占用服务员的平均数,排队顾客的平均数,系统内顾客的平均数,顾客的平均排队时间,顾客在系统内中平均停留时间,单通道混合制系统,混合制排队模型实例,某修理站只有一个修理组,在修理站内最多只能停放,3,座机器，若超过,3,座，则请到别的修理战去。设修理机器的到达强度,1,座,/,天，并且服从泊松流。修理时间是指数分布，平均修理时间是,1.25,，试求系统的效率指标。,解：,1,，,1/1.25=0.8,，,m=3,混合制排队模型实例,混合制排队模型实例,某汽车自动加油站，设有两条加油管。汽车按最简单流到达，每分钟平均到达两辆。加油时间服从指数分布，每辆汽车的平均加油时间为,2,分钟。自动加油站上最多只能停,3,辆汽车。如果汽车到达时，系统满员，则汽车开到另外加油站去，另求服务。求此系统的效率指标。,解：,n=2,2,，,1/2=0.5,，,m=3,混合制排队模型实例,混合制排队模型练习,某理发店只配置,3,把椅子，设顾客到达流服从参数为,=2/h,的最简单流，理发时间服从负指数分布，平均理发时间为,20min,求店的经营效率。,某服务台有,2,个服务员，只有,5,个位置供等待，顾客到达流服从每分钟,0.4,的最简单流，服务时间服从负指数分布，平均服务时间为,10,分钟，求该系统效率指标。,单通道混合制算法,模型：排队系统为单通道。顾客到达时，系统内已有,n,个顾客排队。这时顾客以,n,的概率参加排队。当,n=0,时，,n,1,，即没有不耐烦的顾客，因为当时系统闲着，顾客一到，立即接受服务。顾客按简单流到来，其强度为,。服务时间服从指数分布，其强度为,。,单通道混合制算法,系统内的顾客平均数,L,系,系统内排队顾客的平均数,L,队,系统损失概率,P,损,服务员的平均负荷,L,队,单通道混合制实例,某公用电话，每分钟平均有,0.4,个顾客到达。平均通话时间为,4,分钟。顾客按最简单流到达，服务时间服从指数分布。通过观察，当电话机前已经有两个人等待打电话时，有,5,的顾客自动离去，成为不耐烦的顾客。求顾客的效率指标。,解：,n=3,=0.4,=0.25,n,=0.95.,单通道混合制实例,单通道混合制习题,某售票窗口，每分钟平均有,0.8,个顾客到达，平均服务时间为,2,分钟。旅客按最简单流到达，服务时间按最简单流到达，服务时间服从负指数分布。已知此窗口前的第,11,名旅客去另外窗口排队的概率为,0.1,，求此售票窗口的效率指标。,闭合式系统,多通道闭合式系统,模型：顾客源为有限数,n.,由于顾客源为有限数,n,，因此系统的最大状态为,n,而且顾客的平均到达概率将依赖于已经有多少顾客在系统中，即,不再是常数。这类系统在生产中，如机器的维修和管理等问题中得到应用。在机器的维修和管理中，就是共有,m,个修理工人，有,n,台机器，顾客到达就是机器出了故障，顾客到达率,是指每台机器每单位运转时间出故障的次数期望值。而排队的顾客代表出了故障而由于修理员正在忙需要等待的机器。,多通道闭合式系统,例子：两个修理工人包干维修,6,台机器，机器平均每月出故障,2,次，一个修理工人修理一台机器平均需要,5,天，求系统的效率指标,解：,n=6,m=2,=2,=6,多通道闭合式系统,单通道闭合式系统实例,一个修理工人负责维修,3,台大型机器，每台机器平均每月出,2,次故障，修理工人平均每月能够修理,6,台机器，试求服务的效率指标？,单通道闭合式系统实例,闭合式系统习题,2,个道路维修队负责维修某地区的,5,条道路，道路每