排队论与案例分析主讲教师：梁明杰

《排队论与案例分析主讲教师：梁明杰》由会员分享，可在线阅读，更多相关《排队论与案例分析主讲教师：梁明杰（52页珍藏版）》请在金锄头文库上搜索。

1、 排队论与案例分析主讲教师：梁明杰三明学院2012年全国大学生数学建模竞赛培训班内容提要1 排队服务系统的基本概念 2 等待制排队模型 3 损失制排队模型 4 混合制排队模型 5 闭合式排队模型 6 排队系统的最优化模型1 排队服务系统的基本概念排队论(Queueing Theory)又称随机服务系统, 是通过研究各种服务系统等待现象中的概率特征，从而解决服务系 统最优设计与最优控制的一种理论.1.1 排队的例子及基本概念某维修中心在周末现只安排一名员工为顾客提供服务。新来 维修的顾客到达后，若已有顾客正在接受服务，则需要排队 等待。若排队的人数过多，势必会造成顾客抱怨，会影响到 公司产品的销

2、售；若维修人员多，会增加维修中心的支出， 如何调整两者的关系，使得系统达到最优.例1 排队的例子它是一个典型的排队的例子, 关于排队的例子有很多, 例如： 上下班坐公共汽车, 等待公共汽车的排队; 顾客到商店购物形 成的排队; 病人到医院看病形成的排队; 售票处购票形成的排 队等; 另一种排队是物的排队，例如文件等待打印或发送; 路 口红灯下面的汽车、自行车通过十字路口等等.排队现象是由两个方面构成，一方要求得到服务，另一方设 法给予服务。我们把要求得到服务的人或物（设备）统称为 顾客, 给予服务的服务人员或服务机构统称为服务员或服务台。顾客与服务台就构成一个排队系统，或称为随机服务系 统。

3、显然缺少顾客或服务台任何一方都不会形成排队系统.对于任何一个排队服务系统，每一名顾客通过排队服务系统 总要经过如下过程：顾客到达、排队等待、接受服务和离 去，其过程如下图所示:顾客总体队 伍 输出输入服务台服务系统输入 过程顾客源总体：顾客的来源可能是有限的，也可能是无限的1.2 排队服务系统的基本概念到达的类型：顾客是单个到达，或是成批到达相继顾客到达的间隔时间：通常假定是相互独 立、同分布的，有的是等距间隔时间，有的是 服从Poisson分布，有的是服从k阶Erlang分布输入过程是描述顾客来源及顾客是按怎样的规律抵达排队系统排队 规则损失制排队系统：顾客到达时,若所有服务台均被占,服务机

4、 构又不允许顾客等待, 此时该顾客就自动离去1.2 排队服务系统的基本概念等待制排队系统：顾客到达时若所有服务台均被占，他们就排队等待服务。在等待制系统中,服务顺序又分为：先到先服务,即顾客按到达的先后顺序接受服务；后到先服务 .混合制排队系统：损失制与等待制的混合，分为队长(容量)有限的混合制系统，等待时间有限的混合制系统，以及逗留时间有限制的混合系统.排队规则是指服务允许不允许排队，顾客是否愿意排队服务 机构服务台的数目: 在多个服务台的情形下，是串联或是并联；1.2 排队服务系统的基本概念顾客所需的服务时间服从什么样的概率分布， 每个顾客所需的服务时间是否相互独立，是成 批服务或是单个服

5、务等。常见顾客的服务时间 分布有：定长分布、负指数分布、超指数分 布、k阶Erlang分布、几何分布、一般分布等.1.3符号表示排队论模型的记号是20世纪50年代初由D. G. Kendall (肯达尔)引入的，通常由35个英文字母组成，其形式为其中A表示输入过程，B表示服务时间，C表示服务台数目 ，n表示系统空间数。例如:(1) M/M/S/ 表示输入过程是Poisson流, 服务时间服从负 指数分布, 系统有S个服务台平行服务, 系统容量为无穷的 等待制排队系统.(2) M/G/1/ 表示输入过程是Poisson流，顾客所需的服务时间为独立、服从一般概率分布，系统中只有一个服务 台，容量为

