高级运筹学-排队论.ppt

《高级运筹学-排队论.ppt》由会员分享，可在线阅读，更多相关《高级运筹学-排队论.ppt（139页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Page:1QSCQueueing Theory排队论 Page:2QSCPage:3QSC排队排队常常是件很令人恼火的事情尤其是在我们这样的人口大国电话亭1978年在北京15%的电话要在1小时后才能接通。在电报大楼打电话的人还要带着午饭去排队 超市购物交通信号灯银行窗口，ATM医院、理发、火车售票游乐场的游乐项目Page:4QSCWhere the Time Goes美国人一生中平均要花费美国人一生中平均要花费-6年年 吃吃5年年 排队等待排队等待4年年 做家务做家务2年年 回电话不成功回电话不成功 1年年 寻找放置不当的物品寻找放置不当的物品8个月个月 打开邮寄广告打开邮寄广告6个月个月

2、停在红灯前停在红灯前Page:5QSCDisneyParissEuroDisney,TokyosDisneyJapan,andtheU.S.sDisneyWorldandDisneylandallhaveonefeatureincommonlonglinesandseeminglyendlesswaits.However,Disneyisoneoftheworldsleadingcompaniesinthescientificanalysisofqueuingtheory.Itanalyzesqueuingbehaviorsandcanpredictwhichrideswilldrawwhat

3、lengthcrowds.Tokeepvisitorshappy,Disneymakeslinesappeartobeconstantlymovingforward,entertainspeoplewhiletheywait,andpostssignstellingvisitorshowmanyminutesuntiltheyreacheachride.Page:6QSC在游乐园中的频频排队会极为扫兴在佛罗里达州,Orlando的DisneyLand里,游客们依着绳子排成许多队.指示牌可以估计出等待的时间,而许多大的电视屏幕为游客们提供消遣.DisneyLand中的FastPass系统就是想解

4、决排队问题Page:7QSCWhatisFastPass?工作原理：v到达的顾客将自己的票插入FastPass的slot中vFastPass计算出建议顾客返回的时间间隔（timeinterval）或时间点或时间窗（timewindow）v顾客无需排队，在指定的时间返回就可持票进入Page:8QSC服务系统的构成排队现象抽象成服务系统，它有顾客、服务机构、队列和服务规则等组成典型的服务系统典型的服务系统Page:9QSCThreePartsofaQueuingSystematDavesCar-WashPage:10QSC排队系统的基本特征排队系统的基本特征离开排队规则到达过程排队结构排队结构服务

5、过程服务过程退出需求需求群体群体Page:11QSC商业服务系统商业服务系统系统类型系统类型顾客顾客服务台服务台理发店人理发师银行出纳服务人出纳ATM机服务人ATM机商店收银台人收银员电影院售票窗口人售票员机场检票处人航空公司代理人Page:12QSC内部服务系统内部服务系统系统类型系统类型顾客顾客服务台服务台秘书服务雇员秘书复印服务雇员复印机计算机编程服务雇员程序员大型计算机雇员计算机急救中心病员护士传真服务雇员传真机物料处理系统货物物料处理单元维护系统设备维修工人质检站物件质检员Page:13QSC运输服务系统运输服务系统系统类型系统类型顾客顾客服务台服务台公路收费站汽车收费员卡车装货地卡

6、车装货工人港口卸货区轮船卸货工人等待起飞的飞机飞机跑道航班服务人飞机出租车服务人出租车电梯服务人电梯消防部门火灾消防车停车场汽车停车空间急救车服务人急救车Page:14QSC为什么要研究排队问题为什么要研究排队问题?减少顾客等待时间计算顾客平均等待时间计算顾客的平均队长提高服务系统的效率计算服务强度计算忙期闲期对服务系统进行成本效益平衡分析增加服务台的成本与效益分析Page:15QSC排队论发展简述1909年丹麦数学家A.K.Erlang服务于一家电话公司，他发表论文研究电话机的使用状况上世纪50年代，英国人D.G.Kendall系统地阐述了排队问题。上世纪60年代更多的应用于生产线，交通等问

