运筹学导论之排队论

上传人:M****1 文档编号:587882461 上传时间:2024-09-06 格式:PPT 页数:115 大小:1.43MB
返回 下载 相关 举报
运筹学导论之排队论_第1页
第1页 / 共115页
运筹学导论之排队论_第2页
第2页 / 共115页
运筹学导论之排队论_第3页
第3页 / 共115页
运筹学导论之排队论_第4页
第4页 / 共115页
运筹学导论之排队论_第5页
第5页 / 共115页
点击查看更多>>
资源描述

《运筹学导论之排队论》由会员分享,可在线阅读,更多相关《运筹学导论之排队论(115页珍藏版)》请在金锄头文库上搜索。

1、第12章 排队系统1Agner Krarup Erlang1878-1929丹麦电信工程师,排队论之父研究人们打电话的方式,发展出人们需要等待多久的公式,并于1909年出版了关于排队理论的第一篇论文2UCLA, Leonard Kleinrock1934“互联网之父” ,“影响本世纪的50人”UCLA, James R. Jackson19242011排队网络之父排队论焕发了新的生命力,影响巨大!3生活在城市中的居民在生产、生活以及学习消费的过程中,存在大量的排队现象,例如,食堂打饭、图书馆借还书、超市收银台、医院等待看病、车辆在信号灯控制路口排队等待通过、在银行柜台前很多顾客等待办理业务、城

2、市中随时可能有急诊病人等待救护车的救援、港口外多艘万吨级船舶等待进港装卸货物、等待加工的零部件、等待装配的汽车等等。排队现象无处不在!排队现象无处不在!12.1 为什么要研究排队系统4排队现象的特征是:顾客以某种随机方式到达一个服务设施,之后在队列中等待,直到他们接受服务。一旦服务结束,通常离开系统。不花费极大的成本,等待现象是不可能完全消除的,我们的目标是要把他的不利影响减小到“可以忍受的”程度。56为什么会产生排队现象?泛泛地说,是由于顾客需求量大于设施能提供的服务量顾客需求量大于设施能提供的服务量。究竟又是什么原因导致服务设施的服务不足?原因很多,例如缺少服务点、提供的更多服务则经济上不

3、可行、空间限制无法容纳更多的服务台。一般来说,当然可以通过增加投资建设更多的服务设施增加投资建设更多的服务设施消除上述因素,但这需要分析“应该再增加多少服务台才可以消除排应该再增加多少服务台才可以消除排队?队?”。这就需要回答诸如“一个顾客必须要等待多久?一个顾客必须要等待多久?”、“排队长度会有多长?排队长度会有多长?”等很多问题。7例例McBurger是一家快餐店,有3个服务柜台。该店的经理委托他人调查顾客对服务速度慢的投诉。调查结果显示,服务台数量与服务等待时间之间有着如下关系:收款台数1234567平均等待时间16.210.36.94.82.91.91.3仔细观察这些数据,在3个柜台的

4、情况下,平均等待时间要7分钟。需要5个柜台才能把等待时间减少到3分钟。排队分析的结果可以用在费用优化模型中,即求两种费用(服务费用和等待费用)之和的最小值。如下图8顾客等待时间成本服务时间成本总费用服务水平费用最优服务水平上图显示了一个典型的费用模型,使用费用模型的主要障碍就是很难估计可靠的等待费用,特别是当人的行为成为操作的有机组成部分时。9分析排队系统的最终目的是为了对排队等待的顾客提供满意对排队等待的顾客提供满意的服务的服务。排队论主要研究服务设施的需求与用户延误之间的关系服务设施的需求与用户延误之间的关系,其在分析和规划城市服务设施扮演重要角色,例如地铁闸机的设置、消防站及消防车的配置

5、以及医疗救护点配置等等;在工业上的用途包括生产线的设计及布置、加工设备的配置;服务业中服务人员、柜台的设置及调配。研究排队论的目的10排队论,作为运筹学的重要分支,并不是一种优化理论作为运筹学的重要分支,并不是一种优化理论。 而是用于度量排队系统的性能指标,如队列的平均等待时间和服务设施的效率,这些度量指标可以用来设置服务设施。排队论的重点在于实际中排队分析结果的实施在于实际中排队分析结果的实施;为了充分理解排队系统的实际问题,就需要了解相当的基础理论背景。为此,首先介绍下构成排队系统的基本要素,然后介绍两个重要分布(泊松和指数分布)的“完全随机” 性质。11n一个排队系统中的主要参与者是顾客

6、顾客和服务台服务台。顾客从某个输入源输入源产生,到达一个服务设施设施,他们可以立即得到服务;n假如服务设施繁忙,也可能在队列队列中等待,当一个设施完成一次服务,如果有顾客等待的话,自动地“拉出”一个等待顾客;假如队列为空,设施就变成空闲,直到一个新的顾客到达。n从分析队列的角度,我们用连续两个顾客之间的到达时间到达时间间隔间隔表示顾客的到达,用对每个顾客的服务时间服务时间来描述服务。12.2 排队模型的要素12组成排队系统的要素至少包括:顾客输入源顾客输入源、队列队列以及服务台服务台,而服务台可以是单个的,也可以是多个并行联接的。如果要全面而准确的描述一个排队系统,则需要有如下6个要素:(1)

