运筹学课件第11章-排队论

第11章排队论重庆三峡学院关文忠教学目标与要求生死过程(方法论)基本概念系统、特征、分类、指标、输入输出单服务台排队系统M/M/1/∞/∞：M/M/1/N/∞；M/M/1/∞/m多服务台排队系统M/M/s/∞/∞：M/M/s/N/∞；M/M/s/∞/m其他排队系统M/G/1；M/D/1模型的优化（目的）Kendall标志：输入/输出/服务台数/队长/顾客源系统运行指标Ls,Lq,Ws,Wq【教学目标】1．理解下列基本概念：排队系统构成、特征、分类、主要性能指标及相互关系2．掌握以下三种排队系统主要性能指标的计算：M/M/C/∞/∞；M/M/C/N/∞；M/M/C/∞/m。3．了解M/G/1、M/D/1的主要指标计算公式【知识结构】导入案例：主任医师招聘问题某三甲医院肝胆内科有主任医师1名，由于他的存在而使前来诊疗的患者大增。根据一个月的统计，平均每h到达医院的患者6名，并对各时间段统计，经回归符合泊松分布；该医生每h可诊疗4名，但患者病情不同，分布也不是均匀的，对每位患者就诊时间的统计，经回归，符合指数分布。医院配备有电子回馈信息系统，及时观察到已挂号排队等候的患者数量。当排队等候人数少于5人时，挂号系统可以挂号。当前来就诊的患者挂上号若医生空闲则可直接就诊，否则排队等候。医生采取先到先服务的规则。若前来就诊的患者挂不上号，则立即到邻近的一家医院就诊。经统计，经该主任医师诊疗的患者，其诊疗费、检验费、医药费等医院可获纯收入100元；主任医师可高薪聘请，其薪金及住房和各种福利年均25万元，医院实行每周5天工作制，年工作日250天，平均每天支付1000元的成本。当医生过少，由于患者得不到服务离去而产生的损失增加；当医生过多，由于医生空闲时间的增加也使医院的成本增加。问：医院应招聘多少名肝胆内科主任医师可使得盈利最大？导入案例：主任医师招聘问题此类排队现象在日常生活中经常遇到，如客户到银行排队办理存贷款业务，出纳员为客户提供服务；汽车到加油站排队，加注系统为汽车提供加油服务；超市顾客到收银台前排队，收款员为顾客提供交款服务；旅客到公交车站排队，公交车为旅客提供位移服务。排队论的基本思想是1910年丹麦电话工程师A.K.埃尔朗在解决自动电话设计问题时开始形成的，当时称为话务理论。他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的埃尔朗电话损失率公式。自20世纪初以来，电话系统的设计一直在应用这个公式。20世纪30年代前苏联数学家欣钦把处于统计平衡的电话呼叫流称为最简单流；瑞典数学家巴尔姆又引入有限后效流等概念和定义；美国数学家费勒(W.Feller)关于生灭过程的研究；20世纪50年代初，英国数学家D.G.肯德尔提出嵌入马尔可夫链理论，以及对排队队型的分类方法，为排队论奠定了理论基础；20世纪70年代以来，人们开始研究排队网络和复杂排队问题的渐近解等，成为研究现代排队论的新趋势。本章主要内容11.1基本概念11.1.1排队系统的一般表示11.1.2排队系统的三个特征11.1.3排队系统模型的分类11.1.4排队系统的主要性能指标11.1.5排队系统的输入和输出11.2生死过程11.3单服务台排队系统模型11.3.1M/M/1/∞/∞（标准系统）11.3.2M/M/1/N/∞（系统容量有限）11.3.3M/M/1/∞/m（顾客源有限）11.4多服务台排队系统模型11.4.1M/M/s/∞/∞系统11.4.2M/M/s/N/∞系统11.4.3M/M/s/∞/m系统11.5其他排队系统模型11.5.1一般服务时间M/G/1模型11.5.2定长服务时间M/D/1模型11.5.3埃尔朗服务时间M/Ek/1模型11.5.3具有优先服务权的排队模型11.6排队系统的优化11.6.1M/M/1模型中的最优服务率11.6.2M/M/s模型中的最优服务台数本章小结11.1.1排队系统的一般表示11.1.2排队系统的三个特征排除系统的三个特征是指：输入过程、排队规则、服务机构。1．输入过程输入是指顾客到达服务系统的情况。可能有下列情况，但并不相互排斥：（1）按顾客源总数划分为有限和无限两大类。如工厂需要检修的机器是有限的，准备进京观光旅游的游客是无限的。（2）按顾客到达的人数可以划分为单个到达和成批到达。如到超市购买商品的顾客是单个的，到港国际航班等待安检的旅客是成批的。（3）按顾客到达时间间隔是否固定可以划分为确定型和随机型。如定期运行的班车、班轮、班机是确定的，到加油站加油的汽车是随机的。对随机的顾客到达需要知道单位时间到达的顾客数或时间间隔的概率分布。（4）按接受过服务的顾客对顾客到达数是否有影响，划分为相互独立到达和非相互独立到达。如提供优质服务的餐饮业所产生了大量“回头客”，就属于非相互独立到达。我们只讨论独立到达情况。（5）按顾客相继到达间隔时间的分布及其数字特征是否与时间有关可分为平稳与非平稳的。相继到达的间隔时间分布及其数学期望、方差等数字特征都与时间无关，称为平稳的，否则是非平稳的。一般非平稳情况的数学处理很困难，我们只讨论平稳状况。11.1.2排队系统的三个特征2．排队规则排队规则指到达排队系统的顾客按怎样的规则排队等待。（1）按顾客到达排队系统时发现服务设施已被占用是否离去可分为损失制，等待制和混合制三种。当顾客到达时，所有的服务台均被占用，顾客随即离去，称为损失制（或称即时制、消失制）；当顾客到达时，所有的服务台均被占用，顾客就排队等待，直到接受完服务才离去，称为等待制，例如出故障的机器排队等待维修就是这种情况；介于损失制和等待制之间的是混合制。对于等待制，有下列服务规则：先到先服务（FCFS）、先到后服务（LCFS）、带优先服务权（PR）、随机服务（SIRO）等。在后面研究的问题中均假设采取FCFS服务规则。（2）按队列长度是否有限，可分为队长有限和队长无限两种情况。在限度以内就排队等待，超过一定限度就离去。（3）按排队方式分为单列、多列。对于多列排队的顾客有的可以相互转移，有的则不能（用栏杆等隔开）；有的排队顾客因等候时间过长而离开，有的则不能（如在高速公路行驶的汽车必须坚持到高速出口）。我们所讨论的问题限制在队列间不能相互转移，中途不能退出的情形。11.1.2排队系统的三个特征3．服务机构从机构形式和工作情况来看有以下几种：（1）服务机构可以没有服务员，也可以有一个或多个服务员（服务台、窗口）。如超市的货架可以没有服务员，但交款时可能有多个服务员。（2）多个服务台的情况中，可以是平行排列的（并联），也可以是前后排列的（串联），也可以是混合的。（3）服务方式可以对单个顾客进行，也可成批进行。我们只讨论单个服务情况。（4）服务时间可分为确定型的和随机型的。如旅客列车对乘客的服务是按列车时刻表进行位移服务的，是确定型的；因患者病情不同，医生诊断的时间不是确定的，是随机型的。（5）服务时间的分布总假定是平稳的，即分布的期望值、方差等参数不受时间的影响。SS1S2S3S1S2S3S1S2S1S2S3S4S5(a)单台单队(b)多队多台并联(c)单队多台并联(d)单队多台串联(e)多台混合11.1.3排队系统模型的分类肯德尔（Kendall）于1953年提出了排队服务系统的分类记号：输入/输出/并联的服务站数1971年国际排队符号标准会上肯德尔将上述分类记号扩充到六项，记为：输入/输出/并联的服务站数/系统容量（队长）/系统状态（顾客源数）/服务规则11.1.4排队系统的主要性能指标求解排队问题的目的，是研究排队系统运行的效率，估计服务质量，确定系统参数的最优值，以决定系统结构是否合理、研究设计改进措施等。因此必须确定用以判断系统运行优劣的基本数量指标。1．常用指标（1）队长（Ls）和排队长（Lq）：队长指系统内顾客数，包括正在接受服务的顾客与排队等待服务的顾客数（排队长），即系统中的顾客数=排队等候服务的顾客数+正在接受服务的顾客数（2）逗留时间（Ws）和等待时间（Wq）：逗留时间指顾客在排队服务系统中从进入到服务完毕离去的平均逗留时间；等待时间指顾客排队等待服务的平均等待时间。这对顾客来讲是最关心的，每个顾客希望逗留时间或等待时间越短越好。（3）服务机构工作强度：指服务机构累计的工作时间占全部时间的比例，是衡量服务机构利用效率的指标。即：1服务机构用于服务顾客的时间服务设施总的空闲时间工作强度服务设施总的服务时间服务设施总的服务时间11.1.4排队系统的主要性能指标2．指标间的关系设：λ表示单位时间内顾客的平均到达数，则1/λ表示相邻两个顾客到达的平均间隔时间；μ表示单位时间内被服务完毕离去的平均顾客数，则1/μ表示对每个顾客的平均服务时间；s表示服务系统中并联的服务台数，Pn(t)在时刻t系统中恰好有n个顾客的概率。则有下列关系：,ssLWssLW或,qqLWqqLW或1sqWWsqLL0snnLnP1()qnnsLnsP(Little公式)11.1.5排队系统的输入和输出排队系统的输入和输出是指顾客到达流和服务时间流，它们的分布一般都是非负的随机变量。最常见的是泊松分布、指数分布和埃尔朗分布。然而在研究具体问题时，究竟是服从哪种分布呢？通常抽取到达时间间隔和服务时间样本，统计其分布（经验分布），并按照统计学的方法进行检验（如检验），以确定服从哪种理论分布。为此，我们先介绍常用的泊松分布、指数分布和埃尔朗分布，之后介绍经验分布检验的Excel操作。1.泊松分布（最简单流）2.指数分布3.埃尔朗分布4.经验分布21.最简单流（泊松分布）所谓最简单流，是指在t这段时间内有k个顾客来到服务系统的概率服从泊松（Poisson）分布，故也称为泊松流。即：0.000.020.040.060.080.100.1205101520253035404550λ=15λ=20λ=251.最简单流（泊松分布）最简单流需要满足以下三个条件：（1）平稳性指在一定时间间隔内，来到服务系统有k个顾客的概率仅与这段时间间隔的长短有关，而与这段时间的起始时刻无关；（2）无后效性指在不相交的时间区间内到达的顾客数是相互独立的，或者说在区间[a,a+t]来到k个顾客的概率与时间a之前来到多少个顾客无关；（3）普通性指在足够小的时间区间内只能有一个顾客到达，不可能有两个以上顾客同时到达。1.最简单流（泊松分布）最简单流的一些性质：（1）参数λ代表单位时间内到达顾客的平均数证由于考虑单位时间，取t=1，其数学期望为：（2）在[t,t+Δt]没有顾客到达的概率为1-λΔt+o(Δt)证在时间Δt没有顾客到达的概率为，将右端展开为麦克劳林级数有：当Δt0时，从第3项开始为Δt的高阶无穷小，故结论得证。（3）在[t,t+Δt]内恰好有1个顾客到达的概率为λΔt+o(Δt)证在[t,t+Δt]内恰好有1个顾客到达的概率为，将的麦克劳林级数代入，结论得证。1001(1)!(1)!kkkkkkkPkeekk0()tPte23()()1()...2!3!tttet1()tPtette2．指数分布的服务时间0.002.004.006.008.0010.0012.0014.0016.0000.10.20.30.40.5μ=20μ=25μ=30指数分布的性质3．阶埃尔朗（Erlang）分布0.002.004.006.008.0010.0012.0014.0016.0018.0000.10.20.30.40.5k=1k=2k=4k=6k=204．经验分布例:大连港1979年500吨以上非定期进港航班(数据见下页)(1)统计频数分布(2)检验符合泊松分布吗?1979年大连港非定期500万吨以上货船进港航班第1步:求相关参数.=AVERAGE(B2:M32)求平均值=STDEV(B2:M32)求标准