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

7/16/2024第10章排队论1WheretheTimeGoes美国人一生中平均要花费---7/16/202426年吃5年排队等待4年做家务2年回电话不成功1年寻找放置不当的物品8个月打开邮寄广告6个月停在红灯前AC尼尔森公司的调查在消费者经常遭遇排队问题的各类场所银行的排队率是73%；医院以44%居第二；零售商店的排队率以43%居第三。在调查受访的消费者中，超过60%的受访者称通常一周用于排队的时间高于30分钟。在所有受访的消费者中，有28%的人因排长队而转选其它服务提供商，66%的人因不想耽误时间而选择离开，而46%的人会有抱怨。7/16/20243行为研究结论行为科学家发现：无序排队是影响客户流失的一条主要原因。研究结果表明等候时间：超过十分钟，情绪开始急躁；超过二十分钟，情绪表现厌烦；超过四十分钟，常因恼火而离去。7/16/20244如何减少排队？减少等候时间的解决方案：开设更多的服务点；提供自助服务解决方案；雇用更多员工。7/16/20245排队管理系统的应用近年来，许多公共服务场所出现了排队机(ticketdispenserunit)，窗口秩序为之一变，一种令人耳目一新的排队方式：进得大门，在排队机的触摸屏上点一下所要办理的项目，排队机就会“吐”出一张像名片大小的号票，拿着这张号票安安静静地坐在休息区舒适的椅子上等候，轮到自己时，大屏幕和语音系统会提醒你到相应的窗口办理，井然有序。7/16/20246DisneyParis’sEuroDisney,Tokyo’sDisneyJapan,andtheU.S.’sDisneyWorldandDisneylandallhaveonefeatureincommon—longlinesandseeminglyendlesswaits。在游乐园中的频频排队会极为扫兴……7/16/20247Disney在佛罗里达州Orlando的DisneyLand里,游客们依着绳子排成许多队，指示牌可以估计出等待的时间，而许多大的电视屏幕为游客们提供消遣。DisneyLand中的FastPass系统就是想解决排队问题。7/16/20248WhatisFastPass?工作原理：到达的顾客将自己的票插入FastPass的slot中FastPass计算出建议顾客返回的时间间隔（timeinterval）或时间点或时间窗（timewindow）顾客无需排队，在指定的时间返回就可持票进入7/16/20249Disney’sFastpass7/16/202410

如何计算顾客等待时间？7/16/202411

排队论！服务系统的构成排队现象抽象成服务系统，它由顾客、服务机构、队列和服务规则等组成7/16/202412ThreePartsofaQueuingSystem

atDave’sCar-Wash7/16/202413排队系统的基本特征离开排队规则到达过程排队结构服务过程退出需求群体7/16/202414什么是排队论排队论是研究服务系统中排队现象随机规律的理论与方法。因为排队现象是一个随机现象，因此在研究排队现象的时候，主要采用的是研究随机现象的概率论作为主要工具，还有微分方程。7/16/202415排队论研究目的和内容减少顾客等待时间计算顾客平均等待时间计算顾客的平均队长提高服务系统的效率计算服务强度计算忙期\闲期对服务系统进行成本效益平衡分析增加服务台的成本与效益分析7/16/202416排队论发展简述1909年丹麦数学家A.K.Erlang(爱尔朗)服务于一家电话公司，他在解决自动电话设计问题时开始形成的，当时称为话务理论。他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的爱尔朗电话损失率公式。7/16/202417排队论发展简述上世纪50年代，英国人D.G.Kendall提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论奠定了理论基础；上世纪60年代更多的应用于生产线，交通信号灯绿信比的设置等问题；上世纪70年代应用于计算机网络、通信等领域；如今通信系统仍然是排队论应用的主要领域,同时在运输、港口泊位设计、机器维修、库存控制等领域得到广泛应用，特别是服务行业。7/16/202418CONTENTS019目录7/16/202410.1

排队服务系统的基本概念10.2

到达间隔与服务时间的分布10.3

生灭过程与系统状态方程10.4

单服务台负指数分布排队模型10.5

多服务台排队模型10.6

其他类型排队模型10.7

