1、排排 队队 论论 方方 法法 讲讲 解解简单讲解排队论方法讲解服务系统服务系统被服务者（顾客）服务设施|排队排队日常生活常见的一种现象日常生活常见的一种现象共同特点：在一个排队系统中，进入系共同特点：在一个排队系统中，进入系统的顾客不能立即得到服务，出现了排统的顾客不能立即得到服务，出现了排队现象。队现象。如：医院病人，商店柜台顾客，如：医院病人，商店柜台顾客，公交车乘客公交车乘客由于被服务者到达系统的时间不确定，由于被服务者到达系统的时间不确定，故故“排队论排队论”又称为又称为“随机服务系统理随机服务系统理论论”无形的排队：网络用户，租车方顾客无形的排队：网络用户，租车方顾客排队主体是物：生
2、产线产品，维修工排队主体是物：生产线产品，维修工待修机器，卫星信息，跑道飞机待修机器，卫星信息，跑道飞机排队论方法讲解离开系统（输出）接受服务等候服务进入排队系统（输入）排队系统1. 基本概念基本概念1.排队过程的一般模型排队过程的一般模型顾客服务过程分为顾客服务过程分为四个步骤四个步骤：顾客接受服务后立即离开系统，因此输出顾客接受服务后立即离开系统，因此输出过程可以不用考虑过程可以不用考虑输入过程输入过程排队规则排队规则服务机构服务机构输出过程输出过程排队论方法讲解IV.顾客到达相互关系顾客到达相互关系输入过程：输入过程：I.顾客总体顾客总体（顾客源）（顾客源）II.顾客到来方式顾客到来方式
3、III.顾客到达时间间隔顾客到达时间间隔V.时间间隔分布时间间隔分布有限有限无限无限一个一个一个一个一批一批一批一批确定型确定型随机型随机型相互独立相互独立相互关联相互关联与时间无关（平稳）与时间无关（平稳）与时间有关（非平稳）与时间有关（非平稳）排队论方法讲解III. 队列数队列数 排队规则：排队规则：I. 排队方式排队方式等待制：等待制：II. 形状形状先到先服，先到先服，后到先服，后到先服，随机服务，随机服务，有优先权服务有优先权服务损失制损失制等待制等待制混合制混合制有形有形无形无形容量有限容量有限容量无限容量无限单列单列多列多列可以互相转移可以互相转移不能互相转移不能互相转移即时制即
4、时制排队论方法讲解V. 服务时间分布服务时间分布服务机构服务机构I. 服务台数目服务台数目II. 服务台形式服务台形式III. 服务方式服务方式IV. 服务时间服务时间一个一个多个多个并联并联串联串联一个一个一个一个一批一批一批一批确定型确定型随机型随机型平稳平稳非平稳非平稳排队论方法讲解如如 D/M/10/1000/ / F1.2 排队论模型的标准形式排队论模型的标准形式标准形式：标准形式：X/Y/Z/A/B/C相继到达时间间隔相继到达时间间隔服务时间的分布服务时间的分布服务台个数服务台个数系统容量限制系统容量限制顾客源数目顾客源数目服务规则服务规则其中其中M负指数分布负指数分布D确定型分布
5、确定型分布EkGI一般相互独立的时间间隔分布一般相互独立的时间间隔分布k阶爱尔朗分布阶爱尔朗分布G一般服务时间的分布一般服务时间的分布X：Y：Z：A：B： C：FCFS：先到先服：先到先服LCFS：后到先服后到先服排队论方法讲解Q：相对通过能力：相对通过能力:请求服务的顾客数A1.3 排队系统的运行指标排队系统的运行指标 Ls：队长队长 Lq：排队长排队长 Ln：正在接受服务的顾客数正在接受服务的顾客数 Ls=Lq+Ln Ws： 逗留时间逗留时间 Wq：排队时间，排队时间，服务时间服务时间Ws=Wq+ Tb：忙期服务机构连续工作时间长度忙期服务机构连续工作时间长度 P损损：损失率，顾客被拒绝服
6、务而使服损失率，顾客被拒绝服务而使服务部门受损失的概率务部门受损失的概率服务强度：服务强度： A：平均服务率（绝对通过率）平均服务率（绝对通过率）单位时间内完成服务的顾客数均值单位时间内完成服务的顾客数均值系统中顾客数的期望系统中顾客数的期望系统中等待服务的顾客数系统中等待服务的顾客数排队论方法讲解且通常在经过某一时段后即可到达稳态，且通常在经过某一时段后即可到达稳态，nntPtP)(lim1.4 系统状态的概率系统状态的概率系统的状态系统的状态系统中的顾客数系统中的顾客数 Ls无限制：无限制：n0，1，2，3， Ls有限制：有限制： n0，1，2，3，N 服务台个数为服务台个数为c，且服务为
7、即时制，且服务为即时制，则则n0，1，2，c Pn(t)=t时刻，状态为时刻，状态为n的概率的概率若若，称为稳态解。，称为稳态解。实际中，多数问题都属于稳态情况，实际中，多数问题都属于稳态情况，而不需要而不需要t排队论方法讲解 下面分别介绍一下以上下面分别介绍一下以上3个常个常用分布：用分布：1.5 到达时间的间隔分布和服到达时间的间隔分布和服务时间的间隔分布务时间的间隔分布常见分布：常见分布：1.泊松分布；泊松分布；2.负指数分布；负指数分布；3.爱尔朗分布：爱尔朗分布：排队论方法讲解 若若Pn(t1,t2)满足以下三个条件满足以下三个条件,则称顾客的到达形成则称顾客的到达形成泊松流泊松流：
8、1.5.1 泊松分布泊松分布设设 N(t)=在时段在时段0,t)内到达的顾客数内到达的顾客数,Pn(t1,t2)=在时段在时段t1,t2)内有内有n个顾个顾客到达的概率客到达的概率,则则Pn(t1,t2)=PN(t2)-N(t1)=n排队论方法讲解),(),(P1totttt(1) 无后效性：无后效性：在不相交的时间区间内在不相交的时间区间内,顾客到达数相互顾客到达数相互独立，即在独立，即在t,t+t时段内到达的顾客数，时段内到达的顾客数，与时刻与时刻t之前到达的顾客数无关；之前到达的顾客数无关； (2)平稳性：平稳性：对于充分小的对于充分小的t，在，在t,t+t内有个内有个顾客到达的概率，只
9、与顾客到达的概率，只与t有关，而与有关，而与无关，且无关，且称为概率强度，其中, 0表示单位时间内有一名顾客到来的表示单位时间内有一名顾客到来的概率概率排队论方法讲解 对于充分小的对于充分小的t，在，在t,t+t内有内有2个个或多个顾客到达的概率极小或多个顾客到达的概率极小,可以忽略可以忽略不计不计,即即2)(),(nntotttP的概率分布：下面研究系统状态为n如果取时间段的初始时刻为如果取时间段的初始时刻为t=0.则记则记）tPtPnn(, 0(由于由于2100),(),(),(),(1nnnntttPtttPtttPtttP(3)普通性：普通性：排队论方法讲解故故)(1),(),(1),
10、(210tottttPtttPtttPnn 则在时间段则在时间段0,t+t)内到达内到达n个顾客的个顾客的概率为概率为)()()1)(1tottPttPnn)0()()(nNttNPttPnnkknNtNPktNttNP0)0()()()(nkknktPtttP0)(),( 将将0,t+t)分为分为0,t)和和t,t+t),nkknknntPtttPtPtttPtPtttP2110)(),()(),()(),(排队论方法讲解即即ttotPtPttPttPnnnn)()()()()(1令令t0,则则) 1( , 0)0()()()(1nPtPtPdttdPnnnn特别的特别的,当当n=0时时,有
11、有1)0()()(000PtPdttdP)(ttPn)()()1)(1tottPttPnn排队论方法讲解解上述两个方程组解上述两个方程组,可得可得,!)()(,! 2)()(,)(,)(2210tnntttenttPettPtetPetP其中期望、方差为其中期望、方差为ttNDtNE)()(由上结果可知由上结果可知,在长度为在长度为t的时间段内到达的时间段内到达n个顾客的概率个顾客的概率,服从泊松分布服从泊松分布.排队论方法讲解,1)(tTetF则)(1)(1)(0tPtTPtTPtFT,)(0tetP又,)(tTetf故密度函数为顾客数，达的表示单位时间内平均到这里1.5.2 负指数分布负指
12、数分布当顾客流为泊松流时当顾客流为泊松流时,用用T表示两顾表示两顾客相继到达的时间间隔客相继到达的时间间隔,则则T是一个随机变量是一个随机变量,均时间间隔为相继到达的顾客的平则1)(TE其分布函数为其分布函数为排队论方法讲解 类似的类似的,设系统对一个顾客的服务设系统对一个顾客的服务时间时间v服从负指数分布服从负指数分布,分布函数为分布函数为,1)(tvetF密度函数为密度函数为tvetf)(其中则期望值则期望值1)(vE的泊松流等价的泊松流等价 表示平均一个顾客的服务时间表示平均一个顾客的服务时间,因此因此v服从负指数分布服从负指数分布,与概率强与概率强度为度为 表示平均服务率表示平均服务率
13、即单位时间内的服务人数即单位时间内的服务人数排队论方法讲解则称则称kkiivT1当当k=1时，即为负指数分时，即为负指数分布布ktkkekktktf)!1()()(1其密度函数为其密度函数为1.5.3 爱尔朗分布爱尔朗分布设有如下的顾客流，记设有如下的顾客流，记k个顾客到达个顾客到达时间间隔序列为时间间隔序列为v1,v2,v3vk(为相互为相互独立的随机变量独立的随机变量)都服从于参数为都服从于参数为 的负指数分布，的负指数分布，服从服从k阶爱尔朗分布阶爱尔朗分布因此因此k阶爱尔朗分布比负指数分布更为广泛阶爱尔朗分布比负指数分布更为广泛排队论方法讲解（推导过程略）（推导过程略） 令令11)1
14、(10nPPnn（1）系统状态为）系统状态为n的概率为的概率为2.排队论基本模型排队论基本模型2.1 单服务台的排队模型单服务台的排队模型(1) 标准型：标准型：M / M / 1 /(2) 系统容量有限：系统容量有限：M/M/1/N/(3) 顾客源有限：顾客源有限： M/M/1/m2.1.1 标准型：标准型：M/M/1排队论方法讲解（2）系统运行指标）系统运行指标qsqsWWLL,1,qsqsqqssLLWWWLWL,1,（3）运行指标之间的关系）运行指标之间的关系排队论方法讲解2.1.2 系统容量有限系统容量有限 M/M/1/N/NnPPnNnN1 ,111,1111011)1 ()1 (
15、1,1) 1(1011sqNqssqNNsWWPLWPLLNL（2）系统运行指标）系统运行指标（1）系统状态概率）系统状态概率排队论方法讲解2.1.3 顾客源有限顾客源有限 M/M/1/mmnPnmmPimmPnnmii1 ,)()!()()!(!1000)1 (,1,1)1 (),1 (000PLLWWPmWPmLsqsqss（2）运行指标）运行指标（1）系统状态平衡方程）系统状态平衡方程排队论方法讲解2.2 多服务台模型多服务台模型cnPcccnPnPckPncnnnckck,)(1!1,)(!1,)(11!1)(!101100（1）系统状态概率）系统状态概率2.2.1 标准型标准型 M
16、/ M/ c /排队论方法讲解020202)1 ( !)(,1)1 ( !)(, ,)1 ( !)(,PccWPccWcnkcPccLLLcqcscqqs其中（2）系统运行指标）系统运行指标排队论方法讲解2.2.2 系统容量有限制系统容量有限制 M/M/c/N/nNnnnnnnPcPNncPcPPccnPnPPnPP1111101)()()1 ()() 1(系统容量为系统容量为N，则当系统状态，则当系统状态n时，状态平衡方程：时，状态平衡方程：各台服务时间负指数分布，工各台服务时间负指数分布，工作相互独立，平均服务率作相互独立，平均服务率c个服务台，顾客为个服务台，顾客为Poission流，流
17、，平均到达率为平均到达率为 ，排队论方法讲解可利用上述方程求解可利用上述方程求解 ，0PnPcncnssqqnnckkPcnPLWWLPccPkcP101100)1 (,1, 0!)(,!)(，系统服务强度c其中其中更为特殊的更为特殊的 M/M/c/c/排队论方法讲解2.2.3 顾客源有限：顾客源有限：M/M/c/m100000,)(!)!(!0 ,)(!)!(!)()!(1!)()!( !1!1mncPccnmmcnPnnmmPmkmccmckmkmPncnnnckkcckk)(,)(,11seeqqessmcnnqmnnsLmLWLWPcnLnPL（2）运行指标）运行指标（1）状态平衡方程
18、）状态平衡方程排队论方法讲解3. 排队系统的最优化问题排队系统的最优化问题(2)系统控制最优化，系统控制最优化，(1)系统设计最优化，系统设计最优化，3.1.1 最优化问题的分类最优化问题的分类3.1 一般排队系统的最优化问题一般排队系统的最优化问题是指在服务系统设置以前，根据一定的质量指标是指在服务系统设置以前，根据一定的质量指标,找找出参数的最优值，从而使系统设计最经济。出参数的最优值，从而使系统设计最经济。也称也称静态最优化静态最优化例如服务机构的规模大小，服务台的个数，系统容量例如服务机构的规模大小，服务台的个数，系统容量的大小；的大小；对已有的排队系统，需求某一最优运营机制，使某目对
19、已有的排队系统，需求某一最优运营机制，使某目标函数最优标函数最优也称也称动态最优化动态最优化排队论方法讲解3.1.2 费用模型费用模型swsLccz单位时间的费用每个顾客在系统中停留表示时服务机构的服务费，表示wscc1目标函数：目标函数：3.2.1 标准型标准型 ：M/M/13.2 模型模型M/M/1中的最优服务率中的最优服务率一般说来，提高服务水平自然会降低等一般说来，提高服务水平自然会降低等待费用，最优化目标之一是使二者的费待费用，最优化目标之一是使二者的费用之和最小，另一个目标是使服务机构用之和最小，另一个目标是使服务机构的纯收入最大。的纯收入最大。通常所说的费用是指服务机构的服务费通
20、常所说的费用是指服务机构的服务费和顾客等待的费用。和顾客等待的费用。排队论方法讲解则，可得到最优解则，可得到最优解swcc*3.2.2 系统容量有限系统容量有限 ：M/M/1/N/ 为单位时间内实际进入服务系为单位时间内实际进入服务系统的顾客数统的顾客数)1 (NPGPN)1 ( 则系统的纯利润为则系统的纯利润为sNcGPz)1 (如果系统中已有如果系统中已有N名顾客，名顾客，PN为被拒绝为被拒绝的概率，的概率，1- PN为接受服务的概率，为接受服务的概率，设系统服务设系统服务1名顾客收入为名顾客收入为G元，于是单元，于是单位时间收入的期望值为位时间收入的期望值为0ddz令排队论方法讲解，求得
21、最优解，求得最优解GcNNsNNN2111)1 () 1(,111NNNNP其中，最后，将所有已知数值带入，利用数值法最后，将所有已知数值带入，利用数值法求解出求解出*0ddz令 3.2.2 顾客源有限的顾客源有限的 ：M/M/1/m1服务机构成本费为服务机构成本费为Cs,!)/()()(1mekmmEcGLmzmkmkmss其中，设顾客数为设顾客数为m，单个服务台、服务时，单个服务台、服务时间服从负指数分布，当服务率间服从负指数分布，当服务率纯利润为纯利润为单位时间内服务完的顾客数为单位时间内服务完的顾客数为m-Ls，单位时间内服务完一位顾客收入为单位时间内服务完一位顾客收入为G排队论方法讲
22、解GcmEmEmEmEmmEmEsmmmmmm22111最优解为最优解为给定给定Cs，G，m， 后，利用泊松分布后，利用泊松分布表和数值法进行计算。表和数值法进行计算。3.2 模型模型M/M/C中的最优服务台数中的最优服务台数仅对标准的模型进行讨论。仅对标准的模型进行讨论。在稳态的假设下，单位时间内每服务台在稳态的假设下，单位时间内每服务台的成本费为的成本费为Cs每个顾客在系统中停留单位时间的费用每个顾客在系统中停留单位时间的费用为为Cw则单位时间内费用的期望值为则单位时间内费用的期望值为z=CsC+CwLs其中其中Ls =Ls(C),即与服务台的个数即与服务台的个数C有关有关因此总费用为因此总费用为z=z(C)记记C的最优值为的最优值为C*，则，则z(C*)为最小费用为最小费用由于由于C只能取整数，即只能取整数，即z(C)是离散函数，是离散函数，只能用边际分析法求解，根据只能用边际分析法求解，根据z(C*)为最为最小值，有小值，有) 1*(*)() 1*(*)(CzCzCzCzswsLCCCz由) 1*() 1*(*)(*) 1*() 1*(*)(*CLCCCCLCCCCLCCCCLCCCswsswsswssws则有则有化简整理得化简整理得*)() 1*() 1*(*)(CLCLCCCLCLswsss
