第九章排队论1资料.ppt

第9章 排队论,南京航空航天大学,排队是我们在日常生活中经常遇到的现象，例如病人到医院看病、客户到银行汇款、城市拥堵路段的汽车排队、占线等排队现象产生的原因之一是要求服务的数量超过了服务机构的容量，也就是有部分的服务对象不能立即得到服务；原因之二是系统服务对象到达和服务时间均存在随机性前者可以通过增加服务机构的容量来解决排队现象，但无休止地增加服务机构的容量会导致追加投资并可能发生系统资源长时间闲置后者，也就是系统服务对象到达和服务时间均存在随机性，致使无法准确预测估算排队拥堵的具体情况所以，在服务系统中的排队现象几乎不可避免9.1排队论的基本概念,排队论是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使服务机构的费用最经济或某些指标最优9.1.1排队过程的一般表示,排队系统示意图,一般的排队系统有三个基本组成部分： 输入过程 排队及排队规则 服务机构,输入过程,主要包括： 顾客相继到达系统的时间间隔 顾客到达系统的方式（顾客可能单个到达，也可能成批到达） 顾客源情况,输入过程说明顾客按怎样的规律到达服务系统的。

它可用一定时间内顾客到达的数量或前后两个顾客相继到达的间隔时间来描述按照一定时间内顾客到达数量或前后两个顾客相继到达的间隔时间类型的不同，输入过程可以划分为确定型和随机型两种：如在自动装配线上装配的各部件就必须是按确定时间间隔到达装配点，定期的航班、长途客车等都是确定型的；顾客到商店购买商品、到医院就诊的病人等都是随机型的在排队论中，讨论的输入过程主要是随机型的 随机型的输入是指在时间t内顾客到达数量n(t)服从一定的概率分布如服从泊松分布，则在时间t内到达n个顾客的概率为： 或相继到达的顾客的间隔时间T服从负指数分布，即：,式中λ为单位时间顾客期望到达数量，称为平均到达率；1/λ为平均间隔时间排队论的系统输入还要关注顾客源是有限集还是无限集如工厂内待修的机器数显然是有限集，而到某航空售票处购票的顾客源则可以认为是无限的 顾客的到达可以是相互独立的，也就是说，以前的到达情况对以后顾客的到达没有影响，否则就是有关联的如工厂内的机器在一个短的时间区间内出现故障（顾客到达）的概率就受已经待修或被修理机器数目的影响我们主要讨论的是相互独立的情形 输入过程可以是平稳的，或称为对时间是齐次的，是指描述相继到达的时间间隔分布和所含参数（如期望、方差）都是与时间无关的，否则成为非平稳的。

我们主要讨论的是平稳的情形排队及排队规则,（1）排队 排队规则是指顾客来到排队系统后如何排队等候服务的规则，一般有即时制、等待制和混合制三大类其中即时制(损失制)是指当顾客到达时，如果所有服务台都已被占用，顾客可以随即离开系统等待制指顾客到达系统时，所有服务台被占用，顾客就加入排队队列等待服务而混合制是即时制和等待制相结合的一种排队服务规则混合制主要分为两种情况：一是队长有限制的情况，即当顾客排队等侯服务的人数超过规定数量（等待空间有限）时，后来的顾客就自动离开，另求服务；二是排队等侯时间有限制的情况，即当顾客排队等候超过一定时间就会自动离开，不能再等2）排队规则 最常见的等待制排队规则是： 先到先服务FCFS：即按到达次序接受服务，这是最常见的情形 后到先服务LCFS：如仓库中存放的货物常常是后放入的先被出库使用 具有优先权的服务PS：如医院对病情严重的病人予以优先治疗，公交车上对老年人予以优先上车就坐等 随机服务SIRO：指服务员从等待的顾客中随机地选取其中一个进行服务而不管到达的先后如交换台接通呼唤的服务机构,排队系统的服务机构主要包含： 服务员（服务设施）数量及其连接形式（并联或串联） 顾客是单个接受服务还是成批接受服务 服务时间的分布,各类型排队系统,,服务台的服务时间一般也分成确定型和随机型两种。

