1、第十三章第十三章 排队论排队论13-1 13-1 M/M/1排队系统排队系统13-2 13-2 M/M/C排队系统排队系统13-3 13-3 一般服务时间模型一般服务时间模型13-4 13-4 一般服务时间损失制模型一般服务时间损失制模型 13.1 M/M/1排队系统排队系统v系统设定：顾客到达和服务时间随机；单队；系统设定：顾客到达和服务时间随机；单队；FIFOFIFOv一、一、M/M/1/FIFOM/M/1/FIFO顾客平均到达数顾客平均到达数；平均服务数；平均服务数；且；且令令:且注意到：且注意到：带入第三章系统稳态概率公式得到系统的状态概率表达带入第三章系统稳态概率公式得到系统的状态概
2、率表达式为：式为：排队系统的运行参数如下：排队系统的运行参数如下：1.队长（即在系统中的平均顾客数）队长（即在系统中的平均顾客数）1i,2,1,0ii，1110，iinnPP)1(;101)1()1()(1100nnnsnnPnnELsL2022年7月29日11时41分Page 2 of 28系统中至少有一个顾客的概率（或系统不为空的概率），即系统为忙期的概率 11101PPn2.排队长（即排队顾客数）ssnnnqLLPnPPnL1)1(21113.逗留时间（在系统中耗费时间）ssLWEW1)(（推导略，参见P.325角注）4.等待时间（即排队等候的时间）qssqLWWW1这是因为 （每名顾客
3、被服务时间的平均值）。/1qsWW13.1 M/M/1排队系统排队系统标准型标准型2022年7月29日11时41分Page 3 of 28概述四个指标之间的关系为：ssWLqqWL/1qsWW/qsLL除此之外，我们还可以求得：系统内顾客多于k 的概率：111)1()(kknnknnPknP在系统中逗留时间大于的概率：tsetTP)()(tqqetTPtW)1(1)(排队等待时间 的概率：tTq逗留时间 的概率 tTstssetTPtW)(1)(例：汽车平均以每5分钟一辆的到达率去某加油站加油，并且到达过程构成泊松流。汽车加油时间服从负指数分布，且平均需要4分钟。若此加油站只有一台加油设备，试
4、求1.加油站里的平均汽车数；2.每辆汽车平均等待加油的时间为多少？3.汽车等待加油时间超过2分钟的概率为多少？13.1 M/M/1排队系统排队系统标准型标准型2022年7月29日11时41分Page 4 of 28 1 0 n+1 n n-1 2 解：本题为M/M/1系统。若取单位时间为5分钟，则：8.0,25.1,11.平均汽车数：（辆）4125.11sL2.每辆汽车的平均等待时间：（单位时间）=16（分钟）2.3125.18.0qW3.汽车等待加油时间超过2分钟的概率：P等待时间2/5=1等待时间2/5=72.052)(e二、有限队长模型/1/NMM系统容量限制为N，则排队顾客最多为N1个
5、，如果顾客数超过N个，则被拒绝进入系统。根据系统状态转移图：N N-1 N-2 13.1 M/M/1排队系统排队系统有限队长有限队长2022年7月29日11时41分Page 5 of 2811101)(NNnnnPPPPPPP求稳态方程的解1,Nn）注：1(0NnP110NPPn时，nNnP1111011NPNn，1由此也得到系统的运行指标如下：（推导略，见卢向华等著运筹学p.317）1N1NN0is11N1iPL )()()(0sN1iiqP1LP1iL esssLPLW)1(01sqWW13.1 M/M/1排队系统排队系统有限队长有限队长2022年7月29日11时41分Page 6 of
6、28 0 1 2 n-1 n n+1(m-n+1)(m1)m (mn)m-2 m-1 m 2 注意到是平均到达率，而PN是顾客被拒绝的概率，(1PN)是顾客被接纳的概率。故 是到达系统并被接纳的概率，称之为有效到达率。记为)1(NP)1()1(0PPNe三顾客源有限mmMM/1/顾客数为m，平均每个人的到达率为（注：此处与前述含义不同），系统外的平均数为 ，有效到达率：sLm)(seLm典型的例子就是企业中设备故障修理问题，其状态转移图为：13.1 M/M/1排队系统排队系统有限顾客源有限顾客源2022年7月29日11时41分Page 7 of 28每台设备有正常转移为故障转移率为 0Pm台设
7、备转移为一台故障转移率为 0Pm由状态1转移到状态0 转移率为 1P所以在稳态条件下上述状态转移规律可以描述为：111)()1(011110miimmnnnPPPmnPnmPnmPPPm，解此差分方程得：miiimmP00)()!(!10)()!(!PnmmPnn11mn13.1 M/M/1排队系统排队系统有限顾客源有限顾客源2022年7月29日11时41分Page 8 of 28系统的运行参数为：)1(0PmLs11)1(1)1)(000sqssqWWPmWPLPmL）（平均正常运转台数：)1(0PLms13.1 M/M/1排队系统排队系统有限顾客源有限顾客源2022年7月29日11时41分
8、Page 9 of 28作业：教材Lets take break.Lets take break.Would you like coffee or Would you like coffee or tea?tea?Help yourself please.Help yourself please.2022年7月29日11时41分Page 10 of 28 0 1 2 n-1 n n+1 2 n(n+1)cn n-1 n n+1 2 c c cn 13.2 M/M/C排队系统排队系统4.2.1.标准标准M/M/C模型模型(M/M/n/FIFO)v系统稳态概率及等待概率系统稳态概率及等待概率有有c
9、个服务台，彼此独立，顾客到达率为个服务台，彼此独立，顾客到达率为，平均服务率，平均服务率相同为相同为。整个服务系统的平均服务率为。整个服务系统的平均服务率为c(nc)或或n(nc)令 (平均服务强度)，只有 时才能形成稳定局面。c1按上述状态转移图有：)(,)()1(,)()1(111101cnPcPPccnPnPPnPPnnnnnn11iiP1且有：2022年7月29日11时41分Page 11 of 28v解之得系统状态概率及运行指标为：ssqqcncnqqqsccnnncnnnckckLWLWPccPcnLcLLLcPPcnPcnPcccnPnPckP,)1(!)()()1(!)()()
10、(,)(!1)(,)(1)(!1)(10120001100！13.2 M/M/C排队系统排队系统标准型标准型2022年7月29日11时41分Page 12 of 28例：某车站售票处有三个售票口，顾客以泊松流到达，到达率为 ；售票员的服务时间为负指数分布，每个服务的服务率为 ；另顾客排成一队依次购票。求1。系统的运行参数。2。购票人数超过3人的概率。3。与排成3队购票比较。解：14.0352c523c.,.,045.035.211!35.2!25.2!15.2!05.2132100P1.系统运行指标：13.2 M/M/C排队系统排队系统标准型标准型2022年7月29日11时41分Page 13
11、 of 28515.3045.0)35.21(!335.25.223qL01.6qsLL515.3qqLW01.65.2515.3sW 70004501352P133nP2303.)(!.)(!)(.3.与 相比较 1MM/3/14.083.016.4qL17.00P15sW5.12qW5314.031sL必须等待的概率为：0.8313.2 M/M/C排队系统排队系统标准型标准型2022年7月29日11时41分Page 14 of 284.2.2 混合制，无限源FIFONcMM/令从顾客源来的顾客到达率为，每台的服务率为 则有 j=,j=0,1,.,N1;N=0，j=j,当jc;j=c,当jc
12、,j=1,.,N将j,j 代入生灭方程，得)1()(1)1(!)(!0!11)(!1200000cNcNcqncnnckNcckcNccPLNncPcccnPncPcckcP），（），（，c13.2 M/M/C排队系统排队系统有限队长有限队长2022年7月29日11时41分Page 15 of 28)1(NqsPcLL)1(NqqPLW1qsWW特别地，当 时，系统为损失制，这时当nc时，系统的到达率为 零。带入到稳态概率公式的：cN 100!)(ckkkcP0!)(PncPnncn 0当N=c时，排队系统已满，顾客被拒绝的概率为Pc，并且有：/100sqqWWL；)1(!010!11ccnc
13、nccnnsPcnccnPLn例题：教材P.3362022年7月29日11时41分Page 16 of 2813.2.3 顾客源有限模型FIFOmcMM/cm，到达率按每个顾客考虑；时，均在服务，个工人闲着；时，个顾客等待服务。cm cn ncmnccn1010)!(1!)!(!1!1ckmckkckckmcckmkmP），（），（mncPccnmmcnPnnmmPncnnn1!)!(!0!)!(!0013.2 M/M/C排队系统排队系统有限顾客源有限顾客源2022年7月29日11时41分Page 17 of 2813.2 M/M/C排队系统排队系统有限顾客源有限顾客源平均设备故障数：；等待修
14、理设备数：；有效到达率：，其它运行参数：mnsnPL1mcnnqPcnL1seLmeqsLLessLWeqqLW例题：教材P.337 例82022年7月29日11时41分Page 18 of 28作业：教材13.2 M/M/C排队系统排队系统Take a break2022年7月29日11时41分Page 19 of 2813.3 一般服务时间模型一般服务时间模型1/GMqseqsLLLL1qqsWTEWWssWLqqWL以上七个变数只要知道其中三个就可以求出其余四个。在容量有限和顾客源有限时，要换成有效到达率 。e假设：1.输入为泊松流;2.无限队长，无限源；3 单队；4 FIFO；5 单服
15、务员；6 服务时间T任意分布，均值E T，方差为Var(T)；7 到达时间间隔大于期望服务时间。则总有下面的关系式成立：1/E T13.3.1 M/G/1一般服务时间模型2022年7月29日11时41分Page 20 of 28令 ，应用嵌入马尔可夫链分析可得Pollaczek-Khintchine(P-K)公式：TE)1(222TVarLs10TEPsqLLssLW qqLW 且有：13.3.2 M/D/1 定长服务时间模型定长服务时间模型到达率为，服务率是常数，方差为0，则有：1TE)1(2)1(222sL10P)1(22sqLLssLW qqLW且有：例题：教材P.339例1013.3.
16、3 M/E/1 爱尔朗服务时间模型爱尔朗服务时间模型2022年7月29日11时41分Page 21 of 2813.3.3 M/E/1 爱尔朗服务时间模型爱尔朗服务时间模型 此模型所描述的是更为普遍的现象。负指数服务和定长服务都可以看作是爱尔朗服务时间模型的特例。此模型描述的是k个环节串联服务的过程，并且k个环节的服务相互独立，服从相同的参数为k的负指数分布。1 2 kkk)!1(),(1ketkktfktkk,3,2,100kt kTEi1 221kTVari 1TE 21kTVar 设 是k个独立随机变量，服从k的负指数分布。服从k阶爱尔朗分布，则有：kVVV21kVVVT212022年7
17、月29日11时41分Page 22 of 28对每个k期望值都一样，单方差随k的增加而减少。当k=1时为负指数分布；当k时，。0TVar1212kkLqssLWqqLW 例题：教材P.340例1113.3.3 M/E/1 爱尔朗服务时间模型爱尔朗服务时间模型1212kkLs2022年7月29日11时41分Page 23 of 2813.4 一般服务时间一般服务时间M/G/c/c/损失制模型损失制模型 这是一种有c个服务台一般服务时间的损失制模型，当系统满时，后来的顾客不再进入系统。该模型要解决的主要问题是在服务机构的空闲与顾客的流失之间找到平衡，找出最合适的服务台数，使得该系统效益最大。典型的
18、应用系统有：电话中转系统、民航电话订票系统等。由于损失制，故不存在排队顾客的数目Lq及WS，这里给出系统里有几个顾客的概率Pn和在系统里的平均顾客数Ls 。（推导略）2022年7月29日11时41分Page 24 of 28为顾客的平均到达率，为平均服务率，c为服务台数。ciinninP0!/)/(!/)/()1(csPL其中Pc为系统里正好有c个顾客的概率，也就是系统里c个服务台都被顾客占满的概率。例题：某电器商场开展了电话订货业务，据统计分析电话到达过程服从泊松分布，平均到达率为每小时16个，而一个接话员处理订货事宜的时间是随着订货的产品、规格、数量及顾客的不同而变化的，但平均每个人每小时
19、可以处理8个订货电话，在此电器商场里安装了一台电话自动交换台，它接到电话后可以接到任一个空闲的接话员的电话上。试问该商场应该安装多少台接话员的电话，使得订货电话占线而损失的概率不超过10%。13.4 一般服务时间一般服务时间M/G/c/c/损失制模型损失制模型 2022年7月29日11时41分Page 25 of 28解：这是一个损失值的M/G/c/c/模型。当c=3时，我们来计算M/G/3/3/系统中正好有3位顾客的概率，这时c=n=3，用上述公式计算得：2105.03333.63333.16/)8/16(2/)8/16(1/)8/16(1/)8/16(6/)8/16(!/)/(!3/)/(
20、321033033iiiP这也就是说，当设置三个接受订货的电话时，三个电话都被占满的概率为21.05%，这时别的电话就打不进来损失到了，也就是在这个系统了因电话占线而损失的概率为21.05%，超过了10%的要求，显然不合要求。如果设置4个订货电话，这时c=4，在M/G/4/4/系统中，正好有4位顾客的概率为：13.4 一般服务时间一般服务时间M/G/c/c/损失制模型损失制模型 2022年7月29日11时41分Page 26 of 280952.076667.024/)8/16(6/)8/16(2/)8/16(1/)8/16(1/)8/16(24/)8/16(!/)/(!4/)/(4321044044iiiP可见当设置四个电话时，四个电话都被占用，别的电话打不进来，损失掉的概率为9.52%，这就符合公司的目标要求，故公司应设置四个电话。另外还可求出此电话系统里的平均顾客数为：81.1)0952.01(816)1(4PLs13.4 一般服务时间一般服务时间M/G/c/c/损失制模型损失制模型 2022年7月29日11时41分Page 27 of 28作业：教材Have a rest13.4 一般服务时间一般服务时间M/G/c/c/损失制模型损失制模型 本章结束2022年7月29日11时41分Page 28 of 28
