第11章-排队论-管理运筹学-课件.pptx

1、重 庆 三 峡 学 院重 庆 三 峡 学 院管理运筹学管理运筹学课件课件本章主要内容基本概念基本概念1生死过程生死过程2单服务台排队系统模型单服务台排队系统模型3多服务台排队系统模型多服务台排队系统模型4其他排队系统模型其他排队系统模型5排队系统的优化排队系统的优化6本章小结本章小结教学目标1理解下列基本概念：排队系统构成、特征、分类、主要性能指标及相互关系2掌握以下三种排队系统主要性能指标的计算：M/M/s/；M/M/s/N/；M/M/s/m。3了解M/G/1、M/D/1的主要指标计算公式 知识结构教学目标与要求导入案例：主任医师招聘问题某三甲医院肝胆内科有主任医师1名，由于他的存在而使前来

2、诊疗的患者大增。根据一个月的统计，平均每h到达医院的患者6名，并对各时间段统计，经拟合优度检验符合泊松分布；该医生每h可诊疗4名，但患者病情不同，分布也不是均匀的，对每位患者就诊时间的统计，经拟合优度检验，符合指数分布。医院配备有电子回馈信息系统，及时观察到已挂号排队等候的患者数量。当排队等候人数少于5人时，挂号系统可以挂号。当前来就诊的患者挂上号若医生空闲则可直接就诊，否则排队等候。医生采取先到先服务的规则。若前来就诊的患者挂不上号，则立即到邻近的一家医院就诊。经统计，经该主任医师诊疗的患者，其诊疗费、检验费、医药费等医院可获纯收入100元；主任医师可高薪聘请，其薪金及住房和各种福利年均25

3、万元，医院实行每周5天工作制，年工作日250天，平均每天支付1000元的成本。当医生过少，由于患者得不到服务离去而产生的损失增加；当医生过多，由于医生空闲时间的增加也使医院的成本增加。问：医院应招聘多少名肝胆内科主任医师可使得盈利最大？此类排队现象在日常生活中经常遇到，如客户到银行排队办理存贷款业务，出纳员为客户提供服务；汽车到加油站排队，加注系统为汽车提供加油服务；超市顾客到收银台前排队，收款员为顾客提供交款服务；旅客到公交车站排队，公交车为旅客提供位移服务。排队论的基本思想是1910年丹麦电话工程师A.K.埃尔朗在解决自动电话设计问题时开始形成的，当时称为话务理论。他在热力学统计平衡理论的

4、启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的埃尔朗电话损失率公式。自20世纪初以来，电话系统的设计一直在应用这个公式。20世纪30年代前苏联数学家欣钦把处于统计平衡的电话呼叫流称为最简单流；瑞典数学家巴尔姆又引入有限后效流等概念和定义；美国数学家费勒(W.Feller)关于生灭过程的研究；20世纪50年代初，英国数学家D.G.肯德尔提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论奠定了理论基础；20世纪70年代以来，人们开始研究排队网络和复杂排队问题的渐近解等，成为研究现代排队论的新趋势。11.1.1 排队系统的一般表示排队系统的一般表示11.1.

5、2 排队系统的三个特征排队系统的三个特征11.1.3 排队系统模型的分类排队系统模型的分类11.1.4 排队的主要性质指标排队的主要性质指标11.1.5 排队系统的输入和输出排队系统的输入和输出11.1.1 排队系统的一般表示队伍服务机构顾客源服务规则排队规则顾客到来（输入）顾客离去（输出）服务系统一个排队系统都具有以下三个特征：输入过程 在一定时间内顾客平均到来多少？按什么规律到来；排队规则 进入系统的顾客按什么规则排队；服务机构 设置多少服务设施？排列形式？服务时间服从什么分布？11.1.2 排队系统的三个特征输入是指顾客到达服务系统的情况。可能有下列情况，但并不相互排斥：（1）按顾客源总

6、数划分为有限和无限两大类。如工厂需要检修的机器是有限的，准备进京观光旅游的游客是无限的。（2）按顾客到达的人数可以划分为单个到达和成批到达。如到超市购买商品的顾客是单个的，到港国际航班等待安检的旅客是成批的。（3）按顾客到达时间间隔是否固定可以划分为确定型和随机型。如定期运行的班车、班轮、班机是确定的，到加油站加油的汽车是随机的。对随机的顾客到达需要知道单位时间到达的顾客数或时间间隔的概率分布。（4）按接受过服务的顾客对顾客到达数是否有影响，划分为相互独立到达和非相互独立到达。如提供优质服务的餐饮业所产生了大量“回头客”，就属于非相互独立到达。我们只讨论独立到达情况。（5）按顾客相继到达间隔时

