搜索
排队论排队论又称随机服务系统，它应用于一切服务系统，包括生产管理系统、通信系统、交通系统、计算机存储系统。它通过建立一些数学模型，以对随机发生的需求提供服务的系统预测。现实生活中如排队买票、病人排队就诊、轮船进港、高速路上汽车通过收费站、机器等待修理等等。一、排队论的基本构成（1）输入过程输入过程是描述顾客是按照怎样的规律到达排队系统的。包括：①顾客总体：顾客的来源是有限的还是无限的。②到达的类型：顾客到达是单个到达还是成批到达。③相继顾客到达的时间间隔：通常假定是相互独立同分布，有的是等间隔到达，有的是服从负指数分布，有的是服从k阶Erlang分布。（2）排队规则排队规则指顾客按怎样的规定的次序接受服务。常见的有等待制，损失制，混合制，闭合制。当一个顾客到达时所有服务台都不空闲，则此顾客排队等待直到得到服务后才离开，称为等待制。在等待制中，可以采用先到先服务，如排队买票；也有后到先服务，如天气预报；也有随机服务，如电话服务；也有有优先权的服务，如危重病人可优先看病。当一个顾客到来时，所有服务台都不空闲，则该顾客立即离开不等待，称为损失制。顾客排队等候的人数是有限长的，称为混合制度。当顾客对象和服务对象相同且固定时是闭合制。如几名维修工人固定维修某个工厂的机器就属于闭合制。(3)服务机构服务机构主要包括：服务台的数量；服务时间服从的分布，常见的有定长分布、负指数分布、几何分布等。二、排队系统的数量指标(1)队长与等待队长队长（通常记为sL）是指系统中的平均顾客数（包括正在接受服务的顾客）。等待队长（通常记为qL）指系统中处于等待的顾客的数量。显然，队长等于等待队长加上正在服务的顾客数。(2)等待时间顾客的平均逗留时间（通常记为sW）是指顾客进入系统到离开系统这段时间，包括等待时间和接受服务的时间。顾客的平均等待时间（通常记为qW）是指顾客进入系统到接受服务这段时间。(3)忙期从顾客到达空闲的系统，服务立即开始，直到再次变为空闲，这段时间是系统连续繁忙的时期，称之为系统的忙期。它反映了系统中服务机构工作强度，是衡量服务系统利用效率的指标，即：服务强度=忙期/服务总时间=1─闲期/服务总时间闲期与忙期对应的系统的空闲时间，也就是系统连续保持空闲的时间长度。三、排队论中的符号表示排队论中的记号是20世纪50年代初由D.G.Kendall引入的，通常由3~5个字母组成，形式为：A/B/C/n其中A表示输入过程，B代表服务时间，C代表服务台数量，n表示系统空间数。M-负指数分布;D-确定型;Ek-k阶埃尔朗分布；GI-一般相互独立分布；G-一般随机分布等。如：(1)M/M/S/∞表示输入过程是Poisson流，即!nttetPNnn，服务时间服从负指数分布，即{}1,(0)tptet；系统有S个服务台平行服务，系统容量为无穷大的等待制排队系统。(2)M/G/S/∞表示输入过程是Poisson流，服务时间服从一般概率分布，系统有S个服务台平行服务，系统容量为无穷大的等待制排队系统。（3）D/M/S/K表示顾客相继到达时间间隔独立、服从定长分布，服务时间服从负指数分布，系统有S个服务台平行服务，系统容量为K个的混合制系统。(4)M/M/S/S表示输入过程是Poisson流，服务时间服从负指数分布，系统有S个服务台平行服务，顾客到达后不等待的损失制系统。（5）M/M/S/K/K表示输入过程是Poisson流，服务时间服从负指数分布，系统有S个服务台平行服务，系统容量和顾客容量都为K个的闭合制系统。四、排队系统的主要数量指标研究排队系统的目的是通过了解系统运行的状况，对系统进行调整和控制，使系统处于最优运行状态。因此，首先需要弄清系统的运行状况。描述一个排队系统运行状况的主要数量指标有：1.Pn：系统中恰好有n个顾客的概率，这n个顾客包括排队和正在被服务的顾客；在系统里没有顾客的概率，即所有服务设施空闲的概率，记为P0。2.Pw顾客到达系统时，得不到及时服务，必须排队等待服务的概率。3.Ls在系统里的平均顾客数，包括排队的顾客数和正在被服务的顾客数。4.Lq排队的平均长度，即排队的平均顾客数。5.Wq平均一位顾客花在排队上的时间。6.Ws平均一位顾客在系统里的平均逗留时间,它包括排队时间和被服务的时间。7.Little公式，L=λW。λ为单位时间内到达的顾客数。四、生灭过程及生灭过程排队系统1.生灭过程生灭过程是一类非常简单具有广泛应用的一类随机过程，很多排队模型中都假设其状态过程为生灭过程；这样的排队子系统如：M/M/C和M/M/C/R，我们也可称之为生灭过程的排队系统。在这样的排队系统中，一个新顾客的到达看作“生”，一个顾客服务完之后离开系统看作是“灭”，设N(t)的任意时刻t排队系统的状态（即排队子系统中的总顾客数），则对M/M/C/K系统N(t)具有有限个状态0,1,…,k,对M/M/C来说N(t)具有可列个状态0,1,2…。一般来说，随机过程0()tNt满足以下条件，称为生灭过程：1)假设N(t)=n，则从时刻t起到下一个顾客到达时刻为止的时间服从参数为的泊松分布，n=0,1,2,…2)假设N(t)=n，则从时刻t起到下一个顾客离去时刻为止的时间服从参数为的负指数分布，n=0,1,2,…3)同一时刻时只有一个顾客到达或离去。即只在相邻状态间转换。•一般来说，得到N(t)的分布Pn(t)=P{N(t)=n},n=0,1,2,…是比较困难的，因此通常是求当系统运行一段时间达到平稳状态后的状态分布，记为Pn。•当系统运行长时间达到平稳状态后，对于任一个状态n，单位时间内进入该状态的平均次数和单位时间离开该状态的平均次数应该相等，这就是系统的统计平衡下的“流入=流出”原理。2.生灭过程稳态方程11001111(),1nnnnnnnpppppn输入（出）率=某一稳态概率×平均转换率由此可求得生灭过程的平稳状态分布：01011011nnnPPPn由于01nnP即有011nPPP即有01010000012111nnPPPP即有1100101nnnP即当1010nnn时，此生灭过程存在平稳状态分布：1100101200111,1,2,nnnnnnnnPPPn（上述演算过程具体见：数学建模+排队论.ppt）五、排队论中四种重要的模型1.等待制模型M/M/S/∞该模型中顾客到达规律服从参数为的Poisson分布，在[0,]t时间内到达的顾客数()Xt服从的的分布为：().{()}!kttePXtkk（1）其单位时间到达的顾客平均数为，[0,]t时间内到达的顾客平均数为t。顾客接受服务的时间服从负指数分布，单位时间服务的顾客平均数为，服务时间的分布为：0()0tetft（2）每个顾客接受服务的平均时间为1。下面分别给出S=1和S1的一些主要结果。5.1只有一个服务台的S=1情形可以计算出稳定状态下系统有n个顾客的概率：(1)nnp0,1,2,3n（3）其中称为系统的服务强度。则系统没有顾客的概率为：011p系统中顾客的平均队长为：00.(1).1nsnnnLnpn（4）系统中顾客的平均等待队长为：2211(1).(1)(1).1()nqnnnLnpn（5）系统中顾客的平均逗留时间为：1sW（6）系统中顾客的平均等待时间为：11()qW（7）从(4)~(6)式可以看出：ssLW，qqLW（8）或ssLW，qqLW（9）该公式称为Little公式。在其它排队论模型中依然适用。Little公式的直观意义：ssLW表明排队系统的队长等于一个顾客平均逗留时间内到达的顾客数。qqLW表明排队系统的等待队长等于一个顾客平均等待时间内到达的顾客数。5.2系统有多个服务台S1情形当系统中有s个服务台，系统服务能力为s，服务强度为s。系统中顾客的平均队长为：02().!(1)sssLsps（10）其中1100()()!!(1)kssksspks，表示所有服务台都空闲的概率。系统中顾客的逗留时间为：ssLW（11）系统中顾客的平均等待时间为：1qsWW（12）系统中顾客的平均等待队长为：qqLW（13）5.3LINGO中的相关函数及相关参数计算公式(1)顾客等待概率的公式waitP=@peb(load,S)（14）其中S为服务台服务台个数，load为系统到达的载荷，即load。(2)顾客的平均等待时间公式qwaitTW=PSload（15）其中T为顾客接受服务的平均时间，有1T。当loads时无意义，表示当系统负荷超过服务台个数时，排队系统达到不稳定状态，队伍将越排越长。(3)系统中顾客的平均逗留时间1sqWW（16）(4)系统中顾客的的平均队长ssLW（17）(5)系统中顾客的的平均等待队长qqLW（18）例1某机关接待室只有1名对外接待人员，每天工作10小时，来访人员和接待时间都是随机的。设来访人员按照Poisson流到达，到达速率为8人/小时，接待人员的服务速率为9人/小时，接待时间服从负指数分布。（1）计算来访人员的平均等待时间，等候的平均人数。（2）若到达速率增大为20人/小时，每个接待人员的服务速率不变，为使来访问人员平均等待时间不超过半小时，最少应该配置几名接待人员。解答：（1）该问题属于M/M/1/∞排队模型。S=1,8,9需要计算来访人员的平均等待时间qW，等候的平均人数qL。LINGO程序为：model:lp=8;u=9;T=1/u;load=lp/u;S=1;Pwait=@PEB(load,S);!等待概率;W_q=Pwait*T/(S-load);!平均等待时间;L_q=lp*W_q;!顾客的平均等待队长;end计算结果：来访人员的平均等待时间0.89qW小时=53分钟，等候的平均人数7.1qL人。（2）该问题属于M/M/S/∞排队模型求最小的S使，来访人员的平均等待时间0.5qW。LINGO程序为：model:min=S;lp=20;u=9;!服务率;T=1/u;load=lp/u;Pwait=@PEB(load,S);!接待人员的等待概率;W_q=Pwait*T/(S-load);!平均等待时间;W_q=0.5;S=load;L_q=lp*W_q;!顾客的平均等待队长;TT=W_q*60;@gin(S);end计算结果为：最少需要接待人员S=3人,来访人员等待概率为0.55，排队等待平均时间为4.7分钟，队长平均长度为1.58人。2.损失制模型M/M/S/SM/M/S/S模型表示顾客到达人数服从Poisson分布，单位时间到达率为，服务台服务时间服从负指数分布，单位时间服务平均人数为。当S个服务台被占用后，顾客自动离开，不再等待。这里我们给出LINGO中的有关函数及相关参数的计算公式(1)系统损失概率lostP=@pel(load,S)（19）其中S为服务台服务台个数，load为系统到达的载荷，即load。损失概率表示损失的顾客所占的比率。(2)单位时间内进入系统的平均顾客数lost(1P)e（20）(3)系统中顾客的平均队长（系统在单位时间内占用服务台的均值）esL（21）(4)系统中顾客的平均逗留时间(服务时间)1sWT（22）(5)系统服务台的效率sLs（23）在损失制排队模型中，顾