排队论

排队论模型排队论是20世纪初由丹麦数学家Erlang应用数学方法在研究电话话务理论过程中而发展起来的一门学科，排队论也称随机服务系统理论，它涉及的是建立一些数学模型，以对随机发生的需求提供服务的系统预测其行为，它已应用于电讯、纺织、矿山、交通、机器维修，可靠性，计算机设计和军事领域，都已取得了显著的成绩。一、排队论简介二、实例分析一、排队论简介（一）基本概念1．排队系统排队是指在服务机构处要求服务对象的一个等待队列排队系统是指一个具有排队等待现象的服务系统排队论是指定量的研究排队问题，寻找系统内在规律，寻找供求关系平衡的最优方案。现实世界中排队的现象比比皆是，但有如下共同特征:(1)有请求服务的人或物，如候诊的病人，请求着陆的飞机等，我们将此称为“顾客”。(2)有为顾客提供服务的人或物，如医生、飞机跑道等，我们称为“服务员”。由顾客和服务员就组成服务系统。(3)顾客随机地一个一个(或者一批一批)来到服务系统每位顾客需要服务的时间不一定确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时间服务员又空闲无事。2排队系统的特征为了描述一个给定的排队系统，必须规定系统的下列组成(1)输入过程顾客陆续来到的过程，设N(t):(0，t)时间内来到的顾客数(非负整数值)}0),({ttN是随机过程，又设iT第i个顾客到达的时间，从}{iT随机变量序列，1iiiTT时间间距(隔)},max{)(1jiitjtN一般假设顾客来到时间间隔i相互独立与随机变量有相同的；可以根据原始资料，由顾客到达的规律、作出经验分布，x2检验法)确定服从哪种理论分布，并概率分布为负指数分布M(另外有定长分布D，k阶爱尔兰分布Ek，一般独立分布GI等)而分布然后按照统计学的方法(如估计它的参数值。我们主要讨论(2)服务机构服务员对顾客服务过程，服务机构可以是一个服务员或多个服务员的。对顾客可以单独进行服务，也可以对成批顾客进行服务，在我们这儿介绍对顾客单独进行服务。设C为服务机构服务员个数，当C=1时，为单服务系统，当C≥2，为多服务系统。和输入过程一样，服务时间都是随机的，且我们假设，设n表示服务员为第n个顾客提供服务所需的时间，则服务{}n服从相互独立的且与某一随机有相同分布，其中根据原始资料判断得到的，主要有的分布为负指数分布(定长分布，一般独立分布等)(3)排队与服务规则顾客排队和等待的规则，排队规则一般有等待制，消失制和混合制。所谓等待制(系统容量D就是当一个顾客到达时，若所有服务台均被占用时，该顾客便排队等待服务；消失制也称即时制(系统容量D=C)就是服务台被占用时顾客便即时离去；混合制也时间所构成的序列变量的概率分布是已知的可以)有限制(系统容量D:CDk)就是一顾客到达若系统中顾客称队长(包括排队等待和正在接受服务的)数目小于k则他排队等待，否则他即时离去，等待制服务的次序规则有先到先服务随机服务，有优先权的先服务等，我们主要讨论先到先服务的系统。3.排队系统的主要指标研究排队问题的目的，是研究排队系统的运行效率估计服务质量，确定系统参数最优值，以决定系统的结构是否合理，设计改进措施等，所以必须确定用来判断系统运行优劣的基本数量指标，这些数量指标通常是(1)队长:是指系统中顾客(包括排队等待和正在接受服务的)的数目，它的期望值为Ls排队等待的顾客数，其期望记为Lq(队长)=等待服务的顾客数+正被服务的顾客数，所以LLqs()或越大，；排队长度则仅指在队列中.系统中的顾客数说明服务效率越低。(2)等待时间:是指从顾客到达时间算起到他开始接受Wq顾客到达时刻算起到他接受服务完毕为止所需要的时间，Ws逗留时间=等待时间+服务时间(3)忙期:是指服务台连续繁忙的时间，即顾客从到达空闲服务台算起到服务台再次变为空闲时止的这段时间。这是服务台最关心数量指标，它直接关系到服务员工作强度，与忙期相对应的是闲期，这是指服务台连续保持空闲的时间长度；显然，在排队系统中忙期与闲期，是交替出现的。服务时止的这段时间，其期望值记；逗留时间则指从即是顾客在系统中所花费的总时间，其期望值记。排队系统除了上述三个主要数量指标外，另外服务台的利用率(即服务员忙碌的时间在总时间中所占比例)在排队论的研究中也是很重要的指标。（二）排队模型的符号表示与几种重要排队模型1.排队模型的符号一般表示法一般表示法A/B/C/D/E/FA:顾客来到时间间隔的分布类型B:服务时间的分布类型C:服务员个数D:系统容量E:顾客源个数F:服务规则先来先服务的等待排队模型主要由三参数法即A/B/C例“M/M/1/k/时间均服从负指数分布，一个服务台，系统至多容纳k个顾客潜在的顾客数不限，先来先服务的排队系统。/F1F0”表示顾客到达间隔时间和服务“M/M/c”即Poisson输入负指数服务时间分布C个服务台的等待制排队模型。“M/G/1”即Poisson输入，一般服务时间分布，单个服务台的等待制排队模型。00…00服务台顾客到达顾客离去排队服务机构顾客到达00…00排队服务台服务台顾客离去顾客离去2.几种重要的排队模型(1)单服务台系统(2)多服务台的平衡系统顾客到达00…00排队顾客离去000检验调试10%090%()(3)串联排队系统1M顾客到达00…00排队00…顾客离去02MnM(4)排队网络模型煤矿煤仓港口轮船汽车(或火车)火车(5)匹配排队模型另外还有(6)优先权的排队系统(7)成批排队模型(8)有限源排队模型我们讨论(1)(2)两种（三）、建立排队模型步骤1.确定表达排队问题各个变量并建立它们之间的相互关系。2.根据现有的数据，运用适当的统计检验，假设检验有关分布。3.应用已得到的概率分布，确定描述整个系统的运行特征。4.根据系统的特征，通过应用适当的决策模型，改进系统的功能。（四）、生灭过程的差分微分方程组当顾客到达时间间隔为负指数分布(即输入过程具有Poisson特征，N(t)服从Poisson分布)，服务时间为负指数分布，则系统的排队过程是Markov(马尔科夫)过程，而且它具有一类特殊Markov过程的特征，通常称这类随机过程的生灭过程。1.生灭过程的定义设有一个系统，具有有限个状态，其状态集s={0，1，2…k}或有可数个状态，状态集s={0，1，2…}，令X(t)为系统在时刻t所处的状态，若在某一时刻t系统的状态数为n，如果对△t0有。(1)到达(生):在(t，t+△t)内系统出现一个新的到达的概率为(),0nntot的常数；没有发生新的到达的概率1()ntot；出现多于一个以上的新的到达概率();0nntot的常数，没有消失的概率为1();ntot消失多于一个以上的概率为0(△t)则称系统状态随时间而变化的过程X(t)为一个生灭过程。为为0(△t)。(2)消失(灭):在(t，t+△t)内，系统消失一个的概率的2.生灭过程微分差分方程组设pnt()表示系统在时刻t的状态X(t)=n的概率即ppXtnnt(){()}ns，t0状态为n的概率近似于以下四个概率之和。(1)P{系统在时刻t时为n，而在△t内没有到达也没有消失}=()()[1](1)(1)()ntnnntnnpttpttot(2)P{系统在t时为n-1而在△t内有一个到达并且没有一个消失}=1()111()1(1)()ntnnntnpttptot(3)P{系统在t时为n+1，而在△t内没有到达而有一个消失}=1()111()1(1)()ntnnntnpttptot则系统在时刻t+△t的(4)P{系统在△t内发生多于一个的到达或消失}=o(△t)即应用全概率公式有1111()()(1)()()()nnnnnnnnPttptttpttpttot当时类似地，当S为有限集时，对有令△t→0得当系统状态S为有限集时，生灭过程的微分差分方程组为0n00011()()(1)()()pttpttpttotkn11()()(1)()()kkkkkpttpttpttotppppnkppppppntnntnnntnnttttktkktkkt()'()()()()'()()()'()()()|11110001111当系统状态S为可数集时，生灭过程微分差分方程组为(9.2)若能求解这组方程，则可得到在时刻t系统状态概率分布称为生灭过程的瞬时解，一般这种瞬时解是难以求得的ppppnppptntnntnnntnnttt()'()()()()'()()()1111000111{,}()pnsnt3.统计平衡下的极限解实际应用中，关心的是时，方程的解称为生灭过程微分差分方程组的极限解。令及(9.1)(9.2)式得当S为有限状态集时，(9.1)式变为(9.3)当S为可数状态集时(9.2)式变为(9.4从而可以求得概率分布列ttntnntppplim()()'由00010)(1111001111kkkknnnnnnnppppknpppnnnnnnnpppnpp11110011010(){}pn（五）、典型排队模型和理论结果下面给出满足生灭过程典型排队M/M/1与M/M/C的结果(一)单服务台等待制M/M/1排队模型1.M/M/1/顾客来到的时间间隔服从参数λ的负指数分布，服务员为顾客服务时间服从参数的指数分布，且与相互独立，1个服务台，系统容量为的等待制排队模型。可理解为:单位时间平均到达的顾客数-----平均到达率可理解为:单位时间平均服务完的顾客数----平均服务率(1)顾客输入过{:},()()()NtNt000是平均率为的Poisson过程即Ntt()()～设M(t)为(0，t)内离去顾客数，则{:}()Mtt0是平均率为的Poisson分布即Mtt()()～(2)X(t):时刻t系统中的顾客数则XNMttt()()()L(t):时刻t排队等待顾客数则LXtt()()max{,}10研究X(t)的分布模型令PPXnPpnttntntj()()()(){}(,)显然010当依赖于t时，称是瞬时解如果则称是稳定解。此系统的状态转移图图1pnt(){,,,}()pnnt012ntntpp)(lim,1,0,npn012………n-1nn+1………从而在生灭过程中取,,{0,1,2}nns(9.5)记，称为服务强度当时，模型不稳()当＜1时，模型稳定，有稳定解(3)X(t)的分布律由(9.2)式得此模型的微分差分方程组(9.6)当时，稳态解满足1,;时队列越来越长dpdtpppndpdtppntntntntttt()()()()()()()()1100111(9.7)求解(9.7)式差分方程，得(9.8)(4)结论平均队长(9.9)平均等待队长(9.10)系统中顾客数的方差(9.11)010)(1011ppnpppnnn1)(00pppnn1))((tXELssqLtLEL1))((2022)))(((jtXEj()12顾客不须等待概率(9.12)可以证明，顾客在系统中逗留时间T服从参数为的负指数分布，从而顾客在系统平均逗留时间(9.13)顾客在系统平均等待时间(9.14)从上结论可以看出，各指标之间有如下关系(9.15)(9.16)p01()