高级运筹学-排队论

1、Queuing Theory排队论 第四章Where the Time Goes美国人一生中平均要花费- 6年 吃5年 排队等待4年 做家务2年 回电话不成功 1年 寻找放置不当的物品8个月 打开邮寄广告6个月 停在红灯前排队经济时隔10年重回国人生活 银行排队排队时间：40分钟 2007年某日，记者来到新街口招商银行营业大厅，取了排队号码纸：631号。此时，刚刚排到484号，排在记者前的还有147个人。 AC尼尔森公司的调查在消费者经常遭遇排队问题的各类场所银行的排队率是73%；医院以44%居第二；零售商店的排队率以43%居第三。在调查受访的消费者中，超过60%的受访者称通常一周用于排队的时

2、间高于30分钟。在所有受访的消费者中，有28%的人因排长队而转选其它服务提供商，66%的人因不想耽误时间而选择离开，而46%的人会有抱怨。 行为科学家发现：无序排队是影响客户流失的一条主要原因。研究结果表明等候时间：超过十分钟，情绪开始急躁；超过二十分钟，情绪表现厌烦；超过四十分钟，常因恼火而离去。如何减少排队？减少等候时间的解决方案 ：开设更多的服务点；提供自助服务解决方案；雇用更多员工。排队管理系统的应用 近两年，许多公共服务场所出现了排队机(ticket dispenser unit) ，窗口秩序为之一变，一种令人耳目一新的排队方式：进得大门，在排队机的触摸屏上点一下所要办理的项目，排队

3、机就会“吐”出一张像名片大小的号票，拿着这张号票安安静静地坐在休息区舒适的椅子上等候，轮到自己时，大屏幕和语音系统会提醒你到相应的窗口办理，井然有序。 DisneyPariss EuroDisney, Tokyos Disney Japan, and the U.S.s Disney World and Disneyland all have one feature in commonlong lines and seemingly endless waits。在游乐园中的频频排队会极为扫兴However, Disney is one of the worlds leading compani

4、es in the scientific analysis of queuing theory。It analyzes queuing behaviors and can predict which rides will draw what length crowds。To keep visitors happy, Disney makes lines appear to be constantly moving forward, entertains people while they wait, and posts signs telling visitors how many minut

5、es until they reach each ride。Disney在佛罗里达州Orlando的DisneyLand里,游客们依着绳子排成许多队，指示牌可以估计出等待的时间，而许多大的电视屏幕为游客们提供消遣。DisneyLand中的FastPass系统就是想解决排队问题DisneyWhat is FastPass?工作原理：到达的顾客将自己的票插入FastPass的slot中FastPass计算出建议顾客返回的时间间隔（time interval）或时间点或时间窗（time window）顾客无需排队，在指定的时间返回就可持票进入 如何计算顾客等待时间？服务系统的构成排队现象抽象成服务系

6、统，它有顾客、服务机构、队列和服务规则等组成典型的服务系统Three Parts of a Queuing System at Daves Car-Wash排队系统的基本特征离开排队规则到达过程排队结构服务过程退出需求群体什么是排队论排队论是研究服务系统中排队现象随机规律的理论与方法 因为排队现象是一个随机现象，因此在研究排队现象的时候，主要采用的是研究随机现象的概率论作为主要工具。此外，还有微分和微分方程。排队论研究目的和内容减少顾客等待时间计算顾客平均等待时间计算顾客的平均队长提高服务系统的效率计算服务强度计算忙期闲期对服务系统进行成本效益平衡分析增加服务台的成本与效益分析排队论发展简述1

7、909年丹麦数学家A.K.Erlang(爱尔朗)服务于一家电话公司，他在解决自动电话设计问题时开始形成的，当时称为话务理论。他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的爱尔朗电话损失率公式。上世纪30年代苏联数学家.辛钦把处于统计平衡的电话呼叫流称为最简单流。 上世纪50年代，美国数学家关于生灭过程的研究、英国人D.G. Kendall提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论奠定了理论基础；上世纪60年代更多的应用于生产线，交通等问题；上世纪70年代应用于计算机网络、通信等领域；如今通信系统仍然是排队论应用的主要领域

