运筹学：第七章 排队论

第七章排队论第一节排队论的基本概念第二节生灭过程第三节常用的排队模型（M/M/1)第四节其他排队模型及优化第五节Excel在排队系统中的应用案例：电话系统排队问题一、排队论及排队系统在日常生活和工作中，会遭遇到许多排队问题，如在火车站排队买票、在医院排队挂号、排队候诊、在企业的生产过程中半成品等待再加工。进入排队系统的对象被统称为达到的顾客（人或物）；这些顾客进入排队系统的目的被统称为服务；顾客将在排队系统中按照系统的规则进行有形或者无形的排队。第一节排队论的基本概念

一般的排队过程可以这样描述：顾客由顾客源出发，到达服务机构（服务台、服务员）前，按排队规则排队等待接受服务，服务机构按服务规则给顾客服务，顾客接受完服务后就离开。

尽管排队系统是多种多样的，但所有的排队系统都是由输入过程、排队及排队规则、服务机构及服务规则三个基本部分组成的。（1）输入过程：描述顾客来源以及顾客到达排队系统的规律。（数量有限或无限；单个或成批；到达时间是否独立；分布是确定型或随机型，等等）

（2）排队及排队规则：描述顾客排队等待的队列和接受服务的次序。（损失制---排队空间为零的系统，顾客不排队，流失；等待制---顾客排队，按以下规则接受服务；混合制---顾客可排队，可流失。）（3）服务机构及服务规则：指服务机构的服务设施的个数、排列方式及服务方式。（服务台数量；服务台排列；服务方式；服务时间。）

常见的几种排队系统的结构12ss单队-单台系统单队-多台（并联）系统单队-多台（串联）系统1多队-多台（并联）系统多队-多台（混联、网络）系统112s

实例、大学生到学生食堂排队就餐。涉及到的问题和需要解决的问题如下:（1）总共有多少学生要到食堂就餐?（2）目前食堂总共有多少个服务窗口？（3）学生排队就餐是按照什么规则？（4）学生在队列中的平均排队时间？（5）队列中的学生数量满足什么分布？（6）学生的排队等待时间满足什么分布？（7）学生心理上的最大等待时间是多少？（8）要确保只有5％内的学生的等待时间不超过其最大心理等待时间，目前的服务窗口是否够用？（9）如果已知增加一个服务窗口的成本，流失一个学生顾客的损失，现有条件下，设置多少个服务窗口最合算？……1、输入过程的模型输入过程是用来表述顾客到达排队系统的背景及规律；根据顾客来源的数量不同可以分为有限顾客源和无限顾客源；根据顾客达到排队系统的方式的不同可以分为单个到达和成批到达。输入过程中最重要的表述是顾客相继到达时间间隔，Tn表示第n个顾客到达时刻，Xn=Tn-Tn-1表示第n个顾客与其前一个顾客的时间间隔，一般地，假设｛Xn｝是独立的同分布的。二、排队论模型顾客相继到达时间间隔Xn的分布形式主要有以下几种：①定长输入（D）②最简单流输入（M）③埃尔朗输入（Ek）④一般独立输入（G）⑤成批到达的输入2、排队规则的模型排队规则模型主要有三种：①损失制，即顾客到达时，若所有服务台均被占，该顾客就自动消失。（如停车场，某些电话呼叫系统）②等待制，即顾客到达时，若所有服务台均被占，顾客就排队等待服务。（如银行、超市收银台、餐厅等）③混合制，系统排队空间有限制的情形，若限制队长为N，则在顾客到达时的队长小于N

时，顾客就排入队伍；当其等于N时，顾客就离去。（如医院门诊人数）当进行排队时，还存在着不同的排队规则：①先到先服务（FCFS）：如餐厅、收银台大多数排队系统等②后到先服务（LCFS）：如货轮上等待卸船的货物③随机服务（SIRO）：如等待抽检的产品④优先权服务（PS）：如医院的急诊病人或银行的VIP客户3、服务机构的模型在服务设施方面，服务台的个数可以是一个或几个；在其组织形式上，可以是并联的或串联的或循环的；在服务方式上，可以是单个服务的或成批服务的；在服务时间上，是与输入过程相类似的各种分布。

输入过程的模型+排队规则模型+服务机构的模型=排队论模型随机服务系统分类的记号X/Y/n/A/B/C，其中X代表输入模型，Y