7、顾客到达模式顾客到达模式(顾客发生源类型);(2)服务台服务模式服务台服务模式(服务台服务方式);(3)排队规则排队规则;(4)排队系统容量排队系统容量;(5)服务通道数量服务通道数量;(6)服务阶段数量服务阶段数量。1312.2.1 顾客到达模式顾客到达模式 n排队系统的顾客输入源常常以单位时间内到达顾客的平均数量(mean arrival rate),两个连续顾客之间的平均到达间隔时间(mean interarrival time)来描述。n进入排队系统的顾客流可以是确定型的,此时完全可以用平均到达率或者平均间隔时间来表示;n如果进入排队系统的顾客流存在不确定性,此时用平均到达率或者平均间

8、隔时间,仅能描述输入顾客的随机过程的集体趋势,如果要进一步完整地描述顾客到达模式,则需要顾客到达随机变量的概率分布。n顾客到达模式可能不是一次到达一个顾客,而是一批一批到达的,此时相邻批次到达的间隔时间可能是随机的,每批次的顾客数量也是随机的。 14不同类型的顾客对于进入排队系统有不同的反应不同类型的顾客对于进入排队系统有不同的反应n有些顾客将一直在队列中等待直到获得服务才离开;n有些顾客会认为队列太长而不进入排队系统直接离开;n有些顾客则是到了排队系统临时决定不参加排队;n有些顾客则参与排队,但是失去耐心后决定离开系统;n而有时候在服务台前有两列或更多的队列,则有些类型的顾客在不同队列之间来

9、回排队,以缩短期望排队时间。 (后4种情况被认为是急躁型的顾客)n如果顾客到达模式不随时间改变(随机型到达模式的参数不随时间变化),则认为是平稳的;反之则为非平稳的。 15服务率服务率以单位时间内服务的顾客数量以服务一个顾客需要的时间当讨论服务台服务时间当讨论服务台服务时间(总假定排队系统是存在顾客要服务)确定型随机型,在系统非空条件下服务台的概率分布服务设施中服务台个数服务设施中服务台个数单个,每次只能服务一个顾客多个,可以同时服务多个顾客 12.2.2 服务台服务模式服务台服务模式 16n先到先服务(First come, First served),先进先出(First in, Firs

10、t out)n后到先服务(Last come, First served),库存系统。n随机顺序服务(Service in random order, SIRO),该规则不考虑顾客到达先后顺序,随机地选择顾客进行服务。n优先权排队规则l绝对抢先式,具有最高优先级的顾客即刻获得服务l非绝对抢先式,具有最高级别的顾客即刻在队列的最前端排队,但不能马上接受服务,直到当前顾客(即使其级别较低)服务结束以后才能接受服务12.2.3 排队规则排队规则 在出现顾客排队的情况下,选择顾客进行服务的选择机制。在出现顾客排队的情况下,选择顾客进行服务的选择机制。17在有些排队系统中,其排队等候区域受到物理空间限制

11、,当队列达到一定长度时,后续的顾客无法进入等待区,除非当前接受服务的顾客接受服务后离开系统,后续新到顾客才被允许进入排队区等待。对于有限队列长度的排队系统,其到达的顾客可视为其到达数量必须累积到排队容量以后的成批的排队。这是最简单成批到达情况,原因在于顾客的批量是固定值。 12.2.4 排队系统容量排队系统容量18n只有1个服务台的系统为单通道服务系统,在服务设施内设置多个并行的服务台是多通道服务系统。n两类不同的多通道服务系统,一般来说,在排队论中都假设服务台是相互独立运作的l多个服务台共同为一个队列服务l每个服务台仅为本队列提供服务12.2.5 服务通道数量服务通道数量在同一时刻能为顾客提

12、供服务的并行服务台数量在同一时刻能为顾客提供服务的并行服务台数量19排队系统中,许多服务设施提供的服务级数包括两类l单级的的,例如高速公路收费站、车站检票口等;l多多级的的,例如医院的体检系统。多级服务也可能是循环的,例如在含有产品质量跟踪控制功能的产品生产线中,一旦零部件经过检测不合格,则需要重新送到生产线再进行处理。下图是带有循环(有时候也称之为反馈)服务的排队系统。12.2.6 服务级数服务级数20上述6个排队系统基本特征元素,一般的可以充分的描述各种排队过程。从上述介绍也可以看出排队过程无处不在。排队模型的要素的总结必须充分理解排队系统的这6个特征元素,以清楚掌握排队系统的运作过程,具

13、体包括排队通道和服务设施之间是如何相互连接和影响的,顾客又是如何被分配到排队通道中的。 2112.3 指数分布的作用在大多数排队情况中,顾客的到达是完全随机的。这里的随机意味着,一个事件的发生(如一个顾客的到达或一项任务的完成)不受上一个时间发生以后所经过的时间长度的影响。排队模型中,随机到达间隔时间到达间隔时间和服务时间服务时间用指数分布来定量描述,定义为对于指数分布(exponential distribution)为单位时间内产生事件的速率。22为什么指数分布是完全随机的?如何理解?假定现在是上午8:20,上一个顾客到达时间是8:02,下一个到达发生在8:29之前的概率只是8:208:2

14、9这一区间的函数,与上一个事件的发生(8:02 8:20)以来所流逝的时间长度完全无关。这个结果称之为指数分布的无记忆性(memoryless)8:028:208:2923令指数分布 f(t) 表示相继事件之间的时间t的概率分布。如果S为上一个事件发生以来的时间区间,则遗忘性意味着而0SS+TSTt证明:注意到对于平均值为1/的指数函数,我们有P(AB)=P(B|A)P(A)24指数分布的无记忆性很重要,因为它意味着如果我们希望知道下次到达的时间概率分布,那么自上次到达以后流逝的时间长短不具有影响。我们假设到达时间间隔服从=6的指数分布。那么无记忆特性意味着自上次到达以后不管经过多长时间,那么