排队系统的优化10.1排队服务系统的基本概念10.1排队服务系统的基本概念一个排队系统可以抽象描述为：为了获得服务的顾客到达服务设施前排队，等候接受服务，服务完毕后就自行离开。要求得到服务的对象称为顾客服务者称为服务设施或服务台顾客的到达和离开称为排队系统的输入和输出。顾客的总体称为顾客源或输入源。因此，任何一个排队系统是一种输入-输出系统。7/16/202421服务系统系统类型 顾客 服务台理发店 人 理发师银行出纳服务 人 出纳ATM机服务 人 ATM机超市收银台 人 收银员电影院售票窗口 人 售票员机场检票处 人 航空公司代理人7/16/202422服务系统系统类型 顾客 服务台公路收费站 汽车 收费员港口卸货区 轮船 卸货工人等待起飞的飞机 飞机 跑道航班服务 人 飞机出租车服务 人 出租车电梯服务 人 电梯停车场 汽车 停车空间急救车服务 人 急救车7/16/20242310.1.1排队服务系统的构成事实上，任何一个排队服务系统都是一种输入-输出系统。顾客的到达和离开称为排队系统的输入和输出。顾客的总体称为顾客源或输入源。顾客源等候队列服务设施到达输入输出离开排队系统7/16/202424排队系统的三个基本组成部分：输入过程(顾客按照怎样的规律到达)；排队规则(顾客按照一定规则排队等待服务)；服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等)10.1.1排队服务系统的构成7/16/202425一、输入ArrivalCharacteristics顾客源是有限集还是无限集（Sizeofthearrivalpopulation）工厂内待修的机器数是有限集，售票处购票顾客源可认为是无限集。顾客到达系统的方式是单个的，还是成批的（Behaviorofarrivals）如到达宾馆服务台住宿有散客，也有团体相继到达系统的时间间隔是确定性的还是随机性的（Patternofarrivalatthesystem）如自动装配线上待装配部件到达各工序的时间间隔是确定的。而多数顾客到达都是随机的，随机的服从某种概率分布：二项、负指数、爱尔朗分布等。7/16/202426到达过程(输入过程)的内容顾客总体数或顾客源数有限或无限顾客的到达类型单个或成批顾客的到达间隔时间间隔时间分布7/16/202427二、排队规则QueueDiscipline顾客来到排队系统后如何排队等候服务的规则1、即时制（损失制）：当顾客到达时，如果所有服务台都已被占用，顾客可以随即离开系统；如电话拨号后出现忙音，顾客可马上挂上电话。2、等候制：当顾客到达时，所有服务台都已被占用，顾客就加入排队队列等候服务。排队规则：FIFO/FCFS先到先服务，最常见LIFO：乘电梯的顾客是后进先出SIRO随机服务：从等待的顾客中随机取一个进行服务，人工电话交换优先权服务：重病优先、老年人优先等7/16/202428二、排队规则QueueDiscipline3、混合制：即时制和等候制相结合的一种排队服务规则。队列长度有限制时：排队等候的人数超过预定数量，后来的顾客就自动离开。排队时间有限制时：顾客排队等候超过一定的时间就会自动离开，不能再等；电子元器件库存超过一定时期，就失效了7/16/202429三、服务机构服务设施的结构、服务方式、服务时间：按服务设施个数分，有一个或多个之分，有并联和串联之分单台服务系统和多台服务系统服务方式有单个服务和成批服务服务时间是确定和随机的7/16/202430服务台结构等候队列服务台单服务台等候队列服务台2服务台1并列多台等候队列服务台1串列多台服务台2等候队列服务台3服务台1混列多台服务台4服务台27/16/202431服务方式

服务的方式是对单个顾客进行的，还是对成批顾客进行的。公共汽车站台等待的顾客是成批进行服务的。7/16/202432服务时间对顾客的服务时间是确定的还是随机的。自动冲洗汽车的装置对每辆汽车冲洗服务的时间是确定性的。但大多数情况下服务时间是随机性的。对于随机要知道它的概率分布，是定长、负指数还是爱尔朗分布。Servicetimedistribution7/16/202433排队结构多队多服务台领号34826101211579单队多服务台入口7/16/202434通常，按排队系统的主要特征来进行排队系统的分类。一般是以相继顾客到达系统的间隔时间分布类型、服务时间的分布类型和服务台数目为分类标志。Kendall提出一个排队系统的分类方法，特征可以用六个参数表示，形式为：