7、间的分布及其数字特征是否与时间有关可分为平稳与非平稳的。相继到达的间隔时间分布及其数学期望、方差等数字特征都与时间无关，称为平稳的，否则是非平稳的。一般非平稳情况的数学处理很困难，我们只讨论平稳状况。1输入过程排队规则指到达排队系统的顾客按怎样的规则排队等待。（1）按顾客到达排队系统时发现服务设施已被占用是否离去可分为损失制，等待制和混合制三种。当顾客到达时，所有的服务台均被占用，顾客随即离去，称为损失制（或称即时制、消失制）；当顾客到达时，所有的服务台均被占用，顾客就排队等待，直到接受完服务才离去，称为等待制，例如出故障的机器排队等待维修就是这种情况；介于损失制和等待制之间的是混合制。对于等

8、待制，有下列服务规则：先到先服务（FCFS）、先到后服务（LCFS）、带优先服务权（PR）、随机服务（SIRO）等。在后面研究的问题中均假设采取FCFS服务规则。（2）按队列长度是否有限，可分为队长有限和队长无限两种情况。在限度以内就排队等待，超过一定限度就离去。（3）按排队方式分为单列、多列。对于多列排队的顾客有的可以相互转移，有的则不能（用栏杆等隔开）；有的排队顾客因等候时间过长而离开，有的则不能（如在高速公路行驶的汽车必须坚持到高速出口）。我们所讨论的问题限制在队列间不能相互转移，中途不能退出的情形。2排队规则从机构形式和工作情况来看有以下几种：（1）服务机构可以没有服务员，也可以有一个

9、或多个服务员（服务台、窗口）。如超市的货架可以没有服务员，但交款时可能有多个服务员。（2）多个服务台的情况中，可以是平行排列的（并联），也可以是前后排列的（串联），也可以是混合的。（3）服务方式可以对单个顾客进行，也可成批进行。我们只讨论单个服务情况。（4）服务时间可分为确定型的和随机型的。如旅客列车对乘客的服务是按列车时刻表进行位移服务的，是确定型的；因患者病情不同，医生诊断的时间不是确定的，是随机型的。（5）服务时间的分布总假定是平稳的，即分布的期望值、方差等参数不受时间的影响。3服务机构SS1S2S3S1S2S3S1S2S1S2S3S4S5(a)单台单队(b)多队多台并联(c)单队多台并

10、联(d)单队多台串联(e)多台混合11.1.3 排队系统模型的分类输入/输出/并联的服务站数肯德尔（Kendall）于1953年提出了排队服务系统的分类记号 输入/输出/并联的服务站数/系统容量（队长）/系统状态（顾客源数）/服务规则1971年国际排队符号标准会上肯德尔将上述分类记号扩充到六项，记为符号含义输入（顾客到达分布）MDGI泊松（Poisson）输入定长输入(确定型输入Deterministic)一般相互独立（General independent）的时间间隔分布输出（服务时间分布）MEkG指数分布（negative exponential）k阶埃尔朗分布（Erlang distri

11、bution）一般（General）服务时间分布服务规则FCFSLCFSPRSIRO先到先服务后到先服务带优先服务权随机服务如如:M/M/1/FCFS（1）队长（Ls）和排队长（Lq）11.1.4 排队系统的主要性能指标 1.常用指标常用指标求解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确定系统参数的最优值，以决定系统结构是否合理、研究设计改进措施等。因此必须确定用以判断系统运行优劣的基本数量指标。常用的指标包括：队长和排队长、逗留时间和等待时间、服务机构强度。系统中的顾客数（队长Ls）排队等候服务的顾客数（排队长Lq）正在接受服务的顾客数 逗留时间指顾客在排队服务系统中从进入到

12、服务完毕离去的平均逗留时间；等待时间指顾客排队等待服务的平均等待时间。这对顾客来讲是最关心的，每个顾客希望逗留时间或等待时间越短越好。（2）逗留时间（Ws）和等待时间（Wq）指服务机构累计的工作时间占全部时间的比例，是衡量服务机构利用效率的指标。即：（3）服务机构工作强度11.1.4 排队系统的主要性能指标 1 服务机构用于服务顾客的时间服务设施总的空闲时间工作强度服务设施总的服务时间服务设施总的服务时间11.1.4 排队系统的主要性能指标 2指标间的关系指标间的关系 设：表示单位时间内顾客的平均到达数，则1/表示相邻两个顾客到达的平均间隔时间；表示单位时间内被服务完毕离去的平均顾客数，则1/

