排队论在实际当中的应用_毕业设计

排队论在实际中的应用1第一章排队论问题的基本理论知识排队是日常生活中经常遇到的现象，本章将介绍排队论的一些基本知识和常见的排队论的模型，使我们对排队论有一个基本的认识。1.1预备知识下图是排队过程的一般模型：各个顾客由顾客源（总体）出发，到达服务机构（服务台、服务员）前排队等候接受服务，服务完成后离开。我们说的排队系统就是图中虚线所包括的部分。一般的排队系统都有三个基本组成部分：输入过程；排队规则；服务机构。1.输入过程输入过程考察的是顾客到达服务系统的规律。可以用一定时间内顾客到达数或前后两个顾客相继到达的间隔时间来描述，一般分为确定型和随机型两种。对于随机型的情形，要知道单位时间内的顾客到达数或到达的间隔时间的概率分布。2.排队规则排队规则分为等待制、损失制和混合制三种。当顾客到达时，所有服务机构都被占用，则顾客排队等候，即为等待制。在等待制中，为顾客进行服务的次序可以是先到先服务，或后到先服务，或是随机服务和有优先权服务。如果顾客来到后看到服务机构没有空闲立即离去，则为损失制。有些系统因留给顾客排队等待的空间有限，因此超过所能容纳人数的顾客必须离开系统，这种排队规则就是混合制。3.服务机构排队结构服务机构顾客源顾客到达排队规则服务规则离去排队系统示意图排队论在实际中的应用2可以是一个或多个服务台。服务时间一般也分成确定型和随机型两种。但大多数情形服务时间是随机型的。对于随机型的服务时间，需要知道它的概率分布。1.2模型理论分析1.2.1模型分类排队模型的表示：X/Y/Z/A/B/CX—顾客相继到达的间隔时间的分布；Y—服务时间的分布；M—负指数分布、D—确定型、Ek—k阶爱尔朗分布。Z—服务台个数；A—系统容量限制（默认为∞）；B—顾客源数目（默认为∞）；C—服务规则（默认为先到先服务FCFS)。1.2.2模型求解一个实际问题作为排队问题求解时，只有顾客到达的间隔时间分布和服务时间的分布须要实测的数据来确定，其他的因素都是在问题提出时给定的。并且必须确定用以判断系统运行优劣的基本数量指标，解排队问题就是首先求出这些数量指标的概率分布或特征值。这些指标通常是：（1）队长：系统中排队等待服务和正在服务的顾客总数，其期望值记为SL；排队长（队列长）：系统中排队等待服务的顾客数，其期望值记为gL；[系统中顾客数]=[在队列中等待服务的顾客数]+[正被服务的顾客数]（2）逗留时间：一个顾客在系统中停留时间，包括等待时间和服务时间，其其期望值记为Ws；等待时间：一个顾客在系统中排队等待时间,其期望值记为Wg；[逗留时间]=[等待时间]+[服务时间]（3）忙期：从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度；系统状态：即指系统中的顾客数；状态概率：用nPt表示,即在t时刻系统中有n个顾客的概率；排队论在实际中的应用3要解决排队问题，首先要确定排队系统的到达间隔时间分布与服务时间分布。要研究到达间隔时间分布与服务时间分布需要首先根据现有系统原始资料统计出它们的经验分布，然后与理论分布拟合，若能对应，我们就可以得出上述的分布情况。1、经验分布经验分布是对排队系统的某些时间参数根据经验数据进行的统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数的经验数据服从该假设分布。2、泊松分布下面我们在一定的假设条件下，推出顾客的到达过程就是一个泊松过程。若设Nt表示在时间区间[0,t)内到达的顾客数(t0)，1,2nPtt表示在时间区间12,tt(t2t1)内有n(≥0)个顾客到达的概率，即1221,nPttPNtNtn（t2t1，n≥0）当1,2nPtt符合于下述三个条件时，我们说顾客到达过程就是泊松过程。(1)再不相重叠的的时间区间内顾客到达数是相互独立的。(2)对于足够小的Δt，在时间区间[t，t+t)内有1个顾客到达的概率为1,Pttttt（λ0是常数，称为概率强度）。(3)对充分小的Δt,在时间区间[t,t+Δt）内有2个或2个以上顾客到达的概率是Δt一高阶无穷小，即2,nnPtttt为了求nPt，即0,nPt，需要研究它在时刻t到t+Δt时刻的改变量，也就是要建立nPt的微分方程。就可以得到：!ntntPtnt0，n=0,1,2,…负指数分布设T为时间间隔，分布函数为TFtPTt，即：tFtPTt。此概率等排队论在实际中的应用4价于在[0，t）区间内至少有1个顾客到达的概率。没有顾客到达的概率为：0tPt，则011tTFtPt（t0），其概率密度函数为：tTTdFftdt（t0）。由前知，λ表示单位时间内顾客平均到达数，这里1/λ表示顾客到达的平均间隔时间，两者是吻合的。下面我们再谈一下服务时间的分布：对顾客的服务时间ν，实际是系统处于忙期时两顾客相继离开系统的时间间隔，一般地也服从负指数分布，即：1tVFttVft。其中：表示单位时间内能被服务完成的顾客数，即平均服务率。1/表示一个顾客的平均服务时间。令则ρ称为服务强度。排队论在实际中的应用5第二章单服务员排队模型在自动存取款机服务中的应用2.1理论分析1.稳态概率nPt的计算已知顾客到达服从参数为λ的泊松过程，服务时间服从参数为μ的负指数分布。在间刻t+Δt，系统中有n个顾客不外乎有下列四种情况。情况时刻的t顾客区间(t,t+t)时刻t+t的顾客(t,t+t)的概率[0,t+t]的概率(略去(t))到达离去An××n1-λt+(t)1μt+(t)Pn(t)(1-λt)(1-μt)Bn+1×√n1-λt+(t)μt+(t)Pn+1(t)(1-λt)(μt)Cn-1√×nλt+(t)1-μt+(t)Pn-1(t)(λt)(1-μt)Dn√√nλt+(t)μt+(t)Pn(t)(λt)(μt)由于这四种情况是互不相容的，所以Pn(t+Δt)应是这四项之和，将所有的高阶无穷小合并，则有：111nnnnPttPtttPttPttt令Δt→0，得关于Pn(t)的微分差分方程：11nnnndPtPtPtPtdt当n=0时，只有表中的（A）、（B）两种情况。00111PttPtPttt排队论在实际中的应用6…………(1)所以…………(2)稳态时，Pn(t)与时间无关，可以写成Pn，它对时间的导数为0，所以由(1)、(2)两式得：011nnnPPP……………(3)010PP……………(4)上式即为关于Pn的差分方程。由此可得该排队系统的状态转移图：这种系统状态(n)随时间变化的过程就是生灭过程,它可以描述细菌的生灭过程。得到：00nnnPPP………………(5)1(否则排队无限远，无法服务完)011nnPP………………(6)上式就是系统稳态概率，以它为基础可以算出系统的运行指标。2.系统的运行指标计算(1)系统中的平均顾客数（队长期望值Ls）：001nsnnnLnPn1(0ρ1)……(7)(2)队列中等待的平均顾客数Lq（队列长期望值）：11111nqnnnLnPn21sL……(8)(3)顾客在系统中的平均逗留时间Ws：11010()()()()()()()()nnnndPtPtPtPtdtdPtPtPtdt01λμ2λμλμn-1nλμn+1λμλμλμ......状态转换图排队论在实际中的应用71sWwssLW(4)顾客在队列中的等待时间的期望值qW：111qsWWqqLW3.系统的忙期与闲期：系统处于空闲状态的概率：01P系统处于繁忙状态的概率：001PNP2.2实例2.2.1问题提出与模型说明问题提出顾客排队等待接受服务，在任何一个服务系统中都是不可避免的。在存取款机排队等待取钱或存钱的排队问题也非常严重，为此,这里拟用排队论的理论和方法,建立评价指标,通过实例来探究如何提高工作效率？如何使系统更加优化？模型说明某街道口只有一个自动存取款机，从而该种情况是单列单服务台的情况，即为M/M/1模型的情况。2.2.2调查方法及数据处理调查内容（1）顾客到达时间。（2）服务时间。调查方法顾客到达的频率与时间段有关，一般在9：00—lO：30和下午2：3O一4：00顾客到达率比其它的时间高。我们把时间分成两段，考虑08：00—9：00、9：OO一1O：00的情况，分别代表了一般情况和繁忙时的情况。（1）服务时间：顾客开始用自动存取款机到服务完成。（2）顾客到达时间：顾客进入排队系统排队。以上两项调查，抽样的时间均是分散的、随机的。不可连续和集中抽样。具体数据如下：排队论在实际中的应用8其中，顾客编号i，到达时间iT，服务时间iS，到达间隔it，排队等待时间iw。表108：00—9：00的统计123456789101112iT028121925293442495460iS325731624294it23476458756iw010110010003表209：00—10：00的统计12345678910111213141510iT0269111519222836414548505660iS3247233251654325it243344368543264iw01026544000246312.2.3模型求解1、根据表1计算得：平均时间间隔为60115.45分钟人平均到达率为1260=0.2人分钟平均服务时间为4812=4.00分钟人平均服务率为1248=0.25人分钟2、根据表2计算得：平均时间间隔为60173.53分钟人平均到达率为1660=0.27人分钟平均服务时间为5716=3.56分钟人排队论在实际中的应用9平均服务率为1657=0.25人分钟把以上两表结合起来为表3，分析服务时间的分布规律，求出均值和方差。表3服务时间和频数服务时间X12345679频率P27644221服务时间的期望值为：2227364454627291283.82XXp服务率期望值：2822273644546272910.262.2.4讨论理论上讲，顾客到达会形成泊松流，因为：(1)在不相重叠的时间内顾客到达数是相互独立的，即无后效性；(2)对于充分小的时间区间内有一个顾客到达的概率与时刻无关，而与区问长成正比；在我们把时问段分开之后来分析，这一点也是满足的；(3)对于充分小的时间区间，有2个或2个以上顾客到达的概率极小。顾客到达满足以上三个条件，形成泊松流；所以顾客到达率服从负指数分布。而服务时问可看作服从正态分布。然而在统计数据比较少的情况下，并不能得出一一般规律，来精确的算出参数(到达率)和(服务率)。本文对此问题只做简单的分析。从表1中可以看出，在8：00—9：00时间区问内，有l2个顾客到达，其中有5个顾客必须等待，平均等待1111+3120.58qW分钟。而在表2中可以得出，在9：00—10：00时间区间内，有16个顾客到达，有11个顾客必须等待，平均等待时间：12654+4+2+4+6+3+1162.375qW分钟。根据以上分析，在8：00—9：00时间区间内，