15、下一次到达时间的概率分布仍然为 6e-6t. 这意味着要观测未来到达模式,我们不需要跟踪上一次到达之后经过了多长时间。这种观测可以简化排队系统的分析。这种观测可以简化排队系统的分析。25例例假设在银行花费的时间以均值为10分钟指数地分布,即=1/10.问一个顾客在此银行中花费15分钟的概率是多少?给定一个顾客10分钟以后仍旧在银行中,她在银行中将花费超过15分钟的概率是多少?解 如果X表示顾客在这个银行中花费的时间,那么第一个概率正是第二个问题。由于指数分布,所以这个顾客已经在银行中花费10分钟是没有记忆的,这就意味着这个已经等待10分钟的顾客还要等5分钟,其概率正好是2612.4 生灭模型排

16、队系统中,任意时间它的状态用这个时间在系统中的人数表示。则该状态取决于各个时刻进入进入和离开离开人数的速率,这样的系统称之为生灭过程。生灭过程例子很多,地区的人口增减、细菌或细胞的繁殖与死亡、服务台前的顾客数量变化等等。为了简化,只考虑只有到达的纯生模型只有到达的纯生模型和只有离开的纯灭模型只有离开的纯灭模型。纯生模型的例子如为新生婴儿制作出生证明,纯灭模型的例子如一家商店对其库存货物的随机提货。2712.4.1 纯生模型纯生模型定义 p0(t)=t 时期内没有到达的概率已知到达时间间隔是指数分布的,并且每单位时间顾客到达率为,则对于一个充分小的时间区间 h0, 根据泰勒级数展开,有指数分布基

17、于假设:在充分小的h0期间,最多有一个事件能够发生。因此,当 h0,这一结果表示,h 期间一次到达的概率与 h 成正比例,到达率为比例常数。28定义某期间 t 内到达数目的分布pn(t) pn(t)= t 期间内有 n 个到达的概率在t 期间内有 n 个顾客的组合,包括以下两种情况:t+h(0,t)(0,t+h)nn0n-11000对于充分小的 h0, 根据互不相容的全概率公式,有根据互不相容的全概率公式,有29重新安排各项并取当 h0 的极限,得到其中 是 pn(t) 关于 t 的一阶导数.求解上述差分-微分方程,得到 这正是t期间平均有E(n|t)=t个到达的泊松分布(Poisson di

18、stribution) 上面的结果说明,若到达时间间隔服从平均值为1/的指数分布,则指定期间 t 内的到达数服从平均值t的泊松分布. 反之亦然.30指数分布指数分布泊松分布泊松分布随机变量相继到达之间的时间 t指定 T 期间的到达数 n取值范围t 0n= 0,1,2,密度函数平均值1/时间单元T期间有T个到达累积概率P(A期间无达到)指数分布与泊松分布之间的关系指数分布与泊松分布之间的关系31例例某人口稀少州的出生率为每12分钟出生一个新生婴儿。出生间隔时间服从指数分布,求下列各值:(1) 每年出生的平均数. (2)任何一天内无新生儿出生的概率.(3) 假设在3个小时时间内前2小时已经发出了4

19、0份出生证明,求这3个小时内发出50份出生证明的概率。 每天的出生率为该州每年出生人口为 任意一天没有新生儿出生的概率可以用泊松分布计算为假设在3个小时内的前2小时已经发出了40份出生证明,计算3小时内发出50份出生证明的概率,相当于1小时(=3-2)内出生10(=50-40)个新生儿,因为出生数的分布是泊松的.3212.4.2 纯灭模型纯灭模型在纯灭模型中,系统在0时刻开始时有N个顾客,后面没有新的顾客到达. 离开的发生率为每单位个顾客. 为了建立t时间单位后剩下n个顾客的概率pn(t)的差分-微分方程,根据出现n个顾客的情况,依据不相容的全概率公式,有t+h(0,t)(0,t+h)NN0n

20、n0n+1100033当h0, 得到这组方程的解得到下面的截尾泊松(Truncated Poisson)分布:经过 t 时间还剩下 n 个顾客的概率例例某杂货店鲜花柜台每周初库存18打玫瑰花. 平均情况下,鲜花柜台每天卖出去3打(一次一打),但实际需求量服从泊松分布. 一旦库存水平剩下5打,就再订货补充到18打,下周一送货。由于鲜花商品的特性,周末没有卖出的玫瑰花就要扔掉,求下列值:(1) 该周内任何一天订货的概率.(2) 周末扔掉的玫瑰花的平均数量.35因为购买的发生率为每天=3打,t 日结束前订货的概率为t (星期几)1234567t36912151821pn5(t)0.0000.0088

21、0.1242 0.4240 0.7324 0.9083 0.9755输出结果如下:周末(t=7)扔掉的玫瑰花平均数为E(n|t=7). 为了计算这个值, 我们需要用到pn(7), n=1,2,18, 计算结果为3612.5 广义泊松排队模型本节利用生灭模型,建立一个通用的排队模型。再根据到达间隔和服务时间服从指数分布,推导出基于泊松分布的排队论模型。广义模型的建立是基于排队情形的长期行为长期行为,或平稳状态行平稳状态行为为,这种状态在系统经过充分长时间的运行后得到的。这种分析和系统初期运行期间所常见的瞬时瞬时(transient)行为完全不同。本章不讨论瞬时行为的一个原因是由于对它的解析过于解

