运筹学-第十章-排队论ppt课件.ppt

《运筹学-第十章-排队论ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹学-第十章-排队论ppt课件.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、排队论排队论v引言v生灭过程和Poisson过程vM/M/s等待制排队模型第一节 引言一、排队系统的特征及排队论排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。排队是我们在日常生活和生产中经常遇到的现象。例如，上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。除了上述有形的排队之外，还有大量的所谓“无形”排队现象，如几

2、个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。排队的不一定是人，也可以是物：例如，通讯卫星与地面若干待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。显然，上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,而把提供服务的人或机构称为“服务员”或“服务机构”。实际的排队系统可以千差万别，但都可以一般地描述如下：顾客为了得到某种服务而到达系

3、统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图10-1至10-4图10-1 单服务台排队系统图10-2 单队列S个服务台并联的排队系统图10-3 S个队列S个服务台的并联排队系统图10-4 单队多个服务台的串联排队系统类似地还可画出许多其他形式的排队系统，如串并混联的系统，网络排队系统等尽管各种排队系统的具体形式不同，但都可以由图10-5加以描述图10-5 随机服务系统通常称上图表示的系统为一随机聚散服务系统，任一排队系统都是一个随机聚散服务系统。这里，“聚”表示顾客的到达，“散”表示顾客的离去。所谓随机性则是排队系统的一个普遍特点，是指顾客的到达情况(如相

4、继到达时间间隔)与每个顾客接受服务的时间往往是事先无法确切知道的，或者说是随机的。一般来说，排队论所研究的排队系统中，顾客到来的时刻和服务台提供服务的时间长短都是随机的，因此这样的服务系统被称为随机服务系统小结排队系统又称随机服务系统排队系统又称随机服务系统有请求服务的人或物；有请求服务的人或物；有为顾客服务的人或物；有为顾客服务的人或物；顾客到达时间与接受服务时间是随机的。顾客到达时间与接受服务时间是随机的。结构：结构：顾客到达顾客到达-排队排队-服务机构服务服务机构服务-顾客离去顾客离去二、排队系统的描述实际中的排队系统各有不同，但概括起来都由三个基本部分组成：1输入过程；输入过程；2排队

5、及排队规则排队及排队规则3服务机制服务机制1输入过程这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流一般可以从3个方面来描述一个输入过程。(1)顾客总体数又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而车间内停机待修得机器显然是有限的。(2)顾客到达方式这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系

6、统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。2排队及排队规则(1)排队排队分为有限排队有限排队和无限排队无限排队两类。有限排队有限排队是指排队系统中的顾客数是有限的，即系统的空间是有限的，当系统被被占满时，后面再来的顾客将不能进入系统；无限排队无限排队是指系统中顾客数可以是无限的，队列可以排到无限长，顾客到达系统后均可进入系统排队或接受服务，这类系统又称为等待制排队系统。有限排队系统有限排队系统损失制排队系统混合制排队系统（排队空间为0的系统

7、）（允许排队，但又不允许队列无限长）这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。损失制排队系统损失制排队系统（排队空间为0的系统）混合制排队系统混合制排队系统这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种： 队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。 如旅馆的床位是有限的。 等待时间有限。即顾客在系统中的等待时间不

8、超过某一给定的长度T，当等待时间超过T 时，顾客将自动离去，并不再回来。如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。（允许排队，但又不允许队列无限长） 逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t 时，若在这个时间内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制。(K为系统中可容纳的顾客数)(2)排队规则当顾客到达时，若所有服务台都被占用且又允许排队，则该顾客将进入队列等待。例如，排队等待售票

9、，故障设备等待维修等。服务台对顾客进行服务所遵循的规则通常有：先到先服务（FCFS）后到先服务（LCFS）优先权（PS）随机服务仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。3服务机制排队系统的服务机制可以从以下3方面来描述：(1)服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有： 单队单服务台式； 单队多服务台并联式； 多队多服务台并联式； 单队多服务台串联式； 单队多服务台并串联混合式 以及多队多服务台并串联混合式等等。(2) 服务方式。这是

