运筹学第10章-排队论课件

1、7/25/2022第10章 排队论1Where the Time Goes美国人一生中平均要花费- 7/25/202226年 吃5年 排队等待4年 做家务2年 回电话不成功 1年 寻找放置不当的物品8个月 打开邮寄广告6个月 停在红灯前AC尼尔森公司的调查在消费者经常遭遇排队问题的各类场所银行的排队率是73%；医院以44%居第二；零售商店的排队率以43%居第三。在调查受访的消费者中，超过60%的受访者称通常一周用于排队的时间高于30分钟。在所有受访的消费者中，有28%的人因排长队而转选其它服务提供商，66%的人因不想耽误时间而选择离开，而46%的人会有抱怨。 7/25/20223行为研究结论行

2、为科学家发现：无序排队是影响客户流失的一条主要原因。研究结果表明等候时间：超过十分钟，情绪开始急躁；超过二十分钟，情绪表现厌烦；超过四十分钟，常因恼火而离去。7/25/20224如何减少排队？减少等候时间的解决方案 ：开设更多的服务点；提供自助服务解决方案；雇用更多员工。7/25/20225排队管理系统的应用 近年来，许多公共服务场所出现了排队机(ticket dispenser unit) ，窗口秩序为之一变，一种令人耳目一新的排队方式：进得大门，在排队机的触摸屏上点一下所要办理的项目，排队机就会“吐”出一张像名片大小的号票，拿着这张号票安安静静地坐在休息区舒适的椅子上等候，轮到自己时，大屏

3、幕和语音系统会提醒你到相应的窗口办理，井然有序。 7/25/20226DisneyPariss EuroDisney, Tokyos Disney Japan, and the U.S.s Disney World and Disneyland all have one feature in commonlong lines and seemingly endless waits。在游乐园中的频频排队会极为扫兴7/25/20227Disney在佛罗里达州Orlando的DisneyLand里,游客们依着绳子排成许多队，指示牌可以估计出等待的时间，而许多大的电视屏幕为游客们提供消遣。Disney

4、Land中的FastPass系统就是想解决排队问题。7/25/20228What is FastPass?工作原理：到达的顾客将自己的票插入FastPass的slot中FastPass计算出建议顾客返回的时间间隔（time interval）或时间点或时间窗（time window）顾客无需排队，在指定的时间返回就可持票进入7/25/20229Disneys Fastpass7/25/202210 如何计算顾客等待时间？7/25/202211 排队论！服务系统的构成排队现象抽象成服务系统，它由顾客、服务机构、队列和服务规则等组成7/25/202212Three Parts of a Queui

5、ng System at Daves Car-Wash7/25/202213排队系统的基本特征离开排队规则到达过程排队结构服务过程退出需求群体7/25/202214什么是排队论排队论是研究服务系统中排队现象随机规律的理论与方法。 因为排队现象是一个随机现象，因此在研究排队现象的时候，主要采用的是研究随机现象的概率论作为主要工具，还有微分方程。7/25/202215排队论研究目的和内容减少顾客等待时间计算顾客平均等待时间计算顾客的平均队长提高服务系统的效率计算服务强度计算忙期闲期对服务系统进行成本效益平衡分析增加服务台的成本与效益分析7/25/202216排队论发展简述1909年丹麦数学家A.K

6、.Erlang(爱尔朗)服务于一家电话公司，他在解决自动电话设计问题时开始形成的，当时称为话务理论。他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的爱尔朗电话损失率公式。7/25/202217排队论发展简述上世纪50年代，英国人D.G. Kendall提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论奠定了理论基础；上世纪60年代更多的应用于生产线，交通信号灯绿信比的设置等问题；上世纪70年代应用于计算机网络、通信等领域；如今通信系统仍然是排队论应用的主要领域,同时在运输、港口泊位设计、机器维修、库存控制等领域得到广泛应用，特别是