22、析过于复杂复杂;另一个原因是由于对大多数排队系统都是在平稳状态平稳状态下来研究下来研究的。37广义模型假设,到达率和离开率都是与状态相关的与状态相关的(state dependent), 也就说系统的状态以服务设施中的顾客数量来度量的。例如,在高速公路收费口,在高峰时间收费员通常会提高收费速度。道路交通网络上的信号灯控制系统会依据交通流量的变化,信号配时作出变化,此时道路网络的状态也是依赖于状态的。 定义 n=系统中的顾客总数(排队+正在接受服务的) n=已知系统中有n个顾客的到达率 n=已知系统中有n个顾客的离开率 pn=系统中有n个顾客的平稳状态概率广义模型中, pn作为 n 和 n 的函

23、数,利用这些概率求出系统行为中的度量指标,例如平均队长、平均等待时间和设备利用率.38如果以系统中的顾客数量来表示系统的状态,那么令排队系统中有n个用户的概率为 pn. 那么概率pn可以用下图的状态转移关状态转移关系图系图来得到. 根据第3小节的解释,在一个时间间隔h里多于1个事件发生的概率随着 h0而趋于0. 这就意味着,对于n0, 状态 n 只能变成两种可能的状态: 当以离开率 离开时变成n-1, 当按照到达率 到达时变成n+1. 状态0按照到达率 到达时只能变成状态1. 注意到,假如系统为空时, 因为没有离开发生, 没有定义.012n-1nn+139当系统处于平稳状态条件下,转入率等于转

24、出率,也就说单位时间进入该状态的平均次数和单位时间内离开状态的平均次数要相等。所以,状态 n 只能变成状态(n-1)和状态(n+1), 因此有类似地系统平稳状态下,单位时间内转入和转出次数要相等对于n=0的平衡方程为n-1nn+140从p0开始递归求解平衡方程如下:对于 n=0,有接下来,对 n=1,有用 替换并化简,得到用归纳法可以得到如下广义稳态概率公式从p0的值可以从等式 求出. 41解得42例例 B&K食品店有3个收款台. 经理根据店内顾客数量,按照下列安排决定提供服务的收款台个数。顾客按照平均10位/小时的泊松分布来收款区. 每位顾客的平均收款时间为指数分布,平均为12分钟. 求n个

25、顾客在收款区的平稳状态概率pn店内顾客数量使用收款台的个数1314626人以上3根据本题的信息,有43因此p0的值从下面的等式求出利用几何级数 得到44因此,p0=1/55. 知道了p0,就可以求出pn. 进而可以计算出系统中使用不同收款台个数的概率. 例如使用一个收款台的概率就是最多出现3个顾客的概率=p1+p2+p34512.6 特殊泊松排队12.6.1 排队系统的Kendall-Lee的符号表示下图显示带有c个并行服务台的特殊泊松排队情形。系统中的顾客数定义为正在接受服务的顾客加队列中等待服务的顾客。服务台1服务台1服务台1.服务台1服务台1服务台1.46为了方便表示上图排队的情形的特性

26、,采用下面的格式(a/b/c):(d/e/f)其中,a=到达分布,b=离开(服务时间)分布,c=并行服务台个数,d=排队规则,e=系统中最大运行容纳的顾客数,f=顾客输入源的多少(有限或无限)表示到达和离开分布表示到达和离开分布(a和和b)的标准记号有的标准记号有M=马尔科夫或泊松分布,D=常数(确定型)时间,Ek=参数为k的埃尔朗或分布(等价于独立指数分布和),GI=到达间隔时间的一般性/通用分布,G=服务时间的一般性/通用分布排队规则排队规则(符号符号d)包括包括FCFS=先到先服务,LCFS=后到先服务,SIRO=随机秩序服务,GD=一般/任意规则(M/D/10): (GD/20/),

27、(M/E2/8/):(FCFS/10/)4712.6.2 队列行为的平稳状态度量Ls=系统中顾客的期望数量Lq=队列中顾客的期望数量Ws=系统中的期望等待时间Wq=队列中的期望等待时间 =繁忙服务台的期望数最常用的队列行为度量指标有系统包括队列加上服务设施。下面说明如何利用系统的状态 n 及其平稳状态概率pn得到上述的度量指标。48首先根据数学期望得到系统中期望的顾客数 队列中期望的顾客数(平均队长)而Ls与Ws(以及Lq与Wq)之间的关系称为Little公式(little formula),具体关系包括如下系统中平均顾客数量与驻留系统的时间之间满足:队列中期望的顾客数(平均队长)与排队时间满

28、足:上述关系在相当一般的条件下成立。参数eff 是系统的有效到达率,当所有到达的顾客都可能加入时,就为;如果系统满了(存在容量限制系统),则顾客不能加入, eff 清华版p319不准确49Ws和Wq之间也存在直接的关系。由定义希望系统驻留时间=期望排队时间+期望服务时间可以写成 对上式两边乘以eff ,建立Ls与Lq的关系. 结合Little公式,得到根据定义,系统的平均顾客数与队列中平均的顾客数的差值等于繁忙服务台的平均数,因此有因此,得到了设施利用率=50例Ozark学院来访者的停车位只有5个,使用这些停车位的车辆以泊松分布到达,每小时到达6辆车。停车时间服从均值为30分钟的指数分布。到达

