排队论模型及实例

《排队论模型及实例》由会员分享，可在线阅读，更多相关《排队论模型及实例（48页珍藏版）》请在金锄头文库上搜索。

1、某维修中心在周末现只安排一名员工为顾客提供服务。新来 维修的顾客到达后，若已有顾客正在接受服务，则需要排队 等待。若排队的人数过多，势必会造成顾客抱怨，会影响到 公司产品的销售；若维修人员多，会增加维修中心的支出， 如何调整两者的关系，使得系统达到最优.,例10.1 排队的例子,它是一个典型的排队的例子, 关于排队的例子有很多, 例如： 上下班坐公共汽车, 等待公共汽车的排队; 顾客到商店购物形 成的排队; 病人到医院看病形成的排队; 售票处购票形成的排 队等; 另一种排队是物的排队，例如文件等待打印或发送; 路 口红灯下面的汽车、自行车通过十字路口等等.,排队现象是由两个方面构成，一方要求得

2、到服务，另一方设 法给予服务。我们把要求得到服务的人或物（设备）统称为 顾客, 给予服务的服务人员或服务机构统称为服务员或服务 台。顾客与服务台就构成一个排队系统，或称为随机服务系 统。 显然缺少顾客或服务台任何一方都不会形成排队系统.,对于任何一个排队服务系统，每一名顾客通过排队服务系统 总要经过如下过程：顾客到达、排队等待、接受服务和离 去，其过程如下图所示:,输入过程,顾客源总体：顾客的来源可能是有限的，也可 能是无限的,2. 排队服务系统的基本概念,到达的类型：顾客是单个到达，或是成批到达,相继顾客到达的间隔时间：通常假定是相互独 立、同分布的，有的是等距间隔时间，有的是 服从Pois

3、son分布，有的是服从k阶Erlang分布,输入过程是描述顾客来源及顾客是按怎样的规律抵达排队系统,排队规则,损失制排队系统：顾客到达时,若有服务台均被占,服务机构 又不允许顾客等待, 此时该顾客就自动辞去,2. 排队服务系统的基本概念,等待制排队系统：顾客到达时若所有服务台均被占，他们 就排队等待服务。在等待制系统中,服务 顺序又分为：先到先服务,即顾客按到达 的先后顺序接受服务；后到先服务 .,混合制排队系统：损失制与等待制的混合，分为队长(容量) 有限的混合制系统，等待时间有限的混 合制系统，以及逗留时间有限制的混合 系统.,排队规则是指服务允许不允许排队，顾客是否愿意排队,服务机构,服

4、务台的数目: 在多个服务台的情形下，是串 联或是并联；,2. 排队服务系统的基本概念,顾客所需的服务时间服从什么样的概率分布， 每个顾客所需的服务时间是否相互独立，是成 批服务或是单个服务等。常见顾客的服务时间 分布有：定长分布、负指数分布、超指数分 布、k阶Erlang分布、几何分布、一般分布等.,3.符号表示,排队论模型的记号是20世纪50年代初由D. G. Kendall (肯 达尔)引入的，通常由35个英文字母组成，其形式为,其中A表示输入过程，B表示服务时间，C表示服务台数目，n表示系统空间数。例如:,M/M/S/ 表示输入过程是Poisson流, 服务时间服从负 指数分布, 系统有

5、S个服务台平行服务, 系统容量为无穷的 等待制排队系统.,(2) M/G/1/ 表示输入过程是Poisson流，顾客所需的服务 时间为独立、服从一般概率分布，系统中只有一个服务 台，容量为无穷的等待制系统.,GI/M/1/表示输入过程为顾客独立到达且相继到达的间 隔时间服从一船概率分布，服务时间是相互独立、服从负指 数分布，系统中只有一个服务台，容量为无穷的等待制系统,3. 符号表示,(4) Ek/G/1/K表示相继到达的间隔时间独立、服从k阶Erlang 分布，服务时间为独立、服从一般概率分布，系统中只有一 个服务台，容量为K的混合制系统.,(5) D/M/S/K表示相继到达的间隔时间独立、