7、服务行业。7/25/202218 CONTENTS019目录7/25/202210.1 排队服务系统的基本概念10.2 到达间隔与服务时间的分布10.3 生灭过程与系统状态方程10.4 单服务台负指数分布排队模型10.5 多服务台排队模型10.6 其他类型排队模型10.7 排队系统的优化10.1 排队服务系统的基本概念10.1 排队服务系统的基本概念一个排队系统可以抽象描述为：为了获得服务的顾客到达服务设施前排队，等候接受服务，服务完毕后就自行离开。要求得到服务的对象称为顾客服务者称为服务设施或服务台顾客的到达和离开称为排队系统的输入和输出。顾客的总体称为顾客源或输入源。因此，任何一个排队系统

8、是一种输入-输出系统。7/25/202221服务系统系统类型顾客服务台理发店人理发师银行出纳服务人出纳ATM机服务人ATM机超市收银台人收银员电影院售票窗口人售票员机场检票处人航空公司代理人7/25/202222服务系统系统类型顾客服务台公路收费站汽车收费员港口卸货区轮船卸货工人等待起飞的飞机飞机跑道航班服务人飞机出租车服务人出租车电梯服务人电梯停车场汽车停车空间急救车服务人急救车7/25/20222310.1.1 排队服务系统的构成事实上，任何一个排队服务系统都是一种输入-输出系统。顾客的到达和离开称为排队系统的输入和输出。顾客的总体称为顾客源或输入源。顾客源等候队列服务设施到达输入输出离开

9、排队系统7/25/202224排队系统的三个基本组成部分：输入过程 (顾客按照怎样的规律到达)；排队规则 (顾客按照一定规则排队等待服务)；服务机构 (服务机构的设置,服务台的数量,服务的方式,服务时间分布等)10.1.1 排队服务系统的构成7/25/202225一、输入 Arrival Characteristics顾客源是有限集还是无限集（Size of the arrival population）工厂内待修的机器数是有限集，售票处购票顾客源可认为是无限集。顾客到达系统的方式是单个的，还是成批的（Behavior of arrivals）如到达宾馆服务台住宿有散客，也有团体相继到达系统的

10、时间间隔是确定性的还是随机性的（Pattern of arrival at the system）如自动装配线上待装配部件到达各工序的时间间隔是确定的。而多数顾客到达都是随机的，随机的服从某种概率分布：二项、负指数、爱尔朗分布等。7/25/202226到达过程(输入过程)的内容顾客总体数或顾客源数有限或无限顾客的到达类型单个或成批顾客的到达间隔时间间隔时间分布7/25/202227二、排队规则 Queue Discipline顾客来到排队系统后如何排队等候服务的规则1、即时制（损失制）：当顾客到达时，如果所有服务台都已被占用，顾客可以随即离开系统；如电话拨号后出现忙音，顾客可马上挂上电话。2、

11、等候制：当顾客到达时，所有服务台都已被占用，顾客就加入排队队列等候服务。排队规则：FIFO /FCFS 先到先服务，最常见LIFO：乘电梯的顾客是后进先出SIRO随机服务：从等待的顾客中随机取一个进行服务，人工电话交换优先权服务：重病优先、老年人优先等7/25/202228二、排队规则 Queue Discipline3、混合制：即时制和等候制相结合的一种排队服务规则。队列长度有限制时：排队等候的人数超过预定数量，后来的顾客就自动离开。排队时间有限制时：顾客排队等候超过一定的时间就会自动离开，不能再等；电子元器件库存超过一定时期，就失效了7/25/202229三、服务机构服务设施的结构、服务方

12、式、服务时间：按服务设施个数分，有一个或多个之分，有并联和串联之分单台服务系统和多台服务系统服务方式有单个服务和成批服务服务时间是确定和随机的7/25/202230服务台结构等候队列服务台单服务台等候队列服务台2服务台1并列多台等候队列服务台1串列多台服务台2等候队列服务台3服务台1混列多台服务台4服务台27/25/202231服务方式 服务的方式是对单个顾客进行的，还是对成批顾客进行的。公共汽车站台等待的顾客是成批进行服务的。7/25/202232服务时间对顾客的服务时间是确定的还是随机的。自动冲洗汽车的装置对每辆汽车冲洗服务的时间是确定性的。但大多数情况下服务时间是随机性的。对于随机要知道