7、题；上世纪70年代应用于计算机网络、通信等领域;如今通信系统仍然是排队论应用的主要领域,同时在运输、港口泊位设计、机器维修、库存控制等领域也得到广泛的应用。Page:16QSC4.1 排队服务系统的基本概念4.1.1 排队系统的一般表示一个排队系统可以抽象描述为：为了获得服务的顾客到达服务设施前排队，等候接受服务，服务完毕后就自行离开。要求得到服务的对象称为顾客服务者称为服务设施或服务台顾客的到达和离开称为排队系统的输入和输出。顾客的总体称为顾客源或输入源。因此，任何一个排队系统是一种输入-输出系统。Page:17QSC排队系统基本结构顾客源等候队列服务设施到达输入输出离开排队系统Page:1

8、8QSCQueue:WaitinglineArrival:1person,machine,part,etc.thatarrivesanddemandsserviceQueue discipline:RulesfordeterminingtheorderthatarrivalsreceiveserviceChannel:NumberofwaitinglinesPhase:NumberofstepsinserviceWaitingLineTerminologyPage:19QSCThreePartsofaQueuingSystematDavesCar-WashPage:20QSC4.1.2 排队系

9、统的四要素用排队论研究服务系统，首先要对各种排队系统进行分类描述。排队系统可从四个方面来描述：输入输出排队服务规则服务机构Page:21QSC一、输入ArrivalCharacteristics相继到达系统的时间间隔是确定性的还是随机性的（Patternofarrivalatthesystem）如自动装配线上待装配部件到达各工序的时间间隔是确定的。而多数顾客到达都是随机的，随机的服从何种概率分布：定长、二项、负指数、爱尔朗分布等。顾客到达系统的方式是单个的，还是成批的（Behaviorofarrivals）如到达宾馆服务台住宿有散客，也有团体顾客源是有限集还是无限集（Sizeofthearri

10、valpopulation）工厂内待修的机器数是有限集，售票处购票顾客源可认为是无限集。Page:22QSC到达过程静态动态预约定价接受/拒绝不加入排队退出排队恒定到达率的随机到达变动到达率的随机到达由设施控制顾客控制到达过程Page:23QSC到达过程的内容顾客总体数或顾客源数顾客总体数或顾客源数有限或无限有限或无限顾客的到达类型顾客的到达类型单个或成批单个或成批顾客的到达间隔时间顾客的到达间隔时间间隔时间分布间隔时间分布Page:24QSC二、输出顾客从得到服务到离开服务机构的情况定长服务时间 随机服务时间单个服务成批服务Page:25QSC三、排队服务规则QueueDiscipline顾

11、客来到排队系统后如何排队等候服务的规则1、即时制（损失制）。当顾客到达时，如果所有服务台都已被占用，顾客可以随即离开系统，如电话拨号后出现忙音，顾客可马上挂上电话。2、等候制。当顾客到达时，所有服务台都已被占用，顾客就加入排队队列等候服务。排队规则：FIFOFCFS先到先服务，最常见LIFO：乘电梯的顾客是后进先出SIRO随机服务：从等待的顾客中随机取一个进行服务，人工电话交换优先权服务：重病优先、老年人优先等Page:26QSC3、混合制。即时制和等候制相结合的一种排队服务规则。队列长度有限制的情况：排队等候的人数超过预定数量，后来的顾客就自动离开。排队时间有限制有情况：顾客排队等候超过一定

12、的时间就会自动离开，不能再等。Page:27QSC排队规则排队规则静态(FCFS 规则)(LCFS 规则).动态基于排队状况选择即与特定顾客特征选择 等待的顾客数协商优先级强占顾客服务时间(SPT 规则)Page:28QSC四、服务机构服务设施的个数、排列及服务方式。按服务设施个数分，有一个或多个之分单站服务系统和多站服务系统按排列形式，有并联和串联之分服务方式有单个服务和成批服务Page:29QSC1、服务台数量是单服务台(single-channel)还是多服务台(multi-channel)2、若是多服务台，它们的结构是并列的还是串列的，或者混合排列等候队列服务台单服务台等候队列服务台2

13、服务台1并列多台等候队列服务台1串列多台服务台2等候队列服务台3服务台1混列多台服务台4服务台2Page:30QSC3、服务的方式是对单个顾客进行的，还是对成批顾客进行的。公共汽车站台等待的顾客是成批进行服务的。排队论主要研究单个服务方式4、对顾客的服务时间是确定的还是随机的。自动冲洗汽车的装置对每辆汽车冲洗服务的时间是确定性的。但大多数情况下服务时间是随机性的。对于随机要知道它的概率分布，是定长、负指数还是爱尔朗分布。ServicetimedistributionPage:31QSC排队结构领号多条队列有限队长有限队长有限或无限队长快速通道排队结构单一队列允许或不允许移动领号机Page:32