X／Y／Z其中X––顾客到达的概率分布，可取M、D、Ek、G等；Y––服务时间的概率分布，可取M、D、Ek、G等；Z––服务台个数，取正整数；10.1.2排队服务系统的分类7/16/202435X、Y可有四种分布符号M、D、Ek、GM—负指数分布所描述的随机现象对于过去的事件具有无记忆性或称马尔可夫性MarkovD—定长分布，事件以不变的方式发生DeterministicEk—k阶爱尔朗分布ErlangG—一般随机分布General如M/M/1表示到达的间隔时间服从负指数分布，服务时间也服从负指数分布的单服务台排队系统模型M/D/2表示到达的间隔时间服从负指数分布，服务时间为定长分布的双服务台排队系统模型10.1.2排队服务系统的分类7/16/2024361971年又将Kendall符号扩展为：

X／Y／Z/A／B／C其中：A––排队系统的最大容量，可取正整数N或

；B––顾客源的最大容量，可取正整数m或

；C––排队规则，可取FCFS、LCFS等。特别约定，如略去后三项，则是指

X／Y／Z/

／

／FCFS因为本课程只介绍FCFS,所以略去最后一项10.1.2排队服务系统的分类7/16/20243710.1.2排队服务系统的分类例

M/M/1/

/

/FCFS表示：顾客到达的时间间隔是负指数分布服务时间是负指数分布一个服务台排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统

7/16/202438一个排队系统开始运行时,系统的运行状态在很大程度上取决于系统的初始状态和运转的时间。经过一段时间以后，系统的状态将独立于初始状态和经历时间，这时系统处于稳定状态。排队系统主要研究稳定状态。系统处于稳定状态时，工作状况与时刻t无关。10.1.3排队系统的相关术语7/16/202439主要名词术语平均到达率

n

：当系统中有n个顾客时，新来顾客的平均到达率（单位时间内顾客的到达数）。当对所有n值

n为常数时，可用代替n1/

为相邻两顾客到达系统的平均间隔时间。平均服务率

n

：当系统中有n个顾客时，单位时间内被服务完毕后离开系统的平均顾客数。当对所有n值，

n为常数时，可用代替n1/

为每个顾客的平均服务时间。c—系统中并列服务台数目。7/16/202440主要名词术语N(t)

在时刻t排队服务系统的顾客数，即系统在时刻t的瞬时状态。Pn(t)

在t时刻系统中恰好有n个顾客的概率主要分析系统平稳分布,即当系统达到统计平衡状态时处于状态n的概率,记为Pn7/16/202441主要系统性能指标平均逗留时间Ws

：进入系统的顾客逗留时间的平均值，包括接受服务的时间。平均等待时间Wq

：进入系统的顾客等待时间的平均值。服务机构工作强度

：服务机构累计的工作时间占全部时间的比例，即服务强度

平均顾客数Ls

：一个排队系统的顾客平均数，包括正在接受服务的顾客。平均队长Lq

：系统中等待服务的顾客平均数。7/16/202442常用的记号c—服务台的个数n––系统中的顾客数,即系统状态

––平均到达率，即单位时间内平均到达的顾客数

––平均服务率，即单位时间内服务完毕的顾客数Pn(t)––时刻t系统状态n的概率Pn––系统中的顾客数n（系统状态n)的稳态概率M––顾客相继到达的时间间隔服从负指数分布D––顾客相继到达的时间间隔服从定长分布Ek––顾客相继到达的时间间隔服从k阶Erlang分布G—顾客相继到达的时间间隔服从一般分布7/16/20244310.2到达间隔与服务时间的分布组成一个排队系统的四要素输入\输出\排队服务规则\服务机构顾客的输入和输出过程一般是随机的研究较多且结果较好的排队系统是：顾客的输入过程服从泊松分布，而服务时间服从负指数分布的排队系统若顾客输入过程服从泊松分布，则顾客相继到达的间隔时间服从负指数分布。10.2到达间隔与服务时间的分布7/16/202445定义：满足以下条件的输入流称为Poisson流（最简单流、Poisson过程）1）无后效性：不相交的时间区间内到达的顾客数互相独立。2）平稳性：对充分小的