8、,同时在运输、港口泊位设计、机器维修、库存控制等领域得到广泛应用，特别是服务行业。排队论发展简述本章大纲4.1 排队服务系统的基本概念4.2 输入与服务时间的分布4.3 生灭过程4.4 几种不同类型排队系统分析标准M/M/1/有限队列模型 M/M/1/N/顾客为有限源系统M/M/1/m多服务台系统M/M/s4.5 排队系统的优化4.1 排队服务系统的基本概念4.1.1 排队系统的一般表示一个排队系统可以抽象描述为：为了获得服务的顾客到达服务设施前排队，等候接受服务，服务完毕后就自行离开。要求得到服务的对象称为顾客服务者称为服务设施或服务台顾客的到达和离开称为排队系统的输入和输出。顾客的总体称为

9、顾客源或输入源。因此，任何一个排队系统是一种输入-输出系统。排队系统基本结构顾客源等候队列服务设施到达输入输出离开排队系统4.1 排队服务系统的基本概念商业服务系统系统类型顾客服务台理发店人理发师银行出纳服务人出纳ATM机服务人ATM机商店收银台人收银员电影院售票窗口人售票员机场检票处人航空公司代理人内部服务系统系统类型顾客服务台秘书服务雇员秘书急救中心病员护士传真服务雇员传真机物料处理系统货物物料处理单元维护系统设备维修工人质检站物件质检员运输服务系统系统类型顾客服务台公路收费站汽车收费员卡车装货地卡车装货工人港口卸货区轮船卸货工人等待起飞的飞机飞机跑道航班服务人飞机出租车服务人出租车电梯服

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

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

12、用，顾客就加入排队队列等候服务。排队规则：FIFO /FCFS 先到先服务，最常见LIFO：乘电梯的顾客是后进先出SIRO随机服务：从等待的顾客中随机取一个进行服务，人工电话交换优先权服务：重病优先、老年人优先等3、混合制：即时制和等候制相结合的一种排队服务规则。队列长度有限制时：排队等候的人数超过预定数量，后来的顾客就自动离开。旅馆的客房等排队时间有限制时：顾客排队等候超过一定的时间就会自动离开，不能再等；电子元器件库存超过一定时期，就失效了二、排队服务规则 Queue Discipline三、服务机构服务设施的结构、服务方式、服务时间：按服务设施个数分，有一个或多个之分，有并联和串联之分单

13、台服务系统和多台服务系统服务方式有单个服务和成批服务服务时间是确定和随机的服务台结构等候队列服务台单服务台等候队列服务台2服务台1并列多台等候队列服务台1串列多台服务台2等候队列服务台3服务台1混列多台服务台4服务台2 服务的方式是对单个顾客进行的，还是对成批顾客进行的。公共汽车站台等待的顾客是成批进行服务的。服务方式服务时间对顾客的服务时间是确定的还是随机的。自动冲洗汽车的装置对每辆汽车冲洗服务的时间是确定性的。但大多数情况下服务时间是随机性的。对于随机要知道它的概率分布，是定长、负指数还是爱尔朗分布。Service time distribution排队结构-例多队多服务台领号 34826

14、101211579单队多服务台入口 4.1.3 排队系统模型的分类按照排队系统的输入、排队规则和服务机构等方面的不同，可以构成不同的排队模型4.2 输入与服务时间的分布 Distribution of Input and service time组成一个排队系统的四要素输入输出排队服务规则服务机构顾客的输入和输出较复杂，是随机的研究较多且结果较好的排队系统是：顾客的输入过程服从泊松分布，而服务时间服从负指数分布的排队系统若顾客输入过程服从泊松分布，则顾客相继到达的间隔时间服从负指数分布。 4.2.1 Poisson流（Poisson过程） 定义：满足以下条件的输入流称为Poisson流（最简单

15、流、Poisson过程）1、无后效性：不相交的时间区间内到达的顾客数互相独立。2、平稳性：对充分小的t，在时间区间t, t+t)内到达1个顾客的概率与t无关，只与t有关:其中：l是一个大于零的常数，表示单位时间内到达一个顾客的概率 3、守序性：设在t, t+t）内到达多于一个顾客的概率为极小o(t)。实际情况是否符合三条性质到达工厂机修车间的要维修的机器情况分析：因为每台机器在各个时刻处的状态大致一样，所以在相等时间区间内各台机器损坏的概率大致相同，即要求维修的机器的流具有平稳性由于一台机器的故障不会引起另一台机器的故障，而对同一台机器，这段时间内损坏的次数不影响到以后损坏次数多少，这表明具有