14、QSC排队结构-例多队多服务台多队多服务台领号领号 34826101211579单队多服务台单队多服务台入口入口 Page:33QSC4.1.3排队系统模型的分类按照排队系统的输入、输出、排队服务规则和服务机构等方面的不同，可以构成不同的排队模型Page:34QSC排队模型分类的排队模型分类的Kendall符号符号 Kendall提提出出一一个个排排队队系系统统的的分分类类方方法法，特特征征可以用六个参数表示，形式为：可以用六个参数表示，形式为：XYZ其中其中X 顾客到达的概率分布，可取顾客到达的概率分布，可取M、D、Ek、G等；等；Y 服务时间的概率分布，可取服务时间的概率分布，可取M、D、

15、Ek、G等；等；Z 服务台个数，取正整数；服务台个数，取正整数；Page:35QSCX、Y可有四种分布符号M、D、Ek、GM负指数分布负指数分布所描述的随机现象对于过去的事件具有无记忆性或称马尔可夫性MarkovD定长分布，事件以不变的方式发生DeterministicEkk阶爱尔朗分布ErlangG一般随机分布General如M/M/1表示到达的间隔时间服从负指数分布，服务时间也服从负指数分布的单服务台排队系统模型M/D/2？表示到达的间隔时间服从负指数分布，服务时间为定长分布的双服务台排队系统模型Page:36QSC排队模型的分类排队模型的分类1971年又将年又将Kendall符号扩展为：

16、符号扩展为：XYZ/ABC其中：其中：A 排队系统的最大容量，可取正整数排队系统的最大容量，可取正整数N或或；B 顾客源的最大容量，可取正整数或顾客源的最大容量，可取正整数或；C 排队规则，可取排队规则，可取FCFS、LCFS等。等。特别约定，如略去后三项，则是指特别约定，如略去后三项，则是指 XYZ/FCFS因为本课程只介绍因为本课程只介绍FCFS,所以略去最后一项所以略去最后一项Page:37QSC例M/M/1/FCFS表示：表示：顾客到达的时间间隔是负指数分布顾客到达的时间间隔是负指数分布服务时间是负指数分布服务时间是负指数分布一个服务台一个服务台排队系统和顾客源的容量都是无限排队系统和

17、顾客源的容量都是无限实行先到先服务的一个服务系统实行先到先服务的一个服务系统 Page:38QSC4.1.4衡量排队系统的名词一个排队系统开始运行时,系统的运行状态在很大程度上取决于系统的初始状态和运转的时间。经过一段时间以后，系统的状态将独立于初始状态和经历时间，这时系统处于稳定状态。排队系统主要研究稳定状态。系统处于稳定状态时，工作状况与时刻t无关Page:39QSC主要名词概念1.系统状态：Ls 一个排队系统中的顾客数，包括正在接受服务的顾客。2.队长Lq系统中等待服务的顾客平均数，它等于系统状态减去正在被服务的顾客数。3.N(t)在时刻t排队服务系统的顾客数，即系统在时刻t的瞬时状态。

18、4.Pn(t)在t时刻系统中恰好有n个顾客的概率l主要分析系统平稳分布,即当系统达到统计平衡状态时处于状态n的概率,记为PnPage:40QSC平均到达率n ：当系统中有n个顾客时，新来顾客的平均到达率（单位时间内顾客的到达数）。当对所有n值n为常数时，可用代替n1/为相邻两顾客到达系统的平均间隔时间。平均服务率n ：当系统中有n个顾客时，单位时间内被服务完毕后离开系统的平均顾客数。当n1，n为常数时，可用代替n1/为每个顾客的平均服务时间。c系统中并列服务台数目。主要名词概念Page:41QSC主要指标1.平均逗留时间Ws：进入系统的顾客逗留时间的平均值，包括接受服务的时间。2.平均等待时间

