第六章排队论

1、第六章第六章 随机服务系统理论随机服务系统理论确定型只是随机现象的特例确定型只是随机现象的特例排排 队队 论论Queuing TheoryQueuing Theory26.1 随机服务系统基础随机服务系统基础 系统的输入与输出是随机变量系统的输入与输出是随机变量 A.k.Erlang 于于19091920年发表了一系列根据话务量计年发表了一系列根据话务量计算电话机键配置的方法，为随机服务理论奠定了基础算电话机键配置的方法，为随机服务理论奠定了基础 又称为又称为排队论排队论(Queuing Theory)或或拥塞理论拥塞理论(Congestion Theory) 应用广泛应用广泛 交通行业应用：

2、交叉口交通行业应用：交叉口/高速收费站高速收费站/机场航班机场航班3顾客来源顾客来源队队 列列服务机构服务机构排队系统排队系统顾客顾客服务完离开服务完离开排队系统的三个基本组成部分排队系统的三个基本组成部分. .输入过程输入过程 (顾客按照怎样的规律到达顾客按照怎样的规律到达);排队规则排队规则 (顾客按照一定规则排队等待服务顾客按照一定规则排队等待服务);服务机构服务机构 (服务机构的设置服务机构的设置,服务台的数量服务台的数量,服务的服务的方式方式,服务时间分布等服务时间分布等)6.1.1 基本要素基本要素4输入过程输入过程 顾客源顾客源 有限 无限 经常性的顾客来源经常性的顾客来源 顾客

3、到达间隔时间: 到下一个顾客到达的时间 服从某一概率分布（确定型/随机型） 顾客的行为假定顾客的行为假定 在未服务之前不会离开 当看到队列很长的时候离开 从一个队列移到另一个队列5排队服务规则排队服务规则 队列容量队列容量 有限有限/无限无限 排队规则排队规则 损失制损失制 等待制：等待制：先到先服务(FCFS)，后到先服务(LCFS)，随机服务(RS)，优先权服务(PS) 混合制 逐个到达，成批服务；成批到达，逐个服务6 单通道和多通道单通道和多通道 并联服务并联服务 串联服务串联服务 串并联服务串并联服务服务机构的组织方式与服务方式服务机构的组织方式与服务方式123顾客到达顾客到达顾客离开

4、顾客离开123顾客到达顾客到达顾客离开顾客离开顾客离开顾客离开顾客离开顾客离开银行服务银行服务-叫号系统叫号系统123顾客到达顾客到达顾客到达顾客到达顾客到达顾客到达顾客离开顾客离开顾客离开顾客离开顾客离开顾客离开机场安全检查通道机场安全检查通道7u常用符号常用符号 M泊松分布（负指数分布）泊松分布（负指数分布） Ekk阶爱尔朗分布阶爱尔朗分布 D确定型分布确定型分布 G一般分布一般分布 M/M/1/K/FCFSM/M/1/K/FCFS顾客到达服从泊松分布，顾客的服务时顾客到达服从泊松分布，顾客的服务时间服从负指数分布，单通道，系统容量有限（间服从负指数分布，单通道，系统容量有限（K K）而顾

5、客源）而顾客源无限，先到先服务的排队系统无限，先到先服务的排队系统顾客到达时间间隔分布顾客到达时间间隔分布/ /服务时间分布服务时间分布/ /服务台数目服务台数目/ /排队系统允许的最大顾客容量排队系统允许的最大顾客容量/ /顾客总体数量顾客总体数量/ /排队规则排队规则 ( (扩充的扩充的Kendall Kendall 符号符号)- )- Kendalls notation 6.1.2 符号表示符号表示8队长队长：系统中的顾客数量的期望值排队长排队长：系统中正在等待的顾客数量期望值逗留时间逗留时间：顾客在排队系统中的总时间（等待时间与被服务时间之和）的期望值排队时间排队时间：顾客的排队等待时

