1、排排 队队 论论 模模 型型 1排队论模型排队论模型 一、排队论的基本概念一、排队论的基本概念 二、单通道等待制排队问题二、单通道等待制排队问题 （MM1排队系统）排队系统）三、多通道等待制排队问题三、多通道等待制排队问题 （MMc排队系统）排队系统） 2一、排队论的基本概念一、排队论的基本概念（一）排队过程（一）排队过程 1.1.排队系统排队系统 “排队排队”是指在服务机构处要求服务对象的一个是指在服务机构处要求服务对象的一个等待队列，而等待队列，而“排队论排队论”则是研究各种排队现象的理则是研究各种排队现象的理论。论。 到来 服服务务规规则则 服服 离离去去 顾顾客客源源 排排队队机机构构
2、 务务 机机 构构 排排队队系系统统 3 在排队论中，我们把要求服务的对象称为在排队论中，我们把要求服务的对象称为“顾客顾客”，而将从事服务的机构或人称为，而将从事服务的机构或人称为“服务服务台台”。 在顾客到达服务台时，可能立即得到服在顾客到达服务台时，可能立即得到服务，也可能要等待到可以利用服务台的时候为止。务，也可能要等待到可以利用服务台的时候为止。4 排队系统队列除了有形的还有无形的排队系统队列除了有形的还有无形的。 排队系统中的排队系统中的“顾客顾客”与与“服务台服务台”这两个名这两个名词可以从不同的角度去理解。词可以从不同的角度去理解。排队系统排队系统顾客顾客服务台服务台上、下班的
3、工人乘公共汽车上、下班的工人乘公共汽车工人工人公共汽车公共汽车病人到医院看病病人到医院看病病人病人医生医生高炮击退敌机高炮击退敌机敌机敌机高炮高炮机器发生故障需要维修机器发生故障需要维修机器机器修理工修理工5 在上述顾客在上述顾客- -服务台组成的排队系统中，顾客到服务台组成的排队系统中，顾客到来的时刻与服务台进行服务的时间一般来说是随不来的时刻与服务台进行服务的时间一般来说是随不同的时机与条件而变化的，往往预先无法确定。因同的时机与条件而变化的，往往预先无法确定。因此，系统的状态是随机的，故而排队论也称此，系统的状态是随机的，故而排队论也称随机服随机服务系统务系统。6 各式各样的排队现象呈现
4、的基本特征：排队系统各式各样的排队现象呈现的基本特征：排队系统由输入过程、排队规则及服务机构三部分组成。由输入过程、排队规则及服务机构三部分组成。(1)(1)输入过程输入过程 输入过程就是顾客按怎样的规律到达输入过程就是顾客按怎样的规律到达包括顾客总体数，是有限的还是无限的；包括顾客总体数，是有限的还是无限的；顾客到达的方式，是成批到达顾客到达的方式，是成批到达( (每批数量是随机的每批数量是随机的还是确定性的还是确定性的) )还是单个到达；还是单个到达；相继到达的顾客相继到达的顾客( (或批或单个或批或单个) )之间的时间间隔的分之间的时间间隔的分布是什么。布是什么。 2.2.排队系统的组成
5、和特征排队系统的组成和特征7 排队规则是指到达的顾客以怎样的规则接受服务。排队规则是指到达的顾客以怎样的规则接受服务。 1 1）损失制：）损失制：顾客到达，服务台不空立即离去，顾客到达，服务台不空立即离去，另求服务。另求服务。 2 2）等待制：）等待制：顾客到达，排队等待。对等待制服顾客到达，排队等待。对等待制服务可分为：先到先服务，后到先服务，优先服务，随务可分为：先到先服务，后到先服务，优先服务，随机服务，成批服务等。机服务，成批服务等。 3 3）混合制：）混合制：在现实生活中，很多服务系统介于在现实生活中，很多服务系统介于损失制和等待制之间，当顾客到达时，服务台不空就损失制和等待制之间，
6、当顾客到达时，服务台不空就排队，若排队的位置已满就离去。排队，若排队的位置已满就离去。 (2)(2)排队规则排队规则8服务机构主要指服务台的数目，服务机构主要指服务台的数目，多个服务台进行服务时，服务方式是并联还多个服务台进行服务时，服务方式是并联还是串联；是串联；服务时间服从什么分布等。服务时间服从什么分布等。 (3)(3)服务机构服务机构9 1.1.排队模型的分类排队模型的分类这里仅针对并列的服务台。这里仅针对并列的服务台。 记记X X：顾客到达的时间间隔分布；顾客到达的时间间隔分布；Y Y：服务时间的服务时间的分布；分布；Z Z：服务台数。则排队模型：服务台数。则排队模型：X XY YZ
7、 Z。 常用的记号：常用的记号：M M负指数分布；负指数分布；D D确定型；确定型；EkEkk k阶爱尔朗（阶爱尔朗（ErlangErlang）分布；分布；GIGI一般相互独立的随一般相互独立的随机分布，机分布，G G一般随机分布。这里主要讨论一般随机分布。这里主要讨论M MM M1 1，M MM MC C。（二）排队模型的分类及数量指标（二）排队模型的分类及数量指标10 (1)(1)队长队长队长是指系统中的顾客数队长是指系统中的顾客数( (包括排队等候和正在包括排队等候和正在接受服务的顾客数接受服务的顾客数) )；等待队长是指系统中等待服务的顾客数。等待队长是指系统中等待服务的顾客数。 2.
8、2.排队模型的数量指标排队模型的数量指标11逗留时间是指一顾客从进入系统起一直到接受服逗留时间是指一顾客从进入系统起一直到接受服务后离开系统为止所花费的时间；务后离开系统为止所花费的时间；等待时间是指一顾客从进入系统起到接受服务时等待时间是指一顾客从进入系统起到接受服务时所花费的时间。所花费的时间。 (2)(2)逗留时间逗留时间12 忙期是指从顾客到达空闲服务机构起到服务机构忙期是指从顾客到达空闲服务机构起到服务机构再次为空闲为止的这段时间，即服务机构连续繁忙的再次为空闲为止的这段时间，即服务机构连续繁忙的时间长度。时间长度。这是服务机构最关心的数量指标，因为它直接关系到这是服务机构最关心的数
9、量指标，因为它直接关系到服务员的工作强度，与忙期相对应的是闲期，即为服服务员的工作强度，与忙期相对应的是闲期，即为服务机构连续保持空闲的时间长度。显然，在排队系统务机构连续保持空闲的时间长度。显然，在排队系统中，忙期与闲期是交错出现的。中，忙期与闲期是交错出现的。 (3)(3)忙期忙期131.1.最简单流与最简单流与PoissonPoisson过程过程 记随机过程记随机过程x x（t t）：）：t0t0为时间为时间0 0，t t内内流流( (事件事件) )发生的次数，例如对于随机到来某电话交换发生的次数，例如对于随机到来某电话交换台的呼叫，以台的呼叫，以x x（t t）表示该交换台在表示该交换
10、台在0 0，t t这段时这段时间内收到呼叫的次数；若是服务机构，可以用间内收到呼叫的次数；若是服务机构，可以用x x（t t）表示该机构在表示该机构在0 0，t t时间内来到的顾客数时间内来到的顾客数。（三）（三）PoissonPoisson流与指数分布流与指数分布14最简单流应最简单流应 具有以下特征称具有以下特征称0: )(ttx(1)(1)流具有平衡性流具有平衡性 对任何对任何 和和 , , 的分布只取决于的分布只取决于 而与而与 无关。无关。(2)(2)流具有无后效性流具有无后效性对互不交接的时间区间序列对互不交接的时间区间序列 ， 是一组相互独立的随机变量。是一组相互独立的随机变量。
11、(3)(3)流具有普通性流具有普通性即在即在 时间内，事件发生多于时间内，事件发生多于1 1次的概率为次的概率为 。 0anttt210)1 ()()(niaxtaxinttt,21a)1 (,nibaii)()(iiaxbx01)()(Prlimtaxtaxtt)( to 15定理定理1 1设设 是最简单流，则对任何是最简单流，则对任何 和和都有都有 我们把满足这一分布规律的随机过程我们把满足这一分布规律的随机过程称为称为PoissonPoisson过程，最简单流亦称过程，最简单流亦称PoissonPoisson流，特别取流，特别取 得得故参数故参数表示单位时间内事件发生次数的平均数表示单位
12、时间内事件发生次数的平均数。0: )(ttx0a0t( t)P()( )(0,1,2,)!ktx atx akekk0: )(ttx( t)Pr( )(0,1,2,)!ktx tkekk0attxE)(162.2.PoissonPoisson流的发生时间间隔分布流的发生时间间隔分布 当流当流( (过程过程) ) 构成构成PoissonPoisson过程时，就称过程时，就称为为PoissonPoisson流。设流发生的时刻依次为流。设流发生的时刻依次为 , ,，发生的时间间隔记为发生的时间间隔记为 ，其中其中 。定理定理2 2 事件流事件流 为为PoissonPoisson流的充要条件是流的充要
13、条件是 的流发生时间间隔的流发生时间间隔 相互独立，且服从相互独立，且服从相同的负指数分布，即相同的负指数分布，即0: )(ttxnttt,21), 2 , 1(1nttnnn00t0: )(ttx0: )(ttx n0001Prttettn17 对于单通道等待制排队问题主要讨论输入过对于单通道等待制排队问题主要讨论输入过程为程为PoissonPoisson流，服务时间服从负指数分布，单服流，服务时间服从负指数分布，单服务台的情形，即务台的情形，即M MM M1 1排队系统。排队系统。（一）标准模型（一）标准模型 即为即为M MM M1 1排队系统。所谓标准模型，排队系统。所谓标准模型，就是顾
14、客的输入流是参数为就是顾客的输入流是参数为的的PoissonPoisson流，每个流，每个顾客的服务时间是相互独立的且服从参数为顾客的服务时间是相互独立的且服从参数为的的负指数分布，单个服务台且系统的容量无限负指数分布，单个服务台且系统的容量无限( (排队排队模型分类第四个表示系统中允许的最大顾客数模型分类第四个表示系统中允许的最大顾客数) )。二、单通道等待制排队问题二、单通道等待制排队问题 （MMMM1 1排队系统）排队系统）181.1.系统的系统的MarkovMarkov特性特性 考虑随机过程考虑随机过程 ，其中其中 为时刻为时刻 时时排队系统中的顾客数。排队系统中的顾客数。 对于任何对
15、于任何 条件概率条件概率由于输入为由于输入为PoissonPoisson流，服务时间服从负指数分布，流，服务时间服从负指数分布，则无论则无论 在在 处取何值，上式条件概率仅依处取何值，上式条件概率仅依赖于赖于 的值和区间的值和区间 的长度的长度 ，即即0: )(ttx)(txtnttt210112211)(,)(,)()(Prnnnnitxitxitxitx)(txnttt,21)(1ntx),(1nntt1nntt11112211)()(Pr)(,)(,)()(Prnnnnnnnnitxitxitxitxitxitx19 记时刻记时刻t t系统处于状态系统处于状态n n的概率的概率利用利用M
16、 MM M1 1对输入与服务时间分布的假设，在时对输入与服务时间分布的假设，在时间区间间区间 内，新进入或离开顾客个数有以下结果：内，新进入或离开顾客个数有以下结果： 内没有顾客进入内没有顾客进入 内新进入一名顾客内新进入一名顾客 内多于一名顾客进入内多于一名顾客进入 内没有顾客离开内没有顾客离开 内有一名顾客离开内有一名顾客离开 内多于一名顾客离开内多于一名顾客离开2.2.排队系统的稳态解排队系统的稳态解ntxtPn)(Pr)(),(ttt)(1),(Prtotetttt)(),(Prtottetttt)(),(Prtottt)(1),(Prtotetttt)(),(Prtottetttt)
17、(),(Prtottt20 当当 时有时有导出导出 满足的微分方程组满足的微分方程组)(tpn)()1 ()()1)()(100totttpttpttp)()()()()(1000tottpttptpttp0t)()()(100tptptp21故故 满足的微分方程组满足的微分方程组)()()1)(1)()()(11tottptttpttpttpnnnn)()()()()(11tptptptpnnnn对对1n)()()(, 2 , 1)()()()()(10011tptptpntptptptpnnnn)(tpn22 对于系统的稳定状态情形，对于系统的稳定状态情形， 与与t t无关，无关，故故 ，
18、记记 ，从而有从而有对于上述差分方程，利用归纳法不难求得对于上述差分方程，利用归纳法不难求得)(tpn0)( tpn)(tppnn0, 2 , 10)(1011ppnpppnnn0)(ppnn23 记记 为排队系统的来往强度，当为排队系统的来往强度，当 时，由时，由 可得可得 由于由于 构成概率分布，则构成概率分布，则 ，从而级数从而级数 必须收敛，故有必须收敛，故有 。 np01nnp0)(nn1101nnp, 2 , 1 , 0)1 (npnn24MMMM1 1系统的数量指标系统的数量指标 (1)(1)稳定状态下系统中顾客数的数学期望的定义为稳定状态下系统中顾客数的数学期望的定义为被称为系
19、统中顾客的平均数，简称被称为系统中顾客的平均数，简称平均队长平均队长。 0nnnpL1)(1(1000nnnnnnnnpL1)1(2000nnnnnnqpnppnL 稳定状态下系统中等待服务顾客数的数学期望，稳定状态下系统中等待服务顾客数的数学期望，简称平均简称平均等待队长等待队长。25 (2)(2)顾客在系统中的顾客在系统中的平均逗留时间平均逗留时间 则顾客在系统中的则顾客在系统中的平均等待时间平均等待时间 可以证明，顾客在系统中逗留时间服从参数为可以证明，顾客在系统中逗留时间服从参数为-的负指数分布。的负指数分布。1)(11q26 与与 是衡量排队系统质量的很重要的效是衡量排队系统质量的很
20、重要的效率度量率度量上式称为上式称为LittleLittle公式。公式。 表明系统中的顾客数，等于一个顾客在表明系统中的顾客数，等于一个顾客在系统时间内来到的新的顾客数；系统时间内来到的新的顾客数； 表明系统中处于等待状态的顾客数，表明系统中处于等待状态的顾客数，等于一个顾客的等待时间内来到的新顾客数。等于一个顾客的等待时间内来到的新顾客数。 LittleLittle公式公式qqLLLqqLqLL,q,27(3)(3)稳定状态下稳定状态下忙期忙期的数学期望的数学期望由此可见，一个忙期中所服务顾客的平均数为由此可见，一个忙期中所服务顾客的平均数为1)(TE忙忙11)(TE28（二）系统容量有限的
21、模型（二）系统容量有限的模型 即为即为M MM M1 1N N排队系统。考虑排队系统的容排队系统。考虑排队系统的容量为量为N N，即若系统已有即若系统已有N N个顾客，则再来新顾客即被个顾客，则再来新顾客即被拒绝进入系统。对于拒绝进入系统。对于n nN N，与与M MM M1 1相类似，相类似， ，有有ntxtPn)(Pr)()()()(1, 2 , 1)()()()()(10011tptptpNntptptptpnnnn对于对于n nN N，)()1)()()(1tottpttpttpNNN)()()(1tptptpNNN29 即即 满足微分方程满足微分方程 在稳态情况下，在稳态情况下， ，
22、 ，则则)(tPn)()()()()()(1, 2 , 1)()()()()(110011tptptptptptpNntptptptpNNNnnnn0)( tpn)(tppnn001, 2 , 10)(11011NNnnnppppNnppp30 则则 由由 ，可得可得0ppnnNnnp01Nnnp00111)1 (1111NnnNp11)1 (11110NNp31系统的各项指标系统的各项指标11) 1(112110NNnNnNNpnL111112) 1(110NNnNnqNNNNpnL32 由于有容量的限制，顾客实际进入系统的速率不由于有容量的限制，顾客实际进入系统的速率不是是，而是而是 (
23、(有效到达率有效到达率) )，因而，因而LittleLittle公式成立：公式成立：1)1 (1121)1 (NNNNNpL1)1 (121)1 (NNNqqNNpL)1 (,NeepqeqeLL33三、多通道等待制排队问题三、多通道等待制排队问题 （MMMMc c排队系统）排队系统） 多通道就是多服务台，这里主要讨论多通道就是多服务台，这里主要讨论M MM Mc c排队系统问题，即输入、输出与排队系统问题，即输入、输出与M MM M1 1相同，相同，这里有这里有c c个相互独立工作，且服务速率相同的服务台，个相互独立工作，且服务速率相同的服务台，这时整个系统的服务能力为这时整个系统的服务能力为cc。 当当 时，系统有稳定解时，系统有稳定解1)(c, 1,)(!11, 1 ,0)(!100ccnpcccnpnpncnnn1100)(!1)(!1cncncccnp34系统指标系统指标 因而因而LittleLittle公式成立公式成立：02)()!1()(pccLcqqLLqqLLq1qqLL35