19、Wq：进入系统的顾客等待时间的平均值。顾客最关心Wq，越短越好3.服务机构工作强度：服务机构累计的工作时间占全部时间的比例，即服务强度 4.平均顾客数Ls：一个排队系统的顾客平均数，包括正在接受服务的顾客。5.平均队长Lq：系统中等待服务的顾客平均数。Page:42QSC常用的记号常用的记号c服务台的个数n系统中的顾客数,即系统状态平均到达率，即单位时间内平均到达的顾客数平均服务率，即单位时间内服务完毕的顾客数Pn(t)时刻t系统状态n的概率Pn系统中的顾客数n（系统状态n)的稳态概率M顾客相继到达的时间间隔服从负指数分布D顾客相继到达的时间间隔服从定长分布Ek顾客相继到达的时间间隔服从k阶E

20、rlang分布G顾客相继到达的时间间隔服从一般分布Page:43QSC4.2输入与服务时间的分布DistributionofInputandservicetime在组成一个排队系统的四要素输入输出排队服务规则服务机构顾客的输入和输出较复杂，是随机的，本节专门研究研究较多且结果较好的排队系统是：顾客的输入过程服从泊松分布，而服务时间服从负指数分布的排队系统若顾客输入过程服从泊松分布，则顾客相继到达的间隔时间服从负指数分布。Page:44QSC 4.2.1Poisson流（流（Poisson过程）过程）定义满足以下条件的输入流称为Poisson流（最简单流、Poisson过程）1、无后效性：不相交

21、的时间区间内到达的顾客数互相独立。2、平稳性：在时间区间t,t+t)内到达1个顾客的概率与t无关，只与t有关:其中：是一个大于零的常数，3、守序性：设在t,t+t）内到达多于一个顾客的概率为极小o(t)。Page:45QSCPoisson流与流与Poisson分布分布定定理理 对对于于一一个个参参数数为为 的的Poisson流流，在在0，t内到达内到达n个顾客的概率为个顾客的概率为 即服从以即服从以 为参数的为参数的Poisson分布。分布。=1=3=7Pn(1)x.4.3.2.1 0Page:46QSCPoissonDistributionsforArrivalTimesProbabilit

22、yProbability=2=4：单位时间顾客的平均到达率Page:47QSC实际情况是否符合三条性质到达工厂机修车间的要维修的机器情况分析：因为每台机器在各个时刻处的状态大致一样，所以在相等时间区间内各台机器损坏的概率大致相同，即要求维修的机器的流具有平稳性由于一台机器的故障不会引起另一台机器的故障，而对同一台机器，这段时间内损坏的次数不影响到以后损坏次数多少，这表明具有无后效性由于每台机器损坏概率很小，在足够小的时间区间内发生两台及以上机器损坏的概率几乎为0，这就符合普通性。因此对到达机修车间的要维修的机器数可以认为是最简单流,即poisson流。Page:48QSCPoisson流与负指

23、数分布之间的关系流与负指数分布之间的关系 定理定理 在排队系统中，如果单位时间内顾客到达在排队系统中，如果单位时间内顾客到达数服从以数服从以 为参数的为参数的Poisson分布，则顾客相继分布，则顾客相继到达的时间间隔服从以到达的时间间隔服从以 为参数的负指数分布。为参数的负指数分布。=0.41/为平均到达间隔时间（expectedinterarrivaltime)Page:49QSC4.2.2服务时间的分布在排队系统中，一般假设服务时间（servicetime)服从参数为的负指数分布：1/为平均服务时间（expectedservicetime)Page:50QSCProbability tx

24、=1=2=3=4NegativeExponentialDistribution负指数分布Servicetime,&timebetweenarrivalsExample:Servicetimeis20min.Meanservicerate=e.g.,customers/hr.平均服务时间Meanservicetime=1/Equation:Page:51QSCNegativeExponentialDistributionAverage service time=1 hourAverage service time=20 minutesPage:52QSC负指数分布的性质1.假如服务设施对每个顾客

25、的服务时间服从负指数分布，则对每个顾客的平均服务时间为1/2.当服务设施对顾客的服务时间t为参数 的负指数分布时，则有在t,t+t 时间内，没有顾客离去的概率为1-t在t,t+t 时间内，恰有一个顾客离去的概率为 t如果 t足够小，在t,t+t 时间内有多于两个以上顾客离去的概率趋于0Page:53QSC负指数分布的性质3.假如服务设施对顾客的服务时间服从负指数分布，则不管对某一个顾客的服务已进行了多久，剩下来的服务时间的概率分布仍为同原先一样的负指数分布。4.若干个独立的负指数分布的最小值是负指数分布。5.若按依次到达的间隔时间统计，顾客流服从负指数分布，则对同一顾客流若按单位时间到达的数量