10、指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3) 服务时间的分布一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K阶爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。三、排队系统的符号表示肯道尔（D.G.Kendall）分类：X / Y / Z / A / B /C 其中： X 顾客到达的分布； Y 服务时间的分布； Z 服务台数； A 系统容量； B 顾客源的个体数。 C 服务规则表示分布的符号：M-负指数分布或泊松输入；D-定长分布；Ek-k阶爱尔朗分布；GI-一般独立

11、随机分布；G-一般随机分布 例如：某排队问题为MMSFCFS，则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明则均理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统四、排队系统的主要数量指标评价排队系统的优劣。评价排队系统的优劣。下面给出的这些数量指标一般都是和系统运行的时刻有关的随机变量，求这些随机变量的瞬时分布一般是很困难的。为了分析上的简便，并注意到相当一部分排队系统在运行了一定时间后，

12、都会趋于一个平衡状态(或称平稳状态)。在平衡状态下，队长的分布、等待时间的分布和忙期的分布都和系统所处的时刻无关，而且系统的初始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡性质。1、队长与排队长、队长与排队长(1)队长队长: 系统中的顾客数（n）； N(t)-N-L (2)排队长排队长: 系统中排队等待服务的顾客数; Nq(t)- Nq-Lq2、逗留时间与等待时间、逗留时间与等待时间(1)逗留时间逗留时间: 指一个顾客在系统中的全部停留时间； T(t)-T-W(2)等待时间等待时间: 指一个顾客在系统中的排队等待时间；Tq(t)- Tq-Wq这四项主要性

13、能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的。2、忙期和闲期、忙期和闲期(1)忙期忙期: 是指从顾客到达空闲着的服务机构起，到服务机构再次 成为空闲止的这段时间，即服务机构连续忙的时间。 (2)闲期闲期: 与忙期相对的是闲期，即服务机构连续保持空闲的时间。 在排队系统中，忙期和闲期总是交替出现的。BBII3、其他相关指标、其他相关指标 (1)(1)忙期服务量：忙期服务量：指一个忙期内系统平均完成 服务的顾客数；(2)损失率损失率: 指顾客到达排队系统，未接受服务 而离去的概率; （对损失制或系统容量有限而言）

