1、第三章 排队论排队现象与排队系统;排队模型与系统参数;排队系统时间参数分布规律;排队系统的生灭过程与状态转移方程;排队系统分析;单服务台负指数分布模型 多服务台负指数分布模型 排队系统优化分析;11、排队现象与排队系统、排队现象与排队系统一、排队现一、排队现象象到达顾客到达顾客 服务内容服务内容 服务机构服务机构病病 人人 诊断诊断/手术手术 医生医生/手术台手术台进港的货船进港的货船 装货装货/卸货卸货 码头泊位码头泊位到港的飞机到港的飞机 降落降落 机场跑道机场跑道电话拨号电话拨号 通话通话 交换台交换台故障机器故障机器 修理修理 修理技工修理技工修理技工修理技工 领取修配零件领取修配零件
2、 仓库管理员仓库管理员上游河水上游河水 入库入库 水闸管理员水闸管理员 2（1）由于顾客到达和服务时间的）由于顾客到达和服务时间的随机性随机性，现实中的排队现象几乎不可避免；现实中的排队现象几乎不可避免；（2）排队过程，通常是一个）排队过程，通常是一个随机过程随机过程，排队论又称排队论又称“随机服务系统理论随机服务系统理论”；3二、排队系二、排队系统统（一）排队服务过程（一）排队服务过程排队系统排队系统顾客源顾客源排队结构排队结构顾客到来顾客到来排队规则排队规则服务规则服务规则顾客离去顾客离去服务机构服务机构。4（二）排队系统的要素及其特征（二）排队系统的要素及其特征1、排队系统的要素：、排队
3、系统的要素：（1）顾客输入过程；）顾客输入过程；（2）排队结构与排队规则；）排队结构与排队规则；（3）服务机构与服务规则；）服务机构与服务规则；52、排队系统不同要素的主要特征：、排队系统不同要素的主要特征：（1）顾客输入过程顾客输入过程顾客源顾客源(总体总体)：有限有限/无限无限;顾客到达方式：顾客到达方式：逐个逐个/逐批逐批;(仅研究逐个情形仅研究逐个情形)顾客到达间隔：顾客到达间隔：随机型随机型/确定型确定型;顾客前后到达是否独立：顾客前后到达是否独立：相互独立相互独立/相互关联相互关联；输入过程是否平稳：输入过程是否平稳：平稳平稳/非平稳非平稳；(仅研究平稳性仅研究平稳性)顾客到达时刻
4、顾客到达时刻 i相继到达间隔时间相继到达间隔时间ti6（2）排队结构与排队规则排队结构与排队规则顾客排队方式：顾客排队方式：等待制等待制/即时制即时制(损失制损失制);排队系统容量：排队系统容量：有限制有限制/无限制无限制;排队队列数目排队队列数目:单列单列/多列多列;是否中途退出是否中途退出:允许允许/禁止禁止;是否列间转移是否列间转移:允许允许/禁止禁止;(仅研究禁止退出和转移的情形仅研究禁止退出和转移的情形)7（3）服务机构与服务规则服务机构与服务规则服务台服务台(员员)数目数目;单个单个/多个多个;服务台服务台(员员)排列形式排列形式;并列并列/串列串列/混合混合;服务台服务台(员员)
5、服务方式服务方式;逐个逐个/逐批逐批;(研究逐个情形研究逐个情形)服务时间分布服务时间分布;随机型随机型/确定型确定型;服务时间分布是否平稳服务时间分布是否平稳:平稳平稳/非平稳非平稳;(研究平稳情形研究平稳情形)112c 12c 12c 8服务台服务台(员员)为顾客服务的顺序为顾客服务的顺序:a)先到先服务先到先服务(FCFS);b)后到先服务后到先服务(LCFS);c)随机服务随机服务;d)优先服务优先服务;9排队模型与系统参数排队模型与系统参数一、排队模一、排队模型型(一一)排队模型表示方法排队模型表示方法1、D.G.Kendall(1953)表示法表示法 X/Y/Z依据排队系统依据排队
6、系统3个主要特征：个主要特征：（1）X 顾客到达间隔时间分布；顾客到达间隔时间分布；（2）Y 服务台（员）服务时间分布；服务台（员）服务时间分布；（3）Z 服务台（员）个数服务台（员）个数（单个或多个并列）（单个或多个并列）；102、国际排队论标准化会议、国际排队论标准化会议(1971)表示法表示法 X/Y/Z/A/B/C（1）A 系统容量限制；系统容量限制；（2）B 顾客源（总体）数目；顾客源（总体）数目；（3）C 服务规则（服务规则（FCFS，LCFS等）；等）；略去后三项，即指略去后三项，即指“X/Y/Z/FCFS”；这里仅研究这里仅研究FCFS的情形；的情形；11(二二)到达间隔和服务
7、时间典型分布到达间隔和服务时间典型分布（1）泊松分布泊松分布 M；（2）负指数分布负指数分布 M；（3）k阶爱尔朗分布阶爱尔朗分布 Ek；（4）确定型分布确定型分布 D；（5）一般服务时间分布一般服务时间分布 G；M/M/1，M/D/1，M/Ek/1；M/M/c，M/M/c/m，M/M/c/N/，。，。(三三)排队模型示例排队模型示例12二、系统参二、系统参数数(一一)系统运行状态参数系统运行状态参数1、系统状态、系统状态 N(t)指排队系统在时刻指排队系统在时刻t时的全部顾客数时的全部顾客数 N(t)，包括包括“排队顾客数排队顾客数”和和“正被服务顾客数正被服务顾客数”；系统状态的可能值如下
8、：系统状态的可能值如下：（1）系统容量无限制，）系统容量无限制，N(t)=0，1，2，;(2)系统容量为系统容量为N时时,N(t)=0,1,2,N;(3)服务台个数为服务台个数为c/损失制损失制,N(t)=0,1,2,c;一般一般,系统状态系统状态N(t)是随机的。是随机的。132、系统状态概率、系统状态概率：(1)瞬态概率瞬态概率Pn(t)表示时刻系统状态表示时刻系统状态 N(t)=n 的概率的概率;(2)稳态概率稳态概率Pn Pn=Pn(t);一般，排队系统运行了一定长的时一般，排队系统运行了一定长的时 间后，系统状态的概率分布不再随时间间后，系统状态的概率分布不再随时间 t变化，即初始时
9、刻（变化，即初始时刻（t=0）系统状态的系统状态的 概率分布概率分布(Pn(0)，n0）的影响将消失。的影响将消失。limt 14(二二)系统运行指标参数系统运行指标参数 评价排队系统的优劣。评价排队系统的优劣。1、队长与排队长、队长与排队长 (1)队长队长:系统中的顾客数（系统中的顾客数（n）；）；期望值期望值 Ls=n*Pn (2)排队长排队长:系统中排队等待服务的顾客数系统中排队等待服务的顾客数;期望值期望值 Lq=Lq=Ls-正被服务的顾客数正被服务的顾客数1()nncncP152、逗留时间与等待时间、逗留时间与等待时间 (1)逗留时间逗留时间:指一个顾客在系统中的全部停留时间指一个顾
10、客在系统中的全部停留时间；期望值，记为期望值，记为 Ws (2)等待时间等待时间:指一个顾客在系统中的排队等待时间；指一个顾客在系统中的排队等待时间；期望值，记为期望值，记为 WqWs=Wq+E服务时间服务时间163、其他相关指标、其他相关指标 (1)忙忙 期期:指从顾客到达空闲服务机构起到服务指从顾客到达空闲服务机构起到服务 机构再次空闲的时间长度；机构再次空闲的时间长度；(2)忙期服务量：忙期服务量：指一个忙期内系统平均完成指一个忙期内系统平均完成 服务的顾客数；服务的顾客数；(3)损失率损失率:指顾客到达排队系统，未接受服务指顾客到达排队系统，未接受服务 而离去的概率；而离去的概率；(4
11、)服务强度：服务强度：=/c ；173、排队系统时间参数分布规律排队系统时间参数分布规律一、顾客到达时间间隔分布一、顾客到达时间间隔分布(一一)泊松流与泊松分布泊松流与泊松分布如果顾客到达满足如下条件如果顾客到达满足如下条件,则称为则称为泊松流泊松流:(1)在不相互重叠的时间区间内，到达顾客数在不相互重叠的时间区间内，到达顾客数 相互独立相互独立(无后效性无后效性).(2)对于充分小的时间间隔对于充分小的时间间隔 内，到达内，到达 1个顾客的概率与个顾客的概率与t无关，仅与时间间隔无关，仅与时间间隔 成正比成正比 (平稳性平稳性)：(3)对于充分小的时间间隔对于充分小的时间间隔 ，2个及以个及
12、以 上顾客到达的概率可忽略不计上顾客到达的概率可忽略不计(普通性普通性)。,ttt)(),(1tottttP,ttt18对泊松流，在时间t系统内有n个顾客的概率服从如下泊松分布 EN(t)=t;Var N(t)=t;单位时间平均到达的顾客数；,2,1,0,0,!)()(ntenttPtnn19若顾客到达间隔若顾客到达间隔T的概率密度为的概率密度为 则称则称T服从负指数分布，分布函数如下：服从负指数分布，分布函数如下：若顾客流是泊松流时，顾客到达的时间间隔若顾客流是泊松流时，顾客到达的时间间隔 显然服从上述负指数分布显然服从上述负指数分布(WHY);ET=1/;Var T=1/2;T=1/(二二
13、)泊松流到达间隔服从负指数分布泊松流到达间隔服从负指数分布,00,0()tetTtft1,00,0()tetTtF t20二、顾客服务时间分布二、顾客服务时间分布(一一)负指数分布负指数分布(1)对一个顾客的服务时间对一个顾客的服务时间Ts，等价于相邻两个顾客等价于相邻两个顾客离开排队系统的时间间隔。若离开排队系统的时间间隔。若Ts服从负指数分布，服从负指数分布，其概率密度和分布函数分别为其概率密度和分布函数分别为 则则 ETs=1/;Var Ts=1/2;Ts=1/(2)ETs=1/：每个顾客的平均每个顾客的平均(期望期望)服务时间；服务时间；:单位时间服务的顾客数，平均单位时间服务的顾客数
14、，平均(期望期望)服务率；服务率；,00,0()tsetTtft1,00,0()tsetTtFt21(二二)爱尔朗爱尔朗(Erlang)分布分布tkkektkktb)!1()()(1 (1)设设v1,v2,vk是是k个相互独立的随机变量个相互独立的随机变量,服从服从相同参数相同参数1/k的负指数分布的负指数分布,则则:T=v1+v2+vk的的概率密度为概率密度为 称称T服从服从k阶爱尔朗分布。阶爱尔朗分布。(2)ET=1/;Var T=1/(k2)(3)T的意义之一的意义之一:k个串联服务台的总服务时间！个串联服务台的总服务时间！224、排队系统的生灭过程与状态转移方程、排队系统的生灭过程与状
15、态转移方程一、排队系统的生灭过程一、排队系统的生灭过程(一一)生灭过程的背景与定义生灭过程的背景与定义 设某系统具有状态集设某系统具有状态集S=0,1,2,或或S=0,1,2,k,N(t)表示系统在时刻表示系统在时刻 t(t=0)的状态。的状态。若在若在N(t)=n的条件下，随机过程的条件下，随机过程N(t),t=0满足满足以下条件以下条件:(1)N(t+t)转移到转移到“n+1”的概率为的概率为n(t);(2)N(t+t)转移到转移到“n-1”的概率为的概率为n(t);(3)N(t+t)转移到转移到其他状态其他状态“S-n+1,n-1”的概的概 率为率为o(t)(高阶无穷小高阶无穷小);则称
16、则称随机过程随机过程N(t),t=0为生灭过程。为生灭过程。n，n，t (？)23(二二)生灭过程状态变化的性质生灭过程状态变化的性质(1)在无穷小在无穷小 t内内,系统或生长系统或生长1个个;或灭亡或灭亡1个个;或既或既 不生长又不灭亡不生长又不灭亡（概率概率:1-n(t)-n(t)）;(2)系统生长一个的概率系统生长一个的概率n(t)与与 t有关，而与有关，而与t无无 关关;与系统当前状态与系统当前状态n有关，而与以前的状态无关；有关，而与以前的状态无关；(3)系统灭亡一个的概率系统灭亡一个的概率n(t)与与 t有关，而与有关，而与t无无 关关;与系统当前状态与系统当前状态n有关，而与以前
17、的状态无关；有关，而与以前的状态无关；马尔可夫性质马尔可夫性质24(三三)排队系统的生灭过程排队系统的生灭过程顾客到达顾客到达“生生”；顾客离开顾客离开“灭灭”服务机构顾客聚顾客散顾客到达顾客到达顾客离去顾客离去n，n，(1)生灭过程示意生灭过程示意25 若排队系统具有下列性质若排队系统具有下列性质:(1)顾客到达为泊松流，时间间隔服从参顾客到达为泊松流，时间间隔服从参 数为数为n的负指数分布的负指数分布;(2)顾客服务时间服从参数为顾客服务时间服从参数为 n的负指的负指 数分布数分布;则排队系统的随机过程则排队系统的随机过程N(t),t=0具有马具有马 尔可夫性质尔可夫性质,为为一个生灭过程
18、一个生灭过程.(2)生灭过程定义生灭过程定义26二、排队系统的状态转移方程二、排队系统的状态转移方程(一一)排队系统状态的概率及其分布排队系统状态的概率及其分布 (1)瞬态概率瞬态概率Pn(t)表示时刻系统状态表示时刻系统状态N(t)=n的概率的概率;(2)稳态概率稳态概率Pn Pn=Pn(t);limt 一般，稳态概率一般，稳态概率Pn的分布，是分析计算的分布，是分析计算排队系统运行优劣的基础。排队系统运行优劣的基础。27(二二)排队系统状态概率的微分差分方程排队系统状态概率的微分差分方程00 01 1()()();0,0dP tP tPttndt1111()()()()();0,0nnnn
19、nnnndPtP tP tPttndt 推导过程：推导过程：P 323求解可得瞬态概率求解可得瞬态概率Pn(t)28(三三)排队系统状态转移方程排队系统状态转移方程求解可得稳态概率求解可得稳态概率Pn0 01 1()()0P tPt1111()()()();0nnnnnnnP tP tPtn 0()0;dP tdt()0ndPtdt令令则则排队系统状态转移方程排队系统状态转移方程29(四四)排队系统状态转移图排队系统状态转移图012nn-10122n1nn1231nn1n在任意状态在任意状态n达到稳态平衡的条件：达到稳态平衡的条件：产生该状态的平均速率产生该状态的平均速率 =该状态转变成其他状
20、态的平均速率该状态转变成其他状态的平均速率 （流入（流入=流出）流出）30012nn-10122n1nn1231nn1n0011pp31012nn-10122n1nn1231nn1n1112200)(ppp32012nn-10122n1nn1231nn1n2223311)(ppp33012nn-10122n1nn1231nn1n11122)(nnnnnnnppp34012nn-10122n1nn1231nn1nnnnnnnnppp)(111135三、三、排队系统稳态概率排队系统稳态概率Pn的求解的求解,2,1,01210121012101210120120101npCpCppppppnnnnn
21、nnnnnnn则记361100110001,111)1(1nnnnnnnnnnnnCCpCppCpCpp37对一般排队系统，均有下式成立eqqessLWLW,eqsqsLLWW,10nnneP 其中有效到达率为四、四、排队系统性能参数的一般关系排队系统性能参数的一般关系 Little 公式公式3839G/G/1和和G/G/c队列队列单位时间个客户到达，一个服务器单位时间能够服务个客户，客户到达时间间隔和服务时间任意分布，1个或者c个服务器，无限等待位。G/G/1或者G/G/c。定义 1：客户不断累积，越来越多 1：排队系统达到平稳态，系统不随时间变化=1：除非客户到达和离开时间固定且匹配，否则
22、无稳态。/c3940一些定义N(t)系统在时刻系统在时刻t的规模的规模（队长（队长系统中人数）系统中人数）Nq(t)队列在时刻队列在时刻t的规模的规模（队列（队列队列中等待数）队列中等待数）Ns(t)时刻时刻t正在接受服务的客户数量正在接受服务的客户数量pn(t)PN(t)=npn稳态稳态pn(t)，即，即limtpn(t)L系统平均规模系统平均规模Lq队列平均规模队列平均规模W客户在系统内平均耗时客户在系统内平均耗时Wq客户在队列中平均耗时客户在队列中平均耗时0()qqnnLE Nnc p0nnLE Nnp WE TqqWE T4041Little等式(Littles law)Little等
23、式（Littles formula）系统规模=客户达到率客户在系统中消耗时间“系统”可以是整个排队系统，也可以是一个队列对于队列，这个结果适用于排队模型，与客户到达模式和服务模式无关！LWqqLW41单服务器G/G/1排队系统 客户在系统时间=排队时间+服务时间 正在接受服务的客户数 同时，服务器繁忙的概率为 pb=1-p0=/（P0无顾客概率）421/qWW()(1/)qqLLWW 单服务器，稳态下/不可能大于1。0111(1)1qnnnnnnLLnpnppp 4243多服务器G/G/c排队系统 每台服务器繁忙的概率为pb=/c共c个服务器，平均/个客户接受服务，平均每个服务器/c个客户，或
24、者单位时间中/c服务器繁忙/很重要。定义=/为一个排队系统的提交负载提交负载（offered load）(服务强度服务强度)：服务器完成一个客户服务的时间平均到达的客户数量1/qWW()(1/)qqLLWW 4344G/G/c排队系统总结排队系统总结提交负载提交负载（服务强度）（服务强度）Little 等式等式Little 等式等式服务器繁忙概率服务器繁忙概率接受服务的客户数量接受服务的客户数量G/G/1系统为空的概率系统为空的概率c/WLqqWL/bpc/r 01p 44例：某快餐店在高峰时每小时到达40位客人，每个客人平均在柜台用5.5分钟点餐。至少需要设置多少个柜台？每小时到达40位客人
25、，假设有c个柜台，则柜台繁忙概率/c=40/c(60/5.5)405.5/60，客人才不至于在柜台累积 c至少为445/1bpc4546例 某公司安排接线员接听顾客电话。由于人手不够，顾客必须等待才能被接听。公司希望顾客平均等待时间为75秒，估计每分钟打进3个客户电话。问需要多少线路用于保持电话等待？Wq=Lq，Lq=375/60=3.75，需要4条线路4647例 考虑一个M/G/1/K排队系统，其阻塞概率为pK=0.1，并且=1，L=5。计算eff，W，Wq，p0和eff。0(1)0.9,5/0.95.561/4.56/0.910.1effiKieffqeffeffeffppWL WWWp
26、47生灭过程（Birth-and-death process）考虑一个群体（比如，海岛上的海鸟群），群体数量取决于两种事件，出生和死亡。当群体个数为n时，n表示此时的出生率，即在一小段时间h，出生一个个体的概率为nh+o(h)；n表示此时的死亡率，即在一小段时间h，死亡一个个体的概率为nh+o(h)。这个群体可以用一个生灭过程来描述。4848定义：考虑一个连续参数的离散随机过程X(t):t0，取值空间为0,1,2,.。如果X(t)=n，则称这个随机过程描述的系统在时间t处于状态En，n=0，1，2，.。如果出生速率n和死亡速率n满足以下条件，则称这个随机过程为生灭过程。1.状态转移只能EnEn
27、+1，n=0，1，2，.。2.如果在时间t系统位于状态En，则在一小段时间t,t+h)发生状态转移EnEn+1的概率是nh+o(h)。3.如果在时间t系统位于状态En，则在一小段时间t,t+h)发生状态转移EnEn-1的概率是nh+o(h)。4.如果在时间t系统位于状态En，则在一小段时间t,t+h)发生其它转移的概率o(h)。4949令Pn(t)=PX(t)=n在时间t+h，系统仍然在状态En的概率Pn(t+h)，有四种情况 在时间t系统位于状态En，t,t+h)状态没有发生改变 在时间t系统位于状态En-1，t,t+h)发生一个出生事件 在时间t系统位于状态En+1，t,t+h)发生一个死
28、亡事件 在时间t系统位于上述状态以外的状态5050情况1发生的概率情况2发生的概率情况3发生的概率情况4发生的概率综合4种情况51()(1()(1()()(1)()nnnnnnP tho hho hP thho h1111()()()()nnnnPtho hPtho h1111()()()()nnnnPtho hPtho h()o h1111()()(1)()()()()()()nnnnnnnnP thP thho hPtho hPtho ho h51整理取h0对n1当n=0初始条件，t=0时，系统位于状态Ei，所有n=0，称为纯生过程，“人口爆炸”如果纯生过程n=，即为泊松过程所有n=0，称
29、为纯灭过程，“种群消亡”521111()()()()()()()nnnnnnnnnP thP to hP tPtPthh111100()()()limlim()()()()nnnnnnnnnhhP thP to hP tPtPthh1111()()()()()nnnnnnnndP tP tPtPtdt 0001 1()()()dP tP tP tdt(0)1,(0)0ijPP52稳态生灭过程当t，系统状态Pn(t)不随时间改变。称这种状态为稳态（Stationary 或者 steady-state）记 ，稳态下稳态下对任意一个状态，“进入该状态的概率=退出该状态的概率”53()lim0ntdP
30、 tdtlim()nntP tp53对状态0，对其它任意一个状态i，解线性方程组可得稳态生灭过程各状态概率当有无限个状态，生灭过程的稳态解为生灭过程有稳态解的必要和充分条件为540011pp1111jjjjjjjppp00111111jjjjjjjppppp101niniipp01nnp 110111niniip1111ninii 54例 一个单服务器排队系统，无等待位。假设客户到达是一个速率为的泊松过程，服务器服务时间服从指数分布，服务速率为，即单位时间服务1/个客户。求解：没有等待位，系统只有两个状态，“0”和“1”根据生灭过程方程55101001()()()()()()dP tP tP
31、tdtdP tP tP tdt 01()()1P tP t并且55解微分方程稳态，t。直接求解稳态，用“流入=流出”计算稳态状态概率56()00()11()(0)()(0)ttP tPeP tPe0011lim(),lim()ttPtpP tp01011pppp01,pp5657例 考虑一个单服务器的生灭过程系统中。系统只能够容纳3个客户，到达速率(012)=(3,2,1)，服务（死亡）速率为(123)=(1,2,2)。计算稳态下各状态概率，并计算有效到达速率 和客户等待时间W求解生灭过程(p0,p1,p2,p4)=(0.117647,0.352941,0.352941,0.176471)ef
32、fiip1.4117651.588236/1.125effieffLipWL57无限源的排队系统无限源的排队系统假定假定顾客来源是无限的顾客来源是无限的，顾客到达间隔时间服从负指顾客到达间隔时间服从负指数分布且不同的到达间隔时间相互独立数分布且不同的到达间隔时间相互独立，每个服务台每个服务台服务一个顾客的时间服从负指数分布，服务一个顾客的时间服从负指数分布，服务台的服务服务台的服务时间相互独立，服务时间与间隔时间相互独立。时间相互独立，服务时间与间隔时间相互独立。1 1 M MM M1 1 系统系统设顾客流是参数为设顾客流是参数为的最简单流，的最简单流，是单位时间内是单位时间内平均的顾客人数只
33、有一个服务台，服务一个顾客的服平均的顾客人数只有一个服务台，服务一个顾客的服务时间务时间服从参数为服从参数为的负指数分布平均服务时间的负指数分布平均服务时间为记为记在服务台忙时，单位时间平均服务在服务台忙时，单位时间平均服务58完的顾客数为完的顾客数为称称为服务强度为服务强度 用用N(t)表示在时刻表示在时刻t顾客在系统中的数量顾客在系统中的数量(包括等待服包括等待服务的和正在接受服务的顾客务的和正在接受服务的顾客)证明系统证明系统组成生灭过程组成生灭过程由于顾客的到达是最简单流，参数由于顾客的到达是最简单流，参数 在长度为在长度为的时间内的时间内有一个顾客到达的概率为有一个顾客到达的概率为5
34、9没有顾客到达的概率为没有顾客到达的概率为到达到达2个或个或2个以上顾客的概率为个以上顾客的概率为 在在服务台忙时服务台忙时(总认为只要系统内有顾客，服务员就总认为只要系统内有顾客，服务员就得进行服务得进行服务)，顾客接受服务完毕离开系统的间隔时间为顾客接受服务完毕离开系统的间隔时间为60独立的、参数为独立的、参数为的负指数分布所以的负指数分布所以在系统忙时，输在系统忙时，输出过程为一最简单流出过程为一最简单流，参数为，参数为，于是当系统忙时，在于是当系统忙时，在时间区间内时间区间内1个顾客被服务完的概率为个顾客被服务完的概率为没有顾客被服务完的概率为没有顾客被服务完的概率为两个或两个或两个以
35、上顾客被服务完的概率为两个以上顾客被服务完的概率为且且顾客数无关，与微小时问区间的起点无关顾客数无关，与微小时问区间的起点无关与系统的与系统的对任意给定的对任意给定的微小增量微小增量假设假设先考虑先考虑ji十十1的情况，的情况，当当时时P 时间内恰好到达时间内恰好到达1个顾客而没个顾客而没有顾客被服务完或恰好有有顾客被服务完或恰好有k个顾客到个顾客到达并且达并且k-1个顾客被服务完，个顾客被服务完，61p 时间内恰好到达时间内恰好到达1个顾客而没有顾客被服务完个顾客而没有顾客被服务完 十十 时间内到达时间内到达k个顾客而服务完个顾客而服务完k-1个顾客，个顾客，当当i0 时时6263由以上结果
36、，可知由以上结果，可知是一生灭过程，并且是一生灭过程，并且由生灭过程求平稳解公式，得由生灭过程求平稳解公式，得由假设由假设则则从而平从而平稳分布稳分布为为64服务台空闲的概率，而服务台空闲的概率，而是排队系统中没有顾客的概率，也就是是排队系统中没有顾客的概率，也就是恰好是服务台忙的概率。恰好是服务台忙的概率。利用平稳分布可以求统计平衡条件下的利用平稳分布可以求统计平衡条件下的平均队长平均队长L、平均等待队长平均等待队长Lq、顾客的平均等待时间顾客的平均等待时间Wq平均逗留时间平均逗留时间W等等用用N表示在统计平稳下系统的顾客数，表示在统计平稳下系统的顾客数，平均队长平均队长L是是N的数学期望的
37、数学期望65 用用Nq表示在统计平衡时，排队等待的顾客数表示在统计平衡时，排队等待的顾客数，它的数，它的数学期望学期望LqE(Nq)就是在等待服务的平均顾客人数就是在等待服务的平均顾客人数 现在来现在来求平均等待时间求平均等待时间Wq，当一个顾客进入系统时，当一个顾客进入系统时，系统中已有系统中已有n个顾客的概率为个顾客的概率为 pn，每个顾客的平均服务时，每个顾客的平均服务时间为间为所以他平均等待时间为所以他平均等待时间为因此因此66 再求顾客的再求顾客的平均逗留时间平均逗留时间(平均等待时间再加上平均平均等待时间再加上平均服务时间服务时间)W 例例7.2.1 某火车站的售票处设有一个窗口若
38、购票者某火车站的售票处设有一个窗口若购票者是以最简单流到达，平均每分钟到达是以最简单流到达，平均每分钟到达1人，假定售票时间人，假定售票时间服从负指数分布，平均每分钟可服务服从负指数分布，平均每分钟可服务2人，试研究售票窗人，试研究售票窗口前排队情况口前排队情况解解 由题设由题设(人分人分)，(人分人分)，67平均队长平均队长(人人)平均等待队长平均等待队长人人)平均等待时间平均等待时间(分分)平均逗留时间平均逗留时间(分分)超过超过5人的概率为人的概率为顾客不需要等待的概率为顾客不需要等待的概率为等待的顾客人数等待的顾客人数68 例例7.2.2 在某工地卸货台装卸设备的设计方案中，有在某工地
39、卸货台装卸设备的设计方案中，有三个方案可供选择，分别记作甲、乙、丙。目的是三个方案可供选择，分别记作甲、乙、丙。目的是选取选取使总费用最小的方案使总费用最小的方案，有关费用，有关费用(损失损失)如下表所示：如下表所示：方案方案每天固每天固定费用定费用每天可变操每天可变操作费作费(元元)每小时平均每小时平均装卸袋数装卸袋数甲甲乙乙丙丙10013025010015020010002000600069 设设货车按最简单流到达，平均每天货车按最简单流到达，平均每天(按按10小时计算小时计算)到到达达15车，每车平均装货车，每车平均装货500袋袋，卸货时间服从负指数分卸货时间服从负指数分布每辆车停留布每
40、辆车停留1小时的损失为小时的损失为10元元于方案于方案解解 平均到达率平均到达率车小时，车小时，服务率服务率依赖依赖由由(7.2.6)，1 辆车在系统内平均停留时间为辆车在系统内平均停留时间为70 每天货车在系统停留的平均损失费为每天货车在系统停留的平均损失费为W(平均停留时平均停留时间间)1015(总车辆总车辆)，每天的实际可变费用每天的实际可变费用(如燃料费等如燃料费等)为为(可变操作费天可变操作费天)设备忙的概率设备忙的概率cp(元天元天)而而所以每个方案的费用综合如下表所示所以每个方案的费用综合如下表所示71从上表知从上表知方案乙的总费用最省。方案乙的总费用最省。例例7.2.3 要购置
41、计算机，有两种方案甲方案是购进要购置计算机，有两种方案甲方案是购进一大型计算机，乙方案是购置一大型计算机，乙方案是购置n台小型计算机每台小型台小型计算机每台小型计算机是大型计算机处理能力的计算机是大型计算机处理能力的1/n 倍设要求上机的题倍设要求上机的题从平均逗留时间、等待时间看，应该选择哪一个方案从平均逗留时间、等待时间看，应该选择哪一个方案目是参数为目是参数为的最简单流，大型计算机与小型计算机计的最简单流，大型计算机与小型计算机计算题目的时间是负指数分布，大型计算机的参数是算题目的时间是负指数分布，大型计算机的参数是试试解解 设设按甲方案，购大型计算机按甲方案，购大型计算机平均等待时间平
42、均等待时间平均逗留时间平均逗留时间按乙方案，购按乙方案，购n台小型计算机，每台小计算机的题目台小型计算机，每台小计算机的题目72到达率为到达率为服务率为服务率为平均等平均等待时间待时间平均逗平均逗留时间留时间所以只是从平均等待时间，平均逗留时间考虑，应所以只是从平均等待时间，平均逗留时间考虑，应该该购置大型计算机购置大型计算机例例7.2.4 设船到码头，在港口设船到码头，在港口停留单位时间损失停留单位时间损失cI元元，进港船只是最简单流，参数为进港船只是最简单流，参数为，装卸时间服从参数为，装卸时间服从参数为的负指数分布的负指数分布，服务费用为服务费用为是一个正常数是一个正常数元元，73求使求
43、使整个系统总费用损失最小的服务率整个系统总费用损失最小的服务率解解 因为平均队长因为平均队长的损失费的损失费为为所以船在港口所以船在港口停留停留服务费用为服务费用为因此因此总费用总费用为为使使F达到最小，先求达到最小，先求F的导数的导数求求让让解出解出因为因为74最优服务率是最优服务率是当当时时 平均队长平均队长L、平均等待队长、平均等待队长Lq、平均逗留时间、平均逗留时间W、平、平均等待时间均等待时间Wq是排队系统的重要特征是排队系统的重要特征这些指标反映了这些指标反映了排队系统的服务质量，是顾客及排队系统设计者关心的几排队系统的服务质量，是顾客及排队系统设计者关心的几个指标个指标由由(7.
44、2.3)到到(7.2.6)的公式，得到这四个指标之间的公式，得到这四个指标之间的关系的关系(7.2.8)75 这两组关系式，可以作这样直观解释：当系统内有顾这两组关系式，可以作这样直观解释：当系统内有顾客时，平均等待队长客时，平均等待队长Lq应该是平均队长应该是平均队长L减减1，当系统内，当系统内没有顾客时，平均等待队长没有顾客时，平均等待队长Lq与平均队长与平均队长L相等相等，所以，所以单位时间内平均进入系统的顾客为单位时间内平均进入系统的顾客为个个 每个顾客在系每个顾客在系Wq个顾客在等待服务个顾客在等待服务统内平均逗留统内平均逗留W单位时间因此系统内平均有单位时间因此系统内平均有W个顾客
45、个顾客同样理由，系统内平均有同样理由，系统内平均有(7.2.8)式在更一般的系统也成立，通常称为式在更一般的系统也成立，通常称为Little公式公式2 MM1k系统系统 有些系统容纳顾客的数量是有限制的有些系统容纳顾客的数量是有限制的例如候诊室只例如候诊室只能容纳能容纳 k个就医者第个就医者第k十十1个顾客到来后，看到候诊室已个顾客到来后，看到候诊室已经坐满了，就自动离开，不参加排队经坐满了，就自动离开，不参加排队76共有共有k个位置可供进入系统的顾客占用个位置可供进入系统的顾客占用，一旦，一旦k个位置已个位置已被顾客占用被顾客占用(包括等待服务和接受服务的顾客包括等待服务和接受服务的顾客)，
46、新到的顾，新到的顾客就自动离开服务系统永不再回来如果系统中有空位置，客就自动离开服务系统永不再回来如果系统中有空位置，新到的顾客就进入系统排队等待服务，服务完后离开系新到的顾客就进入系统排队等待服务，服务完后离开系统统假定一个假定一个排队系统排队系统有有一个服务台一个服务台，服务时间是负指数服务时间是负指数分布，参数是分布，参数是顾客以最简单流到达，参数为顾客以最简单流到达，参数为系统中系统中 用用N(t)表示时刻表示时刻t系统中的顾客数系统中的顾客数，系统的，系统的状态集合状态集合为为S0，1，2，-k与与MM1的证明方法一的证明方法一样，可以证明样，可以证明是个有限生灭过程，且有是个有限生
47、灭过程，且有77平均队长平均队长分两种情况：分两种情况：78时，时，时，时，79平均等待队长平均等待队长 pk是个重要的量，它称为损失概率，是个重要的量，它称为损失概率，即当系统中有即当系统中有k个顾个顾客时，新到的顾客就不能进入系统客时，新到的顾客就不能进入系统单位时间平均损失的单位时间平均损失的顾客数为顾客数为单位时间内平均真正进入系统的顾客数为单位时间内平均真正进入系统的顾客数为80由由Little公式，可以求得公式，可以求得平均逗留时间、平均等待时间平均逗留时间、平均等待时间81平均服务强度平均服务强度这是实际服务强度，就是服务台正在为顾客服务的概率这是实际服务强度，就是服务台正在为顾
48、客服务的概率而而不是服务强度，因为有一部分不是服务强度，因为有一部分顾客失掉了。顾客失掉了。例例7.2.5 一个理发店只有一个理发师，有一个理发店只有一个理发师，有3个空椅供等个空椅供等待理发的人使用设顾客以最简单流来到，平均每小时待理发的人使用设顾客以最简单流来到，平均每小时5人理发师的理发时间服从负指数分布，平均每小时人理发师的理发时间服从负指数分布，平均每小时6人人.试求试求L，Lq，W，Wq解解 5(人小时人小时)，6(人小时人小时)k4，82用公式用公式(7.2.10)，(7.2.11)，(7.2.12)，(7.2.13)得到得到83例例7.2.6 给定一个给定一个MM1/k 系统，
49、具有系统，具有10(人小时人小时)，30(人小时人小时)，k2管理者想改进管理者想改进服务机构服务机构方案甲是增加等待空间，使方案甲是增加等待空间，使k3方案乙是将方案乙是将平均服务率提高平均服务率提高40(人小时人小时)设服务每个顾客的设服务每个顾客的平均收益不变问哪个方案获得更大收益，当平均收益不变问哪个方案获得更大收益，当增加到增加到每小时每小时30人，又将有什么结果人，又将有什么结果?解解 由于服务每个顾客的平均收益不变，因此服务机由于服务每个顾客的平均收益不变，因此服务机构构单位时间的收益与单位时间内实际进入系统的平均人数单位时间的收益与单位时间内实际进入系统的平均人数nk成正比成正
50、比(注意，不考虑成本注意，不考虑成本)方案甲：方案甲：k384方案乙：方案乙：k2因此扩大等待空间收益更大因此扩大等待空间收益更大当当增加到增加到30人小时时，人小时时，这时方案甲有这时方案甲有85而方案乙是把而方案乙是把提高到提高到40人小时人小时30(人小时人小时)时，时，提高服务效益的收益比提高服务效益的收益比扩大等待空间的收益大扩大等待空间的收益大所以当所以当3 MMc系统系统 现在来讨论多个服务台情况现在来讨论多个服务台情况假设系统有假设系统有c个服务台，个服务台，顾客到达时，若有空闲的服务台便立刻接受服务若没有顾客到达时，若有空闲的服务台便立刻接受服务若没有空闲的服务台，则排队等待