t，在时间区间[t,t+

t)内到达1个顾客的概率与t无关，只与

t有关，即：其中：l是一个大于零的常数，表示单位时间内到达一个顾客的概率3）守序性：设在[t,t+

t）内到达多于一个顾客的概率为极小o(

t)。即 10.2.1Poisson流7/16/202446实际情况是否符合三条性质到达工厂机修车间的要维修的机器情况分析：因为每台机器在各个时刻处的状态大致一样，所以在相等时间区间内各台机器损坏的概率大致相同，即要求维修的机器的流具有平稳性由于一台机器的故障不会引起另一台机器的故障，而对同一台机器，这段时间内损坏的次数不影响到以后损坏次数多少，这表明具有无后效性由于每台机器损坏概率很小，在足够小的时间区间内发生两台及以上机器损坏的概率几乎为0，这就符合普通性。因此对到达机修车间的要维修的机器数可以认为是最简单流,即poisson流。7/16/202447Poisson流与Poisson分布定理1对于一个参数为

的Poisson流，在[0，t]内到达n个顾客的概率为

即服从以

为参数的Poisson分布。

7/16/202448PoissonDistributionsforArrivalTimesProbabilityProbability=2=4

：单位时间顾客的平均到达率7/16/202449Poisson流与负指数分布间的关系定理2

在排队系统中，如果单位时间内顾客到达数服从以

为参数的Poisson分布，则顾客相继到达的时间间隔T服从以

为参数的负指数分布。

l=0.41/

为平均到达间隔时间（expectedinterarrivaltime)7/16/202450负指数分布

NegativeExponentialDistribution分布函数7/16/202451负指数分布——无后效性无后效性表示T顾客到达的时间间隔已经过了s后，再等t的时间与s无关。7/16/20245210.2.2服务时间的分布1）负指数分布在排队系统中，一般假设服务时间（servicetime)服从参数为m的负指数分布：1/m为平均服务时间（expectedservicetime)7/16/202453平均服务时间Meanservicetime=1/

分布函数10.2.2服务时间的分布7/16/202454服务时间负指数分布的性质假如服务设施对每个顾客的服务时间服从负指数分布，则对每个顾客的平均服务时间为1/m当服务设施对顾客的服务时间t为参数m

的负指数分布时，则有在[t,t+

t]时间内，没有顾客离去的概率为1-m

t在[t,t+

t]时间内，恰有一个顾客离去的概率为m

t如果

t足够小，在[t,t+

t]时间内有多于两个以上顾客离去的概率趋于07/16/202455服务时间负指数分布的性质若按依次到达的间隔时间统计，顾客流服从负指数分布，则对同一顾客流若按单位时间到达的数量统计，它服从泊松分布。泊松分布和负指数分布是对同一顾客流按不同方式进行统计时得到的两种不同分布。7/16/2024562）k阶Erlang分布爱尔朗分布比负指数分布具有更广泛的适应性，k阶爱尔朗分布（Ek)的概率密度函数为：

10.2.2服务时间的分布7/16/202457爱尔朗分布的均值和方差是由此可得爱尔朗分布的阶数：10.2.2服务时间的分布7/16/20245810.2.2服务时间的分布m=1k=1k=2k=4k=87/16/202459K个相互独立的且具有相同参数的负指数分布的随机变量的和，其分布服从k阶Erlang分布。例如一台自动机床上依次利用三把刀具对一个工件进行加工，若每把刀具对该工件的加工时间均为参数相同的负指数分布，则该工件在自动机床上总的加工时间服从3阶Erlang分布10.2.2服务时间的分布7/16/202460定理3设v1，v2，…，vk是k个互相独立的，具有相同参数m的负指数分布的随机变量，则随机变量

Ek=v1+v2+…+vk服从k阶Erlang分布，Ek的密度函数为10.2.2服务时间的分布7/16/202461均值、方差和阶数总服务时间服从爱尔朗分布，其均值和方差是由此可得爱尔朗分布的阶数：每个服务台的平均服务时间是：7/16/20246210.3生灭过程10.3生灭过程排队系统—随机聚散服务系统顾客到达是“生”，顾客离开是“灭”7/16/202464生灭过程

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