6、无穷的等待制系统.(3) GI/M/1/表示输入过程为顾客独立到达且相继到达的间隔时间服从一般概率分布，服务时间是相互独立、服从负指 数分布，系统中只有一个服务台，容量为无穷的等待制系统1.3 符号表示(4) Ek/G/1/K表示相继到达的间隔时间独立、服从k阶Erlang分布，服务时间为独立、服从一般概率分布，系统中只有一 个服务台，容量为K的混合制系统.(5) D/M/S/K表示相继到达的间隔时间独立、服从定长分布、 服务时间相互独立、服从负指数分布，系统中有S个服务台 平行服务，容量为K的混合制系统.1.4 描述排队系统的主要数量指标 队长与等待队长队长(通常记为LS)是指在系统中的顾客

7、的平均数(包括 正在接受服务的顾客),而等待队长(通常记为Lq)是指系 统中排队等待的顾客的平均数，它们是顾客和服务机 构双方都十分关心的数量指标。显然队长等于等待队 长加上正在被服务的顾客数. 顾客的平均等待时间与平均逗留时间顾客的平均等待时间(通常记为Wq)是指从顾客进入系 统的时刻起直到开始接受服务止的平均时间。平均逗 留时间(通常记为Ws)是指顾客在系统中的平均等待时 间与平均服务时间之和。平均等待时间与平均服务时 间是顾客最关心的数量指标.1.4 描述排队系统的主要数量指标 系统的忙期与闲期从顾客到达空闲的系统，服务立即开始，直到系统再 次变为空闲，这段时间是系统连续繁忙的时间，我们

8、称 为系统的忙期，它反映了系统中服务机构的工作强度， 是衡量服务机构利用效率的指标，即与忙期对应的是系统的闲期，即系统连续保持空闲的时 间长度.服务机构工作强度用于服务顾客的时间服务设施总的服务时间1.5 Little（利特尔）公式用 表示单位时间内顾客到达的平均数,表示单位时间内 被服务完毕离去的平均顾客数，因此1/ 表示相邻两顾客到达的平均时间，1/ 表示对每个顾客的平均服务时间. J. D. C. Little给出了如下公式：1.6 与排队论模型有关的LINGO函数(1) peb (load, S) 该函数的返回值是当到达负荷为load, 服务系统中有S个服务 器且允许排队时系统繁忙的概

9、率,也就是顾客等待的概率. (2) pel (load, S) 该函数的返回值是当到达负荷为load, 服务系统中有S个服务 器且不允许排队时系统损失概率, 也就是顾客得不到服务离 开的概率. (3) pfs (load, S, K) 该函数的返回值是当到达负荷为load, 顾客数为K,平行服务 器数量为S时, 有限源的Poisson服务系统等待或返修顾客数 的期望值.2 等待制排队模型等待制排队模型中最常见的模型是即顾客到达系统的相继到达时间间隔独立，且服从参数 为的负指数分布(即输入过程为Poisson过程), 服务台 的服务时间也独立同分布, 且服从参数为的负指数分 布，而且系统空间无限

10、，允许永远排队.2.1 等待制排队模型的基本参数(1) 顾客等待的概率Pwait其中S是服务台或服务员的个数，load是系统到达负荷， 即 load=/=R*T, 式中R表示, T表示1/, R表示, 在下面的程序中，因此，R或是顾客的平均到达率， 是顾客的平均被服务数，T 就是平均服务时间.2.1 等待制排队模型的基本参数(2) 顾客的平均等待时间Wq其中T/(S-load)是一个重要指标，可以看成一个“合理的 长度间隔”。注意，当loadS时，此值趋于无穷。也就是说，系统负荷接近服从器的个数时，顾客平均等待时 间将趋于无穷. 当load S时, 上式Wq无意义。其直观的解释是：当系统 负荷

11、超过服从器的个数时, 排队系统达不到稳定的状态, 其队将越排越长.2.1 等待制排队模型的基本参数(3) 顾客的平均逗留时间Ws、队长Ls和等待队长Lq这三个值可由Little公式直接得到2.2 等待制排队模型的计算实例 S=1的情况(M/M/1/)即只有一个服务台或一名服务员服务的情况.例2 某维修中心在周末现只安排一名员工为顾客提供服 务。新来维修的顾客到达后，若已有顾客正在接受服务， 则需要排队等待。假设来维修的顾客到达过程为Poisson 流，平均4人/小时，维修时间服从负指数分布，平均需要 6分钟。试求该系统的主要数量指标。解 按照式上面分析, 编写LINGO程序，其中R=4, T=

