排队论之简单排队系统

无限源的简单排队系统所谓无限源的简单排队系统是指顾客的来源是无限的，输入过程是简单流，服务时间是负指数分布的排队系统。本节我们讨论一些典型的简单排队系统。1.M/M/1/排队系统M/M/1/排队系统是单服务台等待制排队模型,可描述为：假设顾客以Poisson过程（具有速率）到达单服务员服务台，即相继到达时间间隔为独立的指数型随机变量，具有均值1 ，若服务员空闲，则直接接受服务，否则，顾客排队等待，服务完毕则该顾客离开系统，下一个排队中的顾客 （若有）接受服务。相继服务时间假定是独立的指数型随机变量，具有均值 。两个M指的是相继到达的间隔时间和服务时间服从负指数分布， 1指的是系统中只有一个服务台， 指的是容量为无穷大，而且到达过程与服务过程是彼此独立的。为分析之，我们首先确定极限概率 pn，n 0,1,2,???，为此，假定有无穷多房间，标号为0,1,2,???，并假设我们指导某人进入房间n（当有n个顾客在系统中），则其状态转移框图如图所示。0 1 2 n n 1图 M/M/1/ 排队系统状态转移速率框图由此，我们有状态 离开速率＝进入速率0p0p1n,n1pnpn1pn1解方程组，容易得到ipip0，i0,1,2,???再根据1pn()np0p0n1n01得到：p0 1 ，pn()n(1),n1令/，则称为系统的交通强度（trafficintensity）。值得注意的是这里要求1，因为若 1，则pn 0，且系统中的人数随着时间的推移逐渐增多直至无穷，因此对大多数单服务排队系统，我们都假定 1。于是，在统计平衡的条件下（ 1），平均队长为Ljpj,1,（5-52）j01由于 a