6、服从定长分布、 服务时间相互独立、服从负指数分布，系统中有S个服务台 平行服务，容量为K的混合制系统.,4. 描述排队系统的主要数量指标,队长与等待队长,队长(通常记为LS)是指在系统中的顾客的平均数(包括正在接受服务的顾客),而等待队长(通常记为Lq)是指系统中排队等待的顾客的平均数，它们是顾客和服务机构双方都十分关心的数量指标。显然队长等于等待队长加上正在被服务的顾客数.,顾客的平均等待时间与平均逗留时间,顾客的平均等待时间(通常记为Wq)是指从顾客进入系 统的时刻起直到开始接受服务止的平均时间。平均逗 留时间(通常记为Ws)是指顾客在系统中的平均等待时 间与平均服务时间之和。平均等待时间

7、与平均服务时 间是顾客最关心的数量指标.,4. 描述排队系统的主要数量指标,系统的忙期与闲期,从顾客到达空闲的系统，服务立即开始，直到系统再次变为空闲，这段时间是系统连续繁忙的时间，我们称为系统的忙期，它反映了系统中服务机构的工作强度，是衡量服务机构利用效率的指标，即,与忙期对应的是系统的闲期，即系统连续保持空闲的时 间长度.,服务机构 工作强度,用于服务顾客的时间 服务设施总的服务时间,用于服务顾客的时间 服务设施总的服务时间,5. Little（利特尔）公式,用 表示单位时间内顾客到达的平均数,表示单位时间内 被服务完毕离去的平均顾客数，因此1/ 表示相邻两顾客到 达的平均时间，1/ 表示

8、对每个顾客的平均服务时间. J. D. C. Little给出了如下公式：,6. 与排队论模型有关的LINGO函数,(1) peb (load, S) 该函数的返回值是当到达负荷为load, 服务系统中有S个服务 器且允许排队时系统繁忙的概率,也就是顾客等待的概率. (2) pel (load, S) 该函数的返回值是当到达负荷为load, 服务系统中有S个服务 器且不允许排队时系统损失概率, 也就是顾客得不到服务离 开的概率. (3) pfs (load, S, K) 该函数的返回值是当到达负荷为load, 顾客数为K,平行服务 器数量为S时, 有限源的Poisson服务系统等待或返修顾客数

9、 的期望值.,10. 2 等待制排队模型,等待制排队模型中最常见的模型是,即顾客到达系统的相继到达时间间隔独立，且服从参数 为的负指数分布(即输入过程为Poisson过程), 服务台 的服务时间也独立同分布, 且服从参数为的负指数分 布，而且系统空间无限，允许永远排队.,1. 等待制排队模型的基本参数,(1) 顾客等待的概率Pwait,其中S是服务台或服务员的个数，load是系统到达负荷， 即 load=/=R*T, 式中R表示, T表示1/, R表示, 在下面的程序中，因此，R或是顾客的平均到达率， 是顾客的平均被服务数，T 就是平均服务时间.,1. 等待制排队模型的基本参数,(2) 顾客的

10、平均等待时间Wq,其中T/(S-load)是一个重要指标，可以看成一个“合理的 长度间隔”。注意，当loadS时，此值趋于无穷。也就 是说，系统负荷接近服从器的个数时，顾客平均等待时 间将趋于无穷. 当load S时, 上式Wq无意义。其直观的解释是：当系统 负荷超过服从器的个数时, 排队系统达不到稳定的状态, 其队将越排越长.,1. 等待制排队模型的基本参数,顾客的平均逗留时间Ws、队长Ls和等待队长Lq 这三个值可由Little公式直接得到,2. 等待制排队模型的计算实例,S=1的情况(M/M/1/) 即只有一个服务台或一名服务员服务的情况.,例10.2 某维修中心在周末现只安排一名员工为

11、顾客提供服 务。新来维修的顾客到达后，若已有顾客正在接受服务， 则需要排队等待。假设来维修的顾客到达过程为Poisson 流，平均4人/小时，维修时间服从负指数分布，平均需要 6分钟。试求该系统的主要数量指标。,解 按照式上面分析, 编写LINGO程序，其中R=4, T=6/60, load=R.T,S=1. 程序名:exam1002.lg4.,2. 等待制排队模型的计算实例,由此得到： (1) 系统平均队长 Ls=0.6666667, (2) 系统平均等待队长 Lq=0.2666667, (3) 顾客平均逗留时间 Ws=0.1666667(小时)=10(分钟) (4) 顾客平均等待时间 Wq