29、后找不到空泊位的来访者可以在停车场边临时停车位等待,直到有停着的车辆离开。临时车位只能放3辆车,而停不了也找不到临时停车位的车辆必须去别的地方停车,求(1) 系统中有n辆车的概率;(2) 实际使用停车场的车辆的有效到达率;(3) 停车场平均的停车数量;(4) 一辆车在停车场内等待停车位的平均时间;(5) 占据停车位的平均车辆数;(6) 停车场的平均使用率。注意到,一个停车位就是一个服务台,这样,系统共有c=5个并行的服务台. 另外,系统的最大容量为5+3=8辆车.可以按照之前介绍的pn计算。51将n和n代入下面的公式得到p0=0.0481252有了p0, 可以计算p1到p8如下n1234567

30、8pn0.144360.21654 0.21654 0.16240 0.09744 0.05847 0.03508 0.02105实际使用停车场的车辆的有效到达率的计算取决于停车场是否满了。有效到达率可以通过如下示意图计算车辆可以以eff 进入停车场或者以lost离开. 假如8辆车已经在停车场,则到达的车便不能进入停车场的概率为p8. 因此停车设施53停车场内车辆的平均数等于系统内车辆的平均数Ls. 我们可以用pn计算出Ls在临时车位等待的车辆实际上就是队列中的车辆. 因此,等待找到车位的等待时间就是Wq. 为确定Wq ,用因此占用了车位的平均车辆数就与繁忙服务台的平均数相等5412.6.3

31、单服务台模型本节介绍仅有一个服务台到达率为、服务率为的排队服务系统. 首先讨论系统容量无穷大的情形, 再讨论系统容量有限情形.之前介绍的各种排队系统的性能指标与具体的排队规则没有关系,所以我们用一般排队规则GD.(M/M/1):(GD/)基本假设如下:与排队系统状态无关55令 ,将其称之为服务强度或业务密度,则广义模型中 pn 的表达式简化为为了求p0的值,用等式设1, 利用几何级数求和公式有所以所以pn的数学推导将用到条件1或者. 如果则几何级发散,平稳态概率不存在. 这个结果有直观的意义,除非服务率大于到达率,否则队列长度将不断增长,不可能到达平稳状态.56排队系统的性能度量指标 Ls 可

32、以按照下面的方式得到:因为对于本情形 ,剩下的系统性能度量指标用6.2节的关系来计算. 因此有57例例Automata洗车房只运行一个清洗位. 车辆按照泊松分布到达,平均每小时4辆车,如果清洗位忙,则到达的车辆等在洗车房的停车场. 一辆车的清洗时间服从指数分布,平均值为10分钟. 不能进停车场的车辆可在洗车房的路边等待,这意味着从实际上来说,系统是没有容量限制的。为洗车房确定出停车场合适的停车泊位数量。该例中,=4辆车/小时,=60/10=6辆车/小时. 因为1,系统可以按照平稳状态运行。一般来说,不建议只用Ls来计算停车位数,因为从某种意义上,停车位代表了要保证最大可能的队列长度. 58例如

33、,停车场的设计要使得来到的车在至少90%的时候能找到停车位。为了做到这一点,令S表示停车位数,有S个停车位等价于系统中有S+1个位置. 假如系统中最多有S个停车位,则到达的车辆90%的时候都能找到位置. 这个条件等价于下面的概率条件:即根据有限项的几何技术求和公式,有所以两边取对数(注意到ln(x)0, 0x1,不等式变号)59(M/M/1):(GD/)的等待时间分布的等待时间分布广义模型中得到的 pn 与排队规则完全无关. 这意味着, 排队系统性能的平均度量指标(Ws, Wq, Ls, Lq) 可以用于所有排队规则.虽然平均等待时间与排队规则无关, 但它的概率密度函数却不然. 我们基于FCF

34、S规则的M/M/1模型导出等待时间的分布来说明.令为刚刚到达的一位顾客为了获得服务必须驻留在系统的时间. 根据FCFS规则,假如一个刚刚到达的顾客前面还有n个顾客在系统中,则其中 是当前在接受服务的顾客所需要的完成服务的时间, t2,t3,tn为队列中的n-1个顾客的服务时间. 时间tn+1表示刚刚到达的这个顾客的服务时间.60定义 为已知系统中有n个顾客在刚刚到达的顾客之前的条件下, 的条件密度函数. 因为服务时间的分布是指数的,指数分布的遗忘性质表明, 也是指数的,服从相同的分布. 因此,等于(n+1)个同分布的独立指数随机变量之和. 由概率论可知, 服从带有参数 和(n+1)的分布. 因

35、此有因此, 为一指数分布,平均值为61例例Automata洗车房只运行一个清洗位. 车辆按照=4辆车/小时泊松分布到达,该服务根据FCFS规则进行的,一辆车的清洗时间=60/10=6辆车/小时,如果清洗位忙,则到达的车辆等在洗车房的停车场. 不能进停车场的车辆可在洗车房的路边等待。评价用Ws作为估计系统中等待时间的可靠性.回答这个问题的一个方法是,估计顾客中等待时间超过Ws的比例,注意到 ,我们得到在FCFS规则下, 大约37%的顾客的等待时间比Ws要长. 我们注意到所计算的概率e-1与任何(M/M/1):(FCFS/)的到达率和服务率都无关, 这意味着它的值不能减少. 这样, 如果我们以Ws

