排队论模型

数学建模讲座排队论模型高秀娟2008年7月1日排队系统的描述顾客总体队伍服务台服务系统输出输入排队服务系统的基本概念输入过程：描述顾客来源是按怎样的规律抵达排队系统。1.顾客源总体:有限还是无限2.到达类型：单个到达还是成批到达3.相继顾客到达的时间间隔：相互独立、同分布的;等时间间隔的;服从Poisson分布的；k阶Erlang分布泊松分布适合于描述单位时间内随机事件发生的次数。如某一服务设施在一定时间内到达的人数，电话交换机接到呼叫的次数，汽车站台的候客人数，机器出现的故障数，自然灾害发生的次数等等。排队服务系统的基本概念排队规则：指服务系统是否允许排队，顾客是否愿意排队1.损失制排队系统：顾客到达若所有服务台被占，服务机构又不允许顾客等待，此时该顾客就自动离去。2.等待制排队系统：顾客到达时若服务台均被占，他们就排队等待。服务顺序有：先到先服务、后到先服务、随机服务、有优先权的服务3.混合制排队系统：损失制与等待制的混合。队长（容量）有限的混合；等待时间有限的混合；逗留时间有限的混合排队服务系统的基本概念服务机构：1.服务台的数目2.顾客所需的服务时间服从怎样的概率分布(常见顾客的服务时间分布有:定长分布、负指数分布、超指数分布、k阶Erlang分布、几何分布、一般分布)排队论模型的符号表示通常由3-5个英文字母组成，其形式为A/B/C/n，其中A表示输入过程，B表示服务时间，C表示服务台数目，n表示系统空间数排队模型的表示：X/Y/Z/A/B/CX—顾客相继到达的间隔时间的分布；Y—服务时间的分布；Z—服务台个数；A—系统容量限制（默认为∞）；B—顾客源数目（默认为∞）；C—服务规则（默认为先到先服务FCFS)。M—负指数分布、D—确定型、Ek—k阶爱尔朗分布。描述排队论系统的主要数量指标1.队长(Ls)：指在系统中顾客的平均数等待队长(Lq)：指系统中等待的顾客的平均数2.顾客的平均等待时间(Wq)：指顾客进入系统的时刻起到开始接受服务止的平均时间与平均逗留时间(Ws)：指顾客在系统中平均等待时间与平均服务时间之和3.系统的忙期与闲期服务机构工作强度=由于服务顾客的时间/服务设施总的服务时间=1-服务设施总的空闲时间/服务设施总的服务时间与排队论模型有关的LINGO函数1.@peb(load,S)该函数返回值是当到达负荷为load，系统中有S个服务台且允许排队时系统繁忙的概率，也就是顾客等待的概率2.@pel(load,S)该函数返回值是当到达负荷为load，系统中有S个服务台且不允许排队时系统损失的概率，也就是顾客得不到服务离开的概率3.@pfs(load,S,K)该函数的返回值是当到达负荷为load，顾客数为K,平行服务台数量为S时，有限源的Poisson服务系统等待或返修顾客数的期望值等待制排队模型等待制排队模型中最常见的模型是：M/M/S/∞,即顾客到达系统的相继到达时间间隔独立，且服从参数为λ的负指数分布（即输入过程为过程），服务台的服务时间也独立同分布，且服从参数为μ的负指数分布，而且系统空间无限，允许永远排队等待制排队模型的基本参数1.顾客等待的概率:Pwait=@peb(load,S),其中S是服务台或服务员的个数，load=λ/μ=RT,其中R=λ,T=1/μ，R是顾客的平均到达率，T是平均服务时间2.顾客的平均等待时间：Wq=Pwait·T/(S-load),其中T/(S-load)可以看成一个合理的长度间隔，3.顾客的平均逗留时间、队长和等待队长（little公式）Ws=Wq+1/μ=Wq+TLs=λ·Ws=RWsLq=λ·Wq=RWq等待制排队模型实例1.S=1(M/M/1/∞)例1：某维修中心在周末现只安排一名员工为顾客提供服务，新来维修的顾客到达后，若已有顾客正在接受服务，则需要排队等待，假设来维修的顾客到达过程为Poisson流，平均每小时4人，维修时间服从负指数分布，平均需要6min,试求该系统的主要数量指标。2.S=3(M/M/S/∞)例2：设打印室有3名打字员，平均每个文件的打印时间为10min,而文件到达率为每小时15件，试求该打印室的主要数量指标。等待制排队模型实例例1：Model:S=1;R=4;T=6/60;load=R*T;Pwait=@peb(load,S);W_q=Pwait*T/(S-load);L_q=R*W_q;W_s=W_q+T;L_s=W_s*R;End例2：Model:S=3;R=15;T=10/60;load=R*T;Pwait=@peb(load,S);W_q=Pwait*T/(S-load);L_q=R*W_q;W_s=W_q+T;L_s=W_s*R;END损失制排队模型损失制排队模型通常记为M/M/S/S,当S个服务器被占用后，顾客自动离去损失制排队模型的基本参数1.系统损失的概率：Plost=@pel(load,S)2.单位时间内平均进入系统的顾客数：λe=Re=λ(1-Plost)=R(1-Plost)3.系统的相对通过能力(Q)与绝对通过能力(A)Q=1-Plost,A=λe·Q=λ(1-Plost)2=Re·Q=R(1-Plost)24.系统在单位时间内占用服务台的均值:Ls=λe/μ=Re·T注意：在损失制系统中，Lq=0,即等待队长为05.系统服务台的效率：η=Ls/S6.顾客在系统内平均逗留时间:Ws=1/μ=T注意：在损失制系统中，Wq=0,即等待时间为0损失制排队模型实例S=1(M/M/1/1)例1：设某条电话线，平均每分钟有0.6次呼唤，若每次通话时间平均为1.25min,求系统相应的参数指标。model:S=1;R=0.6;T=1.25;load=R*T;Plost=@pel(load,S);Q=1-Plost;R_e=Q*R;A=Q*R_e;L_s=R_e*T,eta=L_s/S;endEta-η损失制排队模型实例S1(M/M/S/S)例2：某单位电话交换台有一台200门内线的总机，已知在上班8小时内，有20%的内线分机平均每40min要一次外线电话，80%的分机平均间隔120min要一次外线。又知外线打入内线的电话平均每分钟1次。假设与外线通话的时间为平均3min，并且上述时间均服从负指数分布，如果要求电话的通话率为95%，问该交换台应设置多少条外线？损失制排队模型实例例2：分析：1)电话交换台的服务分成两类，第一类内线打外线，其强度为λ1=（0.2×60/40+0.8×60/120）×200=140第二类是外线打内线，其强度为λ2=1×60=60因此总的强度为λ=λ1+λ2=140+60=2002)按题目要求，系统损失的概率不能超过5%，即Plost≤0.053）外线是整数，在满足条件下，条数越少越好Model:R=200;T=3/60;load=R*T;Plost=@pel(load,S);Plost=0.05;Q=1-Plost;R_e=Q*R;A=Q*R_e;L_s=R_e*T;eta=L_s/S;Min=S;@gin(S);end混合制排队模型混合制排队模型通常记为：M/M/S/K,即有S个服务台或服务员，系统空间容量为K，当K个位置已被顾客占用时，新到的顾客自动离去，当系统中有空位置时，新到的顾客进入系统排队等待。闭合式排队模型设系统内有M个服务台，顾客到达系统的间隔时间和服务台的服务时间均为负指数分布，而系统的容量和潜在的顾客数都为K，顾客到达率为λ，服务台的平均服务率为μ，这样的系统称为闭合式排队模型，记为：M/M/S/K/K闭合式排队模型的基本参数1.平均队长：Ls=@pfs(load,S,K),load=K·λ/μ=KRT即:系统的负荷=系统的顾客数×顾客到达率×顾客的服务时间2.单位时间平均进入系统的顾客数:λe=λ（K－Ls）=R(K－Ls)=Re3.顾客处于正常情况的概率:P=(K－Ls)/K4.平均逗留时间、平均等待队长和平均排队等待时间Ws=Ls/λe=Ls/ReLq=Ls－λe/μ=Ls-Re·TWq=Ws－1/μ=Ws－T5.每个服务台的工作强度:Pwork=λe/(Sμ)排队系统的最优化模型1.系统服务时间的确定例：某工人照管4台自动机床，机床运转时间平均为负指数分布，假定平均每周有一台机床损坏需要维修，机床运转单位时间内平均收入100元，而每增加一单位μ的维修费用为75元，求使总利益达到最大的μ*分析：这是一个闭合式排队系统M/M/1/K/K,且K=4，设Ls是队长，则正常运转的机器为K－Ls部，因此目标函数为：f=100(K－Ls)－75μModel:S=1;K=4;R=1;L_s=@pfs(K*R/mu,S,K);Max=100*(K=L_s)-75*mu;end排队系统的最优化模型2.系统服务台的确定例：一个大型露天矿山，正考虑修建矿石卸位的个数，估计运矿石的车将按Poisson流到达，平均每小时15辆，卸矿石时间服从负指数分布，平均3min卸一辆，又知每辆运送矿石的卡车售价是8万元，修建一个卸位的投资是14万元，问应建多少个矿石卸位最为适宜？分析：用等待制排队系统M/M/S/∞进行分析,其费用包括建造卸位的费用和卡车处于排队状态不能工作的费用，目标函数为：F=14S+8LsModel:R=15;T=3/60;load=R*T;Pwait=@peb(load,S);W_q=Pwait*T/(S-load);W_s=W_q+T;L_s=W_s*R;Min=8*L_s+14*S;@gin(S);@bnd(1,S,5);end试着做一做某售票点有两个售票窗口，顾客按参数λ=8人/min的Poisson流到达，每个窗口的售票时间服从参数μ=5人/min的负指数分布，试比较以下两种排队方案的运行指标，并指出哪种售票方式效率更高。μ=5μ=5μ=5μ=5λ=8λ1=4λ2=41）顾客到达后，以1/2的概率站成两个队列，如下图λ=8到达离去离去离去离去2）顾客到达后排成一个队列，顾客发现哪个窗口空闲时，他就接受该窗口的服务，如下图到达