13、表示对每个顾客的平均服务时间；s表示服务系统中并联的服务台数;Pn(t)在时刻t系统中恰好有n个顾客的概率。则有下列关系：,ssssLLWW或,()qqqqLLWWLittle或公式1,sqsqWWLL01,()snqnnn sLnP Lns P 11.1.5 排队系统的输入和输出排队系统的输入和输出是指顾客到达流和服务时间流，它们的分布一般都是非负的随机变量。最常见的是泊松分布、指数分布和埃尔朗分布、经验分布。然而在研究具体问题时，究竟是服从哪种分布？通常抽取到达时间间隔和服务时间样本，统计其频数，并进行拟合优度检验，以确定服从哪种理论分布。1.最简单流（泊松分布）所谓最简单流，是指在t这段

14、时间内有k个顾客来到服务系统的概率服从泊松（Poisson）分布，故也称为泊松流。即：当k=0时有：均值和方差为：()()(0,1,2,.)!ktktP tekk0()tP te()()E TVar Tt（1）平稳性 指在一定时间间隔内，来到服务系统有k个顾客的概率仅与这段时间间隔的长短有关，而与这段时间的起始时刻无关；（2）无后效性 指在不相交的时间区间内到达的顾客数是相互独立的，或者说在区间a,a+t来到k个顾客的概率与时间a之前来到多少个顾客无关；（3）普通性 指在足够小的时间区间内只能有一个顾客到达，不可能有两个以上顾客同时到达。最简单流需要满足三个条件最简单流需要满足三个条件 证 由

15、于考虑单位时间，取t=1，其数学期望为：（1）参数代表单位时间内到达顾客的平均数 证 在时间t 没有顾客到达的概率为 P0(t)=e-t，将右端展开为麦克劳林级数有：当t0 时，从第3项开始为t 的高阶无穷小，故结论得证。（2）在t,t+t 没有顾客到达的概率为1-t+o(t)证 在 t,t+t内恰好有1个顾客到达的概率为 P1(t)=e-tt，将e-t的麦克劳林级数代入，结论得证。（3）在t,t+t 内恰好有1个顾客到达的概率为 t+o(t)最简单流的一些性质1001(1)!(1)!kkkkkkkPkeekk23()0()()(0)1().:()2!3!ntnnttfetf xxn 麦克劳林

16、级数2指数分布的服务时间 如果随机变量T的概率密度为则称T服从指数分布，其分布函数是：数学期望和方差为：0246810121416180.000.100.200.30指数分布指数分布f(t)=Exp(-t)f(t)=Exp(-t)=10=15=202()1/()1/E TVar T()()10tF tP Ttet()0tf tet指数分布的性质()()|P Tts TsP TtsP Tts TsP TsP Ts ()11 111(1)t stsP TtseeP TtP Tse（1）不管对某一个顾客的服务已进行了多久，剩下来的服务时间的概）不管对某一个顾客的服务已进行了多久，剩下来的服务时间的概

17、率分布仍为同原先一样的指数分布（称为无记忆性或马尔柯夫性）率分布仍为同原先一样的指数分布（称为无记忆性或马尔柯夫性）。证 设刚刚服务完一个顾客所用的时间为s，对t0，有：PTt+s|Ts，根据条件概率公式有：于是结论得证。证。（2）当输入为泊松流时，顾客相继到达时间间隔必是指数分布。）当输入为泊松流时，顾客相继到达时间间隔必是指数分布。证 对于泊松流，在0,t)内至少一个顾客到达的概率=1没有顾客到达的概率.即：1P0(t)=1e-t，结论得证。因此，相继到达的间隔时间是独立的且为相同的指数分布，与输入过程为泊松流是等价的。所以（Kendall）记号中都用M表示。（3）当服务设施对顾客的服）当

18、服务设施对顾客的服务务时间时间t为参数为参数的指数分布时，与泊松流类的指数分布时，与泊松流类似也有：似也有：在在t,t+t内没有顾客离去的概率为内没有顾客离去的概率为1-t+o(t)；在在t,t+t内恰有一个顾客离去的概率是内恰有一个顾客离去的概率是t+o(t)；当如果当如果t足够小，在足够小，在t,t+t内有多于两个以上顾客离去的概率为内有多于两个以上顾客离去的概率为o(t)。（4）数学期望）数学期望 表示表示对每个顾客的平均服务时间对每个顾客的平均服务时间，1/为为平均服务率，平均服务率，即单位时间完成服务的顾客数。即单位时间完成服务的顾客数。（5）若干独立的指数分布的最小值是指数分布。）