14、 (3)服务强度：服务强度： = = /s/s ；根据前面的约定，我们将主要分析系统的平稳分布。于是记：Pn ：当系统达到统计平衡时处于状态n的概率（pn(t)）n :当系统处于状态n时，新来顾客的平均到达率(单位 时间内来到系统的平均顾客数)n：当系统处于状态n时，整个系统的平均服务率。 （单位时间内可以服务完的顾客数）当n为常数时，记为；当每个服务台的平均服务率为常数时，记每个服务台的服务率为。S表示系统中并行的服务台数则当ns时，有ns ,于是令 = /s ， 称为服务强度 （traffic intensity）负指数分布密度函数0for t00 )(tforetftT均值1)(TE方差

15、21)(TVar随机变量 T分布函数tetTP1)(fT(t)t1)(TE)()0(ttTtPtTPfT(t)tttfT(t) 是一个严格下降函数第二节 生灭过程和Poisson过程一、生灭过程简介一类非常重要其广泛存在的排队系统是生灭过程排队系统。生灭过程是一类特殊的随机过程，在生物学、物理学、运筹学中有广泛的应用。定义定义1 设N(t)，t0 为一个随机过程。如N(t)的概率分布具有以下性质： （1）假设N(t)= n，则从时刻 t 起到下一个顾客到达时刻止的时 间服从参数为n 的负指数分布，n=0，1，2，。 （2）假设N(t)= n，则从时刻 t 起到下一个顾客离去时刻止的时间服从参数

16、为n的负指数分布，n=0，1，2，。 （3）同一时刻只有一个顾客到达或离去。则称设N(t)， t0 为一个生灭过程。v顾客到达“生”；v顾客离开“灭”顾客到达顾客到达顾客离去顾客离去n ， n ，生灭过程示意图：为求平稳分布，考虑系统在 t+t 时刻可能处的任一状态n的概率。状态转移图状态转移图一般说来，得到 是比较困难的，因此通常是求当系统达到平稳状态后的状态分布，记为 , n=0,1,2 ( )( )( )nN tp tP N tn的分布np方式 T时刻状态概率（t,t+t）内发生的事件发生的概率1nPn(t)无到达，无离去 （1-nt） (1-nt) 2n -1Pn-1(t)到达一个，无

17、离去 n-1t (1-n-1t) 3n +1Pn+1(t)无到达，离去一个(1-n+1t) n+1t 4nPn(t)到达一个，离去一个 (nt) (nt) 各种方式发生概率表各种方式发生概率表方式1，2，3，4互不相容且完备，于是：111111()( ) (1)(1)( ) ()(1)( ) (1)()( ) ()()nnnnnnnnnnnnnP ttP tttPtttPtttP ttt 0()()( )limnnntdP ttP ttP td tt1111( )( )()( )nnnnnnnPtP tPtt2项都变为零项都变为零对上式求导有：当n=0时，只有方式1和3，4发生，且方式1中无离

18、去的概率为1，则:00011( )( )( )dP tP tP tdt 我们假设系统是稳态的，即与时刻无关，于是可得：( )0ndPtdt00110PP1111()0nnnnnnnPPPn=1,2,3.00110PP0101()PP0011122()0PPP1111122()0PPP012011122()PPP 继续迭代：120011.nnnnnPP记12011.nnnnnC则平稳状态的分布为：0nnPC P如何求P0?由概率分布的要求：01nnP0111nnCP有：0111nnPC于是：小结120011.nnnnnPP 0111nnPC系统达到平稳状态后的状态分布-Pn举例某小型超市有一个收

19、款台。交款顾客以每小时30人的负指数分布到达。当收款台前只有一名顾客时，有一名收款员单独服务，收款时间为平均1.5min的负指数分布；当有2名或以上顾客时，将增加一名助手共同为顾客服务，收款时间将缩短至平均1min的负指数分布。求 收款台前有n 名顾客的概率Pn01.30/nh人16040/1.5h人260.60/1nh人解： 1011112.303 1( ).(40)(60)4 2nnnnnnC n=1,2.0111113111.( )42nnnnPC=则有由级数可知：11nna q当|q| 0称为过程N(t)的强度，而o(t)为当t-0时关于t 的高阶无穷小。( ,)1()P N t tt

20、tot00( )( )( , )( ),0N tN tN t tN t t 表示在时间间隔0,t内出现的质点数注：（2） 独立性任意两个不相交区间内顾客到达情况相互独立（3） 普通性在 t, t+t 内多于一个顾客到达的概率为()ot亦即对于充分小的t，在 t, t+t 内出现2个或2个以上质点的概率与出现一个质点的概率相比可以忽略不计。则称 N(t), t 0 为Poisson过程（强度为 ）。()otj=2P N(t, t+ t)=j定理1 设N(t)为时间 0, t 内到达系统的顾客数，则 N(t), t 0 为Poisson过程的充分必要条件是：()( )!nttP N tnenn=1

21、,2定理1说明，如果顾客的到达为Poisson流的话，则到达顾客数的分布恰为Poisson分布。举例顾客按泊松流到达餐厅，平均每小时20人，在上午11：07餐厅内有18人试求：到11：12餐厅内有20名顾客的概率分析：依题意知 20（人（人/小时）小时）()( )!nttP N tnen由公式可知：21(20)121(20)112()20.2623122!P Ne在（1/12）h内到达顾客2人的概率为：但无论是从Poisson过程的定义，还是根据其概率分布去对顾客的到达情况进行分析，都有许多不便之处。实际问题中比较容易得到和进行分析的往往是顾客相继到达系统的时刻，或相继到达的时间间隔。定理2设

22、N(t)为时间 0, t 内到达系统的顾客数，则 N(t), t 0 为参数为的Poisson过程的充分必要条件是：相续到达时间间隔服从相互独立的参数为的负指数分布。定理2说明，顾客相续到达时间间隔服从相互独立的参数为的负指数分布，与到达过程为参数的Poisson过程是等价的。举例某排队系统，顾客到达为泊松流，平均1人/h。假如有一名顾客于中午12点到达该排队系统情况下。试求：下一名分别于下午1点前、12点间、2点后到达的概率。分析：因顾客到达为泊松流，则说明顾客到达时间间隔T服从负指数分布，故T的概率密度fT(t)为：0( )00tTetftt（1）因下一名顾客在下午1:00前到达，有 0

23、T 1,则1100(01)0.6321ttPTe dte （2）下一名顾客在下午1:002:00之间达到，即 1 T 2,则2200(2)1(2)11 0.1353ttP TP Te dte 第三节 M/M/s等待制排队模型一、单服务台模型M/M/1/ 是指：顾客的相继到达时间服从参数为的负指数分布，服务台数为1，服务时间服从参数为的负指数分布，系统空间无限，允许无限排队。1、队长的分布由n =( n=0，1，2，) n =( n=0，1，2，)记 =/并设 4)；(7)在六天工作日内系统中没有顾客的小时数； (8)若决定当顾客平均逗留时间超过半个小时时，就应增加一个售票窗口，试问这相当于要求