12、6/60, load=R.T,S=1. 程序名:exam1002.lg4.2. 2等待制排队模型的计算实例由此得到： (1) 系统平均队长 Ls=0.6666667, (2) 系统平均等待队长 Lq=0.2666667, (3) 顾客平均逗留时间 Ws=0.1666667(小时)=10(分钟) (4) 顾客平均等待时间 Wq=0.06666667(小时)=4(分钟) (5) 系统繁忙概率 P wait=0.4在商业中心处设置一台ATM机，假设来取钱的顾客平均每 分钟0.6个，而每个顾客的平均取钱的时间为1.25分钟，试 求该ATM机的主要数量指标.解 只需将上例LINGO程序作如下改动：R=0

13、.6,T=1.25 即 可得到结果.程序名:exam1003.lg4.计算结果见运行例3即平均队长为3人，平均等待队长为2.25人，顾客平均逗留 时间5分钟，顾客平均等待时间为3.75分钟，系统繁忙概率 为0.75. S1的情况(M/M/S/)表示有多个服务台或多名服务员服务的情况例 设打印室有3名打字员, 平均每个文件的打印时间为 10分钟，而文件的到达率为每小时15件，试求该打印 室的主要数量指标.解 按照上面分析, 编写LINGO程序, 程名:exam1004.lg4.计算结果分析：即在打字室内现有的平均文件数为6.011 件，等待打印平均文件数3.511件，每份文件在打字室平 均停留时

14、间为0.400小时（24分钟），排队等待打印的平 均时间0.234小时(14分钟),打印室不空闲的概率0.702.某售票点有两个售票窗口，顾客按参数=8人/分钟的 Poisson流到达，每个窗口的售票时间均服从参数=5人/分 钟的负指数分布，试比较以下两种排队方案的运行指标.(1) 顾客到达后,以1/2 的概率站成两个队 列，如右图所示：例5(2) 顾客到达后排成一个队列, 顾客发现哪个窗口空时, 他就 接受该窗口的服务，如下图所示:解 (1) 实质上是两个独立的M/M/1/系统,其参数S=1, R=1=2=4, T=1/=1/5=0.2, 编写其LINGO程序，程序 名: exam1005a

15、.lg4. 计算结果见运行例5(2) 是两个并联系统, 其参数S=2,R=8, T=1/=1/5=0.2, 编写其LINGO程序, 程序名: exam1005b.lg4. 计算结果见 运行两种系统的计算结果从上表中所列的计算结果可以看出,在服务台的各种性能指 标不变的情况下,采用不同的排队方式,其结果是不同的. 从 表得到,采用多队列排队系统的队长为4,而采用单排队系统 总队长为4.444, 也就是说每一个子队的队长为2.222,几乎是 多列队排队系统的1/2, 效率几乎提高了一倍.例5 比较分析3 损失制排队模型损失制排队模型通常记为当S个服务器被占用后，顾客自动离去。其模型的基本 参数与等

16、待制排队模型有些不同, 我们关心如下指标：(1) 系统损失的概率其中load是系统到达负荷,S是服务台或服务员的个数.3.1损失制排队模型的基本参数(2)单位时间内平均进入系统的顾客数(e或Re)(3)系统的相对通过能力Q与绝对通过能力A(4)系统在单位时间内占用服务台(或服务员)的均值Ls注意: 在损失制排队系统中, Lq=0, 即等待队长为0.(5)系统服务台（或服务员）的效率(6)顾客在系统内平均逗留时间(由于Wq=0, 即为Ws）注意: 在损失制排队系统中, Wq=0, 即等待时间为0.在上述公式中, 引入e (或Re)是十分重要的, 因为尽管 顾客的以平均(或R)的速率到达服务系统, 但当系统 被占满后, 有一部分顾客会自动离去, 因此,真正进入系 统的顾客输入率是e ,它小于.3.2 损失制排队模型的计算实例