《排队论在实际当中的应用毕业设计.docx》由会员分享，可在线阅读，更多相关《排队论在实际当中的应用毕业设计.docx（20页珍藏版）》请在三一办公上搜索。
1、第一章 排队论问题的基本理论知识排队是日常生活中经常遇到的现象，本章将介绍排队论的一些基本知识和常见的 排队论的模型，使我们对排队论有一个基本的认识。1.1 预备知识下图是排队过程的一般模型：各个顾客由顾客源（总体）出发，到达服务机构（服务台、服务员）前排队等候接受服务，服务完成后离开。我们说的排队系统就是图中虚线所包括的部分顾客源顾客到达排队规则排队系统示意图一般的排队系统都有三个基本组成部分：输入过程；排队规则；服务机构。1输入过程输入过程考察的是顾客到达服务系统的规律。可以用一定时间内顾客到达数 或前后两个顾客相继到达的间隔时间来描述，一般分为确定型和随机型两种。对 于随机型的情形，要知
2、道单位时间内的顾客到达数或到达的间隔时间的概率分 布。2.排队规则排队规则分为等待制、损失制和混合制三种。当顾客到达时，所有服务机构 都被占用，贝U顾客排队等候，即为等待制。在等待制中，为顾客进行服务的次序 可以是先到先服务，或后到先服务，或是随机服务和有优先权服务。如果顾客来 到后看到服务机构没有空闲立即离去，则为损失制。有些系统因留给顾客排队等 待的空间有限，因此超过所能容纳人数的顾客必须离开系统，这种排队规则就是 混合制。3.服务机构可以是一个或多个服务台。服务时间一般也分成确定型和随机型两种。但大 多数情形服务时间是随机型的。 对于随机型的服务时间， 需要知道它的概率分布。1.2 模型
3、理论分析1.2.1 模型分类排队模型的表示：X/Y/Z/A/B/Cx顾客相继到达的间隔时间的分布；丫一服务时间的分布；M负指数分布、D确定型、Ek k阶爱尔朗分布。Z服务台个数；A系统容量限制（默认为）；B顾客源数目（默认为）；C服务规则（默认为先到先服务 FCFS）。1.2.2 模型求解 一个实际问题作为排队问题求解时，只有顾客到达的间隔时间分布和服务时 间的分布须要实测的数据来确定，其他的因素都是在问题提出时给定的。并且必 须确定用以判断系统运行优劣的基本数量指标，解排队问题就是首先求出这些数 量指标的概率分布或特征值。这些指标通常是：（1）队长：系统中排队等待服务和正在服务的顾客总数，其
4、期望值记为LS ；排队长（队列长）：系统中排队等待服务的顾客数，其期望值记为Lg ； 系统中顾客数 = 在队列中等待服务的顾客数 + 正被服务的顾客数 （ 2）逗留时间：一个顾客在系统中停留时间，包括等待时间和服务时间，其 其期望值记为 Ws ；等待时间：一个顾客在系统中排队等待时间 , 其期望值记为 Wg ； 逗留时间 = 等待时间 + 服务时间 （ 3）忙期：从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度； 系统状态：即指系统中的顾客数；状态概率：用 Pn t 表示 , 即在 t 时刻系统中有 n 个顾客的概率；要解决排队问题，首先要确定排队系统的到达间隔时间分布与服务时间分 布
5、。要研究到达间隔时间分布与服务时间分布需要首先根据现有系统原始资料统 计出它们的经验分布，然后与理论分布拟合，若能对应，我们就可以得出上述的 分布情况。1经验分布经验分布是对排队系统的某些时间参数根据经验数据进行的统计分析，并依 据统计分析结果假设其统计样本的总体分布，选择合适的检验方法进行检验，当 通过检验时，我们认为时间参数的经验数据服从该假设分布。2、泊松分布下面我们在一定的假设条件下，推出顾客的到达过程就是一个泊松过程。若设N t表示在时间区间0,t)内到达的顾客数(t0) ，Pn以2表示在时间区间ti,t2 (t2t1)内有n( 0)个顾客到达的概率，即Fn ti ,t2P N t2
6、N tin(t2t1 ， n 0)当Pn ti,t2符合于下述三个条件时，我们说顾客到达过程就是泊松过程。(1) 再不相重叠的的时间区间内顾客到达数是相互独立的。(2) 对于足够小的 t，在时间区间t，t+ t)内有1个顾客到达的概率为P1 t,tt t t (入0是常数，称为概率强度)。(3) 对充分小的 t,在时间区间t,t+ t )内有2个或2个以上顾客到达的概率是 t 一高阶无穷小，即Pn t,tttn 2为了求Pn t，即R 0,t，需要研究它在时刻t到t+ t时刻的改变量，也就是要建立R t的微分方程。就可以得到：nR t 丄 I t t0，n=0,1,2,n!负指数分布设T为时间
7、间隔，分布函数为Ft t P T t，即：Ft t P T t o此概率等 价于在0 , t)区间内至少有1个顾客到达的概率。没有顾客到达的概率为：P0 t I七，贝U Ft t 1 P0 t 1 I七(t0),其概 率密度函数为：fT t 吐 I t (t0)dt由前知，入表示单位时间内顾客平均到达数，这里1/入表示顾客到达的平均间隔时间，两者是吻合的。下面我们再谈一下服务时间的分布：对顾客的服务时间V,实际是系统处于忙期时两顾客相继离开系统的时间间隔， 一般地也服从负指数分布，即：Fv t 1 I t fV t I t。其中：表示单位时间内能被服务完成的顾客数，即平均服务率。1/表示一个顾
8、客的平均服务时间。令一则P称为服务强度。第二章 单服务员排队模型在自动存取款机服务中的应用2.1理论分析1.稳态概率Pn t的计算已知顾客到达服从参数为入的泊松过程，服务时间服从参数为卩的负指数分布在间刻t+ t，系统中有n个顾客不外乎有下列四种情况。情况时刻的t顾客区间(t, t+ t)时刻t+ t的顾客(t, t+ t)的概率0, t+ t的概率(略去(t)到达离去AnXXn1-入t+ ( t)1卩t+ ( t)Pn(t)(1-入t)(1- 1 t)Bn+1XVn1-入t+ ( t)卩 t+ ( t)Pn+1(t)(1-入t)( 1 t)Cn-1VXn入 t+ ( t)1-1t+ ( t)
9、Pn-1 (t)(入t)(1- 1 t)DnVVn入t+ ( t)1t+ ( t)Pn(t)(入t)( 1 t)由于这四种情况是互不相容的，所以Pn(t+ t)应是这四项之和，将所有的高阶无穷小合并，则有：Pn t tP t 1 t t Pm t t R i t t t令厶t -0,得关于Pn(t)的微分差分方程：dPn t-巳 1 tPn i t巳 tdt当n=0时，只有表中的(A)、(B)两种情况P) t tF0 1t R t 1ttdR(t)(APn1(t)P(t)Pn 1(t) ()Pn(t)P(t)(1)所以dt dF0(t)dt(2)稳态时，Pn(t)与时间无关，可以写成Pn,它对
10、时间的导数为0,所以由、 两式得：Pn 1Pn 1Pn 。 (3)Y.PoPi 0 (4)上式即为关于Pn的差分方程。由此可得该排队系统的状态转移图：这种系统状态(n)随时间变化的过程就是生灭过程，它可以描述细菌的生灭过程n得到：Pn- R % (5)-1 (否则排队无限远，无法服务完)P0 1Pn1上式就是系统稳态概率，以它为基础可以算出系统的运行指标2.系统的运行指标计算(1)系统中的平均顾客数(队长期望值 Ls):Ls n Pnn 1(0 P 1) 队列中等待的平均顾客数Lq （队列长期望值）：2Lq n 1Pnn 11 n Lsqnsn 1n 1I（3）顾客在系统中的平均逗留时间 Ws
11、Ws（4）顾客在队列中的等待时间的期望值 Wq :1 1 1Wq WsLqW3.系统的忙期与闲期：系统处于空闲状态的概率：Po 1系统处于繁忙状态的概率：P N 01 P02.2实例2.2.1问题提出与模型说明问题提出顾客排队等待接受服务，在任何一个服务系统中都是不可避免的。在存取款机排 队等待取钱或存钱的排队问题也非常严重，为此，这里拟用排队论的理论和方法，建 立评价指标，通过实例来探究如何提高工作效率？如何使系统更加优化？模型说明某街道口只有一个自动存取款机，从而该种情况是单列单服务台的情况，即为M/M/1模型的情况。2.2.2调查方法及数据处理调查内容（1）顾客到达时间。（2）服务时间。
12、调查方法顾客到达的频率与时间段有关，一般在 9： 0010: 30和下午2： 3O-4： 00顾客到 达率比其它的时间高。我们把时间分成两段，考虑 08: 009： 00、9： 00- 1O 00的 情况，分别代表了一般情况和繁忙时的情况。(1)服务时间：顾客开始用自动存取款机到服务完成。(2顾客到达时间：顾客进入排队系统排队。以上两项调查，抽样的时间均是分散的、随机的。不可连续和集中抽样。具体数据如下：其中，顾客编号i，到达时间T，服务时间S，到达间隔ti，排队等待时间Wi表1 08 : 009： 00的统计123456789101112Ti028121925293442495460S325
13、731624294ti23476458756wi010110010003表2 09 : 0010： 00的统计12345678910111213141510Ti0269111519222836414548505660Si3247233251654325ti243344368543264wi01026544000246312.2.3模型求解1、根据表1计算得：平均时间间隔为60 11 5.45分钟人平均到达率为12 60=0.2人分钟平均服务时间为48 12=4.00分钟；人平均服务率为12 48=0.25人j分钟2、根据表2计算得:平均时间间隔为60 17 3.53分钟人平均到达率为16 60
14、=0.27人.分钟平均服务时间为57 16=3.56分钟；人平均服务率为16 57=0.25人分钟把以上两表结合起来为表3,分析服务时间的分布规律，求出均值和方差。表3服务时间和频数服务时间X12345679频率P27644221服务时间的期望值为:X X p 222736445462729128 3.82服务率期望值：2822273644546272910.262.2.4讨论理论上讲，顾客到达会形成泊松流，因为：（1）在不相重叠的时间内顾客到达数是 相互独立的，即无后效性；（2）对于充分小的时间区间内有一个顾客到达的概率与时刻 无关，而与区问长成正比；在我们把时问段分开之后来分析，这一点也是
15、满足的；（3）对于充分小的时间区间，有2个或2个以上顾客到达的概率极小。顾客到达满足以上三 个条件，形成泊松流；所以顾客到达率服从负指数分布。而服务时问可看作服从正态 分布。然而在统计数据比较少的情况下，并不能得出一一般规律，来精确的算出参数 （到达率）和（服务率）。本文对此问题只做简单的分析。从表1中可以看出，在8： 00 9： 00时间区问内，有12个顾客到达，其中有5 个顾客必须等待，平均等待 Wq1 1 1 1+3 12 0.58分钟。而在表2中可以得出，在9： 0010： 00时间区间内，有16个顾客到达，有11个顾客必须等待，平均 等待时间：Wq 1 2 6 5 4+4+2+4+6
16、+3+116 2.375 分钟。根据以上分析，在8： 00 9： 00时间区间内，顾客平均到达率0.2人;分钟，平均服务率是0.25人:分钟，在9： 00 10: 00时问区问内分别为0.27人，分钟和0.28人，分钟。可以看出，平均服务律是高于平均到达率的。但是，通过表3的数据分析，在8： 0010: OO寸间区间内平均服务率为0.26人分钟，由于表3中的数据量比较 大，所以更具有代表性。如果这样分析，平均服务率就小于9： 0010: O的顾客平均到达率0. 27,这样就会使排队越来越长而直到高峰期过后才能得到缓解。我们认为在 这个系统中，当平均等待时间超过1分钟，系统被视为效率低下，而低于
17、1分钟被视为 系统有闲置。通过以上分析，在9: 0010: 00时间区间内，等待问题比较严重，而在 8; 00 9: 00系统有闲置现象。现实中，合理的把等待时间控制在1 ,1 内很难（为很小的数）。2.3MM1模型中的最优服务率问题已知有设进入系统的顾客单位时间带来的损失为d ,单位时间服务台每服务一位顾客的服务成本为C2,则单位时间总费用的期望值为：C( ) gL( ) C2qC2dC dC2d2C2 c1)3解得:/ 1最优服务率为最优服务率随着进入系统的顾客数和损失费G的增加而增加，随着服务成本C2的增加而减小某生产厂家有多台机器，每台机器连续运转的时间服从指数分布，平均为1小时, 每
18、台故障机器的损失费为3200元/小时.有1个维修工人，每次维修时间服从指数分布， 每台故障机器的修理费用为100元/小时,求最优的每台机器维修时间。由题意知：最优服务率为:5（台/小时）G !3200 c212 100即最优的机器维修时间为：1 10.2小时 12分钟5第三章 中式快餐店排队系统的优化3.1 理论分析当系统容量最大为N时，排队系统中多于N个的顾客将被拒绝。当N=1时，即 为瞬时制；NX时，即为容量无限制的情况。顾客 被拒绝N432排队系统服务台现在研究系统中有n个顾客的概率Pn t .对于F0 t ,前面的式子仍然成立，当n=1,2,N-1时，也仍能成立。dPN（t）dtPN
19、（t）PN 1（t）但当n=N时，有下面两种情况:情况时刻t的顾客区间t, t+ t时刻t+ t的顾客数概率AN无离去（冃疋不到达）NPN（t） （1-小 t）BN-1一人到达（无离去）NPN-1（t）入 tPN（tt）PN（t）（1 t）Fn 1（t）t其状态转移图为入N-1在稳态情况下有:Pn 1PoPn 1PnP(PnP0解得：Pn1111F面计算其运行指标:（1）平均队长Ls：NLsnn 0Pn(pM 1,n c时），n讥nc时）。令 一，只有当一1时，才不会形成无限队列cc队列从下图的队列图，分析系统中的状态转移关系，状态转移图见下图nc由上图知，当n ,当nc时，为cy,故可得差分
20、方程:(n 1) Pn 1c Pn 1PiPoPn 1 (nPn 1 (C)Pn)Pn(1c)这里： P 1 , pW 1i 0利用递推法解该差分方程可求得状态概率为:当(n c），Pnnc! c(一)Po系统的运行指标为:LqLsLq(n c)Pnn c 1WSwqLs(c)c!(1)LsLq4.2实例4.2.1 问题提出排队论，就是对排队现象进行数学研究的理论，也称随机服务理论，是运筹学中 一个独立的分支。作为一种工具或方法，已在许多行业的管理领域包括医院的管理领 域应用。门诊注射室的服务工作，是一种随机性服务，即患者的到达时间、到达数量、注 射所用时间，都是一种随机现象。这种服务以什么指
21、标才能比较客观地表示、反映注 射室的工作质、工作效率？如何评价注射室的人员、设备配备的合理性？为此 ，笔者 拟用排队论的理论和方法，建立评价指标，为寻求既不使患者排队成龙，又不浪费医 院人力物力的最优方案，提供科学依据，使注射室管理从经验管理转为科学管理。4.2.2调查方法及数据处理调查内容:（1）单位时间内到达的患者数。（2）服务时间。调查方法（1）服务时间：从某患者进人注射室开始记时，到该患者接受注射后走出注射室 止。共随机记录了 593人次的服务时间。单位时间内到达的患者数：以5分钟为一个时间单位，任意选取若干个时间单 位，记录每个5分钟到达的患者数。共随机抽取了 168个时间单位。以上
22、两项调查，抽样的时间均是分散的、随机的，不可连续和集中抽样。调查资 料经统计处理后如下：1、单位时间内到达的患者数单位时间（5分钟）内到达的患者数（人）频数概率060.041150.092300.183340.204430.265160.096100.06790.05840.02910.01合计1681.002、服务时间服务时间（分钟）频数概率1 :1700.292:2030.343:1520.264：560.095:60.016:60.01合计5931.00经曲线拟合检验，服务时间的概率分布服从负指数分布，单位时间内到达患者数 的概率分布服从泊松分布。从而求出排队系统的两个重要参数，患者平均
23、到达率和 平均服务率。又因注射室内有两个注射凳一服务台 C=2故符合排队论中M/M/C型排队模型。应用M/M/C型计算公式计算各项指标4.2.3模型求解（1基本参数1、 患者平均到达率0.71人，分钟2、 平均服务率=0.45人分钟（2）注射室运行状态指标（C=2）1、服务强度0.712 0.450.79说明注射室有79%勺时间是忙期，21%勺时间是空闲的。2、空闲概率：即注射室没有病人的概率。C 1K11C! 101.580!1 21.581.5810.121!2!1 0.79（3）反映患者排队情况指标1、队列长：等待注射的患者数。C期望值Lq C! 12P02.68 人2 、队长：队列长+
24、正在接受注射的患者数。期望值 Ls Lq C 2.68 1.58 4.26 人平均等待时间Lq2.680.713.77分钟4 、平均逗留时间1 Ws Wq 3.772.225.99 分钟现假设只配备一名护士负责注射,即C=1,那么服务强度 =24=1.58。在排队0.45论中，当1时，说明系统处于超负荷状态，将会持续出现排队成龙现象。故此时不可取的。4.2.4讨论1、排队论的应用，可以为合理使用人力、物力提供客观依据。由下表可见注射室现有的服务台C=2时，注射室有71%勺时间被利用，在等注射的 人数为2.68个，等待时间为3.77分钟。如果服务台增为3个时，注射室将53%勺时间被 利用，排队等
25、待的平均人数小于1,平均等待时间不足半分钟。若服务台增为4个，排 队人数和排队时间几乎为0,但是注射室被利用的时间只有39%, 61%勺时间处于空闲, 造成人力浪费。因此，设两个服务台，基本合理,若条件允许，设三个服务台，将是最佳选 择。指标名称服务台个数(C)234服务强度0.790.530.39空闲概率P00.120.190.20等待人数Lq2.680.310.05等待时间Wq3.770.440.072、排队论的应用，可以建立和完善评价注射室运行效率和服务质量的数量指标。(1)患者排队人数及排队时间的指标：据心理学调查结果表明，在就诊中，等待时间是患者最敏感的问题，长时间排队会形成心理压力
26、，产生不良情绪，是患护 产生矛盾冲突的重要原因。同时，由于排队所浪费的时间称为误工费用，据有 关部门报道，我国每一名全民所有制工业企业职工日创产值 38.67元，每耽误 一小时，国家损失4.83元。因此，无论从心理因素还是经济因素，等待时间都 应成为反映注射室服务质量的指标之一。（2）服务时间指标：患者接受注射的时间 , 不同于卖票、收款等服务 , 不能越快越 好。因此也应成为评价服务质量的另一项指标 , 以免求速度请效率。3、排队论的应用 , 为决策人员制定工作规划提供预见性资料。注射室现配有三名护士 , 但因建筑面积狭窄 , 无法安排三套注射桌凳及物品, 服务台只有两个 , 人力未能得到最
27、大限度的发挥。 如果门诊健全各项指标统 计, 积累资料 , 就可以较客观地掌握在本院服务半径内 ,在一定的人口密度下 , 所承受的患者源有多大 , 为医院建设和发展提供预见性资料。第五章 结束语排队现象是日常生活中经常会遇到的现象，排队论是专门研究带有随机因素，产 生拥挤现象的优化理论而发展的一门学科。在上述理论及实例运用中，充分体现了用 排队论模型求解的优越性。排队论应用十分广泛，虽然，在实际的应用中它还存在许 多的不足之处，众多的科学工作者都在这个领域，不懈努力，孜孜以求，相信随着这 些问题的不断的得到解决，排队论这门学科将不断的完善和进步，排队论必将更好的 应用到诸多领域中去，这必将为现代科技的进步，为国民经济的发展作出新的贡献。
