排队论 本章内容重点 √基本概念 输入过程和服务时间分布 √洎松輪入——指教服务排队模型 √其他模型选介 √排队糸统的优化目标与最优化问题
排队论 本章内容重点 ✓基本概念 ✓输入过程和服务时间分布 ✓泊松输入——指数服务排队模型 ✓其他模型选介 ✓排队系统的优化目标与最优化问题
排队论 排队论( Queuing Theory),又称随机服务糸统理论 ( Random Service System Theory),是一门研究拥挤现象(排 队、等待)的科学。具体地说,它是在研究各种排队糸统概 率规律性的基础上,解决相应排队糸统的录优设计和录优 控制问题。排队问题的共同特征: 有要求得到某种服务的人或物。排队论里把要求服务 的对象统称为“顾客” √有提供服务的人或机构。把提供服务的人或机构称为 服务台”或“服务员” 顾客的到达、服务的肘间至少有一个是随机的,服从 某种分布
排队论(Queuing Theory)，又称随机服务系统理论 (Random Service System Theory)，是一门研究拥挤现象(排 队、等待)的科学。具体地说，它是在研究各种排队系统概 率规律性的基础上，解决相应排队系统的最优设计和最优 控制问题。排队问题的共同特征: ✓ 有要求得到某种服务的人或物。排队论里把要求服务 的对象统称为“顾客” ✓ 有提供服务的人或机构。把提供服务的人或机构称为 “服务台”或“服务员” ✓ 顾客的到达、服务的时间至少有一个是随机的，服从 某种分布。 排队论
排队论 不同的顾容与服务组成了各式各样的服务糸统。顾客 为了得到某种服务而到达糸统、若不能立即获得服务而又 允许排队等待,则加入等待队伍,待获得服务后离开糸统, 见图1至图5。 顾客到达 服务完成后离去 O…,服务台 正在接受服务的顾客 图1单服务台排队亲统 O服务台服务完成后离去 顾客到达队列 服务完成舌离去 O服务台2 服务完成后离去 O服务台 图2单队列—S个服务台并联的排队糸统
不同的顾客与服务组成了各式各样的服务系统。顾客 为了得到某种服务而到达系统、若不能立即获得服务而又 允许排队等待，则加入等待队伍，待获得服务后离开系统， 见图1至图5。 图1 单服务台排队系统 图2 单队列——S个服务台并联的排队系统 排队论
排队论 队列1 服务完成后离去 …………○。服务台 到达(→⊙队3.。厘务台一厘务完防后离去 队列 …O○服务台 服务完成后离去 图3S个队列—S个服务台的养联排队糸统 顾客到达 队列 ○服务台 队列 ○………○O服务台2服务完成后离去 图4单队——多个服务台的串联排队糸统 顾客到达 队列1 …○服务台 服务台 务台K十服务台 服务完成后离去 服务台 顾客到达,队列2 ◆O…○|服务台 服务台 图5多队——多服务台混联、网络糸统
图3 S个队列——S个服务台的并联排队系统 图4 单队——多个服务台的串联排队系统 图5 多队——多服务台混联、网络系统 排队论
排队论 面对拥挤现象,顾客排队附间的长经与服务设施规模 的大小,就构成了设计随机服务糸统中的一对矛盾。 如何做到既保证一定的服务质量指标,又使服务设施 费用经济合狸,恰当地解决顾客排队肘间与服务设施费用 大小这对矛盾,这就是排队论所要研究解决的问题之一。 排队论是1909年由丹麦工程师爱尔朗( A K Erlang)在研 究电活糸统肘创立的,几十年来排队论的应用领城越亲越 广泛,理论也日渐完暮。特别是旬二十世纪60年代以来, 由于计算机的飞速发畏,更为排队论的应用开拓了宽阉的 前景
排队论 面对拥挤现象，顾客排队时间的长短与服务设施规模 的大小，就构成了设计随机服务系统中的一对矛盾。 如何做到既保证一定的服务质量指标，又使服务设施 费用经济合理，恰当地解决顾客排队时间与服务设施费用 大小这对矛盾，这就是排队论所要研究解决的问题之一。 排队论是1909年由丹麦工程师爱尔朗(A.K.Erlang)在研 究电活系统时创立的，几十年来排队论的应用领域越来越 广泛，理论也日渐完善。特别是自二十世纪60年代以来， 由于计算机的飞速发展，更为排队论的应用开拓了宽阔的 前景
排队系统的描述 一、糸统特征和基本排队过程 任何一个排队问题的基本排队过程都可以用图6表示。从 图6可知,每个顾容由顾容憑按一定方式到达服务糸统,首 先加入队列排队等待接受服务,然后服务台按一定规则从 队列中选择顾客进行服务,获得服务的顾客立即离开。 受F 顾客到达 顾客源 服务规则 队列 顾客离开 (输入) 服务机构 (输出) 随机服务系统 图6随机服务糸统
排队系统的描述 一 、系统特征和基本排队过程 任何一个排队问题的基本排队过程都可以用图6表示。从 图6可知，每个顾客由顾客源按一定方式到达服务系统，首 先加入队列排队等待接受服务，然后服务台按一定规则从 队列中选择顾客进行服务，获得服务的顾客立即离开。 图6 随机服务系统
排队系统的描述 、排队糸统的基本组成部分 1.輪入过程:这是指要求服务的顾客是按怎样的规律到达 排队糸统的过程,有肘也把它称为顾客流、一般可以从3个 方面来描述一个输入过程。 (1)顾容恿体数(又称顾容源、輪入源)。这是指顾客的来 源。顾客可以是有限的,也可以是无限的。 (2)顾客到达方式。描述顾容是怎样来到糸统的,他们是 草个到达,还是成批到达。 (3)顾客流的概率分布,或称相继顾客到达间间隔的分 布。这是求解排队糸统有关运行指标问题肘,首先需要确定 的指标。也可以狸解为在一定的肘间间隔内到达K个顾客 (K=1、2、…)的概率是多大。顾客流的概率分布一般有定长 分布、三项分布、洎松流(最简单流)、爱尔朗分布等
排队系统的描述 二、排队系统的基本组成部分 1.输入过程:这是指要求服务的顾客是按怎样的规律到达 排队系统的过程，有时也把它称为顾客流．一般可以从3个 方面来描述一个输入过程。 (1) 顾客总体数(又称顾客源、输入源)。这是指顾客的来 源。顾客源可以是有限的，也可以是无限的。 (2)顾客到达方式。描述顾客是怎样来到系统的，他们是 单个到达，还是成批到达。 (3)顾客流的概率分布，或称相继顾客到达时间间隔的分 布。这是求解排队系统有关运行指标问题时，首先需要确定 的指标。也可以理解为在一定的时间间隔内到达K个顾客 (K=1、2、…)的概率是多大。顾客流的概率分布一般有定长 分布、二项分布、泊松流(最简单流)、爱尔朗分布等
排队系统的描述 三、排队糸统的基本组成部分 2.服务规则。这是指服务台从队列中选取顾客进行服务 的顺序。一般可以分为损失制、等待制和混合制等3大类。 (1)损失制。如果顾客到达排队糸统肘,所有服务台都已 被占用,那么他们就自动离开糸统永不再来。 (2)等待制。当顾客来到糸统时,所有服务台都不空,顾 客加入排队行列等待服务。等待制中,服务台在选择顾客进 行服务时,常有如下四种规则: 1)先到先服务。捩顾客到达的先后顺序对顾客进行服务, 这是最普遍的情形。 2)后到先服务。仓库中迭放的钢材,后迭放上去的都先 被领走,就属于这种情况
排队系统的描述 二、排队系统的基本组成部分 2.服务规则。这是指服务台从队列中选取顾客进行服务 的顺序。一般可以分为损失制、等待制和混合制等3大类。 (1)损失制。如果顾客到达排队系统时，所有服务台都已 被占用，那么他们就自动离开系统永不再来。 (2)等待制。当顾客来到系统时，所有服务台都不空，顾 客加入排队行列等待服务。等待制中，服务台在选择顾客进 行服务时，常有如下四种规则： 1)先到先服务。按顾客到达的先后顺序对顾客进行服务， 这是最普遍的情形。 2)后到先服务。仓库中迭放的钢材，后迭放上去的都先 被领走，就属于这种情况
排队系统的描述 3)随机服务。即当服务台空闼附,不按照排队序列 而随意指定某个顾容去接受服务,如电话交换台接通呼叫 电话就是一例。 4)优先权服务。如老人、儿童先进车站;危重病员 先就诊;遇到重要教据需要处理计算机立即中断其他数据 的处狸等,均属于此种服务规则。 (3)妮合制。等待制与损制相结合的一种服务规则, 一般是指允许排队,但又不允许队列无限长下去。具体说 来,大致有三种: 1)队长有限。当排队等待服务的顾客人数超过规定 数量附,后来的顾客就自动离去,另求服务,即無统的等 待空间是有限的
排队系统的描述 3)随机服务。即当服务台空闲时，不按照排队序列 而随意指定某个顾客去接受服务，如电话交换台接通呼叫 电话就是一例。 4)优先权服务。如老人、儿童先进车站；危重病员 先就诊；遇到重要数据需要处理计算机立即中断其他数据 的处理等，均属于此种服务规则。 (3)混合制。等待制与损失制相结合的一种服务规则， 一般是指允许排队，但又不允许队列无限长下去。具体说 来，大致有三种： 1)队长有限。当排队等待服务的顾客人数超过规定 数量时，后来的顾客就自动离去，另求服务，即系统的等 待空间是有限的
排队系统的描述 2)等待肘间有限。顾容在糸统中的等待肘问不超过某 一给定的长度T,当等待肘间超过T时,顾客将自动离去 开不再回来。如易损坏的电子元器件的存问题,超过 定存储肘间的元罻件被自动认为失效。又如顾容到饭馆就 餐,等了一定附间后不愿再等而自动离去另找饭店。 3)逗留肘间有限。例如用高射炮射击敌机,当敌机飞 越高射炮射击有效区城的附间为t时,若在这个时间内朱被 击落,也就不可能再被击落了。 损失制和等待制可看成是混合制的特殊情形,如记S 为糸统中服务台的个教,無统的容量为K,则当K=S时,混 合制即成为损头制;当K=∞时,泥合制即成为等待制
排队系统的描述 2)等待时间有限。顾客在系统中的等待时间不超过某 一给定的长度T，当等待时间超过T时，顾客将自动离去， 并不再回来。如易损坏的电子元器件的库存问题，超过一 定存储时间的元器件被自动认为失效。又如顾客到饭馆就 餐，等了一定时间后不愿再等而自动离去另找饭店。 3) 逗留时间有限。例如用高射炮射击敌机，当敌机飞 越高射炮射击有效区域的时间为t时，若在这个时间内未被 击落，也就不可能再被击落了。 损失制和等待制可看成是混合制的特殊情形，如记s 为系统中服务台的个数，系统的容量为K，则当K=s时，混 合制即成为损失制；当K=∞时，混合制即成为等待制