36、来设计系统的话, 将有36.8%的顾客的等待时间长于平均等待时间62(M/M/1):(GD/N/)模型模型这个模型和(M/M/1):(GD/)不同之处在于,系统最多容纳的顾客数(最大队列长度为N-1)为N. 例如流水线上放置工件的空间是有限的.当系统中的顾客数达到 N 时,不允许再有到达,因此有利用 ,根据广义模型的稳态概率公式可以从等式 求出 p0 的值,这将得到63或因此有在这个模型中, 的值不需要小于1, 因为系统的到达受到系统顾客上限 N 的限制. 这意味着在这种情况下, 重要的是到达率eff而不是. 由于系统中有 N 个顾客,再来的顾客就不再进入系统. 此时64系统中期望顾客数可以计

37、算为当 时,Ls=N/2. 同样从Ls, 利用eff求出Ws, Wq, Lq.(M/M/1):(GD/m)模型模型这个模型和(M/M/1):(GD/)不同之处在于,系统的顾客源的顾客总数为m. 例如最常见的是机器发生故障停机待修的问题,此时总共有m台机器,机器发生故障即表示顾客“到达”,修理工人是服务员,类似的问题还有m个打字员共有一台打字机。虽然顾客有m个,但每个顾客到达并经过服务以后,仍然回到原来的发生源中,所以仍然会到达。顾客源总数达到m时,此时顾客单位时间内的到达次数依赖于当前尚未到达系统的顾客数,假设每个顾客进入系统的到达率为,进入系统的顾客为n, (0nm), 则系统外的顾客为m-

38、n, 所以系统的到达率而系统的离开率取决于服务台数量为1,此时有66根据广义模型,有根据根据 ,有注意,此时不要求 成立67根据Little公式以及系统期望公式,有6812.6.4 多服务台模型本节考虑有多个并行服务台的3个排队模型。前两个是上一节介绍的单服务台的多服务台版本,第三个模型针对自助服务的情况,等价于无限个并行服务台情形。(M/M/c):(GD/)模型模型在这个模型中有c个并行的服务台. 到达率为, 每个服务台的服务率为.因为对系统中的排队人数没有限制,所以使用并行服务台的效果使得设施的服务率成比例的增加. 根据广义模型(第五节),69因此,根据广义稳态概率计算公式p0的值可以从

39、求出,得到70系统的运行指标如下71例例某社区由两家出租车公司提供服务,每家公司有2辆出租车,且两家公司平等分享市场. 事实上,叫车电话到达每家公司的派车办公室的到达率为每小时8次. 每次乘车的平均时间为12分钟. 叫车电话按照泊松分布到达,乘车时间服从指数分布. 最近这个两家公司被一个投资商购买了,他打算把这两个派车办公室合成一个,以便为顾客提供更为优质的服务. 请分析老板的建议.从排队论角度来看,出租车是服务台,乘坐出租车就是服务,每家公司都可以表示为=8次/小时,出租车=60/12=5次/小时乘坐的(M/M/2): (GD/)模型. 合并以后得到(M/M/4): (GD/)模型,其参数为

40、=16次/小时, =5次/小时.72根据参数,利用排队系统运行性能指标计算公式得到下表cp0LsWsLqWq2850.114.4440.5562.8440.35641650.0275.5860.3492.3860.149可以看到,等待乘车的时间在两台出租车情况下为0.356,合并后情况为0.149小时,明显减少了50%多,公司合并以后效果非常明显.以上的结论是,共同分担服务总是一种更加有效的运作模式.73(M/M/c):(GD/N/), c N 模型模型这个模型与(M/M/c):(GD/)模型不同之处在于,系统上限是有限的并且等于N. 这就意味着,最大队列长度是N-c. 到达率和服务率分别是和

41、. 因为系统上限是N,因此有效到达率小于.按照广义模型,当前模型的将上述 代入稳态概率(第五节)的公式,得到74p0的值可以从 求出,得到排队系统的运行指标如下75例例在合并的出租车公司问题中,假设没有新的经费来购买更多出租车,又一个咨询专家向老板建议,有一种减少等待时间的办法是,一旦有6个顾客在等待用车,就让派车办公室通知新的顾客,告诉他们等待时间可能会很长. 这种举动定会让新的顾客去寻求别的公司的服务,但将会减少等式顾客的等待时间. 请评价这位专家的建议.将等待的顾客数限制在6个以内就等价于设定N=6+4=10个顾客. 因此专家建议的排队模型为(M/M/4):(GD/10/), 其中=16

42、次/小时, =5次/小时.cp0LsWsLqWq41650.031214.23980.27481.15420.0748176在设置系统能力上限之前的平均等待时间为Wq=0.149小时,大约是新的平均等待时间0.075小时的两倍. 等待时间的大幅度减少的代价是流失了大约3.6%的潜在顾客(p10=0.03574). 这个结果还不能反映顾客对公司经营印象的损害效果.77(M/M/):(GD/)自助服务模型自助服务模型在这个模型中,因为顾客本身也是服务台,因此服务台数量无限. 该模型的一个典型例子是参加进入系统选课的学生人数、在某个行业的公司数量. 这个模型假设稳定的到达率和服务率分别为和. 按照前

