《排队论及相关程序》由会员分享，可在线阅读，更多相关《排队论及相关程序（17页珍藏版）》请在金锄头文库上搜索。
1、排队论排队论又称随机服务系统，它应用于一切服务系统,涉及生产管理系统、通信系统、交通系统、计算机存储系统。它通过建立某些数学模型，以对随机发生的需求提供服务的系统预测。现实生活中如排队买票、病人排队就诊、轮船进港、高速路上汽车通过收费站、机器等待修理等等。一、排队论的基本构成（1)输入过程输入过程是描述顾客是按照如何的规律达到排队系统的。涉及:顾客总体:顾客的来源是有限的还是无限的。达到的类型：顾客达到是单个达到还是成批达到。相继顾客达到的时间间隔:一般假定是互相独立同分布,有的是等间隔达到，有的是服从负指数分布,有的是服从k阶Elng分布。（）排队规则排队规则指顾客按如何的规定的顺序接受服务
2、。常用的有等待制，损失制，混合制，闭合制。当一种顾客达到时所有服务台都不空闲,则此顾客排队等待直到得到服务后才离开，称为等待制。在等待制中，可以采用先到先服务,如排队买票;也有后到先服务，如天气预报;也有随机服务,如电话服务；也有有优先权的服务，如危重病人可优先看病。当一种顾客到来时,所有服务台都不空闲,则该顾客立即离开不等待,称为损失制。顾客排队等待的人数是有限长的，称为混合制度。当顾客对象和服务对象相似且固定期是闭合制。如几名维修工人固定维修某个工厂的机器就属于闭合制。(3）服务机构服务机构重要涉及:服务台的数量;服务时间服从的分布,常用的有定长分布、负指数分布、几何分布等。二、排队系统的
3、数量指标(1）队长与等待队长队长(一般记为）是指系统中的平均顾客数（涉及正在接受服务的顾客)。等待队长（一般记为)指系统中处在等待的顾客的数量。显然，队长等于等待队长加上正在服务的顾客数。()等待时间顾客的平均逗留时间(一般记为)是指顾客进入系统到离开系统这段时间，涉及等待时间和接受服务的时间。顾客的平均等待时间（一般记为)是指顾客进入系统到接受服务这段时间。（3）忙期从顾客达到空闲的系统，服务立即开始,直到再次变为空闲，这段时间是系统持续繁忙的时期，称之为系统的忙期。它反映了系统中服务机构工作强度，是衡量服务系统运用效率的指标，即:服务强度=忙期/服务总时间=闲期服务总时间闲期与忙期相应的系
4、统的空闲时间，也就是系统持续保持空闲的时间长度。三、排队论中的符号表达排队论中的记号是20世纪50年代初由DG.Kenal引入的，一般由35个字母构成,形式为：A/B/C/n其中表达输入过程,B代表服务时间，代表服务台数量，表达系统空间数。-负指数分布;D-拟定型;Ek-k阶埃尔朗分布；GI一般互相独立分布;G-一般随机分布等。如：(1) MM/S表达输入过程是Pson流,即,服务时间服从负指数分布,即;系统有个服务台平行服务,系统容量为无穷大的等待制排队系统。() M/G/S/表达输入过程是Pson流,服务时间服从一般概率分布，系统有S个服务台平行服务，系统容量为无穷大的等待制排队系统。(3
5、）/S/K表达顾客相继达到时间间隔独立、服从定长分布,服务时间服从负指数分布,系统有S个服务台平行服务,系统容量为K个的混合制系统。() MM/S/S表达输入过程是Poison流,服务时间服从负指数分布，系统有S个服务台平行服务，顾客达到后不等待的损失制系统。（5)M/S/K表达输入过程是Poisson流，服务时间服从负指数分布，系统有个服务台平行服务，系统容量和顾客容量都为K个的闭合制系统。四、排队系统的重要数量指标研究排队系统的目的是通过理解系统运营的状况,对系统进行调节和控制，使系统处在最优运营状态。因此,一方面需要弄清系统的运营状况。描述一种排队系统运营状况的重要数量指标有:1. n：
6、系统中正好有n个顾客的概率，这n个顾客涉及排队和正在被服务的顾客；在系统里没有顾客的概率，即所有服务设施空闲的概率，记为P0。2. Pw顾客达到系统时,得不到及时服务,必须排队等待服务的概率。3. Ls在系统里的平均顾客数，涉及排队的顾客数和正在被服务的顾客数。4. 排队的平均长度,即排队的平均顾客数。5. W平均一位顾客花在排队上的时间。6. s平均一位顾客在系统里的平均逗留时间，它涉及排队时间和被服务的时间。7. Lttle公式，LW。为单位时间内达到的顾客数。四、生灭过程及生灭过程排队系统1.生灭过程生灭过程是一类非常简朴具有广泛应用的一类随机过程,诸多排队模型中都假设其状态过程为生灭过
7、程;这样的排队子系统如：M/C和M/M/,我们也可称之为生灭过程的排队系统。在这样的排队系统中，一种新顾客的达到看作“生”,一种顾客服务完之后离开系统看作是“灭”，设N(t）的任意时刻排队系统的状态（即排队子系统中的总顾客数),则对MC/K系统N(t）具有有限个状态,1，k,对M/M/C来说(t)具有可列个状态0,，。 一般来说,随机过程满足如下条件,称为生灭过程: 1)假设N(）=n，则从时刻起到下一种顾客达到时刻为止的时间服从参数为的泊松分布,n=，1,2, 2)假设N（t）=n，则从时刻t起到下一种顾客拜别时刻为止的时间服从参数为的负指数分布,n=0,2， ) 同一时刻时只有一种顾客达到
8、或拜别。即只在相邻状态间转换。 一般来说，得到N（t)的分布Pn（t)=N（)=n,n=,1,2，是比较困难的，因此一般是求当系统运营一段时间达到平稳状态后的状态分布,记为Pn。 当系统运营长时间达到平稳状态后,对于任一种状态n，单位时间内进入该状态的平均次数和单位时间离开该状态的平均次数应当相等,这就是系统的记录平衡下的“流入=流出”原理。. 生灭过程稳态方程 输入（出）率=某一稳态概率平均转换率由此可求得生灭过程的平稳状态分布:由于即有即有即有即当时,此生灭过程存在平稳状态分布：（上述演算过程具体见：数学建模+排队论.ppt)五、排队论中四种重要的模型.等待制模型/S/该模型中顾客达到规律
9、服从参数为的Posso分布，在时间内达到的顾客数服从的的分布为: (1）其单位时间达到的顾客平均数为，时间内达到的顾客平均数为。顾客接受服务的时间服从负指数分布，单位时间服务的顾客平均数为,服务时间的分布为: （）每个顾客接受服务的平均时间为。下面分别给出S=和S的某些重要成果。51 只有一种服务台的S=1情形可以计算出稳定状态下系统有个顾客的概率： （）其中称为系统的服务强度。则系统没有顾客的概率为：系统中顾客的平均队长为： (）系统中顾客的平均等待队长为： （)系统中顾客的平均逗留时间为： （6)系统中顾客的平均等待时间为: (）从（4)(6)式可以看出： ， （8）或 , (9）该公式称
10、为tle公式。在其他排队论模型中仍然合用。Littl公式的直观意义:表白排队系统的队长等于一种顾客平均逗留时间内达到的顾客数。表白排队系统的等待队长等于一种顾客平均等待时间内达到的顾客数。.2系统有多种服务台S1情形 当系统中有个服务台,系统服务能力为,服务强度为。系统中顾客的平均队长为: （0）其中，表达所有服务台都空闲的概率。系统中顾客的逗留时间为： (11)系统中顾客的平均等待时间为: (12)系统中顾客的平均等待队长为： (13）5ING中的有关函数及有关参数计算公式(1)顾客等待概率的公式 （14）其中S为服务台服务台个数，load为系统达到的载荷,即。(）顾客的平均等待时间公式 （
11、5)其中T为顾客接受服务的平均时间，有。当lods时无意义,表达当系统负荷超过服务台个数时,排队系统达到不稳定状态，队伍将越排越长。（3)系统中顾客的平均逗留时间 （16）()系统中顾客的的平均队长 （17)（5)系统中顾客的的平均等待队长 (18）例1某机关接待室只有1名对外接待人员,每天工作1小时,来访人员和接待时间都是随机的。设来访人员按照Poiss流达到，达到速率为人/小时，接待人员的服务速率为人/小时,接待时间服从负指数分布。(1）计算来访人员的平均等待时间，等待的平均人数。（2)若达到速率增大为人/小时，每个接待人员的服务速率不变,为使来访问人员平均等待时间不超过半小时，至少应当配
12、备几名接待人员。解答：(1）该问题属于M/排队模型。S=1,需要计算来访人员的平均等待时间,等待的平均人数。LING程序为：model:p=;u9;T=1/u;lod=lpu;S=1；Pwait=PEB(load,);!等待概率;W_qPwai*T(S-load);！平均等待时间；L_q=lWq；!顾客的平均等待队长;en计算成果:来访人员的平均等待时间小时=53分钟,等待的平均人数人。(2)该问题属于/M/排队模型求最小的使，来访人员的平均等待时间。O程序为:model:in;lp=0;u=; !服务率;T1/u;lodpu;wait=PE(oad,S);!接待人员的等待概率;_Pwait*
13、T(S-oa)；!平均等待时间;W=load;L=*q；!顾客的平均等待队长;T=_q*60；g（S);nd计算成果为:至少需要接待人员=3人,来访人员等待概率为0.5，排队等待平均时间为47分钟，队长平均长度为1.5人。2 损失制模型MM/ MM/S/S模型表达顾客达到人数服从Poisson分布，单位时间达到率为,服务台服务时间服从负指数分布，单位时间服务平均人数为。当S个服务台被占用后,顾客自动离开,不再等待。 这里我们给出LING中的有关函数及有关参数的计算公式 (1） 系统损失概率 （9)其中S为服务台服务台个数，oad为系统达到的载荷，即。损失概率表达损失的顾客所占的比率。(2）单位时间内进入系统的平均顾客数