6、间的期望值忙期忙期：服务机构连续繁忙的时间长度服务强度服务强度：顾客到达率的期望值与服务率的期望值之比6.1.3 排队系统营运指排队系统营运指标标9 服务系统存在来自两个矛盾方面的要求服务系统存在来自两个矛盾方面的要求 顾客希望服务质量好，如排队等待时间短，损失率低顾客希望服务质量好，如排队等待时间短，损失率低 系统运营方希望设备利用率高系统运营方希望设备利用率高 给用户一个经济上能够承受的满意的质量给用户一个经济上能够承受的满意的质量 哪些系统特性会影响系统的性能？哪些系统特性会影响系统的性能？ 服务机构的组织方式与服务方式服务机构的组织方式与服务方式 顾客的输入过程和服务时间分布顾客的输入

7、过程和服务时间分布 系统采用的服务规则系统采用的服务规则 与服务系统性能相关的特性与服务系统性能相关的特性6.2 顾客到达分布和服务时间分布顾客到达分布和服务时间分布 6.2.1 概述概述顾客的服务时间由于多种原因具有不确定性，最好的描述顾客的服务时间由于多种原因具有不确定性，最好的描述方法就是概率分布；同样顾客到达的间隔时间也服从一定方法就是概率分布；同样顾客到达的间隔时间也服从一定的概率分布的概率分布顾客到达时刻开始服务时刻服务终结时刻t1234 1 2 3 4w2w3h1h2h3h4空123411频率%3020102468到达间隔时间（分钟）若统计区间分得越细，样本越多，则经验分布的轮廓

8、越接若统计区间分得越细，样本越多，则经验分布的轮廓越接近曲线近曲线经验分布一般采用直方图来表示，如下图经验分布一般采用直方图来表示，如下图Frequency Distribution服务时间和到达间隔时间服从什么分布？可以先通过统计服务时间和到达间隔时间服从什么分布？可以先通过统计得到经验分布，然后再做理论假设和检验得到经验分布，然后再做理论假设和检验126.3.2 输入过程（顾客到达分布）输入过程（顾客到达分布）可用相继到达顾客的间隔时间描述，也可以用单位时间内到达可用相继到达顾客的间隔时间描述，也可以用单位时间内到达的顾客数描述的顾客数描述 间隔时间服从定长分布间隔时间服从定长分布（Det

9、erministic Distribution） 间隔时间服从爱尔朗分布间隔时间服从爱尔朗分布（Erlang distribution ） 二项分布二项分布（binomial distribution ） 单位时间单位时间 t （或时间区间（或时间区间t）内到达的顾客数服从）内到达的顾客数服从泊松分泊松分布布(法国数学家法国数学家Poisson, 1836)最简单流（泊松流）最简单流（泊松流） （Poisson Distribution） 负指数分布负指数分布（Negative Exponential Distribution）136.3.2.1 最简单流（泊松流）最简单流（泊松流） -纯生过

10、程纯生过程 (1) 泊松流形成条件泊松流形成条件 流的平稳性流的平稳性 对于任意的对于任意的t0t0及及t0t0，在时间区间在时间区间(t,t+(t,t+t)t)内有内有n n个顾客到达的概率只与个顾客到达的概率只与t t有关，与时间区间的起点有关，与时间区间的起点t t无无关关。 当当t t充分小时，在充分小时，在(t,t+(t,t+t)t)内有内有一个顾客到达的概率顾客到达的概率与与t t成正比，即成正比，即其中，其中，O(O(t)t)是当是当t 0t 0时，关于时，关于t t高阶无穷小；高阶无穷小； 为单位时间内的顾客到达平均数。为单位时间内的顾客到达平均数。1( ,)()P t ttt