例如，自动冲洗汽车的装置对每辆汽车冲洗（服务）时间是相同的，因而是确定型的但大多数情况下服务时间是随机型的，对于随机型的服务时间，我们需要知道服务时间V的概率分布如果服务时间V服从负指数分布，则其分布函数是 式中μ为平均服务率，1/μ为平均服务时间9.1.2排队系统的分类,Kendall符号的形式X/Y/Z各符号的含义如下： X指顾客相继到达间隔时间的分布 Y为服务时间的分布 Z为并列的服务台数目,表示相继到达的间隔时间和服务时间分布符号常用以下符号表示 M：负指数分布，表示每个顾客接受服务的时间相互独立，具有相同的负指数分布； 负指数分布描述的随机现象对于过去的事件具有无记忆性，即Markov性，因此用Markov开头字母M表示； D：定长分布，表示每个顾客接受服务的时间是一个确定的常数；,,Ek：k阶爱尔朗分布〔Erlang)，表示每个顾客接受服务的时间服从k阶爱尔朗分布，其密度函数为 当k=1时爱尔朗分布就是负指数分布；当k增加时，爱尔朗分布逐渐变为对称的当k30时，爱尔朗分布近似于正态分布G：一般随机分布 例如M/M/l表示到达的间隔时间服从负指数分布，服务时间也服从负指数分布的单服务台排队系统模型。

M/D/2表示到达间隔时间服从负指数分布，而服务时间为定长分布的双服务台排队系统模型1971年有关排队论符号的标准化会议将Kendall符号扩展为X/Y/Z/A/B/C，其中A指排队系统的容量，取非负整数或∞；B表示顾客源的数目，取非负整数或∞；C表示服务规则（先来先服务FCFS、后来先服务LCFS，具有优先权的服务PS，随机服务SIRO等） 如M/M/1/ ∞ / ∞ / FCFS:表示顾客到达的时间间隔服从负指数分布、服务时间服从负指数分布、单服务台、系统容量为无限、顾客源为无限、排队规则为先来先服务的排队模型我们这一章的模型只讨论先到先服务的情形，因此后面都略去第六项9.1.3排队系统的衡量指标,构建了排队系统的模型后，需要对排队系统的运行效率和服务质量进行研究和评估，以确定系统的结构是否合理任何排队系统开始运行时，其状态在很大程度上取决于系统的初始状态和运转的时间但系统运行了一段时间后，系统将进入稳定状态（即稳态，系统运行充分长时间后，初始状态的影响基本消失，系统状态不再随时间变化）对排队系统进行分析主要是指对其稳定状态的运行效率指标进行分析 常用于分析排队系统效率的有以下指标：,平均队长Ls和平均排队长Lq 平均逗留时间ws和平均等待时间wq 忙期和闲期 服务强度ρ,（1）平均队长Ls和平均排队长Lq。

平均队长Ls指一个排队系统的顾客平均数（其中包括正在接受服务的顾客）而平均排队长Lq则是指系统中等待服务的顾客平均数； （2）平均逗留时间ws和平均等待时间wq平均逗留时间ws指进入系统的顾客逗留时间的平均值（包括接受服务的时间），而平均等待时间wq则是指进入系统的顾客等待时间的平均值；,（3）忙期和闲期忙期是指服务机构两次空闲的时间间隔，这是一个随机变量，是服务员最关心的指标，因为它关系到服务员的服务强度；与忙期相对的是闲期，它是服务机构连续保持空闲的时间在排队系统中，忙期和闲期总是交替出现的 （4）服务强度ρ每个服务台单位时间内平均服务时间 其中Ls、Lq、ws和wq通常称之为重要的运行指标它们取值越小，说明系统队长越短，顾客等候时间越少，因此系统的性能就越好 我们在稳态下，讨论单服务台排队系统和多服务台排队系统9.2单服务台排队系统分析,本节讨论输入过程为泊松流，服务时间服从负指数分布的单服务台的排队系统其中有： 标准的M/M/1/∞/∞系统； 有限等待空间系统M/M/1/N/∞； 顾客为有限源系统M/M/1/∞/m9.2.1 标准的M/M/1/∞/∞系统,M/M/1系统状态转移图:,系统状态从0转移到l的转移率为λP0，而系统状态从1转移到0的转移率为μP1。