代表服务机构模型，n代表服务台的数目，A代表系统容量，B代表顾客源的数量，C代表排队规则。三、排队模型中的主要参数1、队长和排队长：队长是指系统中顾客总数（包括排队等待和正在接受服务的人数），记为N(t)，它的期望值为平均队长，记为L。队长是排队系统中顾客的平均数（期望值），它是正在被服务的顾客和等待接受服务的顾客总数的期望值。反映了排队系统中的一种总规模。排队长是指排队等待的顾客数，记为Nq(t)，其期望值为平均排队长，记为Lq。L=Lq+正在服务的人数2、等待时间和逗留时间：等待时间是指从顾客到达时间算起到他开始接受服务为止的这段时间，记为Tq(t)，它的期望值为平均等待时间，记为Wq。逗留时间是指顾客到达时刻算起到他接受服务完毕为止的这段时间，记为T(t)，它的期望值为平均逗留时间，记为W。一般地有：逗留时间=等待时间+服务时间。3、忙期和闲期：忙期是指服务台连续繁忙的时间，即顾客从到达空闲服务台算起到服务台再次变为空闲时止的这段时间。这是服务台最关心数量指标，它直接关系到服务员的工作强度。闲期是指服务台连续保持空闲的时间长度。显然在排队系统中忙期与闲期是交替出现的。

排队系统优化问题的研究

研究排队系统的目的就是通过对该系统概率规律的研究，实现系统的优化。系统的优化包括最优设计和最优运营问题。前者属于静态问题，它是在输入和服务参数给定的情况下，确定系统的设计参数，以使服务设施达到最大效益或者服务机构实现最为经济。后者属于动态问题，它是指对于一个给定的系统，在系统运行的参数可以随着时间或状态变化的情况下，考虑如何运营使某个目标函数达到最优。总费用=服务费用+等待费用随着服务水平提高，服务费用增加而等待费用减少！

优化：总费用最少！费用总费用服务费用等待费用服务水平0第二节生灭过程

1、马尔可夫过程简介

随机过程：一连串随机事件动态关系的定量描述。排队系统中的顾客总数记为N(t)。这里的N(t)首先它是一个随机变量，当时间变化到t=t1时刻时，N(t1)又是一个新的随机变量了，把这样的随机变量放在一起，记为｛N(t),t≥0｝，就是一个随机过程。

这里t的取值若规定是t0,t1,…,tn…这样离散的时间点，则为离散时间的随机过程；若t的取值是连续的，则为连续时间的随机过程。过程或（系统）在时刻t0所处的状态为已知的条件下，过程在时刻t>t0所处状态的条件分布，与过程在时刻t0之前处的状态无关的特性称为马尔可夫性或无后效性。即：过程“将来”的情况与过程“过去”的情况是无关的。具有马尔可夫性的随机过程称为马尔可夫过程。此随机过程的t的取值若为离散的时间点t0,t1,…,tn…，又称为马尔可夫链。记过程或（系统）在时刻ti所处的状态为u(ti)，马尔可夫的条件即为：P(u(tn+1)|u(t0),u(t1),…,u(tn))=P(u(tn+1)|u(tn))即：系统在tn+1时刻的状态只与系统在tn时刻的状态有关！对于排队系统来说，系统在时刻ti所处的状态u(ti)是指N(tj)=ntj，为方便起见，把离散的时间点t0,t1,…,tn…简化为0,1,…,n…，这样马尔可夫的条件也就变成：P(Nn+1=in+1|N0=i0,N1=i1,…,Nn=in)=P(Nn+1=in+1|Nn=in)。进一步假设，对所有状态，若P(Nn+1=j|Nn=i)与t无关，可记P(Nn+1=j|Nn=i)=Pij，为马尔可夫链的状态转移概率，同时由于假设了转移概率与t无关，又可称为平稳的马尔可夫链。记马尔可夫链的初始状态概率为qi=P(N0=i)若把马尔可夫链的所有状态记为1,2,…,s，则q=(q1,…,qs)为马尔可夫链的初始状态概率分布。状态转移概率可用矩阵表示为：现在将矩阵P作幂运算，对于Pn来说，其第i行第j列元素记为Pij(n)，则Pij(n)=P(Nn=j|No=i)表示从初始状态的i，通过一步步转移，到第n步转移成了状态j。Pij满足：1、0≤pij≤12、Σpij=1，对j求和例7.1（饮料的市场份额）假设某种饮料在某市场只有有两个品牌A可口可乐、B百事可乐在竞争。假定状态1为顾客最近一次选购了A品牌，状态2为顾客最近一次选择了B品牌。每一次的选择其状态转移概率不变，为如下状态转移矩阵（1）当已知顾客初始选择了A品牌，此后的第三次再选购饮料时选择B品牌的概率；（2）若初始两个品牌的选择概率为（0.5，0.5），则三次转移后两个品牌的选择概率。解：所以当已知顾客初始选择了A品牌，此后的第三次再选购饮料时选择B品牌的概率0.35。当初始两个品牌的选择概率（市场占有率）为（0.5，0.5）时，即（q1，q2）=（0.5，0.5），三次转移后的选择概率（市场占有率）为：不断重复计算，可得出市场占有率将会近似为（0.6,0.4），此即为稳定状态下的市场占有率。稳定状态下的市场占有率二、生灭过程的模型定义：设｛N(t),t≥0｝为一个随机过程，并且满足：当N(t)=n时，从时刻t到下一个顾客到达的时间间隔服从参数为λn的负指数分布；从时刻t到下一个顾客离开的时间间隔服从参数为μn的负指数分布；同一时刻只有一个顾客到达或离开。则称｛N(t),t≥0｝为一个生灭过程。记Pn(t)=P(N(t)=n)。即时刻t顾客为n人的概率在负指数分布中可以假定：从[t,t+⊿t]内，有一个顾客到达的概率为λn⊿t+o(⊿t)，有一个顾客离开的概率为μn⊿t+o(⊿t)，多于一个顾客达到或离开的概率为o(⊿t)。在时刻t+⊿t时，N（t+⊿t）=n的概率用状态转移来理解，可以表述为如下表达式：Pn(t+⊿t)=Pn-1(t)*(λn-1⊿t+o(⊿t))+Pn+1(t)*(μn⊿t+o(⊿t))+Pn(t)*(λn⊿t+o(⊿t))*(μn⊿t+o(⊿t))+Pn(t)*(1-λn⊿t+o(⊿t))*(1-μn⊿t+o(⊿t))整理后可得：Pn(t+⊿t)-Pn(t)=[Pn-1(t)*λn-1+Pn+1(t)*μn

–Pn(t)*λn-Pn(t)*μn]⊿t+o(⊿t))假定生灭过程是一个平稳过程，即系统达到平稳时，Pn(t)与t无关，或者说P’n(t)=0，此时记Pn(t)为pn。化简整理：Pn(t+⊿t)-Pn(t)=[Pn-1(t)*λn-1+Pn+1(t)*μn

-Pn(t)*λn-Pn(t)*μn]⊿t+o(⊿t))两边除⊿t，并令其趋于0，得：pn-1*λn-1+pn+1*μn=pn*λn+pn*μn

