运筹学完整排队论ppt课件

.,第十四章排队论QueuingTheory,基本概念（掌握）输入过程和服务时间分布（掌握）泊松到达、负指数服务排队模型（掌握）其他模型（了解）排队系统的优化目标与最优化问题（了解）,本章内容重点,排队是我们日常生活和生产中经常遇到的现象。例如，上、下班搭乘公共汽车；顾客到商店购买物品；病员到医院看病；旅客到售票处购买车票；学生去食堂就餐等就常常出现排队和等待现象。除了上述有形的排队之外，还有大量的所谓“无形”排队现象，如几个顾客打电话到出租汽车站要求派车，如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待，他们分散在不同地方，却形成了一个无形队列在等待派车。排队的不一定是人，也可以是物：,前言,例如，通讯卫星与地面若干待传递的信息；生产线上的原料、半成品等待加工；因故障停止运转的机器等待工人修理；码头的船只等待装卸货物；要降落的飞机因跑道不空而在空中盘旋等等。,前言,面对拥挤现象，人们总是希望尽量设法减少排队，通常的做法是增加服务设施。但是增加的数量越多，人力、物力的支出就越大，甚至会出现空闲浪费，如果服务设施太少，顾客排队等待的时间就会很长，这样对顾客会带来不良影响。,前言,于是，顾客排队时间的长短与服务设施规模的大小，就构成了随机服务系统中的一对矛盾。如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是随机服务系统理论排队论所要研究解决的问题。,排队论是1909年由丹麦工程师爱尔朗(A.KErlang)在研究电活系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。,前言,排队论(QueuingTheory)，又称随机服务系统理论(RandomServiceSystemTheory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。,前言,显然，上述各种问题虽互不相同，但却都有要求得到某种服务的人或物和提供服务的人或机构。排队论里把要求服务的对象统称为“顾客”,而把提供服务的人或机构称为“服务台”或“服务员”。不同的顾客与服务组成了各式各样的服务系统。,前言,图1单服务台排队系统,前言,顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图1至图5。,图2单队列S个服务台并联的排队系统,图3S个队列S个服务台的并联排队系统,前言,图4单队多个服务台的串联排队系统,图5多队多服务台混联、网络系统,前言,图6-6随机服务系统,前言,一般的排队系统，都可由下面图6加以描述。,通常称由图6表示的系统为一随机聚散服务系统，任一排队系统都是一个随机聚散服务系统。这里，“聚”表示顾客的到达，“散”表示顾客的离去。所谓随机性则是排队系统的一个普遍特点，是指顾客的到达情况(如相继到达时间间隔)与每个顾客接受服务的时间往往是事先无法确切知道的，或者说是随机的）。一般来说，排队论所研究的排队系统中，顾客到来的时刻和服务台提供服务的时间长短都是随机的，因此这样的服务系统被称为随机服务系统。,前言,1.基本概念,一排队系统的描述（一）系统特征和基本排队过程实际的排队系统虽然千差万别，但是它们有以下的共同特征：(1)有请求服务的人或物顾客；(2)有为顾客服务的人或物，即服务员或服务台；,(3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员(台)又空闲无事。,任何一个排队问题的基本排队过程都可以用图6表示。从图6可知，每个顾客由顾客源按一定方式到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开。,1.基本概念,（二）排队系统的基本组成部分通常，排队系统都有输入过程、服务规则和服务台等3个组成部分：1输入过程这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流一般可以从3个方面来描述个输入过程。(1)顾客总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。,1.基本概念,(2)顾客到达方式。这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。,1.基本概念,(3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。,2.服务规则。这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。(1)损失制。这是指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。,1.基本概念,(2)等待制。这是指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。等待制中，服务台在选择顾客进行服务时，常有如下四种规则：先到先服务。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。后到先服务。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。,1.基本概念,随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。优先权服务。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。,1.基本概念,(3)混合制这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种：队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。,1.基本概念,等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店用餐。,1.基本概念,逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。不难注意到，损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，则当K=s时，混合制即成为损失制；当K=时，混合制即成为等待制。,1.基本概念,3服务台情况。服务台可以从以下3方面来描述：(1)服务台数量及构成形式。从数量上说，服务台有单服务台和多服务台之分。从构成形式上看，服务台有：单队单服务台式；单队多服务台并联式；多队多服务台并联式；单队多服务台串联式；单队多服务台并串联混合式,以及多队多服务台并串联混合式等等。见前面图1至图5所示。,1.基本概念,(2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3)服务时间的分布。一般来说，在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔良分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。,1.基本概念,（三）排队系统的描述符号与分类为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，可给出很多排队模型。为了方便对众多模型的描述，肯道尔（DGKendall）提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式：A/B/C/D/E/F各符号的意义为：,1.基本概念,A表示顾客相继到达间隔时间分布，常用下列符号：M表示到达过程为泊松过程或负指数分布；D表示定长输入；Ek表示k阶爱尔朗分布；G表示一般相互独立的随机分布。B表示服务时间分布，所用符号与表示顾客到达间隔时间分布相同。M表示服务过程为泊松过程或负指数分布；D表示定长分布；Ek表示k阶爱尔朗分布；G表示一般相互独立的随机分布。,1.基本概念,C表示服务台(员)个数：“1”则表示单个服务台，“s”。(s1)表示多个服务台。D表示系统中顾客容量限额，或称等待空间容量；如系统有K个等待位子，则0K10%，所以不符合要求。,当c=4时，系统中正好有4位顾客的概率为因9.52%10%，所以设置四个电话较合适。此时，电话系统里的平均顾客数为,这种形式的更一般形式为M/G/c/N/，这个一般形式和M/G/c/c/的区别在于一般形式允许排队，但排队长度不超过（Nc）。,8顾客来源有限制的排队模型,以上所介绍的排队系统都是顾客来源无限制的情况，这一节我们将介绍顾客来源有限制的情况。从M/M/1/m这个记号中我们可以知道这个排队模型的顾客的总数为有限数m。M/M/1/m条件：单位时间顾客平均到达数单位平均服务顾客数,数量指标公式:1、系统中无顾客的概率2、平均排队的顾客数3、系统中的平均顾客数Ls=Lq+(1-p0)4、顾客在排队上的平均花费等待时间Wq=Lq/（m-Ls),5、系统在中顾客的平均逗留时间Ws=Wq+1/6、系统中有n个顾客的概率,n=0,1,2,m,例4.某车间有5台机器，每台机器连续运转时间服从负指数分布，平均连续运转时间为15分钟，有一个修理工，每次修理时间服从负指数分布，平均每次12分钟，假设一个机器停一个小时损失1000元,而一个机修工及其设备运行1小时费用为350元.求该排队系统的数量指标P0，Lq，Ls，Wq，Ws，以及P5；并用“管理运筹学”软件进行经济分析，问安排多少个修理工可使公司的运行最经济？,解：这是一个M/M/1/5系统。其中，m=5,=1/15,=1/12,/=0.8Lq=2.766;Ls=3.759；Wq=33.43;Ws=45.43；P5=0.2870。可见修理工几乎没有空闲时间，机器排队的时间过长。应提高服务率或增加服务台数目。,=0.0073,例4:某车站候车室在某段时间旅客到达服从泊松流分布，平均速度为50人/h，每位旅客在候车室内停留的时间服从负指数分布，平均停留时间为0.5h，问候车室内平均人数为多少？（L),应用举例,解：把旅客停留在候车室看做服务，于是系统为M/M/=50=1/0.5=2,4.排队系统的优化目标与最优化问题,以完全消除排队现象为研究目标是不现实的，那会造成服务人员和设施的严重浪费，但是设施的不足和低水平的服务，又将引起太多的等待，从而导致生产和社会性损失。从经济角度考虑，排队系统的费用应该包含以下两个方面：一个是服务费用，它是服务水平的递增函数；另一个是顾客等待的机会损失(费用)，它是服务水平的递减函数。两者的总和呈一条U形曲线。,4.排队系统的优化目标与最优化问题,系统最优化的目标就是寻求上述合成费用曲线的最小点。在这种意义下，排队系统的最优化问题通常分为两类：一类称之系统的静态最优设计，目的在于使设备达到最大效益，或者说，在保证一定服务质量指标的前题下，要求机构最为经济；另一类叫作系统动态最优运营，是指一个给定排队系统，如何运营可使某个目标函数得到最优。归纳起来，排队系统常见的优化问题在于：,4.排队系统的优化目标与最优化问题,(1)确定最优服务率*；(2)确定最佳服务台数量c*；(3)选择最为合适的服务规则；(4)或是确定上述几个量的最优组合。研究排队系统的根本目的在于以最少的设备得到最大的效益，或者说，在一定的服务质量的指标下要求机构最为经济。排队系统的最优化问题分为两大类：,4.排队系统的优化目标与最优化问题,系统的静态最优设计问题和系统的动态最优控制问题。