Birth-deathprocess7/16/202466当顾客到达时间服从参数为λn

的负指数分布时，则有:在[t,t+

t]时间内，没有顾客到达的概率为在[t,t+

t]时间内，恰有一个顾客到达的概率为如果

t足够小，在[t,t+

t]时间内有多于两个以上顾客到达的概率趋于07/16/202467生灭过程

Birth-deathprocess当服务设施对顾客的服务时间服从参数的负指数分布时，则有:在[t,t+

t]时间内，没有顾客离去的概率为在[t,t+

t]时间内，恰有一个顾客离去的概率为如果

t足够小，在[t,t+

t]时间内有多于两个以上顾客离去的概率趋于07/16/202468生灭过程

Birth-deathprocessnnn+1n-1nPn(t)Pn-1(t)Pn+1(t)Pn(t)t时刻t+

t时刻无到达，无离开无到达，离开一个到达一个，无离开到达一个，离开一个假设在t+

t时刻系统中顾客数为n的概率Pn(t+

t)7/16/202469生灭过程

Birth-deathprocess7/16/202470生灭过程

Birth-deathprocess系统的过渡状态与稳定状态过渡稳定7/16/202471生灭过程的稳定状态方程生灭过程的瞬时状态一般很难求得，但可求得稳定状态分布7/16/202472生灭过程的稳定状态转移图对于稳定的生灭状态，从平均意义上说有：“流入速率=流出速率”稳定的生灭过程可以用状态转移图表示7/16/202473生灭过程的稳态方程基本原理系统任意状态n达到稳态平衡的条件是：产生该状态的平均速率等于该状态转变成其他状态的平均速率例如，对于系统状态n=0的情况，产生和破坏该状态的可能性有两种情况。如后图所示。7/16/202474n=0状态的产生和破坏7/16/202475n=1状态的产生和破坏7/16/202476n=2状态的产生和破坏7/16/202477n-1状态的产生和破坏7/16/202478任意状态n的产生和破坏7/16/202479λ012n-1nn+17/16/202480生灭过程Birth-deathprocess生灭过程的基本公式7/16/202481生灭过程的状态概率因为所以即得7/16/202482标准的排队过程是参数不随状态而变的特殊的生灭过程7/16/202483生灭过程

Birth-deathprocess10.4单服务台负指数分布排队模型输入过程为泊松流，服务时间基本服从负指数分布的排队系统10.4.1标准M/M/1/∞/∞10.4.2有限队列模型M/M/1/N/

/10.4.3顾客为有限源系统M/M/1/∞/m10.4单服务台负指数分布排队模型7/16/20248510.4.1标准排队模型[M/M/1/

/

/FCFS][M/M/1/

/

/FCFS]顾客到达的时间间隔是负指数分布服务时间是负指数分布一个服务台排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统7/16/202486M/M/1的状态转移分析012n-1nn+17/16/202487M/M/1排队模型标准的排队过程是参数不随状态而变的特殊的生灭过程7/16/202488得到

令

称

为服务强度，则得由M/M/1排队模型7/16/202489例10.1高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为100辆／小时，收费时间服从负指数分布，平均收费时间为15秒／辆。求1、收费处空闲的概率；2、收费处忙的概率；3、系统中分别有1，2，3辆车的概率。7/16/202490M/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.417×0.583=0.243系统中有2辆车的概率为：

P2=

2(1-

)=0.4172×0.583=0.101系统中有3辆车的概率为：

P3=

3(1-

)=0.4173×0.583=0.04217/16/202491M/M/1排队模型解：系统绩效度量

系统中的平均顾客数LsExpectednumberofcustomersinsystem

平均等待顾客个数Lq（排队长）

Expectedqueuelength(excludecustomersbeingserved)

顾客平均逗留时间Ws

Waitingtimeinsystem

顾客平均（排队）等待时间WqWaitingtimeinqueue(excludeservicetime)7/16/202492M/M/1/

/

/FCFS的系统指标系统中的平均顾客数Ls