26、统计，它服从泊松分布。泊松分布和负指数分布是对同一顾客流按不同方式进行统计时得到的两种不同分布。Page:54QSC4.2.3k阶Erlang分布K个相互独立的且具有相同参数的负指数分布的和的分布称为k阶Erlang分布。例如一台自动机床上依次利用三把刀具对一个工件进行加工，若每把刀具对该工件的加工时间均为参数 的负指数分布，则该工件在自动机床上总的加工时间服从3阶Erlang分布Page:55QSCk阶阶Erlang分布分布 定定理理 设设v1，v2，vk是是k个个互互相相独独立立的的，具具有有相同参数的负指数分布随机变量，则随机变量相同参数的负指数分布随机变量，则随机变量S=v1+v2+v

27、k服从服从k阶阶Erlang分布，分布，S的密度函数为的密度函数为=1k=1k=2k=4k=8Page:56QSCErlang分布的均值、方差和阶数总服务时间服从爱尔朗分布，其均值和方差是由此可得爱尔朗分布的阶数：每个服务台的平均服务时间是：Page:57QSC4.3生灭过程排队系统随机聚散服务系统顾客到达是“生”，顾客离开是“灭”Page:58QSC生灭过程Birth-deathprocessN(t)是系统t时刻的状态（顾客数），则N(t),t=0就构成一个随机过程，若用“生”表示一个顾客的到达，“灭”代表一个顾客过程的离去，则对许多排队过程来说，N(t),t=0也是一类特殊的随机过程生灭过

28、程Page:59QSC生灭过程Birth-deathprocess定义：设N(t),t=0是一个随机过程，如果其概率分布满足有如下性质：（1）给定N(t)=n,到下一个“生”（顾客到达）的间隔时间服从参数为n的负指数分布;（2）给定N(t)=n,到下一个“灭”（顾客离去）的间隔时间服从参数为n的负指数分布;（3）同一时刻只能到达一个或离去一个顾客；则称N(t),t=0是生灭过程Page:60QSC生灭过程的状态转移图生灭过程的瞬时状态一般很难求得，但可求得稳定状态分布对于稳定的生灭状态，从平均意义上说有：“流入=流出”稳定的生灭过程可以用状态转移图表示Page:61QSC生灭过程的稳态方程基本

29、原理系统任意状态n达到稳态平衡的条件是：产生该状态的平均速率等于该状态转变成其他状态的平均速率例如，对于系统状态n=0的情况，产生和破坏该状态的可能性有两种情况。如后图所示。Page:62QSCn=0的状态的产生和破坏Page:63QSCn=1状态的产生和破坏Page:64QSCn=2状态的产生和破坏Page:65QSC状态(n-1)的产生和破坏Page:66QSC任意状态n的产生和破坏Page:67QSC生灭过程Birth-deathprocess012n-1nn+1Page:68QSC生灭过程的基本公式Page:69QSC生灭过程的状态概率因为所以即得Page:70QSC生灭过程Birth

30、-deathprocess标准的排队过程是参数不随状态而变的特殊的生标准的排队过程是参数不随状态而变的特殊的生灭过程灭过程Page:71QSC4.4不同类型排队系统分析输入过程为泊松流，服务时间基本服从负指数分布的排队系统标准M/M/1/有限队列模型M/M/1/N/客为有限源系统M/M/1/m多服务台系统M/M/sPage:72QSC 4.4.1基本排队模型基本排队模型 M/M/1/FCFS 顾客到达的时间间隔是负指数分布顾客到达的时间间隔是负指数分布服务时间是负指数分布服务时间是负指数分布一个服务台一个服务台排队系统和顾客源的容量都是无限排队系统和顾客源的容量都是无限实行先到先服务的一个服务

