运筹学 第十章 排队论.pptx
《运筹学 第十章 排队论.pptx》由会员分享,可在线阅读,更多相关《运筹学 第十章 排队论.pptx(87页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、排排队论引言生灭过程和Poisson过程M/M/s等待制排队模型第1页/共87页第一节 引言一、排队系统的特征及排队论排队论(Queuing Theory),又称随机服务系统理论(Random Service System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说,它是在研究各种排队系统概率规律性的基础上,解决相应排队系统的最优设计和最优控制问题。第2页/共87页排队是我们在日常生活和生产中经常遇到的现象。例如,上、下班搭乘公共汽车;顾客到商店购买物品;病员到医院看病;旅客到售票处购买车票;学生去食堂就餐等就常常出现排队和等待现象。除了上述有形的排队之外,还有大量的所谓
2、“无形”排队现象,如几个顾客打电话到出租汽车站要求派车,如果出租汽车站无足够车辆、则部分顾客只得在各自的要车处等待,他们分散在不同地方,却形成了一个无形队列在等待派车。排队的不一定是人,也可以是物:第3页/共87页例如,通讯卫星与地面若干待传递的信息;生产线上的原料、半成品等待加工;因故障停止运转的机器等待工人修理;码头的船只等待装卸货物;要降落的飞机因跑道不空而在空中盘旋等等。显然,上述各种问题虽互不相同,但却都有要求得到某种服务的人或物和提供服务的人或机构。第4页/共87页排队论里把要求服务的对象统称为“顾客”,而把提供服务的人或机构称为“服务员”或“服务机构”。实际的排队系统可以千差万别
3、,但都可以一般地描述如下:顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待,则加入等待队伍,待获得服务后离开系统,见图10-1至10-4第5页/共87页图10-1 单服务台排队系统图10-2 单队列S个服务台并联的排队系统第6页/共87页图10-3 S个队列S个服务台的并联排队系统图10-4 单队多个服务台的串联排队系统第7页/共87页类似地还可画出许多其他形式的排队系统,如串并混联的系统,网络排队系统等第8页/共87页尽管各种排队系统的具体形式不同,但都可以由图10-5加以描述图10-5 随机服务系统通常称上图表示的系统为一随机聚散服务系统,任一排队系统都是一个随机聚散服务
4、系统。这里,“聚”表示顾客的到达,“散”表示顾客的离去。第9页/共87页所谓随机性则是排队系统的一个普遍特点,是指顾客的到达情况(如相继到达时间间隔)与每个顾客接受服务的时间往往是事先无法确切知道的,或者说是随机的。一般来说,排队论所研究的排队系统中,顾客到来的时刻和服务台提供服务的时间长短都是随机的,因此这样的服务系统被称为随机服务系统第10页/共87页小结排排队系系统又称随机服又称随机服务系系统有有请求服求服务的人或物;的人或物;有有为顾客服客服务的人或物;的人或物;顾客到达客到达时间与接受服与接受服务时间是随机的。是随机的。结构:构:顾客到达客到达-排排队-服服务机构服机构服务-顾客离去
5、客离去第11页/共87页二、排队系统的描述实际中的排队系统各有不同,但概括起来都由三个基本部分组成:1输入入过程;程;2排排队及排及排队规则3服服务机制机制第12页/共87页1输入过程这是指要求服务的顾客是按怎样的规律到达排队系统的过程,有时也把它称为顾客流一般可以从3个方面来描述一个输入过程。(1)顾客总体数又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的,也可以是无限的。例如,到售票处购票的顾客总数可以认为是无限的,而车间内停机待修得机器显然是有限的。第13页/共87页(2)顾客到达方式这是描述顾客是怎样来到系统的,他们是单个到达,还是成批到达。病人到医院看病是顾客单个到达的例子。
6、在库存问题中如将生产器材进货或产品入库看作是顾客,那么这种顾客则是成批到达的。第14页/共87页(3)顾客流的概率分布,或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时,首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。第15页/共87页2排队及排队规则排队排队分为有限排有限排队和无限排无限排队两类。有限排有限排队是指排队系统中的顾客数是有限的,即系统的空间是有限的,当系统被被占满时,后面再来的顾客将不能进入系统;无限排无限排队是指系统中顾客数可以是
7、无限的,队列可以排到无限长,顾客到达系统后均可进入系统排队或接受服务,这类系统又称为等待制排队系统。第16页/共87页有限排有限排队系系统损失制排队系统混合制排队系统(排队空间为0的系统)(允许排队,但又不允许队列无限长)第17页/共87页这是指如果顾客到达排队系统时,所有服务台都已被先来的顾客占用,那么他们就自动离开系统永不再来。典型例子是,如电话拔号后出现忙音,顾客不愿等待而自动挂断电话,如要再打,就需重新拔号,这种服务规则即为损失制。损失制排失制排队系系统(排队空间为0的系统)第18页/共87页混合制排混合制排队系系统这是等待制与损失制相结合的一种服务规则,一般是指允许排队,但又不允许队
8、列无限长下去。具体说来,大致有三种:队长有限。当排队等待服务的顾客人数超过规定数量时,后来的顾客就自动离去,另求服务,即系统的等待空间是有限的。如旅馆的床位是有限的。等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T,当等待时间超过T 时,顾客将自动离去,并不再回来。如顾客到饭馆就餐,等了一定时间后不愿再等而自动离去另找饭店用餐。(允许排队,但又不允许队列无限长)第19页/共87页 逗留时间(等待时间与服务时间之和)有限。例如用高射炮射击敌机,当敌机飞越高射炮射击有效区域的时间为t 时,若在这个时间内未被击落,也就不可能再被击落了。不难注意到,损失制和等待制可看成是混合制的特殊情形,
9、如记s为系统中服务台的个数,则当K=s时,混合制即成为损失制;当K=时,混合制即成为等待制。(K为系统中可容纳的顾客数)第20页/共87页(2)排队规则当顾客到达时,若所有服务台都被占用且又允许排队,则该顾客将进入队列等待。例如,排队等待售票,故障设备等待维修等。服务台对顾客进行服务所遵循的规则通常有:先到先服务(FCFS)后到先服务(LCFS)优先权(PS)随机服务仓库中迭放的钢材,后迭放上去的都先被领走,就属于这种情况。即当服务台空闲时,不按照排队序列而随意指定某个顾客去接受服务,如电话交换台接通呼叫电话就是一例。第21页/共87页3服务机制排队系统的服务机制可以从以下3方面来描述:服务台
10、数量及构成形式。从数量上说,服务台有单服务台和多服务台之分。从构成形式上看,服务台有:单队单服务台式;单队多服务台并联式;多队多服务台并联式;单队多服务台串联式;单队多服务台并串联混合式 以及多队多服务台并串联混合式等等。第22页/共87页(2)服务方式。这是指在某一时刻接受服务的顾客数,它有单个服务和成批服务两种。如公共汽车一次就可装载一批乘客就属于成批服务。(3)服务时间的分布一般来说,在多数情况下,对每一个顾客的服务时间是一随机变量,其概率分布有定长分布、负指数分布、K阶爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。第23页/共87页三、排队系统的符号表示肯道尔()分类
11、:X/Y/Z/A/B/C 其中:X 顾客到达的分布;Y 服务时间的分布;Z 服务台数;A 系统容量;B 顾客源的个体数。C 服务规则表示分布的符号:M-负指数分布或泊松输入;D-定长分布;Ek-k阶爱尔朗分布;GI-一般独立随机分布;G-一般随机分布 第24页/共87页例如:某排队问题为MMSFCFS,则表示顾客到达间隔时间为负指数分布(泊松流);服务时间为负指数分布;有s(s1)个服务台;系统等待空间容量无限(等待制);顾客源无限,采用先到先服务规则。某些情况下,排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明则均理解为系统等待空间容量无限;顾客源无限,先到先服务,单个服务的
12、等待制系统第25页/共87页四、排队系统的主要数量指标评价排价排队系系统的的优劣。劣。下面给出的这些数量指标一般都是和系统运行的时刻有关的随机变量,求这些随机变量的瞬时分布一般是很困难的。为了分析上的简便,并注意到相当一部分排队系统在运行了一定时间后,都会趋于一个平衡状态(或称平稳状态)。在平衡状态下,队长的分布、等待时间的分布和忙期的分布都和系统所处的时刻无关,而且系统的初始状态的影响也会消失。因此,我们在本章中将主要讨论与系统所处时刻无关的性质,即统计平衡性质。第26页/共87页1、队长与排与排队长(1)队长:系统中的顾客数(n);N(t)-N-L (2)排排队长:系统中排队等待服务的顾客
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 第十章 排队论 第十 排队
限制150内