第五部分排队论

第五部分第五部分 排队论排队论特征特征:v 有请求服务的人或物，我们统称它们为有请求服务的人或物，我们统称它们为“顾客顾客”。v有为顾客服务的人或物，我们叫它们为有为顾客服务的人或物，我们叫它们为“服务员服务员”或或“服务台服务台”。服务系统是由顾客和服务员组成。服务系统是由顾客和服务员组成的。的。v顾客在随机的时刻，一个（批）一个（批）地来顾客在随机的时刻，一个（批）一个（批）地来到服务系统。每位顾客需要的服务时间不一定是确到服务系统。每位顾客需要的服务时间不一定是确定的。服务过程的随机性造成某个阶段顾客排队长，定的。服务过程的随机性造成某个阶段顾客排队长，而某些时候服务员又闲聊无事。而某些时候服务员又闲聊无事。研究内容研究内容:v性态问题。研究各种排队系统的概率规律性。主性态问题。研究各种排队系统的概率规律性。主要是研究队长分布，等待时间分布和忙期分布等，要是研究队长分布，等待时间分布和忙期分布等，包括瞬态和稳态两种情形。包括瞬态和稳态两种情形。v最优化问题。最优化又分静态最优和动态最优，最优化问题。最优化又分静态最优和动态最优，前者指最优设计；后者指现有排队系统的最优运营。前者指最优设计；后者指现有排队系统的最优运营。v排队系统的统计推断，即判断一个给定的排队系排队系统的统计推断，即判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行分析研统符合于哪种模型，以便根据排队理论进行分析研究。究。第十三章第十三章 排队论的基本知识排队论的基本知识 1 排队系统的组成排队系统的组成 顾客源顾客源顾客到达顾客到达按一定排队规则按一定排队规则形成的等待线形成的等待线服务规则服务规则服服务务机机构构顾客顾客离去离去排队系统排队系统图图13-1 排队系统排队系统输入过程输入过程 v顾客源的组成，可能是有限的，如工厂待修理的机顾客源的组成，可能是有限的，如工厂待修理的机器；可能是无限，如某一商店的顾客流可以看成是无器；可能是无限，如某一商店的顾客流可以看成是无限的。限的。v 顾客到达的方式，可能是单个到达，也可能是成顾客到达的方式，可能是单个到达，也可能是成批到达。例如，到餐厅就餐就有单个到达的顾客和受批到达。例如，到餐厅就餐就有单个到达的顾客和受邀请来参加宴会的成批顾客。邀请来参加宴会的成批顾客。v顾客相继到达的间隔时间顾客相继到达的间隔时间T可以是确定的，即定长可以是确定的，即定长输入，每隔一段固定时间到达一个顾客。在排队论中输入，每隔一段固定时间到达一个顾客。在排队论中主要讨论的输入过程是随机型的。主要讨论的输入过程是随机型的。v 顾客到达可以是相互独立的，即在某一时刻以前顾客到达可以是相互独立的，即在某一时刻以前顾客的到达情况，不影响该时刻后顾客的到达，否则顾客的到达情况，不影响该时刻后顾客的到达，否则就是有关联的。就是有关联的。v 输入过程可以是平稳的，或称对时间齐次的。是输入过程可以是平稳的，或称对时间齐次的。是指描述相继到达的间隔分布和所含参数（如期望值，指描述相继到达的间隔分布和所含参数（如期望值，方差等）都是与时间无关的。否则称为非平稳。对非方差等）都是与时间无关的。否则称为非平稳。对非平稳的过程数学处理很复杂。平稳的过程数学处理很复杂。排队规则排队规则 v服务系统的分类服务系统的分类损失制损失制：即顾客到达此服务系统时，若服务员都：即顾客到达此服务系统时，若服务员都不空闲，则顾客离去，另求服务。不空闲，则顾客离去，另求服务。等待制等待制：顾客到达本系统时，服务员都在为先到：顾客到达本系统时，服务员都在为先到的顾客服务（即不空），则顾客排队等待服务，的顾客服务（即不空），则顾客排队等待服务，一直等到有空的服务员为他服务为止。一直等到有空的服务员为他服务为止。混合制混合制：在现实生活中，很多服务系统介于损失：在现实生活中，很多服务系统介于损失制和等待制之间，称为混合制系统。制和等待制之间，称为混合制系统。当顾客到达时，服务员不空，且排队位置满座，当顾客到达时，服务员不空，且排队位置满座，顾客离去，这是排队长度有限的服务系统；顾客离去，这是排队长度有限的服务系统；混合制的另一种情形，是顾客到达时，服务员不混合制的另一种情形，是顾客到达时，服务员不空，它就排队等待服务，当顾客等了一段时间后，空，它就排队等待服务，当顾客等了一段时间后，仍轮不到为他服务，顾客离开排队队列，另求服仍轮不到为他服务，顾客离开排队队列，另求服务。这叫排队时间有限的服务系统。务。这叫排队时间有限的服务系统。v服务规则服务规则先到先服务先到先服务后到先服务后到先服务随机服务随机服务有优先权的服务有优先权的服务v队列的数目队列的数目单队列单队列多队列多队列 服务机构服务机构 v服务员的个数及结构服务员的个数及结构单个服务台、单队列单个服务台、单队列 输入输入队列队列服务台服务台输出输出多个服务台并列、单队列（多队列）多个服务台并列、单队列（多队列）输入输入队列队列台台1台台2台台K单队：单队：多队：多队：输入输入队列队列台台台台队列队列多服务台串列多服务台串列 输入输入队列队列输出输出多服务台混合多服务台混合 输入输入队列队列v服务方式服务方式对单个顾客进行对单个顾客进行对成批顾客进行对成批顾客进行 v对顾客的服务时间对顾客的服务时间确定型确定型随机型随机型 2 排队模型的符号表示排队模型的符号表示 特征中最主要、影响最大的因素：特征中最主要、影响最大的因素：v 顾客相继到达的间隔时间顾客相继到达的间隔时间v 服务时间的概率分布服务时间的概率分布v 服务员的个数服务员的个数v 系统内顾客的容量，即排队系统内的顾客数系统内顾客的容量，即排队系统内的顾客数古典的排队模型：古典的排队模型：A/B/n/mA表示顾客相继到达间隔时间的分布表示顾客相继到达间隔时间的分布B表示服务时间的概率分布表示服务时间的概率分布n表示服务员的数目表示服务员的数目m表示顾客排队允许的长度或系统内顾客表示顾客排队允许的长度或系统内顾客的容量，的容量，0m+表示相继到达间隔时间和服务时间的各种分表示相继到达间隔时间和服务时间的各种分布的符号是：布的符号是：M负指数分布（负指数分布（M是是Markov的字头，因为负的字头，因为负指分布具有无记忆性，即指分布具有无记忆性，即Markov性）。性）。D确定型（确定型（Deterministic）EkK阶爱尔朗（阶爱尔朗（Erlang）分布。分布。GI一般相互独立（一般相互独立（General Independent）的随机分布。的随机分布。G一般（一般（General）随机分布。随机分布。3 服务系统的这行指标服务系统的这行指标 v 单位时间内到达的顾客数约的期望值，记作单位时间内到达的顾客数约的期望值，记作，即即为单位时间内的平均到达率。为单位时间内的平均到达率。v单位时间内服务的顾客数的期望值，记作单位时间内服务的顾客数的期望值，记作，即为即为单位时间内的平均服务率。单位时间内的平均服务率。v 系统内的顾客数叫队长，其期望值记作系统内的顾客数叫队长，其期望值记作Ls（Length System）。）。或叫平均队长。或叫平均队长。v 系统内排队等待的顾客数，叫队列长，它的期望值系统内排队等待的顾客数，叫队列长，它的期望值记作记作Lq（Length Queue）或叫平均队列长。或叫平均队列长。v顾客在系统逗留时间的期望值，记作顾客在系统逗留时间的期望值，记作Ws或算平均或算平均逗留时间。逗留时间。v 顾客在系统中排队等待时间的期望值，记作顾客在系统中排队等待时间的期望值，记作Wq或或算平均等待时间。由此看到顾客的平均逗留时间等于算平均等待时间。由此看到顾客的平均逗留时间等于平均等待时间加上平均服务时间，即：平均等待时间加上平均服务时间，即：Ws=Wq+平均服务时间平均服务时间 v忙期（忙期（Busy Period）：）：服务员在二次空闲之间连服务员在二次空闲之间连续工作的时间长度，它的期望值记作续工作的时间长度，它的期望值记作 （忙期的平均（忙期的平均长度）。长度）。v闲期（闲期（Idle Period）：）：服务员在二次工作之间连续服务员在二次工作之间连续空闲的时间长度，它的期望值记作空闲的时间长度，它的期望值记作 （闲期的平均长（闲期的平均长度）度）Ls、Lq、Ws、Wq是是顾客所关心的数量指标，而最关顾客所关心的数量指标，而最关心的是等待时间心的是等待时间Wq希望不太长。希望不太长。Ls、Lq同时也为系统的设计者设计排队场地提供依据。同时也为系统的设计者设计排队场地提供依据。是服务员关心的指标，它关系到服务员的工是服务员关心的指标，它关系到服务员的工作强度，同时忙期及一个忙期中平均完成服务顾客作强度，同时忙期及一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标。数都是衡量服务机构效率的指标。4 排队系统的常见分布排队系统的常见分布泊松（泊松（Poisson）分布分布 泊松流又叫简单流，它具有如下性质：泊松流又叫简单流，它具有如下性质：v平稳性平稳性 在时间轴在时间轴ot上，任意给定一个时间上，任意给定一个时间t0，在在（t+t）时间内，到达时间内，到达k个顾客的概率与起始时刻个顾客的概率与起始时刻t无关，而只与无关，而只与t和和k的大小有关。记此概率为：的大小有关。记此概率为：v无后效性无后效性 在时间轴在时间轴ot上，互不相交的时间区段上，互不相交的时间区段t1、t2内，内，到达的顾客数是相互独立的。换句话说，每个顾客来到达的顾客数是相互独立的。换句话说，每个顾客来到系统的时刻互不相关。到系统的时刻互不相关。v普通性普通性 即在充分小的间隔时间即在充分小的间隔时间t内，有两个或两个以上顾内，有两个或两个以上顾客来到系统的概率（客来到系统的概率（t）极小，以改可以忽略不计。极小，以改可以忽略不计。即：即：普通性表示在单位时间内顾客是一个一个地到达系普通性表示在单位时间内顾客是一个一个地到达系统，而不是成批到达。统，而不是成批到达。v有限性有限性 即在任意有限的时间区间内，到达有限个顾客的概即在任意有限的时间区间内，到达有限个顾客的概率为率为1。即：。即：同时具备以上四个性质的流，称做最简单流。同时具备以上四个性质的流，称做最简单流。负指数分布负指数分布 v当输入过程是泊松流时，我们研究两顾客相继到当输入过程是泊松流时，我们研究两顾客相继到达的间隔时间达的间隔时间T（也是随机变量）的概率分布。也是随机变量）的概率分布。定理定理 若顾客到达形成参数为若顾客到达形成参数为的泊松流，则两顾客的泊松流，则两顾客相继到达的间隔时间相继到达的间隔时间T服从参数为服从参数为的负指数分布。的负指数分布。即即T的分布函数：的分布函数：（t0）分布密度：分布密度：（t0）表示单位时间内平均到达的顾客数，故表示单位时间内平均到达的顾客数，故1/就表示就表示相继顾客到达的平均间隔时间。相继顾客到达的平均间隔时间。v服务时间服务时间v的分布。对一个顾客的服务时间也就是在的分布。对一个顾客的服务时间也就是在忙期中相继离开系统的两顾客的间隔时间。忙期中相继离开系统的两顾客的间隔时间。表示单位时间能被服务完的顾客数（期望值），称表示单位时间能被服务完的顾客数（期望值），称为平均服务率。为平均服务率。1/1/表示一个顾客的平均服务时间。表示一个顾客的平均服务时间。v服务强度服务强度，我们知道，我们知道，为平均到达率；为平均到达率；为平为平均服务率。均服务率。有着重要的意义：有着重要的意义：1，说明单位时间内顾客来到系统的平均数说明单位时间内顾客来到系统的平均数，大大于单位时间内顾客平均服务数于单位时间内顾客平均服务数。所以，所以，1的等待制的等待制系统一般不属地讨论之到。系统一般不属地讨论之到。=1，即即=。这时系统服务率为这时系统服务率为100%；或者说，；或者说，当一个顾客正在接受服务的时候，平均也只有一个顾客当一个顾客正在接受服务的时候，平均也只有一个顾客来到系统。来到系统。在等待制系统中我们讨论的有关运行指标主要是在在等待制系统中我们讨论的有关运行指标主要是在1的情况。的情况。第十四章第十四章 排队系统的分析排队系统的分析 对随机型排队系统，在给定的输入和服务的条件，我对随机型排队系统，在给定的输入和服务的条件，我们主要是研究系统的运行指标：们主要是研究系统的运行指标：系统中的顾客数（即队长）的期望值系统中的顾客数（即队长）的期望值Ls；在系统内排队等待的顾客数（即队列长）的期望值在系统内排队等待的顾客数（即队列长）的期望值Lq；顾客在系统内逗留时间的期望值顾客在系统内逗留时间的期望值Ws；顾客在系统内排队等待时间的期望值顾客在系统内排队等待时间的期望值Wq。而计算上述数量指标的基础是系统的状态概率而计算上述数量指标的基础是系统的状态概率Pn（t），），即：即：Pn（t）=P任一时刻任一时刻t，系统的状态系统的状态=n所谓系统的状态即为系统中的顾客数。所谓系统的状态即为系统中的顾客数。显然，在单服务台的情形下：显然，在单服务台的情形下：状态状态n1，即为繁忙。即为繁忙。状态状态n=0，即为空闲。即为空闲。若繁忙的概率大，则若繁忙的概率大，则Ls、Lq、Ws、Wq一般较一般较大，反之则较小。大，反之则较小。1 单服务台的单服务台的M/M/1模型模型 M/M/1模型即指输入过程服从泊松流，即顾客相继到模型即指输入过程服从泊松流，即顾客相继到达间隔时间服从负指数分布，服务时间从负指数分布，达间隔时间服从负指数分布，服务时间从负指数分布，单服务台的情况。单服务台的情况。若用符号表示，则为：若用符号表示，则为：M/M/1/M/M/1/N M/M/1/m/N （mN）其符号含义：其符号含义：M/M/1/顾客源顾客顾客源顾客总数总数/最大队长最大队长 M/M/1/M/M/1/模型模型 M/M/1/，又称为标准的又称为标准的M/M/1模型，是符合下列模型，是符合下列条件的排队系统：条件的排队系统：v输入过程：输入过程：顾客源是无限的，顾客单个到来，相互顾客源是无限的，顾客单个到来，相互独立，顾客相继到达的间隔时间服从参数为独立，顾客相继到达的间隔时间服从参数为的负指的负指数分布。数分布。v 排队规则：排队规则：单队，且队长没有限制，先到先服务。单队，且队长没有限制，先到先服务。v服务机构：服务机构：单服务台，各顾客的服务时间是相互独单服务台，各顾客的服务时间是相互独立的，服从相同的负指数分布。立的，服从相同的负指数分布。v 系统的状态概率：系统的状态概率：n0 （3）有：有：系统的繁忙（系统的繁忙（Busy）与空闲（与空闲（Idle）（1）系统处在空闲状态的概率：）系统处在空闲状态的概率：系统处在繁忙状态即系统处于忙期的概率：系统处在繁忙状态即系统处于忙期的概率：（2）在繁忙状态条件下）在繁忙状态条件下 队列中顾客平均数队列中顾客平均数 顾客平均等待时间：顾客平均等待时间：o 忙期（忙期（Pmry Period）：）：指服务台由空闲状态因顾指服务台由空闲状态因顾客到来而开始忙碌到再度空闲为止的时间长度。客到来而开始忙碌到再度空闲为止的时间长度。o和闲期（和闲期（Idle Period）：）：闲期指由原有的顾客都被服闲期指由原有的顾客都被服务完了的时刻开始到下一个顾客到来为止的时间长度。务完了的时刻开始到下一个顾客到来为止的时间长度。各忙期的平均长度为：各忙期的平均长度为：一个忙期所服务的顾客平均数为：一个忙期所服务的顾客平均数为：二、二、M/M/1/NM/M/1/N模型模型 由于系统中排队等待的顾客数最多为由于系统中排队等待的顾客数最多为N-1，在某在某一时刻一顾客到达时，如果系统中已有一时刻一顾客到达时，如果系统中已有N个顾客，那个顾客，那么该顾客就被拒绝进行系统。么该顾客就被拒绝进行系统。N=1 N=1时，为损失制系统；时，为损失制系统；NN时，为等待制系时，为等待制系统，即统，即M/M/1/M/M/1/情形；情形；11NN时，为混合制系时，为混合制系统。这里讨论后一种情形，即统。这里讨论后一种情形，即N N为有限数的情形。为有限数的情形。1系统的状态概率：系统的状态概率：1 nN 2系统的主要运行指标系统的主要运行指标 1（系统中的平均顾客数）系统中的平均顾客数）（在队列中等待的平均顾客数）（在队列中等待的平均顾客数）（3）单位时间内损失顾客的平均数）单位时间内损失顾客的平均数PN，因为损失因为损失率为率为PN。（4）有效到达率）有效到达率e，因为平均到达率因为平均到达率是指系统是指系统中顾客数不以中顾客数不以N（即系统有空）时的平均到达率，当即系统有空）时的平均到达率，当系统已满即系统已满即n=N，则到达率为则到达率为0，故要求出有效到达，故要求出有效到达到到e。（顾客逗留时间的期望值）（顾客逗留时间的期望值）（顾客等待时间的期望值）（顾客等待时间的期望值）它们之间的关系：它们之间的关系：例：单人理发馆有六个椅子接待人们排队等待理发，例：单人理发馆有六个椅子接待人们排队等待理发，当当6个椅子都坐满时，后来到的顾客不进店就离开。个椅子都坐满时，后来到的顾客不进店就离开。顾客平均到达率顾客平均到达率3人人/小时，理发需时平均小时，理发需时平均15分钟。分钟。则则N=7为系统中最大的顾客数，为系统中最大的顾客数，=3人人/小时，小时，=4人人/小时小时 解：（解：（1）求某顾客一到达就能理发的概率。）求某顾客一到达就能理发的概率。这种情形相当于理发馆内没有顾客，所求概率：这种情形相当于理发馆内没有顾客，所求概率：（2）求需要等待的顾客数的期望值。）求需要等待的顾客数的期望值。Lq=Ls-(1-P0)=2.11-(1-0.2778)=1.39（3）求有效到达率）求有效到达率e e=（1-P1-P0 0）=4=4（1-0.27781-0.2778）=2.89=2.89人人/小时小时 （4）求一顾客在理发馆内逗留的期望时间）求一顾客在理发馆内逗留的期望时间Ws=Ls/e=2.11/2.89=0.73小时小时=43.8分钟分钟（5）在可能到来的顾客中有百分之几不等待离开？）在可能到来的顾客中有百分之几不等待离开？这就是求系统中有这就是求系统中有7个顾客的概率：个顾客的概率：这也是理发馆的损失率。这也是理发馆的损失率。