，根据式（5-2）、（5-3）以及上式，可得：平均逗留时间为：L11（5-53）W,平均等待时间为：WQWE[S]1,1（5-54）W()(1)平均等待队长为：22LQWQ),1（5-55）(1另外，根据队长分布易知，01也是系统空闲的概率，而正是系统繁忙的概率。显然，越大，系统越繁忙。队长N(t)由0变成1的时刻忙期即开始，此后N(t)第一次又变回0时忙期就结束。由简单流与负指数分布的性质，显见忙期的长度与忙期的起点无关。可以证明，闲期的期望值为1 ，令忙期平均长度为 b，则在统计平衡下，有：平均忙期：平均闲期＝ ：(1 )，因此平均忙期长度为：1，1b（5-56）1一个忙期中所服务的平均顾客数为1

， 1b 1 （5-57）， 1不难看出，在忙期内相继输出的间隔时间是独立、同参数 ( 0)的随机变量，即为参数 的Poisson流。但是，当系统空闲后，从开始空闲时刻起，到下一个顾客服务完毕离去时之间的间隔时间显然不与服务时间同分布。下面简要推导一下 M/M/1/ 排队系统的输出过程特征。令Tn表示第n个顾客服务完毕的离去时刻，则n1n表示离去的间隔时间，n1，TT于是，对t0，P{Tn1Tnt}P{Nn0}P{Tn1Tnt|Nn0}P{Nn1}P{Tn1Tnt|Nn1}PNn0}P?n1Sn!t}{{P{Nn1}P{Sn1t},其中?n1表示剩余到达间隔时间，与Sn1（服务时间间隔）独立，而Nn表示第n个离去顾客服务完毕离开系统时的队长。由于limP{Nn1，1,0}1,n，0而P{?n1Sn!t}＝etet（根据两独立随机变量和的分布计算公式计算），所以P{Tn1 Tn t} (1 ) e t e t

et（5-58）此式表示在统计平衡下，相继输出的间隔时间服从参数 ( 0)的负指数分布。例某通信团电话维修站，有 1个维修技师，每天工作 10小时。待维修电话的到来服从Poisson分布，每天平均有 90部电话到来，维修时间服从指数分布， 平均速率为 10部/小时。试求排队等待维修的平均电话数；等待维修电话的多于 2部的概率；如果使等待维修的电话数平均为 2部，维修速率应提高多少解：这是一个M/M/1/ 模型已知9，10，则0.92①LQ18.1②1(p0p1p2)1(1)(1)(1)20.729③2LQ99，解得：12.299所以，接待速率应提高：102.29。例假设顾客以Poisson速率为每12分钟1人到达，服务时间是指数型的且服务速率是每8分钟服务1个人，L和W分别是多少解：因为11（人／分），（人／分），我们得到：128L2，W24因此，系统中顾客的平均个数为2，顾客在系统中平均花费的时间是24分钟。现假设到达速率提高20％到1，重新计算L和W得到10L4，W40因此，到达速率20％的增加导致系统中平均顾客数增加了1倍。事实上，从式（5-52）和式（5-53）可以清楚看到，当趋于1时，的一个微小的增加都会导致 L和W大的增加。例战时，集团军通信团的通信设备以指数速率每小时 6台损坏，有一个维修技师，其维修速率是指数速率每小时8台，设备损坏而没有得到及时维修造成的损失是每台设备每小时100次通话，问：由于损坏的设备引起的平均通话损失率是多少解：该问题是一个M/M/1/排队模型，其中6，8。则平均通话损失率＝每台设备每小时100次损坏设备的平均数而损坏设备的平均数就是LL3因此，平均通话损失率等于每小时300次。2.M/M/c/排队系统M/M/c/排队系统是一种多服务等待制系统,指的是：有c(c1)个服务台独立地并行服务。当顾客到达时，若有空闲服务台便立刻接受服务，若没有空闲的服务台，则排队等待，直到有空闲的服务台时再接受服务。假定顾客单个到达，相继到达时间间隔服从参数(0)的负指数分布，每个服务台服务时间独立、服从相同参数(0)的负指数分布，系统容量为无穷大，而且到达与服务是彼此独立的。设N(t)表示系统中的顾客数，则{N(t)，0}是无限状态E{0,1,2,}上的生灭过???程，其参数为，0,1,；i，1ic（5-59）ii???c，ci其分布()()nn0,1,2,???的平稳状态分布记为，0,1,2,???，则pntPNtpnn与无限源生灭过程分析类似，考虑有c个服务台，对任一状态，在统计平衡下，其平衡方程为：状态离开速率＝进入速率0p0p11p1p02p222p2p13p3。。。c1(c1)pc1pc2cpcccpcpc1cpc1。。。nc1cpnpn1cpn1。。。若记，cc，则当c1时，解上述平衡方程组，可得：1jp0，1jc1,pjj!（5-60）1cjc!jp0，jc,cc1jcc1再由概率分布的要求：pn1，解得上式中的p0。j!c!(cn0j0)由于系统中有c个服务台，所以顾客到达时需要等待的概率为ppj1pc,c1（5-61）1cjccc其中，pcp0。c!式（5-61）称为Erlang等待公式，它给出了顾客到达系统时需要等待的概率。在统计平衡下，等待队长LQ显然有分布cP{LQ0}pj，P{LQk}pck，k1,2,???（5-62）j0所以当pc时，有LQ(jc)pj(jc)1jp0jcjcc!jccccp0(jc)jccp0(xj)|cp（5-63）c!jccc!j1xc(1c)2c又令Lc表示系统平衡时，正在被服务的顾客数，则，0,1,2,???,c；c}pj（5-64）P{Lck}pkk1P{Lcjc所以正在接受服务的顾客的平均数LC为：c1LcE[Lc]jpjcpjj0jc1j1

1jp0p0cj(j1)!(c1)!cj0c{1jc1pj}(1c)(c1)!p0c{1pc1jcpj}(1c)(c1)!p05-65）上式表明，平均在忙的服务台的个数与服务台个数 c无关。平均队长L为LLQLccpc，c1（5-66）c)2(1可以验证，c时，即化为系统M/M/结果（讨论略），c1时即化为M/M/1/ 的有关结果。对多服务台系统， Little 公’s式依然成立，即有：平均等待时间为WQcc)2pcLQ,（5-67）(1而平均逗留时间为WWQ1L（5-68）和M/M/1/类似，若令T表示平衡下相继离去的间隔时间，可以证明其分布函数为P{Tt}1et，t0这表明在统计平衡下相继离去的间隔时间服从参数(0)的负指数分布。因此，统计平衡下M/M/c/排队系统的输出过程与到达过程相同。例工件按Poisson流到达服务台，平均间隔时间为10分钟，假设对每一工件的服务（加工）所需时间服从负指数分布，平均服务时间为8分钟。求：①工件在系统内等待服务的平均数和工件在系统内平均逗留时间；②若要求有90％的把握使工件在系统内的逗留时间不超过30分钟，则工件的平均服务时间最多是多少③若每一工件的服务分两段，每段所需时间服从负指数分布，平均都为4分钟。在这种情况下，工件在系统内的平均数是多少解：该问题属于M/M/1/模型依题意知110.8，，108①LQ4（个）W140（分钟）②由90%W30，117.69，故工件的平均服务时间最多是分钟。，解得10③系统已变为M/M/2/模型，c2。10.4，c=，于是，c4c1jcc12，Lc1p0j!LQ(c1)!(c)2p00.417j0c!(c)3以上结果表明，采用多服务员、单队列的排队系统方案，其各项运行指标都优于多队列的排队系统。事实上，该结论是一般性的，其证明过程如下。例设M/M/1/排队模型中到达速率为，服务速率为2；M/M/2/排队模型中到达速率为，服务速率为。证明：M/M/1/排队模型中的逗留时间少于M/M/2/排队模型中的逗留时间，给出一个直观解释。对排队等待时间有类似结论吗证明：对M/M/2/排队模型，建立平衡方程p0p1（每个服务台服务速率为）p1p02p22pnpn12pn1n2方程有解：pnn2n1p0，其中。pn1，可解得p02又因为，pn也即可得。因此n02Lnpn4(2)(2)n0由LW，我们得到WW(M/M/2)4(2)(2)而对具有服务速率为2的M/M/1/排队系统，有W(M/M/1)12要使M/M/1/排队系统是稳定的，则2，即有W(M/M/2)W(M/M/1)直观的解释是：如果一个人发现在M/M/2/情形中系统是空的，那么有两个服务台没有什么益处。而具有一个更快的服务台会更好。记WQ1WQ(M/M/1)，WQ2WQ(M/M/2)，则WQ1W(M/M/1)12，2(2)WQ22W(M/M/2)1)(2)(2那么WQ1WQ2122即2，而这正是M/M/1/排队系统稳定的要求。故对于排队等待时间也有类似结论。M/M/c/K混合制排队系统M/M/c/K排队系统是一种多服务混合制排队系统，系统有K个位置，独立平行工作的服务台数有c个，cK。当系统中有空位置时，新到的顾客就进人系统排队等待服务，反之，若K个位置已被顾客全部占用，则新到的顾客自动离开。顾客的相继到达时间间隔服从参数为 ( 0)的负指数分布（即按 Poisson流到达），每个服务台的服务时间独立、服从参数为 的负指数分布，到达与服务相互独立。与M/M/c/排队系统分析类似，假定N(t)表示在时刻t系统中的顾客数，则{N(t)，t0}是有限状态E{0,1,2,???,K}上的生灭过程，其参数为,i0,1,???,K1；i,1ic,ii,ci（5-69）cK其分布pn(t)PN(t)nn0,1,2,L的平稳分布记为pn,n0,1,2,???，对任一状态，在统计平衡下，其平衡方程为：状态 离开速率＝进入速率0p0p11p1p02p222p2p13p3。。。c1(c1)pc1pc2cpcccpcpc1cpc1c1nK1cpnpn1cpn1于是对一切 ( )，有1jp0,1jc1,pjj!（5-70）1cjc!jp0,cjK,cc1jKj1其中，p0j!cc!cjc。j0jM/M/c/K是损失制，当系统处于状态K时，顾客不能进入系统，即顾客可进入系统的概率为1 pK，而顾客损失的概率为ppK1Kp0（5-71）c!cKc单位时间内平均损失的顾客数为epK（5-72）单位时间内平均进入系统的顾客数为e(1pK)（5-73）由平稳分布记为 pn,n 0,1,2,???，可得平均等待队长为LQKc)pnp0K(nc)np0K(nc)cc)n(nc!nccncc!nc1cn(nccKcKp0c(nc)np0(nc)nc1c!cccnc1c!nc1c(Kc)(Kc1)p0，c12c!ccp0Kc1Kcc!(1c)21c(1c)(Kc1)c

， c 15-74）其中，c。c以Lc表示平衡时正在被服务的顾客数，则KP{Lcj}pj，j0,1,???,c1；P{Lcc}pjjc于是正在被服务的平均顾客数（或平均被占用的服务台数）为c1KLcnpncpnn0ncc1ncKjp0p0nc1c!cjc1p0n1(n1)!(c1)!c1jK1jp0c!cjcp0j0j!jc1pK（5-75）于是得平均队长LLQLcLQ1pK（5-76）再由Little’s公式，得到WL，WQLQW1ee特别地，对一些特殊排队系统的运行指标，有：(1)M/M/1/K排队系统：(1)j，11K1pj0jK1，1K1K，1L2(K1)K1111K1，K(K1)，1LQ2(K1)2(K)K1，111K1e(1pK)LL，WLQLQ1WW(1pK)Q(1pK)ee对M/M/1/1单服务台损失制系统，读者可自行推导相关数量指标。(2) M/M/c/c多服务台损失制系统：ci①pjjj!，ji0i!

5-77）5-78）5-79）5-80）5-81）5-82）0,1,???,c5-83）这就是着名的 Erlang（埃尔朗）公式。②c个服务台均忙的概率（或顾客损失的概率）cipccc!（5-84）i0i!这就是着名的 Erlang（埃尔朗）损失公式，它在通信网规划与设计中有重要作用。③因为不允许排队，故有cLQ0,LLcnpn(1pc)，n0L1（5-85）WQ0,We其中e(1pc)为有效到达率，在损失制系统中，还常用A(1pc)表示系统的绝对通过能力，用Q 1 pc表示系统的相对通过能力， 它们分别表示单位时间内系统实际可完成的服务次数和被服务的顾客数与请求服务的顾客数的比值。服务台利用率（或信道利用率）为：Lc（5-86）c此外，也可以将M/M/c/系统、M/M/1/系统、M/M/等系统看作是M/M/c/K排队系统的特例，如令c1,K即为M/M/1/系统。例某通信维修站，目前只有一个维修技师。假设需要维修通信设备的到来的规律服从Poisson流，平均每4小时到来一台，而设备修理的时间服从负指数分布，平均每3小时1台。如果要求等待维修的通信设备数占要维修设备数的比例为7％，维修站应安排几个位置供待维修通信设备逗留解：属于M/M/1/K模型依题意知11（台/时），34（台/时），43L(K1)K1，LQL(1p0)1K1，因为11K1，p01LQ7%，解得K1.67。令L例设有一个信息交换中心，信息流为Poisson流，每分钟到达240份，线路输出率是每秒800个字符，信息长度（包括控制字符）近似负指数分布，平均长度176个字符。要使在任何瞬间缓冲器充满的概率不超过，问缓冲器的容量K至少应取多大解：信息平均到达率 240份／分＝4份／秒，

800176

4.546份／秒，。显然按系统 M/M/1/K处理，于是缓冲器充满的概率为(1)KpKK11要使pK0.005，由于p250.009045,p260.0044640.005,所以K26,即缓冲器的容量至少应为26个单位。例设某计算机有4个终端，用户按Poisson流到达，平均每10分钟到达个用户。假定每个用户平均用机时间为20分钟，用机时间服从负指数分布，如果4个终端已被占用，则用户到其它计算机处接受服务，求此系统的各种指标。解：此为M/M/4/4损失制系统，9人/小时，3人/小时，3，顾客损失的概率为44ip44!0.235，i0i!单位时间内实际进入系统的平均顾客数为e (1 p4) 6.885（人/小时），平均忙的终端数为Lc1p4＝（个）。4.具有可变到达率和可变服务率的M/M/1/排队模型一般来说，是状态n在实际中，顾客的到达率和服务率是依系统状态的变化而变化的。的函数。例如，系统中人数较多时，后来的顾客可能不愿意再进入系统；而服务台的服务效率在顾客人数较多时则有可能提高。因此，对单服务台系统，可假设实际的到达率和服务率为：0nan01,2,???n(nb,n11)而对于多服务系统，实际的到达率和服务率可假设为：0nk1n1nkkb，an0nknn1nkn1kk例如，考虑一个参数为nn，n,n01,2,???的到达依赖状态的单服务台等待制M/M/1/1排队系统，其相关的运行指标见下（读者可自己推导一下）：npnp0n1,2,L，p0e，Lnpn，n!n0LQ(n1)pne1，有效到达率epn1e，n0n0n1LLQW11。W，WQ，其中ee有限源简单排队系统M/M/c/m/m系统顾客总数是有限的排队系统称为有限源排队系统，这类排队系统的典型例子就是机器维修模型。如有c个工人共同看管 m(m c)台机器，当机器发生故障时即由工人进行适当的修理，修复后再投入使用，修好后的机器有可能再发生故障。或看作是有m个顾客来到有c个服务台的系统里接受服务，每个顾客接受服务后仍回到原来的总体，还有可能再来。设每个顾客的到达率均为（含义是指单位时间内该顾客来到系统请求服务的次数），且每一顾客在系统外的时间均服从参数为的负指数分布，每个服务台的服务时间均服从参数的负指数分布。服务时间和顾客到达的时间间隔相互独立。由于在系统外的顾客的平均数为mL，故系统的有效到达率为e(mL)。仿前分析，设平稳状态下N的队长分布为pn,n0,1,2,???,m，则状态间的转移速率为：n(mn),n0,1,???,m1；n,1ic,（5-87）nc,cim其状态转移强度图如图所示。m(m1)(mc1)(mc)012c1cc1m1m2ccc图M/M/c/m/m系统转移速率根据生灭过程的极限定理容易得到：记 ,则{pj,0 j m}存在,且mjp0，1jc1,pjj（5-88）mj!jp0，cjm,jcjcc!c1mjmmj!1j其中，p0jjc!cjc。j0jc特别地，当c 1时，有pjm!jp0，j1,???,m(mj)!mm!1j其中，p0。(mj)!j0用L与LQ分别表示在统计平衡下系统平均顾客数和等待服务的顾客数，则有mLQ(jc)pjjcLmjpc1m!j)!jpm!mjjpj0jj1(j1)!(m0c!jccjc(mj)!0或LLQeLQ(mL)W L，WQ LQe e另外，系统运行的其它一些重要指标如下平均忙的服务台数为c1 m

5-89）5-90）5-91）5-92）5-93）Lcjpjcpj（5-94）j1jc不需接受服务的顾客平均数为mLm(mj)pjmL（5-95）j0统计平衡下单位时间内需要服务的顾客平均数为me(mj)pj(mL)（5-96）j0统计平衡下单位时间内平均忙的服务台数为c1mjpjcpjLc（5-97）j1jc统计平衡下单位时间内平均忙的服务台数等于单位时间内需要服务的顾客平均数，即e（5-98）特别地，对单服务台（ c 1）系统，读者可自己推出相关指标。M/M/c/c/m损失制系统假定有m个顾客，c个服务台，当c个服务台都在忙时，这时需要服务的顾客不等待而离开，其它有关假定条件与M/M/c/m/m系统相同。假定N(t)表示时刻t系统中需要服务的顾客数，类似于M/M/c/m/m系统的分析易知{N(t)，t0}是有限状态E{0,1,2,???,c}上的生灭过程，其状态转移速率图如图所示。参数为i(mi)，i0,1,,c1；ii，i1,2,???,c。???m(m1)(mc1)012c1c2c图M/M/c/c/m系统状态转移速率记，pjlimP{N(t)j}，j0,1,???,c，则根据生灭过程的极限定理易知：tmjpjck0

j，j0,1,2,???,c（5-99）m kk该分布{p，jc称为恩格塞特（）分布，而j0}Engsetpc(m) ck 0

mcmk

c（5-100）k称为恩格塞特损失公式，这是损失的概率。特别地，当 m c时，mjpjj，j0,1,2,???,m（5-101）(1)m平均需服务顾客数为mmLjpj（5-102）1j0其它排队系统前面讨论的内容都是按 Poisson流到达与负指数服务时间的生灭过程排队系统， 其主要特点是马尔可夫性，能比较容易地得到队长分布的平稳解。但如果输入过程不是 Poisson流或服务时间不服从负指数分布时，仅知道系统当前的顾客数是不足以推断系统未来状态的。在这一部分里，主要介绍一些特殊排队模型，对有的模型只给出基本运行指标，而不再给出详细的推导。1.M/G/1/排队系统M/G/1/排队系统是一种在通信网设计中经常遇到一般服务的排队系统，它是指顾客按参数(0)的Poisson流到达，即相邻到达的间隔时间序列i，i1独立、同负指数分布()1t0；服务时间序列S，i1，独立，分布为同一般分布etiFtG(t)，t0，记平均服务时间为01tdG(t)。系统中只有一个服务台，容量为无0穷大。顾客到达时，若服务台空闲就立即接受服务，否则就排队等待，并按到达的顺序接受服务，服务完毕后就离开系统，到达与服务彼此独立。我们首先引入概念－工作量，然后用这个概念来帮助分析M/G/1/排队系统。对任一排队系统，定义任意时间t系统的工作量为系统中所有顾客在时间t的剩余服务时间总和。比如：假设系统中有3个顾客，1个顾客已经接受3个时间单位服务，而其所需服务时间是5个时间单位，还有2个在排队，各需6个时间单位的服务时间，则此时的工作量是2＋6＋6＝14。记V为系统的（时间）平均工作量，回忆一下我们在（5-1）给出的基本代价方程，并考虑下面花费规则：若顾客的剩余服务时间是y，则该顾客以速率为y单位时间花费，而无论他是在排队或是正在接受服务。则基本代价方程变为：VaE[一个顾客花费量]以S和WQ分别表示某个顾客的服务时间和花费在排队上的等待时间，由于等待时该顾客的花费速率为常数S，而在接受服务时花费速率为Sx（服务用去时间x后），因此，有：E[一个顾客花费量]＝ESWQS(Sx)dx0所以VaE[SWQ]aE[S2]（5-103）2需要特别指出的是，上述等式是一个基本排队恒等式（和5-2～5-4一样），并对几乎所有的模型有效。另外，若顾客的服务时间和等待时间独立，则由式（5-103）得到：VaE[S]WQaE[S2]（5-104）2对M/G/1/排队系统中任一顾客，由于服务台只有一个，故有：顾客在系统中的等待＝他到达时系统的工作量（5-105）对上式两边同时取数学期望，得WQ=到达者所看到的系统的工作量的平均值又由于是 Poisson到达，所以，对 M/G/1/ 模型，有：WQV再结合式（5-104），a，解得：WQ2(1E[S2]E[S2]，1（5-106）E[S])2(1)而队长L，等待队长LQ，以及平均逗留时间W可以由式（5-106）得到：LQWQ2E[S2]2E[S2]E[S])2(1,2(1)WWQE[S]E[S2]E[S]E[S2]1，1（5-107）2(1E[S])2(1)L2E[S2]E[S]2E[S2]WE[S])2(1)2(1系统是以闲期和忙期交替出现的，以In和Bn分别表示第n个闲期和第n个忙期的长度，n1，因此，在第一个nn(InBn)单位时间里，服务台的空闲时间为In，所以服j1j1务台空闲的时间比例，即 p0，可以表示为：p0limI1I2LInI1I2LInB1B2LBnn显然，上式中的In，B（n1）相互独立，将分子和分母同除以n，并利用大数定n律，我们得到：p0lim(I1I2LIn)n(I1I2LIn)n(B1B2LBn)nnE[I]（5-108）E[I]E[B]其中I和B表示空闲和繁忙时间随机变量。I表示的是顾客离开系统且系统为空到下一个顾客到达的时间，由于是Poisson到达，所以E[I]1（5-109）由式（5-4），知：忙服务台平均数＝E[S]，而忙服务台平均数又等于1p0，所以有p01E[S]（5-110）这样，由（5-108）～（5-110），解得：E[B]E[S]1，1（5-111）E[S]1另一个有意思的量是忙期中被服务的顾客数C，显然E[C]E[B]11，1（5-112）1E[S]1另外，一些特殊的M/G/1/排队系统指标有：(1)M/M/1/排队系统：即G(t)1et,t0，当1时，有pj(1)j0,1,2,（5-113），j???(2)M/D/1/排队系统：即服务时间分布为定长1的定长分布0,t1,G(t)11,t,则当1时，有p01j1ij1kipj(1)ei!pjke，j1i0k1i0i!而且(2)，2L)LQ2(1)2(1W2，（5-114）(1)WQ2(1)2rit(3)M/Hr/1/排队系统：即服务时间分布G(t)1ie为超指数分布，则当i1rii1时，有i1p01,r1rjj1rk1iiipj(1)ipjki，j1i111ii11ik1i1ir其中，i，i1,2,???,r，i0，且i1，而且ii1r2r2iiiiLi1，i11LQ1r2r21iiiii1，i1（5-115）W(1)WQ(1)(4)M/Ek/1/排队系统：即服务时间分布为参数k的k阶埃尔朗分布G(t)1ektk1(kt)i，则当1时，有i0i!p01,k1jj1mii)kCiipj(1)Cij1pjm(1k1，j1i0(1)ijkm1i01其中，，而且k(k1)2，(k1)2L)LQ2k(1)2k(1W1(k1)，WQ(k1)2k(1(1)2k(1))（5-116）而对多服务台的M/G/k系统，目前还没有精确的计算公式计算WQ，但有一个近似公式：WQkE[S2](E[S])k1k1(E[S])n(E[S])k2(k1)!(kE[S])2n!(k1)!(kE[S])n0例考虑一个M/G/1/系统：忙期中的第一个顾客的服务时间服从分布G，其它顾1客有服务分布G2。以C表示忙期中的顾客数，S表示任意顾客的服务时间。试证明：①a0p01E[S]；②E[S]a0E[S1](1a0)E[S2]，其中Si具有分布Gi；③E[S1]用①和②证明忙期的期望长度E[B]1E[S2]④求E[C]。证明：①由于是Poisson到达，假设每个顾客在服务中单位时间花费为1元，则由代价方程得服务的平均顾客数＝

E[S]即1

p0

E[S]② 因为

a0是具有服务分布为

G1的到达者的比例，

1

a0是具有服务分布为

G2的到达者的比例，因此结论成立。③ 我们有E[I]，E[I]1p0E[B]E[I]因此1p0E[S]E[B]p01E[S]由①和②E[S](1E[S])E[S1]E[S]E[S2]或E[S]E[S1]E[S1]E[S2]1代入到E[B]E[S](1E[S])，结果得证。④a01E[C]，推导出1E[S1]E[S2]E[C]1E[S2]M/G/1/排队系统变形1）随机批大小到达的M/G/1/系统假设M/G/1/排队模型中，到达是速率为的Poisson流，但每次到达不是一个顾客，而是随机数量的顾客，服务台仍假设1个，其服务时间具有分布G。以 j，j 1表示任意批到达的顾客数为 j的概率；以N表示批大小的随机变量，即有P{N j} j。因为 a

E[N]，基本的工作量公式变为：VE[N]E(S)WQE(S2)（5-117）2为获得V与WQ的第二个关系，考虑平均顾客数。我们有：他在队列中的等待＝他到达时系统的工作量＋由于他的同批而所需的等待时间对上述等式两边同时取数学期望，得：WQVE[由于同批而需的等待]（5-118）令M是一个大数，则第一个M批中大约有Mj批有顾客数是，1，因此，这Mjj批中来自顾客数是j的批次的顾客比例大约等于jMjjMj，令M，则有：j来自j大小批次的顾客比例jjjjjjE[N]j由此，E[W]E[Wjj（5-119）|j大小的批次]BjBE[N]现在，若该批次中有j个顾客，若某顾客在该批成员中位于第i位，则他需等待前面的1位顾客被服务完，又由于他在各个位置的可能性是一样的，故有：j(i1)E[S]1j1E[S]E[WB|j大小的批次]i1j2将其代入式（ 5-119），得到：E[S](j1)jE[S](E[N2]E[N])E[WB]j2E[N]j2E(N)再由式（5-117）和（5-118），我们得到：E[S](E[N2]E[N])2E(N)E[N]E[S2]2WQ1（5-120）E[N]E[S]注：①使WQ有限的条件是E[N]1，这再次说明了到达速率一定要小于服务E[S]速率（服务台忙时）。② 对确定的E[N]，WQ随Var[N]的增加而增加，表明：单服务台排队“不喜欢”方差。③ 其它的指标

L

，

LQ，以及

W可以由式（

5-119）得到：W WQ

E[S]L

aW

E[N]W

（5-121）LQ

E[N]WQ2）有优先权的

M/G/1/

排队系统有优先权的排队系统就是指将系统中的顾客分成若干类，并根据类的不同给予不同的服务优先的系统。考虑有两类顾客的情形：两类顾客独立地按参数为

1和

2的

Poisson

流到达，分别具有的服务分布为

G1和G2。我们假定第一类顾客有服务优先权，

即若有第一类顾客在排队，则不对第二类顾客服务，当然，若第二类顾客正在接受服务时第一类顾客到了，则服务继续进行直至完成。令WQi(i 1,2)表示第i类顾客的平均等待时间，我们的目标就是计算 WQi。首先，注意到是否采用优先规则或采用什么样的优先规则，系统在任意时刻的总工作量是一样的（只要系统有顾客系统就在忙） ，因此，系统在有优先权规则下的工作量等于在FIFO模式下的工作量。而在 FIFO模式下对M/G/1/ 排队系统有：1 2G(x)1G1(x)2G2(x)（5-122）式（5-122）成立是因为独立的两个Poisson过程的组合仍是Poisson过程，且速率为两个分过程的速率之和。而服务分布G可以对两类顾客服务时间的条件化得到。由此，由M/G/1/排队系统的结果，有优先权的排队系统的工作量V为：VE[S2]2(1E[S])((1)E[S12](2)E[S22])2[1((1)E[S1](2)E[S2])]1E[S12]2E[S22]（5-123）2(11E[S1]2E[S2])其中Si有分布Gi，i1,2。记S及WQ表示任一顾客在队列中的服务和等待，它们在优先模型下是不独立的，这是因为关于S的知识会给予顾客类型的信息也即给予了我们WQ的信息。为此我们分别计算出系统类型1和类型2的平均工作量，记Vi为类型i的平均工作量，正如前面所讨论的，有：ViiE[Si]WiiE[Si2]，i1,2（5-124）Q2如果我们定义ii,VQiE[Si]WQVSiiE[Si2]2则VQi表示类型i排队平均工作量，VSi表示类型i服务平均工作量。现在我们准备计算W1，为此，首先考虑任一类型1顾客的到达情况，我们有：Q他的等待＝他到达时系统的类型1工作量+他到达时正接受服务的类型2工作量两边取数学期望，得：WQ1V1VS21E[S1]W11E[S12]2E[S22]Q221E[S12]2E[S22]（5-125）2(11E[S1])由VV1V2，再结合（5-123）～（5-125），解得：21E[S12]2E[S22]（5-126）WQ1E[S1]2E[S2])(11E[S1])2(1注：①使W1有限的条件是1E[S1]1，它独立于类型1参数；要使W2有限则有QQ1E[S1]2E[S2]1，因为12，一个顾客的平均服务时间为(1)E[S1](2)E[S2]，故上述条件就表示平均到达速率小于平均服务速率。②若有n种类型的顾客，我们可以用类似的方式解出Vj，j1,2,???,n，最后有结果：i1E[S12]???nE[Sn2]，2WQii,n（5-127）???2(11E[S]???jE[S])1jj i 13．G/M/1排队模型G/M/1排队模型是假设顾客相继到达时间间隔服从一般分布G，服务时间服从指数分布并具有速率，服务台个数为1。分析这个模型直接困难来自于系统不能提供关于系统中作为状态空间的顾客数的足够信息。要知道目前所发生的，我们不但需要知道系统中顾客的数量，还要知道上一个到达至现在的流逝时间（因为G无记忆），该模型的求解过程已超出本书范围，这里只给出相关指标：p01)k1，k（5-128）pk(11W1(1)WQW1(1)（5-129）LW(1)LQWQ(1)其中，1xdG(x)，满足方程et(1)dG(t)。004．串联排队模型所谓的串联排队系统是指系统由串联的各个服务台组成，顾客必须依次通过每个台的服务才算服务结束。为方便，我们仅考虑一个由两个服务台组成的串联排队系统：顾客以速率到达第1台，接受服务后加入到第2台前队列，第2台服务完后就离去。假设两个服务台等待容量为无穷大。每个服务台每次服务一个顾客，服务时间服从指数分布，服务速率分别为 1，2。每个服务台服务相互独立，并且与到达过程独立（见图） 。服务台1服务台2离开系统图串联排队为分析这个系统，我们需要明了在这两个服务台的顾客数，为此定义状态对(n,m)——表示有n个顾客在服务台1，m个顾客在服务台2，平衡方程有：状态离开速率＝进入速率0，0p0,02p0,1n，0；n01pn,02pn,1pn1,0m，0；m02p0,m2p0,m11p1,m1n，m；nm012pn,m2pn,m11pn1,m1pn1,m（5-130）我们不直接求解上面的方程组，回忆我们学习M/M/1/系统得到的结果，可知：第1个服务台输出过程仍是参数为的Poisson过程，因而第2台的输入过程还是一个参数为的Poisson过程，因而有：nP{服务台1有n个顾客}＝111类似地，有mP{服务台2有m个顾客}＝122如果服务台1和服务台2的顾客数是独立的随机变量，则有nmPn,m＝11（5-131）1122可以验证（5-131）确实是满足平衡方程组（）的解，因而是极限概率。由式（5-131）可以求出系统的顾客平均数L为：Ln,m(nm)pn,mnmn1m1n11m22（5-132）1 2由此得一个顾客在系统中花费的平均时间为L11（5-133）W12注：上面的结果可以进行推广。考虑有k个服务台的情形：顾客从系统外到达第i,i1,L.k服务台服从参数为ri的负指数分布，然后他们加入到第i服务台队列直至轮到他们被服务，一旦在第i服务台服务完，他们就以概率pij加入到第j，j1,???,k服务台队列。kkpij表示顾客在第i因此，pij1，且1服务台服务完后离开系统的概率。j1j1我们令j表示顾客到j服务台的总速率，则j可以从下面的方程组解出：kjrjipij，i1,???,k（5-134）i1等式（5-134）成立是因为rj是自系统外到达j服务台顾客的速率，而i是顾客离开服务台i的速率（流入速率等于流出速率），ipij是自服务台i到达服务台j的顾客速率。由此，每个服务台顾客数彼此独立且具有形式：P{服务台j有n个顾客}

njj，1n1jj其中 j是服务台j的指数服务速率， j是（5-134）的解，且对所有的 j， j j 1。它等价于证明极限概率 P(n1,n2,???,nk) P{有ni个顾客在服务台 j，j 1,???,k}满足：knjjjP(n1,n2,???,nk)1j1jj而（5-135）的证明可以通过验证它满足该模型的平衡方程得到证明。系统的平均顾客数为kkL服务台j的平均顾客数＝jj1j1jj

5-135）5-136）kk顾客在系统中花费的平均时间可以由LW和rj（为什么不是j）j1j1得到：kj(jj)Wj1（5-137）krj1例考虑两个服务台系统，系统外顾客以Poisson速率4到达服务台1，以Poisson速率5到达服务台 2；服务台1和服务台 2的服务速率分别为 8和10，在服务台 1完成服务后等可能到服务台2和离开系统（即p11