13、它的概率分布，是定长、负指数还是爱尔朗分布。Service time distribution7/25/202233排队结构多队多服务台领号 34826101211579单队多服务台入口 7/25/202234通常，按排队系统的主要特征来进行排队系统的分类。一般是以相继顾客到达系统的间隔时间分布类型、服务时间的分布类型和服务台数目为分类标志。Kendall提出一个排队系统的分类方法，特征可以用六个参数表示，形式为：XYZ其中X 顾客到达的概率分布，可取M、D、Ek、G等；Y 服务时间的概率分布，可取M、D、Ek、G等；Z 服务台个数，取正整数；10.1.2 排队服务系统的分类7/25/2022

14、35X、Y可有四种分布符号M、D、Ek、GM负指数分布所描述的随机现象对于过去的事件具有无记忆性或称马尔可夫性MarkovD定长分布，事件以不变的方式发生DeterministicEkk阶爱尔朗分布ErlangG一般随机分布General 如M/M/1表示到达的间隔时间服从负指数分布，服务时间也服从负指数分布的单服务台排队系统模型M/D/2 表示到达的间隔时间服从负指数分布，服务时间为定长分布的双服务台排队系统模型10.1.2 排队服务系统的分类7/25/2022361971年又将Kendall符号扩展为： XYZ / ABC其中：A 排队系统的最大容量，可取正整数N或；B 顾客源的最大容量，

15、可取正整数m或；C 排队规则，可取FCFS、LCFS等。特别约定，如略去后三项，则是指 XYZ / FCFS因为本课程只介绍FCFS, 所以略去最后一项10.1.2 排队服务系统的分类7/25/20223710.1.2 排队服务系统的分类例 M/M/1/FCFS表示：顾客到达的时间间隔是负指数分布服务时间是负指数分布一个服务台排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统 7/25/202238一个排队系统开始运行时,系统的运行状态在很大程度上取决于系统的初始状态和运转的时间。经过一段时间以后，系统的状态将独立于初始状态和经历时间，这时系统处于稳定状态。排队系统主要研究稳定状态。系

16、统处于稳定状态时，工作状况与时刻t无关。10.1.3 排队系统的相关术语7/25/202239主要名词术语平均到达率n ：当系统中有n个顾客时，新来顾客的平均到达率（单位时间内顾客的到达数）。 当对所有n值n为常数时，可用代替n1/为相邻两顾客到达系统的平均间隔时间。平均服务率n ：当系统中有n个顾客时，单位时间内被服务完毕后离开系统的平均顾客数。当对所有n值， n为常数时，可用代替n1/为每个顾客的平均服务时间。c系统中并列服务台数目。7/25/202240主要名词术语N (t ) 在时刻t 排队服务系统的顾客数，即系统在时刻t的瞬时状态。Pn (t ) 在t 时刻系统中恰好有n个顾客的概率

17、主要分析系统平稳分布,即当系统达到统计平衡状态时处于状态n的概率,记为Pn7/25/202241主要系统性能指标平均逗留时间Ws ：进入系统的顾客逗留时间的平均值，包括接受服务的时间。平均等待时间Wq ：进入系统的顾客等待时间的平均值。服务机构工作强度 ：服务机构累计的工作时间占全部时间的比例 ，即服务强度 平均顾客数Ls ：一个排队系统的顾客平均数，包括正在接受服务的顾客。平均队长Lq ：系统中等待服务的顾客平均数。7/25/202242常用的记号c 服务台的个数n 系统中的顾客数,即系统状态 平均到达率，即单位时间内平均到达的顾客数 平均服务率，即单位时间内服务完毕的顾客数Pn(t) 时刻

18、t系统状态n 的概率Pn 系统中的顾客数n（系统状态n)的稳态概率M 顾客相继到达的时间间隔服从负指数分布D 顾客相继到达的时间间隔服从定长分布Ek 顾客相继到达的时间间隔服从k阶Erlang分布G 顾客相继到达的时间间隔服从一般分布7/25/20224310.2 到达间隔与服务时间的分布组成一个排队系统的四要素输入输出排队服务规则服务机构顾客的输入和输出过程一般是随机的研究较多且结果较好的排队系统是：顾客的输入过程服从泊松分布，而服务时间服从负指数分布的排队系统若顾客输入过程服从泊松分布，则顾客相继到达的间隔时间服从负指数分布。10.2 到达间隔与服务时间的分布7/25/202245定义：满