11、ot 14 在时间轴上，互不相交的时间区段在时间轴上，互不相交的时间区段 和和 内，顾客的到达数是相互独立的，内，顾客的到达数是相互独立的，即前一顾客的到达不影响后一顾客的到达即前一顾客的到达不影响后一顾客的到达。 流的无后效性流的无后效性 当当 t 充分小时，充分小时，在在 t 时间内到达一个顾客的概率为时间内到达一个顾客的概率为 t +o( t )，到达两个或两个以上顾客的概率为，到达两个或两个以上顾客的概率为 o( t )；即两个顾客不可能同时到达即两个顾客不可能同时到达 流的普遍性流的普遍性12,t t34,t t1234()tttt 设把长为设把长为t t的时间区间分成的时间区间分成

12、m m等分，每段长度为等分，每段长度为 。若在。若在dtdt内，有一个顾客到达，则称被内，有一个顾客到达，则称被“占着占着”，如果在，如果在dtdt内，没有顾客到达，则称为内，没有顾客到达，则称为“空着空着”。u被被“占着占着”的概率近似为的概率近似为u被被“空着空着”的概率近似的概率近似在长为在长为 t t 的时间区间内，到达的时间区间内，到达n n个顾客的概率个顾客的概率1( ,)()P t tdtdto dt)( tPn/dtt m 0( ,)1()P t tdtdto dt 根据流的无后效性，在根据流的无后效性，在m m个个dtdt中，有顾客到达与没有顾客到中，有顾客到达与没有顾客到达

13、可以看成是达可以看成是m m次独立的试验次独立的试验 (2) 泊松流详解16在长为在长为 t 的时间区间内，到达的时间区间内，到达n个顾客的概率个顾客的概率)( tPn在在m m个个dtdt中，有中，有n n个个dtdt被顾客被顾客“占着占着”的概率的概率 利用二项定律 ()( )1nm nnnmmttPtP nCmm17dt0，m()lim1nm nnnmmttPtCmm(1)(2)(1)lim1!nm nmm mmmnttnmm ()11lim1m nnmtmmmntnmmmm ！()lim 1mnmttnm！ tnnenttP！)()()ntten ！18符合最简单流（泊松流）的随机事件

14、发生规律符合最简单流（泊松流）的随机事件发生规律tnnenttP！)()(单位时间t 内有n个顾客到达的概率顾客的平均到达率 (3) 泊松分布泊松分布19（4） 泊松输入过程及其特点泊松输入过程及其特点1) 平稳性平稳性：顾客到达数只与时间区间长度有关：顾客到达数只与时间区间长度有关2) 无后效性无后效性：不相交的时间区间内所到达的顾客数是独立的：不相交的时间区间内所到达的顾客数是独立的3) 普遍性普遍性：在：在 t 时间内到达一个顾客的概率为时间内到达一个顾客的概率为 t +o( t )，到达两个或两个以上顾客的概率为到达两个或两个以上顾客的概率为 o( t )；即两个顾客不可；即两个顾客不

15、可能同时到达能同时到达泊松过程具有泊松过程具有可迭加性可迭加性 即独立的泊松分布变量的和仍为泊松分布即独立的泊松分布变量的和仍为泊松分布20 泊松过程的到达间隔时间为泊松过程的到达间隔时间为负指数分布负指数分布 令令 h 代表间隔时间，则概率代表间隔时间，则概率 Ph t代表时间区间代表时间区间t 内没有顾客来的概率；由泊松分布内没有顾客来的概率；由泊松分布 可知：可知：P0(h t)= Ph t=et故间隔时间故间隔时间 h 的分布为的分布为 P h t=1 et（1）推导）推导()()ntntPten ！0( )1( )1/tttF tef teht edt n=06.3.2.2 负指数分