19、若干独立的指数分布的最小值是指数分布。证 设T1,T2,Tn分别表示参数为1,2,n的独立的随机变量，U是这些随机变量的最小值，即U=minT1,T2,Tn，对任意t0，有 P(Ut)=PT1t,T2t,Tnt=P(T1t)P(T2t),P(Tnt)=e-1te-2te-nt=e-it即U是参数为=it的指数分布。这一性质说明：第一，如果来到服务机构的有n类不同类型的顾客，第i类顾客来到服务站的间隔时间具有参数i的指数分布，则作为总体来讲，到达服务机构的顾客的间隔时间仍为指数分布；第二，如果一个服务机构中有s个服务设施，各服务设施对顾客的服务时间为具有相同参数的指数分布，于是整个服务机构的输出

20、就是一个具有参数s的指数分布。这样对具有多个并联服务站的服务机构就可以同具有单个服务站的服务机构一样处理。3K阶埃尔朗（ERLANG）分布k个相互独立具有相同参数的指数分布的和的分布称为k阶Erlang分布。k阶Erlang分布的概率密度为：数学期望和方差为：1()()0(1)!kk tk k tf tetk211()()E TVar TkErlang分布族提供了更为广泛的模型类，比指数分布有更大的适应性。当k=1时，Erlang分布即为指数分布；当k增大时，Erlang分布的图形逐渐变为对称；当k30时Erlang分布近似于正态分布；当k时，Erlang分布化为确定型分布。4经验分布所谓的经

21、验分布，就是根据样本确定的分布。设(X1,X2,Xn)是来自总体X的简单随机样本，以vn(x)表示事件Xx在n次简单随机抽样(独立重复观测)中出现的次数，即样本的n个观测值X1,X2,Xn中不大于x的观测值的个数，则称为总体X的经验分布函数对于给定的x，经验分布函数是随机变量；对于给定的样本值，经验分布函数具有随机变量的分布函数的一切性质。()()nnxFxn 求出频率和组中组，得经验分布求出频率和组中组，得经验分布由由frequencyfrequency函数或直方图工具或数函数或直方图工具或数据透视表统计频数据透视表统计频数计算组距计算组距d=R/n,d=R/n,确定组上限确定组上限确定组数

22、确定组数n n。若无实际要求，可由斯。若无实际要求，可由斯特奇斯公式特奇斯公式n=1+3.322lgNn=1+3.322lgN确定确定求最小值、最大值、计算全距求最小值、最大值、计算全距R R经验分布律确定步骤：经验分布律确定步骤：例：产生10列30行平均数为20，标准差为3的正态分布随机数视为观察数据，利用上述方法求得经验分布。11.2 生死过程nn+1n-1生死过程（生灭过程）是用来处理输入为最简单流，服务时间为指数分布这样一类最简单排队模型的方法。它是分析后面各类排队问题的方法论，在排队论中有重要意义，什么是生死过程呢？举一个例子：某地区当前人口数为n，该年人口出生数n，则根据泊松流的性

23、质，在t 时间内出生一个人的概率为nt+o(t)；n为该年人口死亡数，则根据指数分布的性质，在t时间内死亡一个人的概率为nt+o(t)，那么在经过 t时间后，人口将变成多少？当前人口nt后人口t后生0死0nt后生1死0n+1t后生1死1nt后生0死1n-1t后死1生1n设系统处于状态i的概率为Pi当i=0时，输入区仅仅来自状态1，状态0的输入率为1P1；输出也只有一个，输出率为0P0，状态0的平衡方程为：当i=1时，输入和输出各有两个，分别是状态0和状态2；状态1的平衡方程为：生死过程的平衡方程01 100101PPPP00221 11 1PPPP221 11 100PPPP11 11 101

24、1 10PPPP101210221PPP 110021nnnPP 同理依次推得11021nnnC 0(1,2,.)nnPC Pn0001nnnnPPC根据概率的性质001/nnPC令11.3.1 M/M/1/FCFS（标准系统）标准系统）11.3.2 M/M/1/N/FCFS（系统容量有限）系统容量有限）11.3.3 M/M/1/m/FCFS（顾客源有限）顾客源有限）11.3.1 标准的M/M/1/系统1M/M/1/模型需要满足的条件模型需要满足的条件标准的M/M/1/模型是指满足下列条件的排队系统：（1）输入过程：顾客源无限，单个到来，相互独立，到达平均数为常数，且服从泊松分布，到达过程是平