31、系统实行先到先服务的一个服务系统Page:73QSCM/M/1/FCFS排队模型的分析排队模型的分析 假设假设在在t+t时刻系统中顾客数为时刻系统中顾客数为n的概率的概率Pn(t+t)nnn+1n-1nPn(t)Pn-1(t)Pn+1(t)Pn(t)t时刻时刻t+t时刻时刻无到达，无离开无到达，无离开无到达，离开一个无到达，离开一个到达一个，无离开到达一个，无离开到达一个，离开一个到达一个，离开一个Page:74QSCPage:75QSC系统的过渡状态与稳定状态系统的过渡状态与稳定状态过渡过渡稳定稳定Page:76QSC稳定状态下的状态概率稳定状态下的状态概率Page:77QSC得到得到 令令

32、 称称 为服务强度，则为服务强度，则得得Page:78QSCM/M/1的状态转移分析的状态转移分析012n-1nn+1Page:79QSC例例高高速速公公路路入入口口收收费费处处设设有有一一个个收收费费通通道道，汽汽车车到到达达服服从从Poisson分分布布，平平均均到到达达速速率率为为100辆辆小小时时，收收费费时时间间服服从从负负指指数数分分布布，平平均均收收费费时时间间为为15秒秒辆。求辆。求1、收费处空闲的概率；、收费处空闲的概率；2、收费处忙的概率；、收费处忙的概率；3、系统中分别有、系统中分别有1，2，3辆车的概率。辆车的概率。Page:80QSC解解根根据据题题意意,=100辆辆

33、/小小时时,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辆车的概率为：辆车的概率为：P3=3(1-)=0.417 30.583=0.0421Pa

34、ge:81QSC系统绩效度量系统绩效度量 系统中的平均顾客数系统中的平均顾客数Ls（队长）（队长）Expected number of customers in system 平均等待顾客个数平均等待顾客个数Lq（排队长）（排队长）Expected queue length (excludecustomersbeingserved)顾客平均逗留时间顾客平均逗留时间Ws Waiting time in system 顾客平均（排队）等待时间顾客平均（排队）等待时间Wq Waiting time in queue (excludeservicetime)系统利用率系统利用率 Utilization

35、 factor,Traffic intensityPage:82QSCJohn D.C.Little公式公式 Page:83QSCM/M/1/FCFS的系统指标的系统指标系统中的平均顾客数系统中的平均顾客数Ls 队列中的平均顾客数队列中的平均顾客数Lq Page:84QSC顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间Ws 顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间Wq Page:85QSC例1.理发店空闭的概率2.店内有3个顾客的概率3.店内到少有一个顾客的概率4.店内顾客的平均数，等待服务顾客的平均数5.顾客在店内的平均逗留时间和平均等待时间6.必须在店内消耗15分钟以上的

36、概率某理发店只一名理发师，来理发的顾客按泊松分布到达，平均每小时4人，理发时间服从负指数分布，平均需要6分钟，求Page:86QSC解此为M/M/1系统，已知=4/60=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.227Page:87QSC例例 高高速速公公路路入入口口收收费费处处设设有有一一个个收收费费通通道道，汽汽车车到到达达服服从从Poisso

37、n分分布布，平平均均到到达达速速率率为为200辆辆/小小时时，收收费费时时间间服服从从负负指指数数分分布布，平平均均收收费费时时间间为为15秒秒/辆。求辆。求Ls、Lq、Ws和和Wq。Page:88QSC解解根据题意，根据题意，=200辆辆/小时，小时，=240辆辆/小时，小时，=/=5/6。Page:89QSC4.4.2有限队列模型有限队列模型 M/M/1/N/FCFS 当队列的容量从无限值变为有限值当队列的容量从无限值变为有限值N时，时，M/M/1/FCFS就转化成为就转化成为M/M/1/N/FCFS Page:90QSC系统的状态转移图系统的状态转移图012N-1NPage:91QSC系