24、顾客的平均到达率是原有的几倍？举例解：按题意可知=24人人/小时，小时，=40人人/小时，小时，=/=0.6（1）010 .4P（2）1 . 5 ()1L人（3）1W0.0625 =3.75 L小时分钟（4）220.91()qL 人（5）W0.03752.25qqL小时分钟（6）550110.0781p 4nn=0p(L 4)=1-p（7）因每天系统内没有顾客的小时数为8p0=3.2小时,故一周六天工作日内没有顾客的小时数为6*3.2=19.2小时.（8）当1112W时1=38,于是138/241.583、忙期和闲期在平衡状态下，忙期B和闲期I一般均为随机变量，求它们的分布比较麻烦。因此我们一

25、般考虑平均忙期 和平均闲期 BI由于忙期和闲期出现的概率分布为和和1,所以在一段时间内可以认为忙期和闲期的总长度之比为:1又因为忙期和闲期是交替出现的，所以在充分长的时间里，它们出现的平均次数应是相同的。于是，忙期的平均长度 和闲期的平均长度 之比也应是BI:11BI1BI又因为在到达为Poisson流时，根据负指数分布的无记忆性和到达与服务相互独立的假设，容易证明从系统空闲时刻起到下一个顾客到达时刻止（即闲期）的时间间隔仍服从参数为的负指数分布，且与到达时间间隔相互独立。因此，平均闲期应为111.11BI 11.11BI 1LW将上面两式比较，发现平均逗留时间（W）=平均忙期（ ）B这一结果

26、看上去是显然的，顾客在系统中逗留的时间越长，服务员连续忙的时间也就越长。因此，一个顾客在系统内的平均逗留时间应等于服务员平均连续忙的时间二、多服务台模型M/M/s/ 是指：设顾客单个到达，相继到达时间服从参数为的负指数分布，服务台数为s，每个服务台的服务时间相互独立，且服从参数为的负指数分布，系统空间无限，允许无限排队。当考虑系统处于平稳状态后队长N的概率分布,有(1,2. )(,1,2.)nnnnssss ss记ssc且1s有( /)!( /)( /)()!nnsn sn snCsss s n=1,2,sns1、队长的分布故00,1,2,!,!nnnn spnsnPpnss s其中1100)

27、!(1nssnspns上面两个式子给出了平衡条件下系统中顾客数为n的概率，当ns时，即系统中顾客数大于服务台个数，这时再来的顾客必须等待，因此记：0( ,)!(1)snn ssc sPPsErlang等待公式它给出了顾客到达系统时需要等待的概率由平稳状态下队长N的概率分布，可得到平均排队长Lq:102()!(1)nnssssLqns PPs 0( ,)!(1)ssc sPs由于故Lq又可表示为：( ,)1ssc sLq 2、几个主要数量指标由平均排队长Lq，可得到平均排队长L为：L=平均排队长 + 正在接受服务的顾客的平均数正在接受服务的顾客的平均数？记系统中正在接受服务的顾客的平均数为s显然 也是正在忙的服务台的平均数，故：s11snnnnssnPsP上式说明，平均在忙的服务台个数不依赖于服务台个数s在求得“正在接受服务的顾客的平均数” 后,我们可求得平均对长LsL=平均排队长 + 正在接受服务的顾客的平均数( ,)1ssLqc s 对于多服务台系统，Little公式依然成立，即有LW1qqLWW