25、稳的。（2）排队规则：单队，队长不受限制，先到先服务。（3）服务机构：单服务台、平均服务率为常数，对各顾客服务时间相互独立，服从相同的指数分布，服务过程也是平稳的。2M/M/1/系统运行指标系统运行指标由于到达平均数和服务平均数均为常数，即01112.,.nn11021nnnnnC 于是有1式中称为业务密度0011nnnnC001/1nnPC 00(1)nnnnPC PP0snnLnP0(1)nnn10(1)nnn 0(1)nndd 0(1)nndd 1(1)1dd 11ssLW111()qsWW qqLW在系统中的平均顾客数(队长)：在队列中等待的平均顾客数：在系统中顾客平均逗留时间：在队列

26、中顾客平均等待时间：1sWqWqLsL综上所述有M/M/1/系统运行指标：案例11-1(P245):=3台/天，=服务率4台/天，150台设备（顾客源150可视为无限）。要求：顾客平均等待时间不超过2h。3343sL0.75 32.25qsLL11143sW0.75qsWW可见，当每天维修电话从3个减少到2个时，顾客平均等待时间为8h的0.25倍，即2h，满足管理层的要求。排队等待的顾客数也从平均2.25减少到0.5。决策决策 维修量与顾客总体成正比例，目前每个服务代表负责150个顾客总体，减少到100个，可增加技术服务代表，每个负责有100个用户的区域。解：11.3.2 系统容量有限的M/M

27、/1/N/系统M/M/1/N/模型，由于系统容量有限，当nN，顾客不再进入系统，其他条件同M/M/1/模型。其速率图如下：01112.,.nn由于 因此有：110210nnnnnnNCnN 当时10nnNCnN0011/1NnnPCN1/(1),0nNnNPnN当时101,1NNnnnnCC01011/1NnNnPC10110nNnnnNPC PnN0NsnnLnP11011NnNnn1011NnNndd1011NnNndd111111NNdd11(1)11NNN11(1)limlim111NsNNNNL因所以所以M/M/1/模型是模型是M/M/1/N/的特例。的特例。M/M/1/N/主要指标

28、的计算11(1)11NsNNLLittle公式是否还适用？答案是肯定的，但由于队长受限，真正进入服务系统的顾客要小于到达率，我们称为有效到达率eff1()Nqnn sLns P 2(1)NnnnP22NNnnnnnPP101022NNnnnnPnPPPPP000NNnnnnnPPP0(1)qsLLP0(1)effPsseffLWqqeffLWeffsqLL由前所述【例11-1】某单人美发店有3把椅子以备顾客休息等待。后来的顾客发现3把椅子都坐满时就不进店等待而离开。顾客平均到达3人/h，理发时间平均15min/人。要求计算：（1）某顾客一到达就能理发的概率；（2）有效到达率；（3）排队等待顾客

29、的平均数；（4）顾客在理发店平均等待时间；（5）顾客一到就离开的概率。01511 0.750.327811 0.75NP0(1)4(10.3278)2.689effP1155(1)110.755(0.75)1.44431 0.751 0.75NsNNL2.6891.44430.7724effqsLL0.7720.2872.689qqeffLW解 已知=3,=4,=/=0.75（1）一到就能理发，即系统顾客为0的概率（2）（3）（4）（5）顾客一到就离开的）顾客一到就离开的概率概率顾客一到就离开的概率，按系统容量受限的计算公式，当顾客一到就离开的概率，按系统容量受限的计算公式，当nN时时Pn=0

30、.不妨设系统容量为不妨设系统容量为5,而第而第5个是不能进入的个是不能进入的.于是有于是有:n55505 1611 0.750.757.2%11 0.75PC P11.3.3 顾客源有限的M/M/1/M系统M/M/1/m系统除顾客源有限制外，其余条件与M/M/1/系统相同。设顾客源数（设备数）m，系统中顾客数（等待维修和正在维修的设备数）n，单台故障率平均服务率 n-1 n 2 0 3 0 0 0 1 m-1 m n+1 1 m(m-1)(m-2)(m-n+1)(m-n)011,(1),(1)nmmmn 由于11021!,()!0nnnnmnmCmnnm 0001/(1)nmiinPCPC P

31、nm0000()()mmmmnnnnnsnnnnPmnPmPnPmL式中 主要指标计算过程：【例例11-2】一名工人负责看一名工人负责看管管10台自动机床，在加料或台自动机床，在加料或刀具更换时就自动停车，等刀具更换时就自动停车，等待工人照管。设平均每台机待工人照管。设平均每台机床两次停车间隔时间床两次停车间隔时间2h，需，需要工人照管的平均时间为要工人照管的平均时间为12min，设以上两项时间均，设以上两项时间均服从指数分布，计算该系统服从指数分布，计算该系统的各项指标。的各项指标。解解 单台平均停车间隔时间单台平均停车间隔时间2h，则每台单位时间停车率，则每台单位时间停车率为为0.5（=0