因此对状态0而言，必须满足以下平衡方程：,对系统的任何状态n 1，系统状态从n转移到n+1和n-1的转移率为λPn+μPn，而系统状态从n+1和n-1转移到n的转移率为μPn+1+λPn-1由平衡条件可得：,令 可解得,在 ρ1的条件下，标准M/M/l系统的重要运行指 标如下： (1)在平衡条件 下系统中顾客数为n 的概率Pn 由于 ，所以 故,(2)系统在平稳状态下的平均队长(包括等待和接受服务的顾客数)Ls为：,或,(3)系统在平稳状态下平均排队长(系统排队等待的顾客数) Lq为 平均排队人数等于系统的平均人数减去平均的正在接受服务的人数： 或,设每个顾客在系统中平均逗留时间为Ws顾客在系统中逗留的时间T服从参数为μ-λ的负指数分布，即顾客在系统中逗留时间超过t的概率为: 因此顾客在系统中平均逗留时间为：,或,每个顾客在系统中平均等待时间为Wq，平均等待时间为顾客在系统中平均逗留时间减去平均服务时间：,或,例.假设某高铁售票处仅一台自助售票机，买票的人随机到来，且服从泊松分布，平均为每小时20人如果售票的服务时间平均每人需0.5分钟，售票机前会排多长的队？如果平均服务时间为1.0分钟或者2.0分钟，情况会怎样？顾客平均在系统中花费多少时间？,9.2.2有限等待空间系统M/M/1/N/∞,对M/M/1/N/∞来说，系统状态是有限集合，即 : M/M/1/N/∞排队系统的状态转移图如下：,,在稳态条件下，可得如下状态平衡方程：,得,由于 所以,由此可以计算系统的有关运行指标： (1)平均队长Ls 当 时,当等候空间有限、且ρ1时，真正进入服务系统的顾客平均输入率小于顾客平均到达率λ的有效到达率为 。

由于系统容量为N，所以 故 1-P0 =,（2）平均排队长 （3）平均逗留时间 （4）平均等候时间,例.单人理发馆有4个椅子供人们排队等待理发当4个椅子都坐满时，后来的顾客就自动离开若顾客按泊松流到达，平均间隔时间20分钟，顾客理发时间服从负指数分布，平均理发时间为15分钟试求任一顾客的平均等待时间等相关参数9.2.3顾客为有限源系M/M/1/∞/m,该排队系统平均到达率随系统状态的变化而变化该排队系统的状态转移图如下：,系统的状态平衡方程为： 得,因为 ，所以并不要求 所以,由此可推导出系统的各项运行指标: （1）平均顾客数Ls （2）平均排队长Lq,,（3）平均逗留时间,（4）平均等待时间,例.某车间共有6台车床，每台车床的连续运转时间服从负指数分布，平均连续运转时间60分钟车间有一名负责维修人员，该工人每次修理时间服从负指数分布，平均每次维修时间为6分钟试计算以下问题: （1）工人空闲的概率； （2）6台机床都出故障的概率； （3）出故障的平均机床数； （4）等待修理的平均机床数， 〔5〕平均停工的时间； （6）平均等待修理的时间； （7）机床设备利用率。

9.3多服务台排队系统分析,对于多服务台排队系统，本节假定： （1）N个完全相同的服务台并联工作； （2）只有一队顾客； （3）顾客随机到达；,（4）随机的服务时间长度； （5）服务规则为“先到先服务”； （6）系统可以达到稳定状态； （7）对于队列中的顾客数量没有限制； （8）对于接受服务的顾客数量没有限制； （9）所有到来的顾客都等待服务9.3.1标准M/M/c/∞/∞系统,顾客的平均到达率为常数λ，每个服务台的平均服务率均为μ，同时规定各服务台的工作是相互独立的就整个服务机构而言，平均服务率与系统状态有关，即： 同时要求系统的服务强度（服务机构的平均利用率） ,这样系统不会排成无限队列M/M/c系统的状态转移如图：,由图可得：,用递推法求解上述差分方程，可得状态概率：,系统的其它运行指标计算如下：,（1）平均排队长和平均队长： （2）平均等待和逗留时间,例.某邮局有3个窗。