16、布负指数分布21（2）负指数分布的特点）负指数分布的特点负指数分布之所以常用，是因为它有很好的特性，使数学负指数分布之所以常用，是因为它有很好的特性，使数学分析变得方便分析变得方便无记忆性无记忆性。指的是不管一次服务已经过去了多长时间，该。指的是不管一次服务已经过去了多长时间，该次服务所剩的服务时间仍服从原负指数分布次服务所剩的服务时间仍服从原负指数分布 Q.E.D 1)1(1)1(1 , , , : )( 000000000000000ttttteeeethPthPtthPthPtthtPthtthPthtthPthth 它的分布函数为它的分布函数为则服务剩余时间为则服务剩余时间为代表服务已

17、过去的时间代表服务已过去的时间代表服务时间代表服务时间令令证证22 如果顾客的到达过程服从最简单流，则顾客单如果顾客的到达过程服从最简单流，则顾客单位时间内的到达数服从泊松分布。位时间内的到达数服从泊松分布。 如果顾客的到达过程服从最简单流，则顾客到如果顾客的到达过程服从最简单流，则顾客到达的时间间隔服从负指数分布。达的时间间隔服从负指数分布。 从本质上看，泊松分布与负指数分布是同一个从本质上看，泊松分布与负指数分布是同一个过程的不同表现形式。过程的不同表现形式。 可适用于服务时间分布可适用于服务时间分布6.3.3 小结小结23()tP hte 负指数分布负指数分布()()ntntPten ！

18、泊松分布泊松分布在单位时间在单位时间t内，到达内，到达n个顾客的概率个顾客的概率顾客到达时间间隔大于顾客到达时间间隔大于单位时间单位时间t t的概率的概率()1tP hte 顾客到达时间间隔小于顾客到达时间间隔小于单位时间单位时间t t的概率的概率顾客的平均到达率顾客的平均到达率24 例例-1-1 一售货员出售两种商品一售货员出售两种商品A和和B，每日工作，每日工作 8 小时。购买小时。购买每种商品的顾客到达过程为泊松分布，到达率分别为每种商品的顾客到达过程为泊松分布，到达率分别为 A=8人人/日，日， B=16人人/日，试求：日，试求：(1) 1小时内来到顾客小时内来到顾客总数为总数为 3

19、人的概率；人的概率；(2) 三个顾客全是购买三个顾客全是购买B类商品的类商品的概率。概率。解解：(1)总到达率为总到达率为 A+ B=24人人/日，日，1 小时小时=1/8 日，故日，故(2) 3 个顾客全是购买个顾客全是购买 B 类商品的概率为类商品的概率为224. 0! 3)8/124()8/1(8/12433 eP0664. 0! 3)8/116()8/1()8/1(8/188/116303 eePPAB25 例例-2-2 某铁路与公路相交的平面交叉口，当火车通某铁路与公路相交的平面交叉口，当火车通过交叉口时，横木护栏挡住汽车通行。每次火过交叉口时，横木护栏挡住汽车通行。每次火车通过时，

20、平均封锁公路车通过时，平均封锁公路3min，公路上平均每，公路上平均每分钟有分钟有4辆汽车到达交叉口。求火车通过交叉辆汽车到达交叉口。求火车通过交叉口时，汽车排队长度超过口时，汽车排队长度超过100m的概率（即排的概率（即排队汽车超过队汽车超过12辆的概率）。辆的概率）。26 HomeworkHomeworkP186 227 研究系统内部状态变化的过程系统状态系统状态i i状态状态i+1i+1状态状态i-1i-1在在t t时刻内发生两个或两个以上时刻内发生两个或两个以上事件的概率为事件的概率为O(O(t)t)一个事件一个事件一个事件一个事件t0t0， O(O(t) 0t) 06.4 生灭过程生

21、灭过程（Birth and Death Processes）6.4.1 定义定义 系统具有系统具有0,1,2,0,1,2,个状态。在任何时刻，若系统处于状个状态。在任何时刻，若系统处于状态态i i，并且系统状态随时间变化的过程满足以下条件，称，并且系统状态随时间变化的过程满足以下条件，称为一个生灭过程：为一个生灭过程：N(t)N(t)表示时刻表示时刻t t系统中的顾客数。系统中的顾客数。 N(t)N(t) ，t t0 0为一随机过程。为一随机过程。28(1) (1) 在（在（t,t+t,t+t t）内系统由状态）内系统由状态i i转移到状态转移到状态i+1i+1的概率为的概率为 i it+O(

22、t+O(t)t)平稳性条件平稳性条件(2) (2) 在（在（t,t+t,t+t t）内系统由状态）内系统由状态i i转移到状态转移到状态i-1i-1的概率为的概率为 i it+O(t+O(t)t)平稳性条件平稳性条件t t内有一个顾客离开的概率内有一个顾客离开的概率t t内有一个顾客到达的概率内有一个顾客到达的概率(3) (3) 在（在（t,t+t,t+t t）内系统发生两次以上转移的概率为）内系统发生两次以上转移的概率为 O(O(t)t)，即有，即有2 2个以上顾客到达或离开的概率为个以上顾客到达或离开的概率为2()0nnPt普遍性条件普遍性条件排队系统的输入过程和服务过程符合泊松分布，排队

23、系统的输入过程和服务过程符合泊松分布，则排队过程符合生灭过程则排队过程符合生灭过程29状态状态（Status）顾客到达率（顾客到达率（Birth rate）系统服务率系统服务率（Death rate）可以证明：可以证明：tt时，时，P Pi i(t)(t)趋向于常数：系统达到稳定趋向于常数：系统达到稳定6.4.2 状态转移图状态转移图30 系统达到稳定后：每个状态转入率的期望值与转出率的期望值相等。对于状态对于状态i i：转出率的期望值为：转出率的期望值为iiiiiiiPPP)(转入率的期望值为转入率的期望值为1111iiiiPPS0S1S2Si-1SiSi+1Sk-1Sk123i-1ii+1

24、i+2k-1k012i-2i-1ii+1k-2k-1P P0 0P P1 1P P2 2P Pi i6.4.3 状态转移方程状态转移方程31()iiiP1111iiiiPP则则对于对于S S0 00011PP转入转入转出转出11kkkkPP转入转入转出转出对于对于S Sk kS0S1S2Si-1SiSi+1Sk-1Sk123i-1ii+1i+2k-1k012i-2i-1ii+1k-2k-1P P0 0P P1 1P P2 2P Pi i32()iiiP1111iiiiPP状态转移方程状态转移方程求解该方程，可以获得各状态对应的概率求解该方程，可以获得各状态对应的概率330011PP0101PP

25、对于对于S S0 0对于对于S S1 12200111)(PPP0101PP101210212PPP 依次类推依次类推11201011iiiiiiiiPPP 且有且有01kiiP34 6.4.4满足生灭过程的条件满足生灭过程的条件系统的输入过程和服务过程具有平稳、无记忆性和普通性系统的输入过程和服务过程具有平稳、无记忆性和普通性服务台是独立的、相同的、并联的服务台是独立的、相同的、并联的波松输入过程和负指数服务时长就具有这些性质波松输入过程和负指数服务时长就具有这些性质 可以用马氏链来描述系统的状态转移可以用马氏链来描述系统的状态转移 这种系统称为这种系统称为生灭服务系统生灭服务系统，一般用，

26、一般用 M/M/n 表示，又表示，又称为称为标准服务系统标准服务系统； 标准服务系统的形式很多，但都是基于生灭方程，关键标准服务系统的形式很多，但都是基于生灭方程，关键是找出是找出 j , j 的不同表达式，将它们代入的不同表达式，将它们代入生灭方程生灭方程标准服务系统的表示法：标准服务系统的表示法：(X/Y/Z: A/B/C)，X 表示输入过程，表示输入过程，Y 表示服务过程，表示服务过程，Z 表示并联服务台的个数，表示并联服务台的个数，A表示系统容表示系统容量，量，B表示顾客源，表示顾客源，C 表示服务规则表示服务规则 (M/M/n: m/ /FCFS) 表示波松输入，负指数服务时长，表示

27、波松输入，负指数服务时长，n 个并联服务台，系统容量为个并联服务台，系统容量为 m, m n，顾客源无穷，先，顾客源无穷，先到先服务到先服务 D 定长分布；定长分布；Ek k阶爱尔兰分布；阶爱尔兰分布；G 一般独立分布一般独立分布356.4.5 生灭过程推导生灭过程推导（补充参考）（补充参考）采用马氏链采用马氏链 令令 N(t)代表系统在时刻代表系统在时刻 t 的状态，下一瞬间的状态，下一瞬间 t+ t 系统的系统的状态只能转移到相邻状态，或维持不变，如图所示状态只能转移到相邻状态，或维持不变，如图所示 三种转移是不相容的，三者必居其一三种转移是不相容的，三者必居其一 只有具有无记忆性和普通性

28、的过程只有具有无记忆性和普通性的过程(分布分布)才适用马氏链才适用马氏链 令令 Pj(t)=PN(t)=j代表系统在时刻代表系统在时刻 t 处于状态处于状态 j 的概率的概率jjj+1j 1tt+ t j t j+ j) t j t36 生灭过程的马氏链生灭过程的马氏链01j+1njj 1. 0 t j t j t 1 t j t j t 1 t j t n t n t 1+ 1) t j-1+ j-1) t j+ j) t j+1+ j+1) t根据马氏链，应用全概率公式，有状态转移概率方程根据马氏链，应用全概率公式，有状态转移概率方程1, 2, 1)()1)()()()(1111 njto

29、tttpttpttpttpjjjjjjjj 另有两个边界方程另有两个边界方程)()1)()()(00110tottpttpttp )()1)()()(11tottpttpttpnnnnn 37 生灭方程的推导过程生灭方程的推导过程将上述三个差分方程化为微分方程将上述三个差分方程化为微分方程)()()()()( 1, 2, 1)()()()()()(lim11111111tptptptpnjtptptpttpttpjjjjjjjjjjjjjjjjjt 即即上述三个方程是动态方程，当系统处于稳态时，系统处于上述三个方程是动态方程，当系统处于稳态时，系统处于统计平衡状态，即状态概率不随时间变化，从而

30、状态概率统计平衡状态，即状态概率不随时间变化，从而状态概率导数为导数为 0；令上三个方程左侧为；令上三个方程左侧为 0，得稳态方程组，得稳态方程组)()()()()()( 1100110tptptptptptpnnnnn 同理有同理有)3(0)2(10)()1(001111110011njppnjpppjppnnnnjjjjjjj 38 生灭过程稳态解生灭过程稳态解01j+1njj 1. 0 j j 1 j j 1 j n n方程方程(1), (2), (3) 与稳态状态转移图一一对应；递归解如下：与稳态状态转移图一一对应；递归解如下：)3(0)2(10)()1(001111110011njp

31、pnjpppjppnnnnjjjjjjj 11211100002111011021102101011 , 1)( , :)2( , 1 njjjnjjjjjjjppppppppjpp 得得由由归纳法归纳法得得依次递推依次递推式得式得代入代入将将令令39例：例：某排队系统：某排队系统： M/M/1/3/FCFSM/M/1/3/FCFS，=2=2，=3=3。求解各状态对应的概率。求解各状态对应的概率。首先，做出相应的状态转移图首先，做出相应的状态转移图S0S1S2S3222333对于对于S S0 0对于对于S S1 10100123PPP101210021249PPPP 对于对于S S2 2308

32、27PP301iiP000024813927PPPP406.4.6 纯生过程纯生过程令生灭过程中所有消亡率令生灭过程中所有消亡率 j=0， 即只有顾客到达，没有顾即只有顾客到达，没有顾客离去客离去令所有令所有 j= ，且系统服务台无限，即，且系统服务台无限，即 n容易得到下列微分方程组容易得到下列微分方程组, 2 , 1!)()( ,)(1)()()(0)()(0100 jejttPetPjtPtPdttdPjtPdttdPtjjtjjj 并递推得并递推得解一次型微分方程解一次型微分方程由此解出由此解出该问题没有稳态解，正是泊松过程该问题没有稳态解，正是泊松过程41生灭过程求解排队系统各状态概

33、率过程生灭过程求解排队系统各状态概率过程建立状态转移图建立状态转移图建立状态转移方程建立状态转移方程求解状态转移方程求解状态转移方程01kiiP各状态转入率期望值各状态转入率期望值与转出率期望值相等与转出率期望值相等各状态概率各状态概率统计平衡下的统计平衡下的“流入流入=流出流出”原理原理生灭平衡生灭平衡42Homework：利用生灭过程求解以下排队系统各状态的概率。利用生灭过程求解以下排队系统各状态的概率。S0S1S2S32 22 23 32 24 43 343第三节 M/M/1排队系统顾客到达服从泊松分布顾客到达服从泊松分布顾客到达率为顾客到达率为服务过程服从泊松分布（负指数分布）服务过程

34、服从泊松分布（负指数分布）系统服务率为系统服务率为单通道，先到先服务单通道，先到先服务（FCFS）最简单的最简单的M/M/1M/M/1排队系统：排队系统：M/M/1/M/M/1/M/M/1/m/M/M/1/m/44M/M/1/M/M/1/排队系统排队系统系统容量无限、顾客源无限系统容量无限、顾客源无限最基本的排队系统最基本的排队系统排队过程为生灭过程过程排队过程为生灭过程过程45S0S1S2Si-1SiSi+1P P0 0P P1 1P P2 2P Pi i列状态转移方程组求各状态概率列状态转移方程组求各状态概率01PP100PPP1110iiiiiiPPPP230(1)1iP01iiP462

35、30(1)1iPM/M/1/排队系统各状态概率归结为无穷等比数列求和无穷等比数列求和11 1，数列发散，数列发散系统稳定系统稳定系统不稳定系统不稳定称称为服务强度，若服务强度大于为服务强度，若服务强度大于1 1，说明单位时间内到达的顾客，说明单位时间内到达的顾客数比完成服务的顾客数多，系统中排队长度越来越大，产生阻塞。数比完成服务的顾客数多，系统中排队长度越来越大，产生阻塞。47利用排队系统各状态概率计算运行指标利用排队系统各状态概率计算运行指标 1、队长、队长系统中的顾客数量系统中的顾客数量0 SiiLPi队长队长0100232323 (1) (23)(2) (01)1iiiiiiiii S

36、L 48 2、排队长、排队长系统中等待的顾客数量系统中等待的顾客数量1(1)qiiLPi通道数通道数1102 (1) 1 1iiiiSiPPLPqL49 3、逗留时间、逗留时间顾客在排队系统中的总时间顾客在排队系统中的总时间1/()SSLW李太勒公式李太勒公式-1（Little Formula）/SSWL前后前后2名顾客到达系名顾客到达系统的平均时间间隔统的平均时间间隔适用于任何排队系统。适用于任何排队系统。504、排队时间、排队时间顾客在排队系统中的等待时间顾客在排队系统中的等待时间1/()qqLW李太勒公式李太勒公式-2/qqWL前后前后2名顾客到达系名顾客到达系统的平均时间间隔统的平均时

37、间间隔51排队系统运营指标及相互关系：排队系统运营指标及相互关系：01P (1)nnP1sL22()1qsLL 1sW()qsWW 1()kP Nk52M/M/s queuing computationsArrival rate5Service rate 6Number of servers 1 Utilization83.33%P(0), probability that the system is empty0.1667Lq, expected queue length4.1667L, expected number in system5.0000Wq, expected time in

38、queue0.8333W, expected total time in system1.000000.050.10.150.20246810121416182022242628303234363840NUMBER IN SYSTEMProbability53例1 某医院急诊室同时只能诊治一个病人，诊治时间某医院急诊室同时只能诊治一个病人，诊治时间服从负指数分布，每个病人平均需要服从负指数分布，每个病人平均需要1515分钟。病人按分钟。病人按泊松分布到达，平均每小时到达泊松分布到达，平均每小时到达3 3人。试对此排队队人。试对此排队队系统进行分析。系统进行分析。603/ ,/4/15hhh人人

39、人30.754（1）确定参数值：确定参数值：服务强度：服务强度：54急诊室繁忙（需要等待）的概率:010.75P 011 0.750.25P （2）稳态概率：）稳态概率：这就是急诊室空闲的概率，也是病人不必等待立即就能就诊的概率。55病人平均等候时间：3343sL人人3 0.752.25qLL 人人11160min43sWhh1 0.750.7545minqWWhh 急诊室内外的病人平均数：急诊室外排队等待的病人平均数：病人在急诊室内外平均逗留时间：5615123min即平均服务时间至少应减少3min112sW1112min5h为使病人平均逗留时间不超过半小时，那么平均服务时间应减少多少？代入

40、=3，解得5，平均服务时间为：57若医院希望候诊的病人90% 以上都能有座位,则候诊室至少应安置多少座位? 设应该安置个座位,加上急诊室的一个座位,共有+1个。要使90% 以上的候诊病人有座位，相当于使“来诊的病人数不多于+1个”的概率不少于90%，即(1)1(1)0.9P NxP Nx (1)0.1P Nx(1) 120.1xx58两边取对数（x2）lg lg0.1因 1，故(1) 120.1xxlg0.1128lglg0.75x所以 6即候诊室至少应安置6个座位。59例：例：某修车店只有一个修理工，来修理的顾客到达过程服从某修车店只有一个修理工，来修理的顾客到达过程服从PoissonPoi

41、sson流，平均流，平均4 4人人/ /小时；修理时间服从负指数分布，小时；修理时间服从负指数分布，平均需要平均需要6 6分钟，试求：分钟，试求：1 1）修理店空闲的概率；）修理店空闲的概率；2 2）店内恰有）店内恰有3 3个顾客的概率；个顾客的概率；3 3）店内至少有）店内至少有1 1个顾客的概率；个顾客的概率；4 4）在店内的平均顾客数；）在店内的平均顾客数；5 5）每位顾客在店内的平均逗留时间；）每位顾客在店内的平均逗留时间；6 6）等待服务的平均顾客数；）等待服务的平均顾客数；7 7）每位顾客平均等待服务时间；）每位顾客平均等待服务时间；8 8）顾客在店内等待时间超过十分钟的概率。）顾

42、客在店内等待时间超过十分钟的概率。60M/M/1/m/排队系统系统容量有限、顾客源无限系统容量有限、顾客源无限61列状态转移方程组求各状态概率列状态转移方程组求各状态概率01PP100PPP1110iiiiiiPPPP01miiP230(1)1imPS0S1S2Si-1SiSi+1P P0 0P P1 1P P2 2P Pi i62230(1)1imP并不要求并不要求10Q0）0.750.750 05555L Lq q2.252.25人人0 01212人人L L3 3人人0 08787人人W W60min60min17174min4minW Wq q45min45min2 24min4min0

43、P88例例 某储蓄所内，已知忙时顾客到达率某储蓄所内，已知忙时顾客到达率 =40人人/小时，窗口营业小时，窗口营业员服务率为员服务率为 =16人人/小时小时，要求：，要求：(1)工时利用率不低于工时利用率不低于 60%；(2)顾客平均等待时间不超过顾客平均等待时间不超过 5 分钟；问：设几个窗口适当。分钟；问：设几个窗口适当。解解：系统是无限源：系统是无限源 M/M/s 等待制。等待制。 = / =40/16=2.5Erl(1) * = /s 0.6，解出，解出 s 4.17，故，故 s可取值可取值 3， 4 (2) n=3 时，时，p0=(1+ + 2/2! + ( 3/3!)(3/(3-2.5) 1=0.045分钟分钟小时小时时时分钟分钟小时小时8 . 0013328. 00737. 05 . 1! 3405 . 2)()!1(07370. 0 , 4 )3(27. 50