运筹学导论第八版12排队论

1第12章排队系统2AgnerKrarupErlang1878-1929丹麦电信工程师，排队论之父研究人们打电话的方式，发展出人们需要等待多久的公式，并于1909年出版了关于排队理论的第一篇论文3UCLA,LeonardKleinrock1934—“互联网之父”，“影响本世纪的50人”UCLA,JamesR.Jackson1924—2011排队网络之父排队论焕发了新的生命力，影响巨大！4生活在城市中的居民在生产、生活以及学习消费的过程中，存在大量的排队现象，例如，食堂打饭、图书馆借还书、超市收银台、医院等待看病、车辆在信号灯控制路口排队等待通过、在银行柜台前很多顾客等待办理业务、城市中随时可能有急诊病人等待救护车的救援、港口外多艘万吨级船舶等待进港装卸货物、等待加工的零部件、等待装配的汽车等等。排队现象无处不在！12.1为什么要研究排队系统5排队现象的特征是：顾客以某种随机方式到达一个服务设施，之后在队列中等待，直到他们接受服务。一旦服务结束，通常离开系统。不花费极大的成本，等待现象是不可能完全消除的，我们的目标是要把他的不利影响减小到“可以忍受的”程度。67为什么会产生排队现象？泛泛地说，是由于顾客需求量大于设施能提供的服务量。究竟又是什么原因导致服务设施的服务不足？原因很多，例如缺少服务点、提供的更多服务则经济上不可行、空间限制无法容纳更多的服务台。一般来说，当然可以通过增加投资建设更多的服务设施消除上述因素，但这需要分析“应该再增加多少服务台才可以消除排队？”。这就需要回答诸如“一个顾客必须要等待多久？”、“排队长度会有多长？”等很多问题。8例McBurger是一家快餐店，有3个服务柜台。该店的经理委托他人调查顾客对服务速度慢的投诉。调查结果显示，服务台数量与服务等待时间之间有着如下关系：收款台数1234567平均等待时间16.210.36.94.82.91.91.3仔细观察这些数据，在3个柜台的情况下，平均等待时间要7分钟。需要5个柜台才能把等待时间减少到3分钟。排队分析的结果可以用在费用优化模型中，即求两种费用(服务费用和等待费用)之和的最小值。如下图9顾客等待时间成本服务时间成本总费用服务水平费用最优服务水平上图显示了一个典型的费用模型，使用费用模型的主要障碍就是很难估计可靠的等待费用，特别是当人的行为成为操作的有机组成部分时。10分析排队系统的最终目的是为了对排队等待的顾客提供满意的服务。排队论主要研究服务设施的需求与用户延误之间的关系，其在分析和规划城市服务设施扮演重要角色，例如地铁闸机的设置、消防站及消防车的配置以及医疗救护点配置等等；在工业上的用途包括生产线的设计及布置、加工设备的配置；服务业中服务人员、柜台的设置及调配。研究排队论的目的11排队论，作为运筹学的重要分支，并不是一种优化理论。而是用于度量排队系统的性能指标，如队列的平均等待时间和服务设施的效率，这些度量指标可以用来设置服务设施。排队论的重点在于实际中排队分析结果的实施；为了充分理解排队系统的实际问题，就需要了解相当的基础理论背景。为此，首先介绍下构成排队系统的基本要素，然后介绍两个重要分布(泊松和指数分布)的“完全随机”性质。12一个排队系统中的主要参与者是顾客和服务台。顾客从某个输入源产生，到达一个服务设施，他们可以立即得到服务；假如服务设施繁忙，也可能在队列中等待，当一个设施完成一次服务，如果有顾客等待的话，自动地“拉出”一个等待顾客；假如队列为空，设施就变成空闲，直到一个新的顾客到达。从分析队列的角度，我们用连续两个顾客之间的到达时间间隔表示顾客的到达，用对每个顾客的服务时间来描述服务。12.2排队模型的要素13组成排队系统的要素至少包括：顾客输入源、队列以及服务台，而服务台可以是单个的，也可以是多个并行联接的。如果要全面而准确的描述一个排队系统，则需要有如下6个要素：（1）顾客到达模式（顾客发生源类型）；（2）服务台服务模式（服务台服务方式）；（3）排队规则；（4）排队系统容量；（5）服务通道数量；（6）服务阶段数量。顾客发生源队列服务台到达系统的基准位置离开系统的基准位置1412.2.1顾客到达模式排队系统的顾客输入源常常以单位时间内到达顾客的平均数量（meanarrivalrate），两个连续顾客之间的平均到达间隔时间（meaninterarrivaltime）来描述。进入排队系统的顾客流可以是确定型的，此时完全可以用平均到达率或者平均间隔时间来表示；如果进入排队系统的顾客流存在不确定性，此时用平均到达率或者平均间隔时间，仅能描述输入顾客的随机过程的集体趋势，如果要进一步完整地描述顾客到达模式，则需要顾客到达随机变量的概率分布。顾客到达模式可能不是一次到达一个顾客，而是一批一批到达的，此时相邻批次到达的间隔时间可能是随机的，每批次的顾客数量也是随机的。15不同类型的顾客对于进入排队系统有不同的反应有些顾客将一直在队列中等待直到获得服务才离开；有些顾客会认为队列太长而不进入排队系统直接离开；有些顾客则是到了排队系统临时决定不参加排队；有些顾客则参与排队，但是失去耐心后决定离开系统；而有时候在服务台前有两列或更多的队列，则有些类型的顾客在不同队列之间来回排队，以缩短期望排队时间。（后4种情况被认为是急躁型的顾客）如果顾客到达模式不随时间改变（随机型到达模式的参数不随时间变化），则认为是平稳的；反之则为非平稳的。16服务率•以单位时间内服务的顾客数量•以服务一个顾客需要的时间当讨论服务台服务时间（总假定排队系统是存在顾客要服务）•确定型•随机型，在系统非空条件下服务台的概率分布服务设施中服务台个数•单个，每次只能服务一个顾客•多个，可以同时服务多个顾客12.2.2服务台服务模式17先到先服务（Firstcome,Firstserved），先进先出（Firstin,Firstout）后到先服务（Lastcome,Firstserved），库存系统。随机顺序服务（Serviceinrandomorder,SIRO），该规则不考虑顾客到达先后顺序，随机地选择顾客进行服务。优先权排队规则绝对抢先式，具有最高优先级的顾客即刻获得服务非绝对抢先式，具有最高级别的顾客即刻在队列的最前端排队，但不能马上接受服务，直到当前顾客（即使其级别较低）服务结束以后才能接受服务12.2.3排队规则在出现顾客排队的情况下，选择顾客进行服务的选择机制。18在有些排队系统中，其排队等候区域受到物理空间限制，当队列达到一定长度时，后续的顾客无法进入等待区，除非当前接受服务的顾客接受服务后离开系统，后续新到顾客才被允许进入排队区等待。对于有限队列长度的排队系统，其到达的顾客可视为其到达数量必须累积到排队容量以后的成批的排队。这是最简单成批到达情况，原因在于顾客的批量是固定值。12.2.4排队系统容量19只有1个服务台的系统为单通道服务系统，在服务设施内设置多个并行的服务台是多通道服务系统。两类不同的多通道服务系统，一般来说，在排队论中都假设服务台是相互独立运作的多个服务台共同为一个队列服务每个服务台仅为本队列提供服务顾客发生源队列服务台到达系统的基准位置离开系统的基准位置...a)...b)12.2.5服务通道数量在同一时刻能为顾客提供服务的并行服务台数量20排队系统中，许多服务设施提供的服务级数包括两类单级的，例如高速公路收费站、车站检票口等；多级的，例如医院的体检系统。多级服务也可能是循环的，例如在含有产品质量跟踪控制功能的产品生产线中，一旦零部件经过检测不合格，则需要重新送到生产线再进行处理。下图是带有循环（有时候也称之为反馈）服务的排队系统。12.2.6服务级数21上述6个排队系统基本特征元素，一般的可以充分的描述各种排队过程。从上述介绍也可以看出排队过程无处不在。排队模型的要素的总结必须充分理解排队系统的这6个特征元素，以清楚掌握排队系统的运作过程，具体包括排队通道和服务设施之间是如何相互连接和影响的，顾客又是如何被分配到排队通道中的。2212.3指数分布的作用在大多数排队情况中，顾客的到达是完全随机的。这里的随机意味着，一个事件的发生(如一个顾客的到达或一项任务的完成)不受上一个时间发生以后所经过的时间长度的影响。排队模型中，随机到达间隔时间和服务时间用指数分布来定量描述，定义为,0tftet对于指数分布(exponentialdistribution)2011()1TttEtVartPtTedteλ为单位时间内产生事件的速率。23为什么指数分布是完全随机的？如何理解？假定现在是上午8:20,上一个顾客到达时间是8:02，下一个到达发生在8:29之前的概率只是8:20~8:29这一区间的函数，与上一个事件的发生(8:02~8:20)以来所流逝的时间长度完全无关。这个结果称之为指数分布的无记忆性(memoryless)8:028:208:29(8:298:20(8:208:02)|(8:208:02))(8:298:20)PttPt(918|18)(9)PttPt24令指数分布f(t)表示相继事件之间的时间t的概率分布。如果S为上一个事件发生以来的时间区间，则遗忘性意味着(|)()PtTStSPtT()1()TPtTPtTe而0SS+TSTt证明：注意到对于平均值为1/λ的指数函数，我们有()(|)()()()()TSTSPtTStSPtTStSPtSPtTSeePtTPtSeP(AB)=P(B|A)P(A)25指数分布的无记忆性很重要，因为它意味着如果我们希望知道下次到达的时间概率分布，那么自上次到达以后流逝的时间长短不具有影响。我们假设到达时间间隔服从λ=6的指数分布。那么无记忆特性意味着自上次到达以后不管经过多长时间，那么下一次到达时间的概率分布仍然为6e-6t.这意味着要观测未来到达模式，我们不需要跟踪上一次到达之后经过了多长时间。这种观测可以简化排队系统的分析。26例假设在银行花费的时间以均值为10分钟指数地分布，即λ=1/10.问一个顾客在此银行中花费15分钟的概率是多少？给定一个顾客10分钟以后仍旧在银行中，她在银行中将花费超过15分钟的概率是多少？解如果X表示顾客在这个银行中花费的时间，那么第一个概率正是第二个问题。由于指数分布，所以这个顾客已经在银行中花费10分钟是没有记忆的，这就意味着这个已经等待10分钟的顾客还要等5分钟，其概率正好是153/2150.220PXee51/250.604PXee2712.4生灭模型排队系统中，任意时间它的状态用这个时间在系统中的人数表示。则该状态取决于各个时刻进入和离开人数的速率，这样的系统称之为生灭过程。生灭过程例子很多，地区的人口增减、细菌或细胞的繁殖与死亡、服务台前的顾客数量变化等等。为了简化，只考虑只有到达的纯生模型和只有离开的纯灭模型。纯生模型的例子如为新生婴儿制作出生证明，纯灭模型的例子如一家商店对其库存货物的随机提货。2812.4.1纯生模型定义p0(t)=t时期内没有到达的概率已知到达时间间隔是指数分布的，并且每单位时间顾客到达率为λ，则()()1()1(1)=0ttpt=Pt=-Pt=--ee到达间隔时间≥到达间隔时间≤对于一个充分小的时间区间h0,根据泰勒级数展开，有2201102!hhphehhh指数分布基于假设：在充分小的h0期间，最多有一个事件能够发生。因此，当h→0，101phphh这一结果表示，h期间一次到达的概率与h成正比例，到达率λ为比例常数。29定义某期间t内到达数目的分布pn(t)pn(t)=t期间内有n个到达的概率在t期间内有n个顾客的组合，包括以下两种情况：0110010,0,01,0(1)1,0(2)nnnn