12、=0.06666667(小时)=4(分钟) (5) 系统繁忙概率 P wait=0.4,在商业中心处设置一台ATM机，假设来取钱的顾客平均每 分钟0.6个，而每个顾客的平均取钱的时间为1.25分钟，试 求该ATM机的主要数量指标.,解 只需将上例LINGO程序作如下改动：R=0.6,T=1.25 即 可得到结果.程序名:exam1003.lg4.计算结果见运行,例10.3,即平均队长为3人，平均等待队长为2.25人，顾客平均逗留 时间5分钟，顾客平均等待时间为3.75分钟，系统繁忙概率 为0.75.,S1的情况(M/M/S/) 表示有多个服务台或多名服务员服务的情况,例10. 设打印室有3名打

13、字员, 平均每个文件的打印时间为10分钟，而文件的到达率为每小时15件，试求该打印 室的主要数量指标.,解 按照上面分析, 编写LINGO程序, 程名:exam1004.lg4.,计算结果分析：即在打字室内现有的平均文件数为6.011 件，等待打印平均文件数3.511件，每份文件在打字室平 均停留时间为0.400小时（24分钟），排队等待打印的平 均时间0.234小时(14分钟),打印室不空闲的概率0.702.,某售票点有两个售票窗口，顾客按参数=8人/分钟的 Poisson流到达，每个窗口的售票时间均服从参数=5人/分 钟的负指数分布，试比较以下两种排队方案的运行指标.,(1) 顾客到达后,

14、以1/2的概率站成两个队列，如右图所示：,例10.5,(2) 顾客到达后排成一个队列, 顾客发现哪个窗口空时, 他就 接受该窗口的服务，如下图所示:,解 (1) 实质上是两个独立的M/M/1/系统,其参数S=1, R=1=2=4, T=1/=1/5=0.2, 编写其LINGO程序，程序 名: exam1005a.lg4. 计算结果见运行,例10.5,(2) 是两个并联系统, 其参数S=2,R=8, T=1/=1/5=0.2, 编写其LINGO程序, 程序名: exam1005b.lg4. 计算结果见 运行,两种系统的计算结果,从上表中所列的计算结果可以看出,在服务台的各种性能指 标不变的情况下

15、,采用不同的排队方式,其结果是不同的. 从 表得到,采用多队列排队系统的队长为4,而采用单排队系统 总队长为4.444, 也就是说每一个子队的队长为2.222,几乎是 多列队排队系统的1/2, 效率几乎提高了一倍.,例10.5 比较分析,10. 3 损失制排队模型,损失制排队模型通常记为,当S个服务器被占用后，顾客自动离去。其模型的基本 参数与等待制排队模型有些不同, 我们关心如下指标：,(1) 系统损失的概率,其中load是系统到达负荷,S是服务台或服务员的个数.,1.损失制排队模型的基本参数,(2)单位时间内平均进入系统的顾客数(e或Re),(3)系统的相对通过能力Q与绝对通过能力A,(4

16、)系统在单位时间内占用服务台(或服务员)的均值Ls,注意: 在损失制排队系统中, Lq=0, 即等待队长为0.,(5)系统服务台（或服务员）的效率,(6)顾客在系统内平均逗留时间(由于Wq=0, 即为Ws）,注意: 在损失制排队系统中, Wq=0, 即等待时间为0.,在上述公式中, 引入e (或Re)是十分重要的, 因为尽管 顾客的以平均(或R)的速率到达服务系统, 但当系统 被占满后, 有一部分顾客会自动离去, 因此,真正进入系 统的顾客输入率是e ,它小于.,2. 损失制排队模型的计算实例,S=1的情况(M/M/1/1),例10.6 设某条电话线，平均每分钟有0.6次呼唤，若每次 通话时间平均为1.25分钟，求系统相应的参数指标。,解 按照上面分析, 编写LINGO程序，其中S=1,R=0.6, T=1/=1.25, 程序名:exam1006.lg4，结果见运行,系统的顾客损失率为43%, 即43%的电话没有接通, 有57% 的电话得到了服务,通