32、.5）；对每台停）；对每台停车 的 机 床 平 均 照 管 时 间车 的 机 床 平 均 照 管 时 间12min，单位时间照管的台，单位时间照管的台数为数为5（=5）,/=0.5/5=0.1001/mnnPC0nnPC P0msnnLnP2(1)mqnnLnP/ssWL/qqWL!,()!nnmCnmmn!,()!nnmCnmmn()0.5(102.146)3.9274smL/2.146/40.5385/1.34/40.335ssqqWLWL11021000021/(1)nnnnnnnsnqnnnqssqCPCPC PLnPLnPLLWW 基本关系式:，1/1/:1,2,.iiM Mi 11

33、/1/:,0,0iiiiM MNif iNelse 11/1/:(),0iiiM Mmif immielse 01(1)/nnnnsqssqqCPPLLWLWL，0,0,(1)nneffnNCnNP!,()!0,()nnsmnmCmnnmmL单服务台小结11.4.1 M/M/s/（标准系统）（标准系统）11.4.2 M/M/s/N/（系统容量有限）（系统容量有限）11.4.3 M/M/s/m（顾客源有限）（顾客源有限）11.4.1 标准的M/M/S/系统1模型需满足的前提条件标准的多服务设施排队系统规定的条件：（1）顾客到达率为常数（n=），服从泊松分布；（2）每台服务率为常数，服从指数分布；

34、（3）单队排队，队长不受限制，排队规则FCFS；（4）各服务台相互独立，不搞协作。S1 S2 S3 队列 顾客 总体 服务系统 2模型指标的计算设服务台数为s，则有：,nnnssns110211101211!()()()(!)1!nnnnnnssnn ssnn snsnCssnss s =/sCn001/nnPC0nnPC P0snnLnP1()qnn sLns P/ssWL/qqWL数值计算流程：【例11-3】有2个油泵的加油站，平均加注一辆汽车需要1.2min，平均每h有80台汽车前来加油。到达率服从泊松分布，服务时间间隔服从指数分布。要求确定：（1）预期在加油站的汽车数；（2）预期汽车在

35、加油站停留多长时间；（3）某个油泵空闲的概率。解 每个油泵服务率50辆/h，到达率80辆/h。1!1!nnnn snsnCnss s承上例，假设有2个单油泵加油站，平均每个加油站到达率为40台/h，其他条件不变，由式11.1511.18计算，并与1个双油泵加油站指标比较列于表由表可见，1个多服务台要明显好于多个单服务台系统运行指标。31个M/M/s/系统与多个M/M/1/系统运行指标的比较指标1个双油泵加油站2个单油泵加油站平均逗留时间Ws/min3.336平均等待时间Wq/min2.134.8队长Ls/台4.444排列长Lq/台2.843.211.4.2 系统容量有限的M/M/S/N/系统对

36、于容量有限的M/M/s/N/系统，由于多于N个时不允许进入服务系统，故有：系统运行指标公式推导较复杂，可用EXCEL按下列步骤进行：1!1!0nnnn snsnCsnNs snN=/sCn001/nnPC0nnPC P0snnLnP1()qnn sLns P/sseffWL/qqeffWL:()effsqLL式中【例11-4】某单位电话交换台有一台200门的内线总机。已知在上班的8h内有20%的内线分机平均每40min要拨一次外线电话，80%的分机平均隔2h拨一次外线电话。又知从外单位打来的电话呼唤率平均1次/min。设外线通话时间平均为3min，以上两个时间均服从指数分布，如果要求电话接通率

37、为95%，问交换台应该设置多少外线？解 （1）以h为时间单位；与外线通话包括拨出与拨入。拨出：20%分机1.5次/h，80%分机0.5次/h，平均数1=(20%1.5+80%0.5)200=140；拨入60次/h，即2=60，总计=1+2=200；通话时间1/=3min平均通话=20 次/h，/=200/20=10。（2）该问题是一个多服务设施损失制排队系统，当ns时，为损失制服务系统。此时0001(),1/,()!nsnnnnnCns PCPC PP nsn，为损失率若损失率小于若损失率小于5%,至少要有至少要有15个外线电话个外线电话.11.4.3 顾客源有限的M/M/S/M系统如m台设备