38、统的状态概率平衡方程系统的状态概率平衡方程对于状态对于状态0：P0=P1对于状态对于状态k：Pk-1+Pk+1=(+)Pk 0k=1)=1-P0=0.75Ls=/(-)=3Lq=Ls-=3-0.75=2.25Ws=Ls/=10 分Wq=Ws-1/=7.5 分 Page:120QSC指标指标 模型模型M/M/3M/M/1服务台空闲的概率服务台空闲的概率P00.07480.25(每个子系统）顾客必须等待的概率顾客必须等待的概率0.570.75平均队列长（等待顾客数）平均队列长（等待顾客数）Lq1.702.25(每个子系统）平均队长（顾客数）平均队长（顾客数）Ls3.959.00（整个系统）平均逗留

39、时间平均逗留时间Ws4.39分钟10分钟平均等待时间平均等待时间Wq1.89分钟7.5分钟由此可见，单队比三队有显著的优越性。由此可见，单队比三队有显著的优越性。Page:121QSCM/M/c/N/FCFS模型模型 离开离开服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列Page:122QSC分析分析设系统容量为设系统容量为N(Nc)，当系统中的顾数，当系统中的顾数nN时，到时，到达的顾客就进入系统；当达的顾客就进入系统；当n=N时，到达的顾客就被时，到达的顾客就被拒绝。设顾客到达的速率为拒绝。设顾客到达的速率为，每个服务台服务的，每个服务台服务的速率为速率为，=/c。由于系统不会无限

40、止地接纳。由于系统不会无限止地接纳顾客，对顾客，对不必加以限制。不必加以限制。Page:123QSC状态转移图与状态转移方程状态转移图与状态转移方程对状态对状态0:P0=P1对状态对状态 1:P0+2P2=(+)P1对状态对状态 c：Pc-1+cPc+1=(+c)Pc对状态对状态N PN-1=cPN 01cNPage:124QSC状态概率状态概率Page:125QSC系统指标系统指标 Page:126QSC例例 某某旅旅馆馆有有8个个单单人人房房间间，旅旅客客到到达达服服从从Poisson流流，平平均均速速率率为为6人人天天，旅旅客客平平均均逗逗留时间为留时间为2天，求：天，求：(1)每天客房

41、平均占用数；每天客房平均占用数；(2)旅馆客满的概率。旅馆客满的概率。Page:127QSC解解旅馆旅馆8个房间全满的概率为个房间全满的概率为0.423 平均占用客房数为平均占用客房数为6.9间。客房占用率为间。客房占用率为86.6%Page:128QSCM/M/c/m/FCFS模型模型 顾客到达修理速率发生故障等待修理的机器修理速率修理速率正在修理的机器到达速率(m-n)修理速率c运行的机器数 m-nPage:129QSC状态概率状态概率 其中其中 Page:130QSC系统指标系统指标有有效效到到达达速速率率e为为单单位位时时间间内内出出现现故故障障的的机机器数，有器数，有e=(m-Ls)

42、Page:131QSC例例车车间间有有5台台机机器器，每每台台机机器器的的故故障障率率为为1次次小小时时，有有2个个修修理理工工负负责责修修理理这这5台台机机器器，工工作作效效率率相相同同，为为4台小时。求：台小时。求：(1)等待修理的平均机器数；等待修理的平均机器数；(2)等待修理及正在修理的平均机器数；等待修理及正在修理的平均机器数；(3)每小时发生故障的平均机器数；每小时发生故障的平均机器数；(4)平均等待修理的时间；平均等待修理的时间；(5)平均停工时间。平均停工时间。Page:132QSC解解 可以计算得到（算式略）：可以计算得到（算式略）：P1=0.394，P2=0.197，P3=

43、0.074，P4=0.018，P5=0.002 Page:133QSC由此，计算系统的各项运行指标如下：由此，计算系统的各项运行指标如下：Page:134QSC排队系统的优化排队系统的优化一般排队系统的总费用构成：一般排队系统的总费用构成：总费用总费用=服务能力费服务能力费+顾客损失费顾客损失费最佳服务能力最佳服务能力服务能力顾客损失费顾客损失费服务能力费服务能力费总费用总费用费用Page:135QSCM/M/1/FCFS模型的模型的单位时间总费用单位时间总费用单位时间单位时间服务成本服务成本单位顾客停单位顾客停留单位时间留单位时间损失成本损失成本Page:136QSCPage:137QSCM/M/c:/FCFS模型的模型的cPage:138QSCPage:139QSC本章小节掌握排队系统的特征、理解研究排队现象的目的；掌握Poisson分布与负指数分布的特征、概率密度公式及特征值；掌握标准排队模型M/M/1/的系统特征、系统状态概率、系统指标的计算公式；了解排队模型M/M/1/N/和M/M/1/m的系统特征、系统指标值之间的关系（Little公式）；了解多服务台排队模型M/M/c/的系统特征、系统指标值之间的关系（Little公式）。