第14章_排队论方法1

·214·第十四章排队论方法排队是日常生活中常见的一种现象，其共同的特点是：在一个排队服务系统中包含有一个或多个“服务设施”，有许多需要进入服务系统的“被服务者”，或“顾客”，当被服务者进入系统后不能立即得到服务，也就出现了排队现象．一个服务系统总是由“服务设施”与“被服务者”构成．如：医院与病人、商店与顾客、机场与飞机、火车站与火车、水库与水、网络与用户等等．由于“被服务者”到达服务系统的时间是不确定的，即是随机的，所以排队论又是称为“随机服务系统理论”，因此，排队论在实际中有广泛的应用．排队论要研究的内容有三部分：（1）性态问题：即研究排队系统的概率分布规律，主要是研究队长分布、等待时间分布和忙期分布等．（2）最优化问题：分为静态最优化和动态最优化，即为系统的最优设计和系统的最优运营问题．（3）排队系统的统计推断：判断一个给定的排队系统符合于哪种模型，以便于根据排队理论进行分析研究．14.1排队服务系统的基本概念14.1.1排队过程的一般模型设要求服务的顾客从顾客总体进入排队系统（输入），到达服务机构前排队等候服务，服务完后立即离开（输出）．排队系统的主要有输入过程、排队规则和服务机构三个部分组成：1.输入过程：顾客到达排队系统的过程，具有如下的特征：(1)顾客总体（称为顾客源）的组成可能是有限的，也可能是无限的；(2)顾客到来的方式可能是一个一个的，也可能是成批的；(3)顾客相继到达的间隔时间可以是确定型的，也可以是随机的；(4)顾客的到达是相互独立的；(5)输入过程是平稳的，或称为对时间是齐次的，即相继到达的时间间隔分布与时间无关．2.排队规则：顾客到达后的排队方式、形状和队列数目，其特征有三条：(1)顾客到达后的排队方式可以是“即时制”，也可以是“等待制”，对于等待制的服务次序有：先到先服务、后到先服务、随机服务、有优先权的服务等；(2)排队可以是有形的，也可以是无形的，有的排队容量是有限的，有的是无限的；(3)排队数目可以是单列，也可以是多列，有的可相互转移，有的不可相互转移．3.服务机构：对顾客提供服务的设施或对象，从机构的形式和工作情况来分有以下特征：(1)服务机构可以没有服务员（或服务台），也可以有一个或多个服务台；(2)对于多个服务台的情况，可以是并列，可以是串列，也可以是混合排列；(3)服务方式可以是一个一个的进行，也可以是成批成批的进行；(4)服务时间可以是确定型的，也可以是随机型的，对于随机型的需要知道它的概率分布；·215·(5)服务时间的分布对时间是平稳的，即分布均值、方差等都与时间无关．14.1.2排队模型的标准形式排队模型的标准形式为X/Y/Z/A/B/C，其中X表示相继到达间隔时间的分布，Y表示服务时间的分布，X和Y的取值有下列几种情况：M（Markov）表示负指数分布；D（Deterministic）表示确定型的分布；Ek（Erlang）表示k阶爱尔朗分布；GI（GeneralIndependent）表示一般相互独立的时间间隔分布；G（General）表示一般服务时间的分布．Z表示服务台的个数，A表示系统的容量限制，B表示顾客源数目，C表示服务规则，可分为先到先服务（FCFS）、后到先服务（LCFS）、随机服务、有优先权的服务等，通常只考虑FCFS的情况，此时可省略此项．例如：mNCMM////．14.1.3排队系统的运行指标排队论主要是研究排队系统运行的效率，估计服务质量，确定系统参数的最优值，以决定系统结构是否合理、研究设计改进措施．因此，研究排队问题，首先要确定用以判断系统运行优劣的基本量化指标，然后求出这些指标的概率分布和数学特征．要研究的系统运行指标主要有：(1)队长：指在系统中的顾客数，期望值记作SL；(2)排队长（队列长）：指在系统中排队等待服务的顾客数，其期望值记作qL,即nqSLLL，其中nL为正在接受服务的顾客数；(3)逗留时间：指一个顾客在系统中的停留时间，其期望值记作SW；(4)等待时间：指一个顾客在系统中排队等待的时间，其期望值记作qW，即qSWW，其中为服务时间；(5)忙期：服务机构连续工作的时间长度，记作bT；(6）损失率：由于系统的条件限制，使顾客被拒绝服务而使服务部门受到损失的概率，用损P表示；(7)服务强度：绝对通过能力A，表示单位时间内被服务完顾客的均值，或称为平均服务率；相对通过能力Q，表示单位时间内被服务完的顾客数与请求服务的顾客数之比值．14.1.4系统状态的概率系统状态是求运行指标的基础，所谓系统的状态是指系统中顾客的数量．如果系统中有n个顾客，则说系统的状态为n，即可能的取值为(1)当队长无限制时，则,2,1,0n；·216·(2)当队长为有限制，且最大值为N时，则Nn,,2,1,0；(3)当服务台个数为c，且服务为即时制时，则cn,,2,1,0．一般说来，状态的取值与时间t有关，因此，在时刻t系统状态取值为n的概率记为)(tPn，如果nntPtP)(lim，则称为稳态（或统计平衡状态）解．实际中多数问题都有是属于稳态的情况，并不是真正的t，即过某一段时间以后就有nnPtP)(．14.2到达时间的间隔分布和服务时间的分布实际中，到达时间的间隔分布和服务时间的分布一般服从于以下三种分布：普阿松（Poisson）分布、负指数分布和爱尔朗分布．14.2.1普阿松分布设)(tN表示在时间段),0[t内到达的顾客数，),(21ttPn表示在时间段)(),[1221tttt内有)0(n个顾客到达的概率，即})()({),(1221ntNtNPttPn，当),(21ttPn满足如下三个条件时，则称顾客的到达形成普阿松流：（1）无后效性：在不相交的时间区间内顾客到达数是相互独立的，即在时间段],[ttt内到达k个顾客的概率与时刻t以前的到达多少顾客无关．（2）平稳性：对于充分小的t，在时间间隔],[ttt内有1个顾客到达的概率只与时间段的长度t有关，而与起时时刻t无关，且)(),(1tottttP，其中0称为概率强度（或平稳流强度），即表示单位时间内有一个顾客到达的概率．（3）普通性：对于充分小的t，在时间间隔],[ttt内有2个或2个以上顾客的概率极小，可以忽略不计，即)(),(2totttPnn．下面研究系统状态为n的概率分布．如果取时间段的初始时间为0t，则可记)(),0(tPtPnn，在),[ttt内，由于1),(),(),(),(2100nnnntttPtttPtttPtttP故在),[ttt内没有顾客到达的概率为)(1),(),(1),(210tottttPtttPtttPnn将),0[tt分为),0[t和),[ttt，则在时间段),0[tt内到达n个顾客的概率应为nknknNtNPktNttNPnNttNPttP0})0()({})()({})0()({)(·217·)()()1)((),()(10tottPttPtttPtPnnnkkkn即ttotPtPttPttPnnnn)()()()()(1令0t，则)1(0)0()()()(1nPtPtPdttdPnnnn（14.1）特别地，当0n时有1)0()()(000PtPdttdP（14.2）由（14.2）式解得tetP)(0，代入（14.1）式解得ttetP)(1，tettP!2)()(22．一般地有0,,2,1,0(!)()(tnenttPtnn）表示在长为t的时间段内到达n个顾客的概率，即为普阿松分布，数学期望和方差分别为ttNDttNE)]([,)]([．14.2.2负指数分布当顾客流为普照阿松流时，用T表示两个相继到达的时间间隔，是一个随机变量，其分布函数)(1}{1}{)(0tPtTPtTPtFT．由上可知tetP)(0，于是0,1)(tetFtT，分布密度为0,)(tetftT．这里表示单位时间内平均到达的顾客数，则1)(TE表示相继顾客到达平均间隔时间．类似地，设系统对一个顾客的服务时间为（即在忙期内相继离开系统的两个顾客的间隔时间）服从于负指数分布，分布函数为0,1)(tetFt，分布密度为0,)(tetft，其中表示平均服务率（即单位时间内被服务完的顾客数），且期望值为1)(E，表示一·218·个顾客的平均服务时间．因此，T服从于负指数分布，即与概率强度为的普阿松流等价．并且注意到，由条件概率可知：}{}{tTPsTstTP，即说明后一个顾客的到来所需时间与前一个顾客到来所需时间s无关，故T具有无记忆性．于是，在排队模型的记号中都用M表示，且21)(,1)(TDTE14.2.3爱尔朗分布设有如下的顾客流，记k个顾客到达系统的时间间隔序列为k,,,21（为相互独立的随机变量），同服从于参数为k的负指数分布，则称随机变量kiiT1服从于k阶爱尔朗分布，分布密度为)0,0()!1()()(1tekktktfktkk．注意到：),,2,1(1][kikEi，则1][)(1kiiETE，且21)(kTD．当1k时，即为负指数分布，因此爱尔朗分布比负指数分布更广泛．类似地，设系统中有串列的k个服务台，每个服务台对顾客的服务时间是相互独立的，且服从于（参数为k）负指数分布，则一个顾客在接受完k个服务台的服务所需的总时间T服从于k阶爱尔朗分布．14.3单服务台的排队模型设系统的输入过程服从于普阿松流，服务时间服从于负指数分布，单服务台的排队系统有下三种情形：（1）标准型：1//MM（//1//MM）（2）系统容量有限制：//1//NMM（3）顾客源为有限的：mMM//1//14.3.1标准型：1//MM排队模型1//MM表示顾客源为无限的，顾客的到达相互独立，到达规律服从参数的普阿松分布；单服务台、队长无限、先到先服务；各顾客的服务时间相互独立，且同服从于参数为的负指数分布．1.确定系统在任意时刻t的状态为n的概率因为已知顾客的到达规律服从参数为的普阿松分布，服务时间服从参数为的负指数分·219·布，于是在时间间隔),[ttt内有：有一个顾客到达的概率为：)(tot没有一个顾客到达的概率为：)(1tot有一个顾客被服务完的概率为：)(tot没有一个顾客被服务完的概率为：)(1tot多于一个顾客到达或被服务完离去的概率为：)(to现在考虑在tt时刻系统中有n个顾客（即状态为n）的概率)(ttPn，可能的情况如表14-1所示．表14-1情况时刻t的顾客数在区间),(ttt在时刻tt的顾客数)(ttPn到达离去（A）（B）（C）（D）n1n1nn××√√×√×√nnnn)1)(1)((tttPntttPn)1)((1)1)()((1tttPn))()((tttPn这是一个生灭过程，四种情况是相互独立的事件．则有)()()()1)(()(11tottPttPtttPttPnnnn移项整理，两边同除以t，并令0t，则得,2,1),()()()()(11ntPtPtPdttdPnnnn当0n时，类似地可有)()()(100tPtPdttdP．于是，一般地有1),()()()()()()()(11100ntPtPtPdttdPtPtPdttdPnnnn此方程为差分微分方程，其解是贝塞尔（B