16、无后效性由于每台机器损坏概率很小，在足够小的时间区间内发生两台及以上机器损坏的概率几乎为0，这就符合普通性。因此对到达机修车间的要维修的机器数可以认为是最简单流,即poisson流。Poisson流与Poisson分布定理1 对于一个参数为的Poisson流，在0，t内到达n个顾客的概率为即服从以为参数的Poisson分布。 Poisson Distributions for Arrival TimesProbabilityProbability=2=4：单位时间顾客的平均到达率Poisson流与负指数分布之间的关系 定理2 在排队系统中，如果单位时间内顾客到达数服从以为参数的Poisson分

17、布，则顾客相继到达的时间间隔服从以为参数的负指数分布。 l=0.41/为平均到达间隔时间（expected interarrival time)负指数分布Negative Exponential Distribution 分布函数 负指数分布无后效性无后效性表示T顾客到达的时间间隔已经过了s后，再等t的时间与s无关。.4.2.2 服务时间的分布在排队系统中，一般假设服务时间（service time) 服从参数为m的负指数分布：1/m为平均服务时间（expected service time)平均服务时间Mean service time = 1/分布函数4.2.2 服务时间的分布服务时间负指

18、数分布的性质假如服务设施对每个顾客的服务时间服从负指数分布，则对每个顾客的平均服务时间为1/m当服务设施对顾客的服务时间 t为参数 m 的负指数分布时 ，则有在t, t+t 时间内，没有顾客离去的概率为 1- mt在t, t+t 时间内，恰有一个顾客离去的概率为mt如果t足够小，在t, t+t 时间内有多于两个以上顾客 离去的概率趋于0若按依次到达的间隔时间统计，顾客流服从负指数分布，则对同一顾客流若按单位时间到达的数量统计，它服从泊松分布。泊松分布和负指数分布是对同一顾客流按不同方式进行统计时得到的两种不同分布。服务时间负指数分布的性质4.2.3 k阶Erlang分布 K个相互独立的且具有相

19、同参数的负指数分布的随机变量的和，其分布称为k阶Erlang分布。例如一台自动机床上依次利用三把刀具对一个工件进行加工，若每把刀具对该工件的加工时间均为参数 相同 的负指数分布，则该工件在自动机床上总的加工时间服从3阶Erlang分布爱尔朗分布比负指数分布具有更广泛的适应性，k阶爱尔朗分布（Ek)的概率密度函数为： 4.2.3 k阶Erlang分布 Erlang分布的均值、方差和阶数爱尔朗分布的均值和方差是由此可得爱尔朗分布的阶数：m=1k=1k=2k=4k=8k阶Erlang分布 定理3 设v1，v2，vk是k个互相独立的，具有相同参数m的负指数分布的随机变量，则随机变量Ek=v1+v2+v

20、k服从k阶Erlang分布，Ek的密度函数为均值、方差和阶数总服务时间服从爱尔朗分布，其均值和方差是由此可得爱尔朗分布的阶数：每个服务台的平均服务时间是：排队模型分类的Kendall符号 Kendall提出一个排队系统的分类方法，特征可以用六个参数表示，形式为：XYZ其中X 顾客到达的概率分布，可取M、D、Ek、G等；Y 服务时间的概率分布，可取M、D、Ek、G等；Z 服务台个数，取正整数；4.2.4 排队系统模型的分类X、Y可有四种分布符号M、D、Ek、GM负指数分布所描述的随机现象对于过去的事件具有无记忆性或称马尔可夫性MarkovD定长分布，事件以不变的方式发生Deterministic