43、面的广义排队模型,有因此有p0的值可以从 求出,得到78排队系统的运行指标如下例例一个投资者每月平均投入1000美元购买一种股票市场的债券. 因为这个投资者必须要等待好的“买入”机会,实际发生的购买时间是完全随机的. 该投资者平均要把债券保留3年,但是当好的“卖出”机会来了,他会在随机的时间把它卖掉. 根据过去的统计表明,这个投资家大约25%的债券每年下跌20%左右,其余的75%每年上涨12%左右. 请估算这个投资者在股票市场的(长期)平均资产净值.79从实际情况看,这位投资者并不需要排队等待债券的买入或者卖出. 买卖间隔的平均时间是1个月,因此每年有=12只债券. 债券的销售率为每年=1/3

44、只债券. 此时每只债券就是就是服务台本身,有多少债券就有多少服务台,这一情形符合(M/M/):(GD/)模型. 已知 和 ,得到该投资者的预计(长期)平均年度净值为80机器伺服模型机器伺服模型 (M/M/R):(GD/K/K), RK这个模型的背景是有K台机器的车间,当1台机器出现故障时,就呼叫R个有时间的修理工之一来进行修理. 每台机器的故障率为每单位时间次故障,每个修理工修理故障及其的服务率为每单位时间台机器. 所有的故障和服务假定都服从泊松分布.这个模型类似于前面介绍的(M/M/1):(GD/m)模型模型,区别在于,本模型中有R个修理工。81本模型有有限个输入源,原因在于,此时总共有K台

45、机器,机器发生故障即表示顾客“到达”,修理工人是服务员。虽然有K台机器,但每个发生故障的机器经过维修以后回到良好状态,但是容易再次发生故障,所以仍然会有“顾客”到达。顾客源总数达到K时,此时顾客单位时间内的到达次数依赖于当前尚未到达系统的顾客数,假设每个顾客进入系统的到达率为,进入系统的顾客(即等待维修的机器)为n(0nm), 则此时有机器出现故障的发生率取决于完好状态的机器数量K-n.即82根据广义排队模型,根据广义排队模型的稳态概率计算公式,可以得到83遗憾的是,在(M/M/R):(GD/K/K) 模型(RK)中, 没有计算Ls、Lq、Ws和Wq的简单的、封闭型的表达式,必须用下面的基本定

46、义来计算:其中,例例ToolCo公司经营一家22台机床的工厂. 已知每台机床平均每2小时发生一次故障,修理工作平均需要12分钟. 故障间隔时间均服从指数分布. ToolCo想要确定修理工数量,以保证工厂能“平稳的”运转.84要分析该情况,考察作为修理工数的函数的机床生产率,这一生产率的度量可以定义为该情形属于(M/M/R):(GD/K/K) 模型,其中=0.5,=5, R=1,2,3,4,系统上限=22, 输入源=22. 根据前面的计算公式得到Reffp0LsLqWsWq10.554.9980.000412.00411.0042.4012.201820.558.8160.05644.36772

47、.6040.49540.295430.559.7670.10782.4660.5120.25250.052540.559.950.11992.100.1100.21110.0111修理工R1234机床生产率45.4480.1588.7990.45边际增长率34.718.641.6685上述结果说明,用1个修理工时,生产率很低(45.44%), 把修理工增加到2个时,生产率增加到80.15%,上升了34.71%. 当雇用3个修理工时,生产率只增加了8.64%,提高到88.79%,而4个修理工只把生产率增加很小量1.66%,提高到90.45%.从这些结果可以判断出,用2个修理工最划算,用3个修理工

48、的效果不明显,因为生产率只提高了8.64%. 当然我们可以用经费上的比较来确定是否划算,这需要对第三个修理工的成本和8.64%的生产率提高所带来的收入进行比较. 至于雇用第4个修理工,生产率的微量增长1.66%,不支持这样的计划。8612.7 一般服务时间M/G/1模型前面讨论的排队模型到达时间和服务时间均服从指数分布,这类系统的主要特征是Markov特性,即未来状态仅由当前系统的状态决定。但是当到达时间间隔和服务时间间隔至少至少有一个不服从负指数分布时,仅靠当前状态不足以推断未来状态,这样的排队模型称为非马氏排队模型。这类排队模型非常复杂,对于这类情形的分析,我们将在以后介绍采用模拟方法来研

49、究87(M/G/1):(GD/)排队模型本节介绍一个很少出现的具有解析结果的非泊松排队. 它所描述的情况是,服务时间 t 服从任何概率分布,平均值为Et, 方差为Vart. 这个模型的结果包括系统性能的基本指标Ls、Lq、Ws和Wq. 由于公式非常复杂, 这个模型没有pn的封闭型表达式.令为单服务台设施的到达率,已知服务时间分布的Et和Vart,并且Et/时,排队系统处于稳态,依次增加服务台个数,计算Ls及成本,结果表明,最优员工数为4.cLsz27.467397.3532.217146.8541.842140.1051.769148.4561.754159.7010212.10 排队网络当一

50、组资源由一组顾客共享时形成了排队网络。每个资源表示一个可能有多个服务台并行工作的服务中心。如果一个到达的顾客发现一个特定的中心繁忙,他可能加入该中心的队列等候服务(也可能离开该队列去寻找其他类型的服务). 在一站服务结束后,该顾客可能转入另一个服务中心,或者重新进入同一个中心,或者离开系统。103在串连队列中, 一旦一个顾客进入系统, 他将必须留在系统中直到接受了全套服务。通常, 每个服务台前都运行等候, 前面讨论的M/Ek/1模型是这种串连模型的特例, 在M/Ek/1模型中除了第一个服务台前可以有等候队列, 其他的服务台是不允许有等候的, 在这种情况下, 必须是n个服务项目都结束以后, 一个