19、足以下条件的输入流称为Poisson流（最简单流、Poisson过程）1）无后效性：不相交的时间区间内到达的顾客数互相独立。2）平稳性：对充分小的t，在时间区间t, t+t)内到达1个顾客的概率与t无关，只与t有关，即：其中：l是一个大于零的常数，表示单位时间内到达一个顾客的概率 3）守序性：设在t, t+t）内到达多于一个顾客的概率为极小o(t)。即10.2.1 Poisson流7/25/202246实际情况是否符合三条性质到达工厂机修车间的要维修的机器情况分析：因为每台机器在各个时刻处的状态大致一样，所以在相等时间区间内各台机器损坏的概率大致相同，即要求维修的机器的流具有平稳性由于一台机器

20、的故障不会引起另一台机器的故障，而对同一台机器，这段时间内损坏的次数不影响到以后损坏次数多少，这表明具有无后效性由于每台机器损坏概率很小，在足够小的时间区间内发生两台及以上机器损坏的概率几乎为0，这就符合普通性。因此对到达机修车间的要维修的机器数可以认为是最简单流,即poisson流。7/25/202247Poisson流与Poisson分布定理1 对于一个参数为的Poisson流，在0，t内到达n个顾客的概率为即服从以为参数的Poisson分布。 7/25/202248Poisson Distributions for Arrival TimesProbabilityProbability=

21、2=4：单位时间顾客的平均到达率7/25/202249Poisson流与负指数分布间的关系 定理2 在排队系统中，如果单位时间内顾客到达数服从以为参数的Poisson分布，则顾客相继到达的时间间隔T服从以为参数的负指数分布。 l=0.41/为平均到达间隔时间（expected interarrival time)7/25/202250负指数分布Negative Exponential Distribution 分布函数7/25/202251负指数分布无后效性无后效性表示T顾客到达的时间间隔已经过了s后，再等t的时间与s无关。7/25/20225210.2.2 服务时间的分布1）负指数分布在排队

22、系统中，一般假设服务时间（service time) 服从参数为m的负指数分布：1/m为平均服务时间（expected service time)7/25/202253平均服务时间Mean service time = 1/分布函数10.2.2 服务时间的分布7/25/202254服务时间负指数分布的性质假如服务设施对每个顾客的服务时间服从负指数分布，则对每个顾客的平均服务时间为1/m当服务设施对顾客的服务时间 t为参数 m 的负指数分布时 ，则有在t, t+t 时间内，没有顾客离去的概率为 1- mt在t, t+t 时间内，恰有一个顾客离去的概率为mt如果t足够小，在t, t+t 时间内有多

23、于两个以上顾客 离去的概率趋于07/25/202255服务时间负指数分布的性质若按依次到达的间隔时间统计，顾客流服从负指数分布，则对同一顾客流若按单位时间到达的数量统计，它服从泊松分布。泊松分布和负指数分布是对同一顾客流按不同方式进行统计时得到的两种不同分布。7/25/2022562）k阶Erlang分布爱尔朗分布比负指数分布具有更广泛的适应性，k阶爱尔朗分布（Ek)的概率密度函数为： 10.2.2 服务时间的分布7/25/202257爱尔朗分布的均值和方差是由此可得爱尔朗分布的阶数：10.2.2 服务时间的分布7/25/20225810.2.2 服务时间的分布m=1k=1k=2k=4k=87

24、/25/202259K个相互独立的且具有相同参数的负指数分布的随机变量的和，其分布服从k阶Erlang分布。例如一台自动机床上依次利用三把刀具对一个工件进行加工，若每把刀具对该工件的加工时间均为参数相同的负指数分布，则该工件在自动机床上总的加工时间服从3阶Erlang分布10.2.2 服务时间的分布7/25/202260定理3 设v1，v2，vk是k个互相独立的，具有相同参数m的负指数分布的随机变量，则随机变量Ek=v1+v2+vk服从k阶Erlang分布，Ek的密度函数为10.2.2 服务时间的分布7/25/202261均值、方差和阶数总服务时间服从爱尔朗分布，其均值和方差是由此可得爱尔朗分