21、Ekk阶爱尔朗分布ErlangG一般随机分布General 如M/M/1表示到达的间隔时间服从负指数分布，服务时间也服从负指数分布的单服务台排队系统模型M/D/2 表示到达的间隔时间服从负指数分布，服务时间为定长分布的双服务台排队系统模型4.2.4 排队系统模型的分类4.2.4 排队系统模型的分类1971年又将Kendall符号扩展为： XYZ / ABC其中：A 排队系统的最大容量，可取正整数N或；B 顾客源的最大容量，可取正整数m或；C 排队规则，可取FCFS、LCFS等。特别约定，如略去后三项，则是指 XYZ / FCFS因为本课程只介绍FCFS, 所以略去最后一项例M/M/1/FCFS

22、表示：顾客到达的时间间隔是负指数分布服务时间是负指数分布一个服务台排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统 4.2.5 排队系统的相关名词术语一个排队系统开始运行时,系统的运行状态在很大程度上取决于系统的初始状态和运转的时间。经过一段时间以后，系统的状态将独立于初始状态和经历时间，这时系统处于稳定状态。排队系统主要研究稳定状态。系统处于稳定状态时，工作状况与时刻t无关。平均到达率n ：当系统中有n个顾客时，新来顾客的平均到达率（单位时间内顾客的到达数）。 当对所有n值n为常数时，可用代替n1/为相邻两顾客到达系统的平均间隔时间。平均服务率n ：当系统中有n个顾客时，单位时间内

23、被服务完毕后离开系统的平均顾客数。当对所有n值， n为常数时，可用代替n1/为每个顾客的平均服务时间。c系统中并列服务台数目。主要名词术语主要名词术语N(t) 在时刻t排队服务系统的顾客数，即系统在时刻t的瞬时状态。Pn(t) 在t时刻系统中恰好有n个顾客的概率主要分析系统平稳分布,即当系统达到统计平衡状态时处于状态n的概率,记为Pn主要系统性能指标平均逗留时间Ws ：进入系统的顾客逗留时间的平均值，包括接受服务的时间。平均等待时间Wq ：进入系统的顾客等待时间的平均值。服务机构工作强度 ：服务机构累计的工作时间占全部时间的比例 ，即服务强度 平均顾客数Ls ：一个排队系统的顾客平均数，包括正

24、在接受服务的顾客。平均队长Lq ：系统中等待服务的顾客平均数。常用的记号c 服务台的个数n 系统中的顾客数,即系统状态 平均到达率，即单位时间内平均到达的顾客数 平均服务率，即单位时间内服务完毕的顾客数Pn(t) 时刻t系统状态n 的概率Pn 系统中的顾客数n（系统状态n)的稳态概率M 顾客相继到达的时间间隔服从负指数分布D 顾客相继到达的时间间隔服从定长分布Ek 顾客相继到达的时间间隔服从k阶Erlang分布G 顾客相继到达的时间间隔服从一般分布4.3 生灭过程排队系统随机聚散服务系统顾客到达是“生”，顾客离开是“灭”生灭过程Birth-death processN(t)是系统t时刻的状态（

25、顾客数），则N(t),t=0就构成一个随机过程，若用“生”表示一个顾客的到达，“灭”代表一个顾客过程的离去，则对许多排队过程来说， N(t),t=0也是一类特殊的随机过程生灭过程生灭过程Birth-death process定义：设N(t),t=0是一个随机过程，如果其概率分布满足有如下性质：（1）给定N(t)=n,到下一个“生”（顾客到达）的间隔时间服从参数为ln的负指数分布;（2）给定N(t)=n,到下一个“灭”（顾客离去）的间隔时间服从参数为mn的负指数分布;（3）同一时刻只能到达一个或离去一个顾客； 则称N(t),t=0 是生灭过程当顾客到达时间服从参数为l 的负指数分布时，则有:在t

26、, t+t 时间内，没有顾客到达的概率为 1- lt在t, t+t 时间内，恰有一个顾客到达的概率为lt如果t足够小，在t, t+t 时间内有多于两个以上顾客到达的概率趋于0当服务设施对顾客的服务时间服从参数 m 的负指数分布时，则有:在t, t+t 时间内，没有顾客离去的概率为 1- mt在t, t+t 时间内，恰有一个顾客离去的概率为mt如果t足够小，在t, t+t 时间内有多于两个以上顾客离去的概率趋于0 假设在t+t时刻系统中顾客数为n的概率Pn(t+t) nnn+1n-1nPn(t)Pn-1(t)Pn+1(t)Pn(t)t时刻t +t时刻无到达，无离开无到达，离开一个到达一个，无离开