51、新的顾客才运行进入系统接受服务。12.10.1 开放排队系统开放排队系统串联系统或序贯系统104服务网络行为由输出分布、各服务台的服务时间分布以及输入分布和各种排队规则共同确定. 在一个串连网络中, 由于一个服务台的输出是下一个服务台的输入, 网络的稳态性质由队列的输出分布共同规定. 在这个方面,Burke已经证明:在一个M/M/r队列中,稳态时的离开时间间隔是独立的随机变量. 而且,这样一个队列的输出构成了一个泊松过程,其中参数与输入的参数相同. 按照Burke的结论,当一个M/M/r串连网络的输入是一个参数为的泊松过程时,稳态时所有后续输入和输出均具有相同参数的泊松过程。奈奎斯特定理奈奎斯

52、特定理 一个具有参数的泊松输入的M/M/r队列的稳态输出也是一个具有参数为的泊松过程.105Jackson研究了更为一般的问题:每个服务台有独立的泊松到达以及从其他服务台输出的反馈. 稳态时,这样一个复杂网络本质上可以简化为一个具有独立服务台的串连网络, 其中每个服务台有等价的输入速率和服务速率. 作为研究在不同服务台有反馈和泊松到达的排队网络的先导, 我们先研究由两个单服务台M/M/1队列串联的最简单网络。考虑一个两阶段串联网络,它由服务速率分别为1和2的如下图所示的服务台组成。分析这个系统,我们需要追踪在服务线分析这个系统,我们需要追踪在服务线1和和2中的顾客数。中的顾客数。这种系统可用一

53、个随机过程建模,状态由 (n, m) 表示,其中nm0表示的了第 i 个服务台前的顾客数量. 设p(n,m)表示为第一项有n个顾客,第二项有m个顾客的概率106n,mn+1,m-1n+1,mn,m-1n-1,mn-1,m+1n,m1221对于该串联系统,我们该如何描述该系统的状态? 0,00,10,20,31,01,11,21,32,02,12,22,3222222222111111107由Burke定理知,稳态是两个服务台的离开时间间隔为指数随机变量,且该随机过程是马尔科夫的。对上述微分方程的稳态解为稳态时第1个服务台前有 n个顾客的概率为两个服务台均具有的泊松到达和指数服务时间,类似地,第

54、2个服务台前有m个顾客的概率为108从上面可以看到,系统中的顾客平均数 Ls 由下式给出对下面的排队系统如何处理?对下面的排队系统如何处理?Jackson给我们作出了回答给我们作出了回答.109将上述结果作实质性的推广. 考虑k个服务台的系统. 顾客按照速率为ri的独立泊松过程从系统外进入服务台i, i=1,2,k, 然后他们加入服务台 i 前面的队列直到轮到他们接受服务. 一旦一个顾客结束了服务台 i 的服务,然后他们以概率pij加入服务台j前面的队列,j=1,k. 因此, ,而 表示一个顾客在结束服务台 i 的服务以后离开系统的概率. 如果以 j 计为顾客到达服务台 j 的总的到达率,那么

55、 j 可以作为上式成立是由于 rj 是由系统外面到 j 的顾客的到达率,而 j 是顾客离开服务台 i 的速度(进去的速率等于离开的速率), 是从服务线 i 到达服务线 j 的速率. 110这表明在每个服务线的顾客数是独立的,而且具有形式其中j是在服务线j的指数服务速率,当然必须对一切的j都有系统中的各个服务线的顾客数为n1,n2,nk的概率为上述结果相当有意义。它表明在服务线 i 顾客数量的分布与具有速率i和i的M/M/1系统是一样的. 但是, 网络模型中节点i出的到达过程不一定是泊松过程。 因为, 如果一个顾客有可能访问一个服务线不只一次(这种情形为反馈). 到达过程将不再是泊松过程. 当容

56、许有反馈时,给定站点的顾客数的稳态概率与M/M/1模型相同,即使这个模型不是M/M/1.111Jackson已经证明:稳态时,上述存在反馈和前馈的网络中,每个服务线的顾客数 的分布与其他任何服务线的顾客数的分布相互独立,并且满足稳态时,在有反馈的情况下,各个服务线的合成输入不再是泊松过程,而服务台输出也不再是泊松过程。然而各个服务线是独立的,并且他们的行为类似于输入速率为i和服务速率为i 的M/M/c的排队系统.112根据Little公式,系统的平均等待时间为它是每一个M/M/1排队系统的平均等待时间之和.在这个系统中的平均数是113例 考虑一个拥有两条服务线的系统, 顾客从系统外部以速率为4的泊松过程到达服务线1, 而以速率为5的泊松过程到达服务线2. 服务线1和2的服务速率分别为8和10. 在完成服务线1的服务的顾客等可能地到服务线2或离开系统,然而从服务线2的离开者, 25%的人去服务线1, 其他人离开系统. 试确定极限概率, Ls和Ws.124525%50%50%75%810解解 到服务线1和2的总到达率分别计为1和2,根据下面的方程 ,有因此且115

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 医学/心理学 > 基础医学

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号