队列中的平均顾客数Lq7/16/202493顾客在系统中的平均逗留时间顾客在系统中的逗留时间Ts服从参数为m-l的负指数分布7/16/202494顾客在系统中的平均逗留时间Ws

顾客在队列中的平均逗留时间Wq

顾客在系统中的平均逗留时间7/16/202495JohnD.C.Little公式7/16/202496理发店空闲的概率店内有3个顾客的概率店内至少有一个顾客的概率店内顾客的平均数，等待服务顾客的平均数顾客在店内的平均逗留时间和平均等待时间必须在店内消耗15分钟以上的概率例10.2某理发店只有一名理发师，来理发的顾客按泊松分布到达，平均每小时4人，理发时间服从负指数分布，平均需要6分钟，求7/16/202497M/M/1排队模型(3)P(n≥1)=1−P(n<1)=1−P0=0.4(4)Ls=r/(1−r)=0.4/(1−0.4)=0.667人

Lq=Ls−r=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=1−r=1=0.4=0.6(2)P3=(1−r)r3=0.6×0.43=0.03847/16/202498M/M/1排队模型

例10.3高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为200辆/小时，收费时间服从负指数分布，平均收费时间为15秒/辆。求Ls、Lq、Ws和Wq。7/16/202499M/M/1排队模型解：根据题意，

=200辆/小时，

=240辆/小时，

=

/

=5/6。7/16/2024100M/M/1排队模型当队列的容量从无限值变为有限值N时，[M/M/1/

/

/FCFS]就转化成为[M/M/1/N/

/FCFS]

10.4.2有限队列模型M/M/1/N/

/FCFS7/16/2024101系统的状态转移图012N-1N7/16/2024102系统的状态概率平衡方程对于状态0：

0P0=

1P1

… …对于状态n：

n-1Pn-1+

n+1Pn+1=(

n+

n)Pn0<n<N… …对于状态N：

N-1PN-1=

NPN7/16/2024103系统参数7/16/2024104系统状态概率PN称为顾客损失率7/16/2024105系统的状态概率由得到

7/16/2024106系统的运行指标当r=1时的情形，此时由得：7/16/2024107系统的运行指标对于

1有7/16/2024108有效到达率7/16/2024109Little公式7/16/2024110例10.4

一个单人理发店，除理发椅外，还有4把椅子可供顾客等候。顾客到达发现没有座位空闲，就不再等待而离去。顾客到达的平均速率为4人/小时，理发的平均时间为10分钟/人。顾客到达服从Poisson流，理发时间服从负指数分布。求：1、顾客到达不用等待就可理发的概率；2、理发店里的平均顾客数以及等待理发的平均顾客数；3、顾客来店理发一次平均花费的时间及平均等待的时间；4、顾客到达后因客满而离去的概率顾客损失率；5、增加一张椅子可以减少的顾客损失率。7/16/202411110.4.2有限队列模型M/M/1/N/

/FCFS解：这是一个[M/M/1/N/

/FCFS]系统，其中N=4+1=5，

=4人/小时，

=6人/小时，

=2/3。

7/16/202411210.4.2有限队列模型M/M/1/N/

/FCFS因客满而离去的概率为0.00487/16/202411310.4.2有限队列模型M/M/1/N/

/FCFS当N=6时

P5-P6=0.0480-0.0311=0.0169=1.69%即增加一张椅子可以减少顾客损失率1.69%7/16/202411410.4.2有限队列模型M/M/1/N/

/FCFS设顾客总数为m,当顾客需要服务时，就进入队列等待；服务完毕后，重新回到顾客源中,如此循环往复。。。服务台...顾客源需要服务服务完毕队列10.4.3M/M/1/∞/m/FCFS模型7/16/2024115关于顾客的平均到达率，在无限源的情形下是按全体顾客来考虑的，而在有限源的情形下，必须按照每个顾客来考虑，l即为每一顾客单位时间内请求服务的平均次数。10.4.3M/M/1/∞/m/FCFS模型7/16/2024116分析假定每一个顾客在单位时间内需要接受服务的平均次数是相同的，设为λ

。当正在等待及正在接受服务的顾客数为n时，则在单位时间内要求接受服务的平均顾客数为：

