《高级运筹学-排队论》由会员分享，可在线阅读，更多相关《高级运筹学-排队论（157页珍藏版）》请在金锄头文库上搜索。
1、Queuing Theory排排队队论论 第四章Where the Time Goes美国人一生中平均要花费美国人一生中平均要花费- - 6 6年年 吃吃5 5年年 排队等待排队等待4 4年年 做家务做家务2 2年年 回电话不成功回电话不成功 1 1年年 寻找放置不当的物品寻找放置不当的物品8 8个月个月 打开邮寄广告打开邮寄广告6 6个月个月 停在红灯前停在红灯前排队经济时隔10年重回国人生活 l银行排队排队时间：40分钟 l2007年某日，记者来到新街口招商银行营业大厅，取了排队号码纸：631号。此时，刚刚排到484号，排在记者前的还有147个人。 AC尼尔森公司的调查l在消费者经常遭遇排
2、队问题的各类场所l银行的排队率是73%；l医院以44%居第二；l零售商店的排队率以43%居第三。l在调查受访的消费者中，超过60%的受访者称通常一周用于排队的时间高于30分钟。l在所有受访的消费者中，有28%的人因排长队而转选其它服务提供商，66%的人因不想耽误时间而选择离开，而46%的人会有抱怨。 l行为科学家发现：无序排队是影响客户流失的一条主要原因。l研究结果表明等候时间：l超过十分钟，情绪开始急躁；l超过二十分钟，情绪表现厌烦；l超过四十分钟，常因恼火而离去。如何减少排队？l减少等候时间的解决方案 ：l开设更多的服务点；l提供自助服务解决方案；l雇用更多员工。排队管理系统的应用 l近两
3、年，许多公共服务场所出现了排队机(ticketdispenserunit)，窗口秩序为之一变，一种令人耳目一新的排队方式：l进得大门，在排队机的触摸屏上点一下所要办理的项目，排队机就会“吐”出一张像名片大小的号票，拿着这张号票安安静静地坐在休息区舒适的椅子上等候，轮到自己时，大屏幕和语音系统会提醒你到相应的窗口办理，井然有序。 DisneylPariss EuroDisney, TokyosDisney Japan, and the U.S.sDisneyWorldandDisneylandallhaveonefeatureincommonlonglinesandseeminglyendles
4、swaits。l在游乐园中的频频排队会极为扫兴lHowever, Disney is one of the worlds leadingcompanies in the scientific analysis of queuingtheory。lIt analyzes queuing behaviors and can predictwhichrideswilldrawwhatlengthcrowds。lTokeepvisitorshappy,Disneymakeslinesappeartobeconstantlymovingforward,entertainspeoplewhiletheyw
5、ait,andpostssignstellingvisitorshowmanyminutesuntiltheyreacheachride。Disneyl在佛罗里达州Orlando的DisneyLand里,游客们依着绳子排成许多队，指示牌可以估计出等待的时间，而许多大的电视屏幕为游客们提供消遣。lDisneyLand中的FastPass系统就是想解决排队问题DisneyWhat is FastPass?l工作原理：1.到达的顾客将自己的票插入FastPass的slot中2.FastPass计算出建议顾客返回的时间间隔（time interval）或时间点或时间窗（time window）3.顾客
6、无需排队，在指定的时间返回就可持票进入 如何计算顾客等待时间？服务系统的构成l排队现象抽象成服务系统，它有顾客、服务机构、队列和服务规则等组成典型的服务系统典型的服务系统Three Parts of a Queuing System at Daves Car-Wash排队系统的基本特征排队系统的基本特征离开排队规则到达过程退出需求需求群体群体什么是排队论l排队论是研究服务系统中排队现象随机规律的理论与方法 l因为排队现象是一个随机现象，因此在研究排队现象的时候，主要采用的是研究随机现象的概率论作为主要工具。此外，还有微分和微分方程。排队论研究目的和内容排队论研究目的和内容l减少顾客等待时间l计
7、算顾客平均等待时间l计算顾客的平均队长l提高服务系统的效率l计算服务强度l计算忙期闲期l对服务系统进行成本效益平衡分析l增加服务台的成本与效益分析排队论发展简述l1909年丹麦数学家A.K.Erlang(爱尔朗)服务于一家电话公司，他在解决自动电话设计问题时开始形成的，当时称为话务理论。他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的爱尔朗电话损失率公式。l上世纪30年代苏联数学家.辛钦把处于统计平衡的电话呼叫流称为最简单流。l上世纪50年代，美国数学家关于生灭过程的研究、英国人D.G. Kendall提出嵌入马尔可夫链理论，以及对排队队
8、型的分类方法，为排队论奠定了理论基础；l上世纪60年代更多的应用于生产线，交通等问题；l上世纪70年代应用于计算机网络、通信等领域；l如今通信系统仍然是排队论应用的主要领域,同时在运输、港口泊位设计、机器维修、库存控制等领域得到广泛应用，特别是服务行业。排队论发展简述本章大纲l4.1 排队服务系统的基本概念l4.2 输入与服务时间的分布l4.3 生灭过程l4.4 几种不同类型排队系统分析l标准M/M/1/l有限队列模型M/M/1/N/l顾客为有限源系统M/M/1/ml多服务台系统M/M/sl4.5 排队系统的优化4.1 排队服务系统的基本概念4.1.1 排队系统的一般表示l一个排队系统可以抽象
9、描述为：为了获得服务的顾客到达服务设施前排队，等候接受服务，服务完毕后就自行离开。l要求得到服务的对象称为顾客l服务者称为服务设施或服务台l顾客的到达和离开称为排队系统的输入和输出。l顾客的总体称为顾客源或输入源。l因此，任何一个排队系统是一种输入-输出系统。排队系统基本结构顾客源等候队列服务设施到达输入输出离开排队系统4.1 排队服务系统的基本概念商业服务系统商业服务系统系统类型系统类型顾客顾客服务台服务台理发店人理发师银行出纳服务人出纳ATM机服务人ATM机商店收银台人收银员电影院售票窗口人售票员机场检票处人航空公司代理人内部服务系统内部服务系统系统类型系统类型顾客顾客服务台服务台秘书服务
10、雇员秘书急救中心病员护士传真服务雇员传真机物料处理系统货物物料处理单元维护系统设备维修工人质检站物件质检员运输服务系统运输服务系统系统类型系统类型顾客顾客服务台服务台公路收费站汽车收费员卡车装货地卡车装货工人港口卸货区轮船卸货工人等待起飞的飞机飞机跑道航班服务人飞机出租车服务人出租车电梯服务人电梯消防部门火灾消防车停车场汽车停车空间急救车服务人急救车排队系统的三个基本组成部分：输入过程 (顾客按照怎样的规律到达)；排队规则 (顾客按照一定规则排队等待服务)；服务机构 (服务机构的设置,服务台的数量,服务的方式,服务时间分布等)4.1.2排队系统的组成一、输入 Arrival Character
11、istics顾客源是有限集还是无限集（Size of the arrival population）工厂内待修的机器数是有限集，售票处购票顾客源可认为是无限集。顾客到达系统的方式是单个的，还是成批的（Behavior of arrivals）如到达宾馆服务台住宿有散客，也有团体相继到达系统的时间间隔是确定性的还是随机性的（Pattern of arrival at the system）如自动装配线上待装配部件到达各工序的时间间隔是确定的。而多数顾客到达都是随机的，随机的服从何种概率分布：二项、负指数、爱尔朗分布等。到达过程(输入过程)的内容顾客总体数或顾客源数顾客总体数或顾客源数有限或无限有
12、限或无限顾客的到达类型顾客的到达类型单个或成批单个或成批顾客的到达间隔时间顾客的到达间隔时间间隔时间分布间隔时间分布二、排队规则 Queue Discipline顾客来到排队系统后如何排队等候服务的规则1、即时制（损失制）：当顾客到达时，如果所有服务台都已被占用，顾客可以随即离开系统；l如电话拨号后出现忙音，顾客可马上挂上电话。2、等候制：当顾客到达时，所有服务台都已被占用，顾客就加入排队队列等候服务。排队规则：lFIFO /FCFS 先到先服务，最常见lLIFO：乘电梯的顾客是后进先出lSIRO随机服务：从等待的顾客中随机取一个进行服务，人工电话交换l优先权服务：重病优先、老年人优先等3、混
13、合制：即时制和等候制相结合的一种排队服务规则。l队列长度有限制时：排队等候的人数超过预定数量，后来的顾客就自动离开。l旅馆的客房等l排队时间有限制时：顾客排队等候超过一定的时间就会自动离开，不能再等；l电子元器件库存超过一定时期，就失效了二、排队服务规则QueueDiscipline三、服务机构服务设施的结构、服务方式、服务时间：按服务设施个数分，有一个或多个之分，有并联和串联之分单台服务系统和多台服务系统服务方式有单个服务和成批服务服务时间是确定和随机的服务台结构等候队列服务台单服务台等候队列服务台2服务台1并列多台等候队列服务台1串列多台服务台2等候队列服务台3服务台1混列多台服务台4服务
14、台2 服务的方式是对单个顾客进行的，还是对成批顾客进行的。l公共汽车站台等待的顾客是成批进行服务的。服务方式服务时间对顾客的服务时间是确定的还是随机的。l自动冲洗汽车的装置对每辆汽车冲洗服务的时间是确定性的。l但大多数情况下服务时间是随机性的。对于随机要知道它的概率分布，是定长、负指数还是爱尔朗分布。Service time distribution排队结构-例多队多服务台多队多服务台领号领号 34826101211579单队多服务台单队多服务台入口入口 4.1.3 排队系统模型的分类l按照排队系统的输入、排队规则和服务机构等方面的不同，可以构成不同的排队模型4.2 输入与服务时间的分布 Di
15、stribution of Input and service timel组成一个排队系统的四要素l输入输出排队服务规则服务机构l顾客的输入和输出较复杂，是随机的l研究较多且结果较好的排队系统是：l顾客的输入过程服从泊松分布，而服务时间服从负指数分布的排队系统l若顾客输入过程服从泊松分布，则顾客相继到达的间隔时间服从负指数分布。 4.2.1 Poisson流（流（Poisson过程）过程） 定定义义：满足以下条件的输入流称为Poisson流（最简单流、Poisson过程）1、无后效性：不相交的时间区间内到达的顾客数互相独立。2、平稳性：对充分小的t，在时间区间t,t+t)内到达1个顾客的概率与
16、t无关，只与t有关:其中：是一个大于零的常数，表示单位时间内到达一个顾客的概率3、守序性：设在t,t+t）内到达多于一个顾客的概率为极小o(t)。实际情况是否符合三条性质l到达工厂机修车间的要维修的机器情况分析：l因为每台机器在各个时刻处的状态大致一样，所以在相等时间区间内各台机器损坏的概率大致相同，即要求维修的机器的流具有平稳性l由于一台机器的故障不会引起另一台机器的故障，而对同一台机器，这段时间内损坏的次数不影响到以后损坏次数多少，这表明具有无后效性l由于每台机器损坏概率很小，在足够小的时间区间内发生两台及以上机器损坏的概率几乎为0，这就符合普通性。l因此对到达机修车间的要维修的机器数可以
17、认为是最简单流,即poisson流。Poisson流与流与Poisson分布分布定定理理1 对对于于一一个个参参数数为为 的的Poisson流流，在在0，t内到达内到达n个顾客的概率为个顾客的概率为 即服从以即服从以 为参数的为参数的Poisson分布。分布。 Poisson Distributions for Arrival TimesProbabilityProbability=2=4：单位时间顾客的平均到达率Poisson流与负指数分布之间的关系 定理定理2 2 在排队系统中，如果单位时间内顾客到在排队系统中，如果单位时间内顾客到达数服从以达数服从以 为参数的为参数的Poisson分布，
18、则顾客相分布，则顾客相继到达的时间间隔服从以继到达的时间间隔服从以 为参数的负指数分为参数的负指数分布。布。 =0.41/为平均到达间隔时间（expectedinterarrivaltime)负指数分布Negative Exponential Distribution l分布函数分布函数 负指数分布无后效性无后效性表示T顾客到达的时间间隔已经过了s后，再等t的时间与s无关。.4.2.2 服务时间的分布l在排队系统中，一般假设服务时间（service time) 服从参数为的负指数分布：1/为平均服务时间（expectedservicetime)l平均服务时间平均服务时间Mean service
19、 time = 1/l分布函数分布函数4.2.2 服务时间的分布服务时间负指数分布的性质l假如服务设施对每个顾客的服务时间服从负指数分布，则对每个顾客的平均服务时间为1/l当服务设施对顾客的服务时间 t为参数 的负指数分布时 ，则有l在t, t+ t 时间内，没有顾客离去的概率为 1- tl在t, t+ t 时间内，恰有一个顾客离去的概率为 tl如果 t足够小，在t, t+ t 时间内有多于两个以上顾客 离去的概率趋于0l若按依次到达的间隔时间统计，顾客流服从负指数分布，则对同一顾客流若按单位时间到达的数量统计，它服从泊松分布。l泊松分布和负指数分布是对同一顾客流按不同方式进行统计时得到的两种
20、不同分布。服务时间负指数分布的性质4.2.3 k阶Erlang分布 lK个相互独立的且具有相同参数的负指数分布的随机变量的和，其分布称为k阶Erlang分布。l例如一台自动机床上依次利用三把刀具对一个工件进行加工，若每把刀具对该工件的加工时间均为参数 相同 的负指数分布，则该工件在自动机床上总的加工时间服从3阶Erlang分布l爱尔朗分布比负指数分布具有更广泛的适应性，k阶爱尔朗分布（Ek)的概率密度函数为： 4.2.3 k阶Erlang分布 Erlang分布的均值、方差和阶数l爱尔朗分布的均值和方差是由此可得爱尔朗分布的阶数：= 1k = 1k = 2k = 4k = 8k阶阶Erlang分
21、布分布 定定理理3 设设v1，v2，vk是是k个个互互相相独独立立的的，具具有有相相同同参参数数 的的负负指指数数分分布布的的随随机机变变量量，则则随随机机变变量量Ek=v1+v2+vk服从服从k阶阶Erlang分布，分布，Ek的密度函数为的密度函数为均值、方差和阶数l总服务时间服从爱尔朗分布，其均值和方差是由此可得爱尔朗分布的阶数：每个服务台的平均服务时间是：排队模型分类的排队模型分类的Kendall符号符号 Kendall提提出出一一个个排排队队系系统统的的分分类类方方法法，特特征征可以用六个参数表示，形式为：可以用六个参数表示，形式为：XYZ其中X顾客到达的概率分布，可取M、D、Ek、G
22、等；Y服务时间的概率分布，可取M、D、Ek、G等；Z服务台个数，取正整数；4.2.4 排队系统模型的分类lX、Y可有四种分布符号M、D、Ek、GlM负指数分布所描述的随机现象对于过去的事件具有无记忆性或称马尔可夫性MarkovlD定长分布，事件以不变的方式发生DeterministiclEkk阶爱尔朗分布ErlanglG一般随机分布General l如M/M/1表示到达的间隔时间服从负指数分布，服务时间也服从负指数分布的单服务台排队系统模型lM/D/2 表示到达的间隔时间服从负指数分布，服务时间为定长分布的双服务台排队系统模型4.2.4 排队系统模型的分类4.2.4 排队系统模型的分类1971
23、年又将年又将Kendall符号扩展为：符号扩展为： XYZ / ABC其中：其中：A 排队系统的最大容量，可取正整数排队系统的最大容量，可取正整数N或或 ；B 顾客源的最大容量，可取正整数顾客源的最大容量，可取正整数m或或 ；C 排队规则，可取排队规则，可取FCFS、LCFS等。等。特别约定，如略去后三项，则是指特别约定，如略去后三项，则是指 XYZ / FCFS因为本课程只介绍因为本课程只介绍FCFS, 所以略去最后一项所以略去最后一项例M/M/1/ / /FCFS表示：表示：顾客到达的时间间隔是负指数分布顾客到达的时间间隔是负指数分布服务时间是负指数分布服务时间是负指数分布一个服务台一个服
24、务台排队系统和顾客源的容量都是无限排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统实行先到先服务的一个服务系统 4.2.5 排队系统的相关名词术语l一个排队系统开始运行时,系统的运行状态在很大程度上取决于系统的初始状态和运转的时间。l经过一段时间以后，系统的状态将独立于初始状态和经历时间，这时系统处于稳定状态。l排队系统主要研究稳定状态。系统处于稳定状态时，工作状况与时刻t无关。l平均到达率n ：当系统中有n个顾客时，新来顾客的平均到达率（单位时间内顾客的到达数）。 l当对所有n值n为常数时，可用代替nl1/为相邻两顾客到达系统的平均间隔时间。l平均服务率n ：当系统中有n个顾客时，
25、单位时间内被服务完毕后离开系统的平均顾客数。l当对所有n值， n为常数时，可用代替nl1/为每个顾客的平均服务时间。lc系统中并列服务台数目。主要名词术语主要名词术语N(t) 在时刻t排队服务系统的顾客数，即系统在时刻t的瞬时状态。Pn(t) 在t时刻系统中恰好有n个顾客的概率主要分析系统平稳分布,即当系统达到统计平衡状态时处于状态n的概率,记为Pn主要系统性能指标1.平均逗留时间Ws ：进入系统的顾客逗留时间的平均值，包括接受服务的时间。2.平均等待时间Wq ：进入系统的顾客等待时间的平均值。3.服务机构工作强度 ：服务机构累计的工作时间占全部时间的比例 ，即服务强度 4.平均顾客数Ls ：
26、一个排队系统的顾客平均数，包括正在接受服务的顾客。5.平均队长Lq ：系统中等待服务的顾客平均数。常用的记号c服务台的个数n系统中的顾客数,即系统状态平均到达率，即单位时间内平均到达的顾客数平均服务率，即单位时间内服务完毕的顾客数Pn(t)时刻t系统状态n的概率Pn系统中的顾客数n（系统状态n)的稳态概率M顾客相继到达的时间间隔服从负指数分布D顾客相继到达的时间间隔服从定长分布Ek顾客相继到达的时间间隔服从k阶Erlang分布G顾客相继到达的时间间隔服从一般分布4.3 生灭过程l排队系统随机聚散服务系统l顾客到达是“生”，顾客离开是“灭”生灭过程Birth-death processlN(t)
27、是系统t时刻的状态（顾客数），则N(t),t=0就构成一个随机过程，若用“生”表示一个顾客的到达，“灭”代表一个顾客过程的离去，则对许多排队过程来说，N(t),t=0也是一类特殊的随机过程生灭过程生灭过程Birth-death processl定义：设N(t),t=0是一个随机过程，如果其概率分布满足有如下性质：（1）给定N(t)=n,到下一个“生”（顾客到达）的间隔时间服从参数为n的负指数分布;（2）给定N(t)=n,到下一个“灭”（顾客离去）的间隔时间服从参数为n的负指数分布;（3）同一时刻只能到达一个或离去一个顾客； 则称N(t),t=0 是生灭过程l当顾客到达时间服从参数为 的负指数分
28、布时，则有:l在 t t, , t t+ + t t 时间内，没有顾客到达的概率为 1- t tl在 t t, , t t+ + t t 时间内，恰有一个顾客到达的概率为 t tl如果 t t足够小，在 t t, , t t+ + t t 时间内有多于两个以上顾客到达的概率趋于0l当服务设施对顾客的服务时间服从参数 的负指数分布时，则有:l在 t t, , t t+ + t t 时间内，没有顾客离去的概率为 1- t tl在 t t, , t t+ + t t 时间内，恰有一个顾客离去的概率为 t tl如果 t t足够小，在 t t, , t t+ + t t 时间内有多于两个以上顾客离去的概
29、率趋于0 假设假设在在t+ t时刻系统中顾客数为时刻系统中顾客数为n的概率的概率Pn(t+ t) nnn+1n-1nPn(t)Pn-1(t)Pn+1(t)Pn(t)t时刻时刻t + t时刻时刻无到达，无离开无到达，无离开无到达，离开一个无到达，离开一个到达一个，无离开到达一个，无离开到达一个，离开一个到达一个，离开一个系统的过渡状态与稳定状态系统的过渡状态与稳定状态过渡过渡稳定稳定生灭过程的稳定状态方程生灭过程的瞬时状态一般很难求得，但可求得稳定状态分布生灭过程的稳定状态转移图l对于稳定的生灭状态，从平均意义上说有：“流入速率=流出速率”l稳定的生灭过程可以用状态转移图表示生灭过程的稳态方程l
30、基本原理l系统任意状态n达到稳态平衡的条件是：产生该状态的平均速率等于该状态转变成其他状态的平均速率l例如，对于系统状态n=0的情况，产生和破坏该状态的可能性有两种情况。如后图所示。n=0的状态的产生和破坏n=1状态的产生和破坏n=2状态的产生和破坏状态(n-1)的产生和破坏任意状态n的产生和破坏生灭过程Birth-death process012n-1nn+1生灭过程的基本公式生灭过程的状态概率因为所以即得生灭过程Birth-death process标准的排队过程是参数不随状态而变的特殊的生标准的排队过程是参数不随状态而变的特殊的生灭过程灭过程4.4 不同类型排队系统分析l输入过程为泊松流
31、，服务时间基本服从负指数分布的排队系统l标准M/M/1/l有限队列模型M/M/1/N/l顾客为有限源系统M/M/1/ml多服务台系统M/M/c 4.4.1标准排队模型标准排队模型 M/M/1/ / /FCFS 顾客到达的时间间隔是负指数分布顾客到达的时间间隔是负指数分布服务时间是负指数分布服务时间是负指数分布一个服务台一个服务台排队系统和顾客源的容量都是无限排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统实行先到先服务的一个服务系统M/M/1的状态转移分析的状态转移分析012n-1nn+1M/M/1排队模型排队模型 标准的排队过程是参数不随状态而变的特殊标准的排队过程是参数不随状态而
32、变的特殊的生灭过程的生灭过程得到得到 令令 称称 为服务强度，则为服务强度，则得得例例高高速速公公路路入入口口收收费费处处设设有有一一个个收收费费通通道道，汽汽车车到到达达服服从从Poisson分分布布，平平均均到到达达速速率率为为100辆辆小小时时，收收费费时时间间服服从从负负指指数数分分布布，平平均均收收费费时时间间为为15秒秒辆。求辆。求1、收费处空闲的概率；、收费处空闲的概率；2、收费处忙的概率；、收费处忙的概率；3、系统中分别有、系统中分别有1，2，3辆车的概率。辆车的概率。解解根据题意根据题意, =100辆辆/小时小时,1/ =15秒秒=1/240（小时（小时/辆）辆）,即即 24
33、0（辆（辆/小时）。小时）。因此，因此， = / =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辆车的概率为：辆车的概率为：P3= 3(1- )=0.417 30.583=0.0421系统绩效度量系统绩效度量 系统中的平均顾客数
34、系统中的平均顾客数Ls Expected number of customers in system 平均等待顾客个数平均等待顾客个数Lq（排队长）（排队长） Expected queue length (excludecustomersbeingserved) 顾客平均逗留时间顾客平均逗留时间Ws Waiting time in system 顾客平均（排队）等待时间顾客平均（排队）等待时间Wq Waiting time in queue (excludeservicetime)M/M/1/ / /FCFS的系统指标的系统指标系统中的平均顾客数系统中的平均顾客数Ls 队列中的平均顾客数队列中
35、的平均顾客数Lq 顾客在系统中的平均逗留时间l顾客在系统中的逗留时间Ts服从参数为-的负指数分布顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间Ws 顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间Wq John D. C. Little公式公式 例1.理发店空闭的概率2.店内有3个顾客的概率3.店内至少有一个顾客的概率4.店内顾客的平均数，等待服务顾客的平均数5.顾客在店内的平均逗留时间和平均等待时间6.必须在店内消耗15分钟以上的概率l某理发店只有一名理发师，来理发的顾客按泊松分布到达，平均每小时4人，理发时间服从负指数分布，平均需要6分钟，求l解 此为M/M/1系统，已知=4/6
36、0=1/15人/分 =1/6人/分，=/=(1/15)/(1/6)=0.4(1) P0=1=1=0.4=0.6(2) P3=(1)3=0.60.43=0.0384(3) P(n1)=1P(n1)=1P0=0.4(4) Ls=/(1)=0.4/(10.4)=0.667 人 Lq=Ls=0.667-0.4=0.227例例 高高速速公公路路入入口口收收费费处处设设有有一一个个收收费费通通道道，汽汽车车到到达达服服从从Poisson分分布布，平平均均到到达达速速率率为为200辆辆/小小时时，收收费费时时间间服服从从负负指指数数分分布布，平平均均收收费费时时间间为为15秒秒/辆。求辆。求Ls、Lq、Ws
37、和和Wq。解解根据题意，根据题意， =200辆辆/小时，小时， =240辆辆/小时，小时， = / =5/6。4.4.2有限队列模型有限队列模型 M/M/1/N/ /FCFS 当队列的容量从无限值变为有限值当队列的容量从无限值变为有限值N时，时，M/M/1/ / /FCFS就转化成为就转化成为M/M/1/N/ /FCFS 系统的状态转移图系统的状态转移图 012N-1N系统的状态概率平衡方程系统的状态概率平衡方程对于状态对于状态0： 0 0P0= 1 1P1对于状态对于状态n： n-1n-1Pn-1+ n+1n+1Pn+1=( n n+ n n)Pn 0n=1)=1-P0=0.75lLs=/(
38、-)=3lLq=Ls- =3-0.75=2.25lWs=Ls/=10 分lWq=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/
39、FCFS模型模型 离开离开服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列分析分析设系统容量为设系统容量为N(Nc)，当系统中的顾数，当系统中的顾数nN时，到时，到达的顾客就进入系统；当达的顾客就进入系统；当n=N时，到达的顾客就被时，到达的顾客就被拒绝。设顾客到达的速率为拒绝。设顾客到达的速率为，每个服务台服务的，每个服务台服务的速率为速率为，=/c。由于系统不会无限止地接纳。由于系统不会无限止地接纳顾客，对顾客，对不必加以限制。不必加以限制。 状态转移图与状态转移方程状态转移图与状态转移方程对状态对状态0:P0=P1对状态对状态 1:P0+2P2=(+)P1对状态对状态c： Pc-1
40、+cPc+1=(+c)Pc 对状态对状态N PN-1=cPN 01cN状态概率状态概率系统指标系统指标 例例 某某旅旅馆馆有有8个个单单人人房房间间，旅旅客客到到达达服服从从Poisson流流，平平均均速速率率为为6人人天天，旅旅客客平平均均逗逗留时间为留时间为2天，求：天，求：(1)每天客房平均占用数；每天客房平均占用数；(2)旅馆客满的概率。旅馆客满的概率。 解解旅馆旅馆8个房间全满的概率为个房间全满的概率为0.423 平均占用客房数为平均占用客房数为6.9间。客房占用率为间。客房占用率为86.6% M/M/c/m/FCFS模型模型 顾客到达修理速率发生故障等待修理的机器修理速率修理速率正
41、在修理的机器到达速率 (m-n)修理速率c运行的机器数 m-n状态概率状态概率 其中其中 系统指标系统指标有有效效到到达达速速率率e为为单单位位时时间间内内出出现现故故障障的的机机器数，有器数，有e=(m-Ls) 例例车车间间有有5台台机机器器，每每台台机机器器的的故故障障率率为为1次次小小时时，有有2个个修修理理工工负负责责修修理理这这5台台机机器器，工工作作效效率率相相同同，为为4台小时。求：台小时。求：(1)等待修理的平均机器数；等待修理的平均机器数；(2)等待修理及正在修理的平均机器数；等待修理及正在修理的平均机器数；(3)每小时发生故障的平均机器数；每小时发生故障的平均机器数；(4)
42、平均等待修理的时间；平均等待修理的时间；(5)平均停工时间。平均停工时间。解解 可以计算得到（算式略）：可以计算得到（算式略）：P1=0.394，P2=0.197，P3=0.074，P4=0.018，P5=0.002 由此，计算系统的各项运行指标如下：由此，计算系统的各项运行指标如下： 更复杂的排队问题l一般分布的排队问题l排队网络l优先排队l。l模特卡罗模拟法4.5 排队系统的优化排队系统的优化一般排队系统的总费用构成：一般排队系统的总费用构成：总费用总费用=服务能力费服务能力费+顾客损失费顾客损失费最佳服务能力最佳服务能力服务能力顾客损失费顾客损失费服务能力费服务能力费总费用总费用费用一、
43、M/M/1模型的单位时间总费用单位时间总费用单位时间单位时间服务成本服务成本单位顾客停单位顾客停留单位时间留单位时间损失成本损失成本1. M/M/1/ 模型优化模型优化M/M/1/模型的l顾客被拒概率为PK, 接受概率1-PK,l有效到达率e.l设每服务一个顾客服务机构获G元, 则单位时间收入期望值为l利润：M/M/1/K模型的l令： 得：l由此确定出r, 进而确定出使服务系统最优的* M/M/1/K模型的二、M/M/c: /FCFS模型的c每个服务台每个服务台单位时间成单位时间成本本每位顾客停留每位顾客停留单位时间损失单位时间损失成本成本二、M/M/c: /FCFS模型的c本章小节l掌握排队系统的特征、理解研究排队现象的目的；l掌握Poisson分布与负指数分布的特征、概率密度公式及特征值；l掌握标准排队模型M/M/1/ / 的系统特征、系统状态概率、系统指标的计算公式；l了解排队模型M/M/1/ N/ 和M/M/1/ / m的系统特征、系统指标值之间的关系（Little公式）；l了解多服务台排队模型M/M/c/ / 的系统特征、系统指标值之间的关系（Little公式）。