38、,s个工人看管,故障率相同,维修水平一样.s 2 3 s-1 s 2 0 3 0 0 0 1 s m-1 m s s+1 1 m(m-1)(m-2)(m-s+1)(m-s)()0nmnnmnm0nnnsssnmnm11021!()!()!0nnnnnn smnsmn nCmsnmmn s snm 可以证明:()smL【例11-5】2个工人联合看管8台机器，已知机器停机（加料或换刀具）时间间隔平均为1h，照管的时间平均为10min。以上两项均服从指数分布，求各项指标。解 这是一个多服务台顾客源有限的排队系统。按计算步骤，运用Excel操作公式输入如图11.20。结果如图11.21。Cn001/n

39、nPC0nnPC P0snnLnP1()qnn sLns P/ssWL/qqWL:()smL式中系统运行指标计算步骤:11021!()!()!0nnnnnn smnsmn nCmsnmmn s snm 由图可见，平均队长1.36台，排队长0.25台；平均逗留时间0.2h（12min），平均等待时间0.038h（2.28min），工人业务密度（劳动强度）73.2%。11.5.1 一般服务时间一般服务时间M/G/1模型模型11.5.2 定长服务时间定长服务时间M/D/1模型模型11.5.3 埃尔朗服务时间埃尔朗服务时间M/Ek模型模型11.5.4 具有优先服务权的排队模型具有优先服务权的排队模型指

40、标间的关系对任何服务时间,下面关系都是正确的:式中ET为服务时间期望值，eff为有效输入率，当顾客源有限或队长有限情况下有不同的计算公式，当顾客源无限及队长无限情况下即为。前提假设 其前提假设是：（1）系统的输入参数为的泊松分布；（2）对每个顾客的服务时间t是独立同分布的随机变量，其概率分布函数为F(t)，期望值和方差分别为：（3）或（4）只有一个服务站。11.5.1 一般服务时间M/G/1模型/sqsesqsseffqqeffLLLWWE TWLWL01()()E ttdF t2()Var t1()E t()1E tPollaczek-KhintchingPollaczek-Khintchi

41、ng公式公式 其他指标公式：其他指标公式：22222222(1)2(1)sL 2222(1)qsLL 2222(1)qqLW 222112(1)sqWW 系统运行各指标，均与方差成正方向变化。因此，当对各顾客服务时间比较接近情况下（方差较小），工作指标就越好，否则就越差。对于定长服务时间（方差为0）指标最好。【例11-6】某自动取款机平均每2min到达一名顾客，服从泊松分布；顾客取款时间分布律为：试求顾客在系统中平均等待时间是多少？队长平均有多长？1.251.251.25()01yeyf yy11.251.250()00tetf tt()(1)()11/11.8E YE TE T 22()(1

42、)()1/1/1.250.64Var YVar TVar T()0.9E Y222220.90.50.640.95.752(1)2(1 0.9)sL 5.750.94.85qsLL/4.85/0.59.7qqWL解 以min为时间单位，到达率为0.5（=0.5）；设Y=T+1，则：答：平均队长4.85人，平均等待时间约9.7min。1.251.251.25(1)1.25()1.25=1.251.25()(0)yytf yeeef t t即服务时间T遵循指数分布.11.5.2 定长服务时间M/D/1模型服务时间是确定的常数，例如在一条流水线上完成一件工作的时间就是常数。这时221/02(1)sT

43、L【例11-7】某医院检验科的血糖检测仪器检测每位患者需5min，平均每h有10位患者按泊松分布到达，求：（1）在检验科排队等候检验的患者人数；（2）每位患者平均逗留时间。10,12,/5/6 22(1)sL25(5/6)1122.91762(1 5/6)121110122121212qsLL/0.2917(17.5min)ssWLh约11.5.3 埃尔朗分布（M/EK）模型若k个服务站串联，每个服务站服务时间Ti相互独立，并服从相同的指数分布（参数为k）则 服从k阶埃尔朗(Erlang)分布。k阶Erlang分布的概率密度为：每服务站服务时间的数学期望和方差为：整个系统服务时间的数学期望和方

44、差为：代入式11.3211.35（一般分布公式）得：1kiiTT1()()0(1)!kk tk k tf tetk2211()()iiE TVar Tkk211()()E TVar Tk2(1)2(1)skLk,/,1/qsqqsqLLWLWW【例11-8】某面包店专门制作热狗面包，为迎得顾客满意，采取现场制作。制作过程包括两道工序：制作与烘烤，每道工序大约需要15分钟，假设服从指数分布。每烤箱可烤制4板，每板12个。顾客到达率20人/h，每人平均需要2个，服从泊松分布。问每个顾客平均逗留多长时间？平均队长有多少人？解 这是一个串联的排队服务系统，符合 M/Ek/1模型的条件。K=2；=20；