27、到达一个，离开一个系统的过渡状态与稳定状态过渡稳定生灭过程的稳定状态方程生灭过程的瞬时状态一般很难求得，但可求得稳定状态分布生灭过程的稳定状态转移图对于稳定的生灭状态，从平均意义上说有：“流入速率=流出速率”稳定的生灭过程可以用状态转移图表示生灭过程的稳态方程基本原理系统任意状态n达到稳态平衡的条件是：产生该状态的平均速率等于该状态转变成其他状态的平均速率例如，对于系统状态n=0的情况，产生和破坏该状态的可能性有两种情况。如后图所示。n=0的状态的产生和破坏n=1状态的产生和破坏n=2状态的产生和破坏状态(n-1)的产生和破坏任意状态n的产生和破坏生灭过程Birth-death process

28、012n-1nn+1生灭过程的基本公式生灭过程的状态概率因为所以即得生灭过程Birth-death process标准的排队过程是参数不随状态而变的特殊的生灭过程4.4 不同类型排队系统分析输入过程为泊松流，服务时间基本服从负指数分布的排队系统标准M/M/1/有限队列模型 M/M/1/N/顾客为有限源系统M/M/1/m多服务台系统M/M/c 4.4.1标准排队模型 M/M/1/FCFS 顾客到达的时间间隔是负指数分布服务时间是负指数分布一个服务台排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统M/M/1的状态转移分析012n-1nn+1M/M/1排队模型 标准的排队过程是参数不随状态

29、而变的特殊的生灭过程得到 令称为服务强度，则得例高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为100辆小时，收费时间服从负指数分布，平均收费时间为15秒辆。求1、收费处空闲的概率；2、收费处忙的概率；3、系统中分别有1，2，3辆车的概率。解根据题意, =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.2

30、43系统中有2辆车的概率为：P2=2(1-)=0.417 20.583=0.101系统中有3辆车的概率为：P3=3(1-)=0.417 30.583=0.0421系统绩效度量 系统中的平均顾客数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 ti

31、me)M/M/1/FCFS的系统指标系统中的平均顾客数Ls 队列中的平均顾客数Lq 顾客在系统中的平均逗留时间顾客在系统中的逗留时间Ts服从参数为m-l的负指数分布顾客在系统中的平均逗留时间Ws 顾客在队列中的平均逗留时间Wq John D. C. Little公式 例理发店空闭的概率店内有3个顾客的概率店内至少有一个顾客的概率店内顾客的平均数，等待服务顾客的平均数顾客在店内的平均逗留时间和平均等待时间必须在店内消耗15分钟以上的概率某理发店只有一名理发师，来理发的顾客按泊松分布到达，平均每小时4人，理发时间服从负指数分布，平均需要6分钟，求解 此为M/M/1系统，已知l=4/60=1/15人

32、/分 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.0384(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例 高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为200辆/小时，收费时间服从负指数分布，平均收费时间为15秒/辆。求Ls、Lq、Ws和Wq。解根据题意，=200辆/小时，=240辆/小时，=/=5/6。4.4.2有限队列模型 M/M/1/N/

33、FCFS 当队列的容量从无限值变为有限值N时，M/M/1/FCFS就转化成为M/M/1/N/FCFS 系统的状态转移图 012N-1N系统的状态概率平衡方程对于状态0：0P0=1P1对于状态n：n-1Pn-1+n+1Pn+1=(n+n)Pn 0n=1)=1-P0=0.75Ls=/(-)=3Lq=Ls- =3-0.75=2.25Ws=Ls/=10 分Wq=Ws-1/=7.5 分 指标 模型M/M/3M/M/1服务台空闲的概率P00.07480.25(每个子系统）顾客必须等待的概率0.570.75平均队列长（等待顾客数）Lq1.702.25(每个子系统）平均队长（顾客数）Ls3.959.00（整个系统）平均逗留时间Ws4.39分钟10分钟平均等待时间Wq1.89分钟7.5分钟由此可见，单队比三队有显著的优越性。M/M/c/N/FCFS模型 离开服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列分析设系统容量为N(Nc)，当系统中的顾数nN时，到达的顾客就进入系统；当n=N时，到达