pn-1*λn-1+pn+1*μn=pn*λn+pn*μn

记

则求解结果可以描述为：

第三节常用的排队模型

一、M/M/1模型M/M/1模型也就是M/M/1/∞/∞/FCFS，是指顾客到达的时间间隔服从参数为λ的负指数分布；服务时间服从参数为μ的负指数分布；只有一个服务台；并且首先假定系统空间是无限的；顾客源是无限的；排队规则是先来先服务。这也是排队系统中最简单的情况！λn=λ，μn=μ，稳态概率为：

令：

得：当0<ρ<1时M/M/1模型有稳态概率

；当ρ≥1时，等比级数不收敛，排队系统不存在稳定状态。定理（Little公式）：对于处于稳定状态的排队系统，下列公式成立：定理（Little公式）：对于处于稳定状态的排队系统，下列公式成立：利用Little公式，可以轻松地计算出排队系统的时间参数。例7.2（M/M/1模型）某医院急症室晚上有一个医生值班，病人的到达时间间隔服从负指数分布，平均每小时来2个病人，医生治疗病人的时间也服从负指数分布，平均治疗时间20分钟（即平均每小时治疗3个病人）。计算急症室平均人数，以及病人的平均等待时间和平均逗留时间，医生空闲的概率。解：由题意可知，此为M/M/1模型，λ=2，μ=3，ρ=λ/μ=2/3<1，模型能收敛。医生空闲的概率：P0=1-ρ=1/3急诊室里有n个病人的概率：

急诊室里的平均队长和排队长：

病人的平均等待时间和平均逗留时间：。二、M/M/1/K模型（空间容量为K）在M/M/1/K模型中，依然可以令μn=μ，但对于到达的情况则需分为两种情况讨论：

同样令

则稳态概率

可解得：

由于系统空间为K有限，因此当系统人数达到K时就不会再有人到达，λ就不再是真正的平均达到率，引进实际平均达到率λe，λe=λ*(1-pK)+0*pK=λ*(1-pK)例7.3某理发店只有1个理发师，店内共有6个座位，顾客到达间隔时间服从负指数分布，平均每小时来20个潜在顾客，当座位满的时候，顾客则不再进店直接离开；理发师为一个顾客理发平均需要15分钟，理发时间也服从负指数分布。求：各项平均指标；理发师空闲的概率；顾客流失的概率。例7.3，解：由题意可知，此为M/M/1/6模型，λ=20，μ=4，ρ=5>1。理发师空闲概率：稳态概率：