25、布的阶数：每个服务台的平均服务时间是：7/25/20226210.3 生灭过程10.3 生灭过程排队系统随机聚散服务系统顾客到达是“生”，顾客离开是“灭”7/25/202264生灭过程 Birth-death processN(t)是系统t时刻的状态（顾客数），则N(t),t=0就构成一个随机过程，若用“生”表示一个顾客的到达，“灭”代表一个顾客过程的离去，则对许多排队过程来说， N(t),t=0也是一类特殊的随机过程生灭过程7/25/202265定义：设N(t),t=0是一个随机过程，如果其概率分布满足有如下性质：（1）给定N(t)=n,到下一个“生”（顾客到达）的间隔时间服从参数为ln的负

26、指数分布;（2）给定N(t)=n,到下一个“灭”（顾客离去）的间隔时间服从参数为mn的负指数分布;（3）同一时刻只能到达一个或离去一个顾客； 则称N(t),t=0 是生灭过程生灭过程 Birth-death process7/25/202266当顾客到达时间服从参数为n 的负指数分布时，则有:在t, t+t 时间内，没有顾客到达的概率为在t, t+t 时间内，恰有一个顾客到达的概率为如果t足够小，在t, t+t 时间内有多于两个以上顾客到达的概率趋于07/25/202267生灭过程 Birth-death process当服务设施对顾客的服务时间服从参数 的负指数分布时，则有:在t, t+t

27、时间内，没有顾客离去的概率为在t, t+t 时间内，恰有一个顾客离去的概率为如果t足够小，在t, t+t 时间内有多于两个以上顾客离去的概率趋于07/25/202268生灭过程 Birth-death processnnn+1n-1nPn(t)Pn-1(t)Pn+1(t)Pn(t)t时刻t +t时刻无到达，无离开无到达，离开一个到达一个，无离开到达一个，离开一个假设在t+t时刻系统中顾客数为n的概率Pn(t+t) 7/25/202269生灭过程 Birth-death process7/25/202270生灭过程 Birth-death process系统的过渡状态与稳定状态过渡稳定7/25/

28、202271生灭过程的稳定状态方程生灭过程的瞬时状态一般很难求得，但可求得稳定状态分布7/25/202272生灭过程的稳定状态转移图对于稳定的生灭状态，从平均意义上说有：“流入速率=流出速率”稳定的生灭过程可以用状态转移图表示7/25/202273生灭过程的稳态方程基本原理系统任意状态n达到稳态平衡的条件是：产生该状态的平均速率等于该状态转变成其他状态的平均速率例如，对于系统状态n=0的情况，产生和破坏该状态的可能性有两种情况。如后图所示。7/25/202274n=0 状态的产生和破坏7/25/202275n=1 状态的产生和破坏7/25/202276n=2 状态的产生和破坏7/25/2022

29、77n-1 状态的产生和破坏7/25/202278任意状态n的产生和破坏7/25/202279012n-1nn+17/25/202280生灭过程 Birth-death process生灭过程的基本公式7/25/202281生灭过程的状态概率因为所以即得7/25/202282标准的排队过程是参数不随状态而变的特殊的生灭过程7/25/202283生灭过程 Birth-death process10.4 单服务台负指数分布排队模型输入过程为泊松流，服务时间基本服从负指数分布的排队系统10.4.1 标准M/M/1/10.4.2 有限队列模型 M/M/1/N/10.4.3 顾客为有限源系统M/M/1/

30、m10.4 单服务台负指数分布排队模型7/25/20228510.4.1 标准排队模型 M/M/1/FCFS M/M/1/FCFS 顾客到达的时间间隔是负指数分布服务时间是负指数分布一个服务台排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统7/25/202286M/M/1的状态转移分析012n-1nn+17/25/202287M/M/1排队模型标准的排队过程是参数不随状态而变的特殊的生灭过程7/25/202288得到 令称为服务强度，则得由 M/M/1排队模型7/25/202289例10.1 高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为100辆小