45、每道工序每小时可操作4次，每次制作48个，共192个可满足96人需求，即2=96，=48。()1/1/48E T2221/1/(2 48)k/()20/485/12E T 22(1)53/(2 48)0.4182(1)122 2(1 5/12)skLk/0.418/201.25minssWLh即平均队长0.418人，平均逗留时间1.25min。当n=2时：即 当n=3时：即 当n=N时：11.5.4 具有优先服务权的排队模型优先权模型服务规则有两种：一是顾客在接受服务过程中，即使有更高优先级顾客到来，服务也不中断，称为无强制优先规则；二是顾客在接受服务过程中，有更高优先级顾客到来时，中断对优先

46、级较低顾客的服务，使其回到系统中等待重新得到服务，此称为强制优先规则。本节所讨论的是无强制优先规则。设有n个优先级别，1,2,n表示各级别顾客输入率；服务率是相同的；Wsi为只有第i级别顾客的平均逗留时间；为各类顾客的平均逗留时间。则有：sW121122()sssWWW1212122sssWWW123112233()ssssWWWW12312312333ssssWWWW111NNiisiiisNsNNWWW【例11-9】某车站一售票窗口购票旅客到达2人/min，服从泊松分布；其中5%是军人；售票员平均每20秒卖一张票，服从指数分布。该车站实行军人优先的排队规则，问：普通旅客在购票过程中平均要逗

47、留多少时间？解 顾客到达率2/min，有优先权的军人占5%，即 1=0.1，普通旅客到达率为 2=2-1=1.9，服务率=311minsW1110.345minsW12121221.034minsssWWW概述概述11.6.1 M/M/1模型中的最优服务率模型中的最优服务率11.6.2 M/M/s模型中的最优服务台数模型中的最优服务台数 11.6 排队系统的优化排队系统的最优化问题分为两类：系统设计的最优化和系统控制最优化。系统设计最优化也称为静态问题，其目的是使设备达到最大效益，或者说，在一定的质量指标下要求机构最为经济。系统控制最优化也称为动态问题，指一个给定的系统，如何运营可使某个目标函

48、数得到最优。我们仅讨论静态最优问题。对于静态问题，可从两个角度考虑：一是费用最低，二是收益最大。作为排队系统，费用主要考虑两个方面：一是服务费用，二是等待费用。在单台服务费用一定时，服务台数越少，服务费用也就越少。但顾客等待时间就越长，等待费用就越多。我们的目标是使提高服务水平所付出的成本与减少顾客等待时间所节约的成本找到一个平衡点，使两者成本之和为最小。费用服务水平服务费用等待费用总费用最小费用最小费用服务水平11.6.1 M/M/1模型中的最优服务率1M/M/1/模型最优服务率M/M/1模型中服务率为，在排队系统中的顾客数为Ls。设 cs表示服务一个顾客的成本；cW表示单位时间一个顾客的等

49、待成本，则总费用：swszcc L:SL将代入得swzcc0dzd令得*wscc【例11-10】有1个油泵的加油站，平均每h有36台汽车前来加油。对出租车车主来说，等待1h，将损失40元，对加油站来说，服务一个顾客平均支付成本10元。求单位时间最优加油数量。解：*wscc4036364810由于当系统中已有N个顾客，后来的顾客将被拒绝。设被拒绝的概率为PN，则能接受服从的概率为1-PN，(1-PN)为单位时间有效进入服务机构的顾客平均数。又设G为服务1名顾客的收入，cs仍为服务单位顾客发生的费用，则有收益最大的目标函数：可由Excel规划求解工具或利用模拟运算表求得，方法如下：（1）取目标函数

50、：（2）输入参数及目标函数表达式；（3）选用“规划求解”、“模拟运算表”求解*。11(1)1NNssNzP GcGc111NsNzGc2M/M/1/N/模型最优服务率【例11-11】某M/M/1/N/系统，cs=10,G=20,=10，要求：（1）利用规划求解工具计算当系统容量N=5时的*（2）利用模拟运算表计算N=1、2、3、4、5时的*解 （1）依据数学模型建立EXCEL模型（2）设置规划求解参数对话框并求解11max1NsNzGc（3）利用模拟运算表计算不同N值的最优服务率=E4=E4=“N”&H2=“N”&H211.6.2 M/M/S模型中的最优服务台数 最优服务台数是指服务成本与等待