其中顾客流失概率为：

平均队长：平均排队长：

λe=λ*(1-pK)=20*0.2=4

三、M/M/s模型M/M/s排队模型中的s是指排队系统中服务台的个数。假设顾客到达率保持稳定λn=λ，每个服务台的服务率也都是μ，但对整个系统而言，μn与系统中的顾客数有关,即：例7.4某银行有3个服务窗口，顾客到达时间间隔服从负指数分布，平均到达率为9人/小时，每个窗口的服务时间服从负指数分布，平均服务率为4人/小时，3个窗口共享一个队列。求这个排队系统的相关指标。例7.4，解：由题意可知，λ=9，μ=4，s=3,ρ=9/4=2.25，ρs=2.25/3=0.75<1整个系统空闲概率：

平均排队长：

平均排队时间：

平均逗留时间：

平均队长：

顾客到达时必须排队的概率：

当有多个服务台并且系统空间有限时，也即M/M/s/K模型时，假设系统空间没满时顾客到达率保持稳定的λ，每个服务台的服务率也都是μ。但对整个系统而言：这里的λe=λ(1-pK)，是指有效到达率表面上看来公式的推导与结果都比前几个模型要复杂。其实在实际运用中，当s和K都不是太大时，可以把所有情况都列出来，也就是把N的分布列具体地表述出来，这样所有的平均指标直接从分布列中就可以简单计算得到。例7.5有一个汽车修理厂，有2个修理台和2个修理师，另有2个等待车位，当4个位置都满了，前来修理的车只能离开修理厂，待修汽车的到达是M流，平均每小时来一辆，修理时间服从负指数分布，平均修理1个小时，求：（1）这个排队系统的各个主要指标；（2）客户的损失率；（3）修理师都空闲的概率和至少有一个修理师空闲的概率。例7.5，解：由题意可知，此为M/M/2/4模型，λ=1，μ=1，ρ=1从分布列中得客户的损失率为：pK=1/23；修理师都空闲的概率为p0=8/23，至少有一个修理师空闲概率为：p0+p1=16/23N的数学期望L=26/23；Nq的数学期望Lq=4/23；由于有损失，有效到达率λe=λ(1-pK)=22/23；N01234Nq00012Pn8/238/234/232/231/23第四节其他排队模型及优化

一、顾客源有限排队模型有时排队系统中顾客源数量很少比如车间里一个维修工负责修理发生了故障的机器，机器一共就m台，机器发生故障相当于顾客到达，然后排队等待维修工修理，在等待过程中，继续正常工作的机器少了，单位时间内有机器发生故障的机会就少了。此类模型记为M/M/s/m/m模型，不能简单套用上节介绍的模型。到达率，假设每个顾客的到达率都是相同的，记为λ，那么λn=λ(m-n)，其中0<n<m，服务率例7.6某车间有5台机器，每台机器的故障间隔时间服从负指数分布，平均间隔时间为1个小时，发生故障后，等待修理，每次的修理时间也服从负指数分布，平均为15分钟，试计算此排队系统的相关指标。解：由题意可知，此模型为M/M/1/5/5模型，λ=1，μ=4，ρ=1/4N的数学期望L=1.7963；Nq的数学期望Lq=0.9953；有效到达率λe=λ(m-L)=3.2037；根据Little公式：N012345Nq001234Pn0.19910.24880.24880.18660.09330.0233二、M/G/1排队模型M/G/1排队模型是指顾客的到达是M流，单个服务台，但是和前面讨论的所有排队模型都不一样的是，服务时间不再是负指数分布。对于服务时间只是假定其服从一般的分布，并假定服务时间的均值为1/μ，方差为σ2，依旧假定ρ=λ/μ，称为服务强度。辛钦-波拉采克公式（Pollaczek-Khintchine公式）：其它相关的结论：例7.7（M/D/1模型）生产线最后一道工序是自动完成的，其服务时间是一个固定值0.5min，半成品达到这道工序的时间间隔依然是负指数分布，平均1分钟到达1个，排队空间可以认为无限，试计算此排队系统的各项平均指标。例7.7解：由题意可知此排队系统是M/D/1模型，λ=1，μ=2，ρ=1/2，由于服务时间是定长分布，所以σ2=0，根据辛钦-波拉采克公式，