31、时，收费时间服从负指数分布，平均收费时间为15秒辆。求1、收费处空闲的概率；2、收费处忙的概率；3、系统中分别有1，2，3辆车的概率。7/25/202290M/M/1排队模型根据题意, =100辆/小时,1/=15秒=1/240（小时/辆）,即240（辆/小时）。因此，=/=100/240=5/12。系统空闲的概率为：P0=1-=1-(5/12)=7/12=0.583系统忙的概率为：1-P0=1-(1-)=5/12=0.417系统中有1辆车的概率为：P1=(1-)=0.4170.583=0.243系统中有2辆车的概率为：P2=2(1-)=0.417 20.583=0.101系统中有3辆车的概率

32、为：P3=3(1-)=0.417 30.583=0.04217/25/202291M/M/1排队模型解：系统绩效度量 系统中的平均顾客数Ls Expected number of customers in system 平均等待顾客个数Lq（排队长） Expected queue length (exclude customers being served) 顾客平均逗留时间Ws Waiting time in system 顾客平均（排队）等待时间Wq Waiting time in queue (exclude service time)7/25/202292M/M/1/FCFS的系统指标

33、系统中的平均顾客数Ls 队列中的平均顾客数Lq 7/25/202293顾客在系统中的平均逗留时间顾客在系统中的逗留时间Ts服从参数为m-l的负指数分布7/25/202294顾客在系统中的平均逗留时间Ws 顾客在队列中的平均逗留时间Wq 顾客在系统中的平均逗留时间7/25/202295John D. C. Little公式 7/25/202296理发店空闲的概率店内有3个顾客的概率店内至少有一个顾客的概率店内顾客的平均数，等待服务顾客的平均数顾客在店内的平均逗留时间和平均等待时间必须在店内消耗15分钟以上的概率例10.2 某理发店只有一名理发师，来理发的顾客按泊松分布到达，平均每小时4人，理发时

34、间服从负指数分布，平均需要6分钟，求7/25/202297M/M/1排队模型(3) P(n1)=1P(n1)=1P0=0.4(4) Ls=r/(1r)=0.4/(10.4)=0.667 人 Lq=Lsr=0.667-0.4=0.227解： 此为M/M/1系统，已知l=4/60=1/15人/分 m=1/6人/分，r=l/m=(1/15)/(1/6)=0.4(1) P0=1r=1=0.4=0.6(2) P3=(1r)r3=0.60.43=0.03847/25/202298M/M/1排队模型 例10.3 高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为200辆/小时

35、，收费时间服从负指数分布，平均收费时间为15秒/辆。求Ls、Lq、Ws和Wq。7/25/202299M/M/1排队模型解：根据题意，=200辆/小时，=240辆/小时，=/=5/6。7/25/2022100M/M/1排队模型当队列的容量从无限值变为有限值N时，M/M/1/FCFS就转化成为M/M/1/N/FCFS 10.4.2 有限队列模型M/M/1/N/FCFS 7/25/2022101系统的状态转移图 012N-1N7/25/2022102系统的状态概率平衡方程对于状态0：0P0=1P1对于状态n：n-1Pn-1+n+1Pn+1=(n+n)Pn 0n=1)=1-P0=0.75Ls=/(-)

36、=3Lq=Ls- =3-0.75=2.25Ws=Ls/=10 分Wq=Ws-1/=7.5 分 7/25/2022136指标 模型M/M/3M/M/1服务台空闲的概率P00.07480.25(每个子系统）顾客必须等待的概率0.570.75平均队列长（等待顾客数）Lq1.702.25(每个子系统）平均队长（顾客数）Ls3.959.00（整个系统）平均逗留时间Ws4.39分钟10分钟平均等待时间Wq1.89分钟7.5分钟由此可见，单队比三队有显著的优越性。系统指标对比结果7/25/2022137离开服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列10.5.2 M/M/c/N/FCFS模型7/25/2022138分析设系统容量为N(Nc)，当系统中的顾数nN时，到达的顾客就进入系统；当n=N时，到达的顾客就被拒绝。设顾客到达的速率为，每个服务台服务的速率为，=/c。由于系统不会无限止地接纳顾客，对不必加以限制。 7/25/2022139状态转移图与状态转移方程对状态0:P0=P1对状态1:P0+2P2=(+)P1对状态c：