λn=λ(m-n)01nm7/16/2024117状态转移方程λ0P0=μP1 ……[λn+μ]Pn=μPn+1+λn-1Pn-1

(n=1，2，…，m-1) ……μPm=λm-1Pm-1

(n=1，2，…，m) 7/16/20241187/16/2024119状态转移方程有效到达率λn=λ(m-n)n=1,2,…,m7/16/2024120系统绩效指标7/16/2024121例10.5某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运行时间15分钟。有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。求:(1)修理工空闲的概率；(2)五台机器都出故障的概率；(3)出故障的平均台数；(4)平均停工时间；(5)平均等待修理时间；(6)评价这个系统的运行情况。7/16/202412210.4.3M/M/1/∞/m/FCFS模型解：根据题意，m=5，λ=1/15，μ=1/12，ρ=λ/μ=0.8

7/16/202412310.4.3M/M/1/∞/m/FCFS模型（7）系统绝对通过能力（工人的维修能力）A=le=l(m-Ls)=m(1-P0)=0.083

每小时维修0.083*60=4.96（台）总体看来，该维修系统较繁忙，机器等待时间过长。7/16/202412410.4.3M/M/1/∞/m/FCFS模型10.5多服务台排队模型标准的[M/M/c/∞/∞/FCFS]模型系统容量有限的[M/M/c/N/∞/FCFS]模型有限顾客源的[M/M/c/∞/m/FCFS]模型

10.5多服务台排队模型7/16/2024126服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列顾客到达后，进入队列尾端；当某一个服务台空闲时，队列中的第一个顾客即到该服务台接收服务；服务完毕后随即离去。各服务台互相独立且服务速率相同，即μ1=μ2=…=μc

10.5.1M/M/c/∞/∞/FCFS模型7/16/2024127分析系统的服务速率与系统中的顾客数有关。当系统中的顾客数k不大于服务台个数，即1≤k≤c时，系统中的顾客全部在服务台中，这时系统的服务速率为kμ；当系统中的顾客数k＞c时，服务台中正在接受服务的顾客数仍为c个，其余顾客在队列中等待服务，这时系统的服务速率为cμ。

则当ρ＜1时系统才不会排成无限的队列

7/16/2024128状态转移图与状态转移方程对状态0: λP0=μP1

对状态1: λP0+2μP2=(λ+μ)P1 …………对状态c： λPc-1+cμPc+1=(λ+cμ)Pc …………对状态n λPn-1+cμPn+1=(λ+cμ)Pn ………01cn7/16/2024129状态概率7/16/2024130运行指标7/16/2024131例10.6某售票处有三个窗口，顾客到达服从Poisson流，到达速率为0.9人／分，售票时间服从负指数分布，每个窗口的平均售票速率为0.4人／分。顾客到达后排成一队，依次到空闲窗口购票。求：(1)所有窗口都空闲的概率；(2)平均队长；(3)平均等待时间及逗留时间；(4)顾客到达后必须等待的概率。7/16/202413210.5.1M/M/c/∞/∞/FCFS模型解：λ/μ=2.25，ρ=λ/cμ=0.75(1)所有窗口都空闲的概率，即求P0的值

(2)平均队长，即求Ls的值，必须先求Lq

7/16/202413310.5.1M/M/c/∞/∞/FCFS模型(3)平均等待时间和平均逗留时间，即求Wq和Ws和的值

(4)顾客到达后必须等待，即n≥37/16/202413410.5.1M/M/c/∞/∞/FCFS模型M/M/C型VSC个M/M/1型如果顾客到达后在每个窗口各排一队，且进入队列后不可更换，形成3个队列，在上例中，每个队列的平均到达率为：7/16/2024135M/M/1系统的指标λ=0.3，μ=0.4，ρ=λ/μ=0.75P0=1-ρ=0.25P(n>=1)=1-P0=0.75Ls=λ/(μ-λ)=3Lq=Ls-ρ=3-0.75=2.25Ws=Ls/λ=10分Wq=Ws-1/μ=7.5分7/16/2024136指标模型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/16/2024137离开服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列10.5.2M/M/c/N/∞/FCFS模型7/16/2024