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

第一章 排队论问题的基本理论知识排队是日常生活中经常遇到的现象，本章将介绍排队论的一些基本知识和常见的 排队论的模型，使我们对排队论有一个基本的认识。1.1 预备知识下图是排队过程的一般模型：各个顾客由顾客源（总体）出发，到达服务机构（服务台、服务员）前排队等候接受服务，服务完成后离开。我们说的排队系统就是图中顾客源-顾客到达虚线所包括的部分。排队结构服务警。服务机构i离去A排队规则II排队系统示意图厂一般的排队系统都有三个基本组成部分：输入过程；排队规则；服务机构。1. 输入过程输入过程考察的是顾客到达服务系统的规律。可以用一定时间内顾客到达数 或前后两个顾客相继到达的间隔时间来描述，一般分为确定型和随机型两种。对 于随机型的情形，要知道单位时间内的顾客到达数或到达的间隔时间的概率分 布。2. 排队规则排队规则分为等待制、损失制和混合制三种。当顾客到达时，所有服务机构 都被占用，则顾客排队等候，即为等待制。在等待制中，为顾客进行服务的次序 可以是先到先服务，或后到先服务，或是随机服务和有优先权服务。如果顾客来 到后看到服务机构没有空闲立即离去，则为损失制。有些系统因留给顾客排队等 待的空间有限，因此超过所能容纳人数的顾客必须离开系统，这种排队规则就是 混合制。3. 服务机构可以是一个或多个服务台。服务时间一般也分成确定型和随机型两种。但大 多数情形服务时间是随机型的。 对于随机型的服务时间，需要知道它的概率分布。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）队长：系统中排队等待服务和正在服务的顾客总数，其期望值记为LS排队长（队列长）：系统中排队等待服务的顾客数，其期望值记为 Lg系统中顾客数=在队列中等待服务的顾客数+正被服务的顾客数（2）逗留时间：一个顾客在系统中停留时间，包括等待时间和服务时间，其其期望值记为 Ws ；等待时间：一个顾客在系统中排队等待时间 ,其期望值记为 Wg ；逗留时间=等待时间+服务时间（3）忙期：从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度；系统状态：即指系统中的顾客数；状态概率：用P （t）表示，即在t时刻系统中有n个顾客的概率；n要解决排队问题，首先要确定排队系统的到达间隔时间分布与服务时间分 布。要研究到达间隔时间分布与服务时间分布需要首先根据现有系统原始资料统 计出它们的经验分布，然后与理论分布拟合，若能对应，我们就可以得出上述的 分布情况。1、经验分布 经验分布是对排队系统的某些时间参数根据经验数据进行的统计分析，并依 据统计分析结果假设其统计样本的总体分布，选择合适的检验方法进行检验，当 通过检验时，我们认为时间参数的经验数据服从该假设分布。2、泊松分布 下面我们在一定的假设条件下，推出顾客的到达过程就是一个泊松过程。若设N(t)表示在时间区间0, t)内到达的顾客数(t0) , P Ct)表示在时间区n 1, 2间t,t )(t2tl)内有n(0)个顾客到达的概率，即12P t ,t = PN(t )-N(t) = n (t2tl, n0)n 1 221当p Ct)符合于下述三个条件时，我们说顾客到达过程就是泊松过程。n 1, 2( l )再不相重叠的的时间区间内顾客到达数是相互独立的。(2) 对于足够小的A t,在时间区间t, t+At)内有1个顾客到达的概率为P (t,t + At) = AAt+o(At)(入0是常数，称为概率强度)。1(3) 对充分小的A t,在时间区间t,t+At)内有2个或2个以上顾客到达的 概率是At 高阶无穷小，即Y P (t, t + At ) = o (At)nn=2为了求P (t)，即P(0, t)，需要研究它在时刻t到t+At时刻的改变量，也就 nn是要建立P (t)的微分方程。就可以得到：nC t P (t)=1t0 ,n=0,1,2,nn!负指数分布设T为时间间隔，分布函数为F (t)= PT t,即：F (t)= PT 0)，其概 0T0率密度函数为：f (t)=经fk (t0)。t dt由前知，入表示单位时间内顾客平均到达数，这里1/入表示顾客到达的平均间隔 时间,两者是吻合的。下面我们再谈一下服务时间的分布：对顾客的服务时间V,实际是系统处于忙期时两顾客相继离开系统的时间间隔， 一般地也服从负指数分布，即：F (t) = 1-0-九f (t)=卩伽。VV其中：卩表示单位时间内能被服务完成的顾客数，即平均服务率。1/卩表示一个顾k客的平均服务时间。令p =-则P称为服务强度。第二章 单服务员排队模型在自动存取款机服务中的应用2.1 理论分析1.稳态概率P (t)的计算n已知顾客到达服从参数为入的泊松过程，服务时间服从参数为口的负指数分布。在间刻t+A t,系统中有n个顾客不外乎有下列四种情况。情况时刻的t顾客区间(t, t+At)时刻t+At的顾客(t, t+At)的概率0, t+At的概率(略去 o (At)到达离去AnXXn1-入 At+o(At)1 口 At+o(At)Pn(t)(l-入 At)(1- 口 At)Bn+1XVn1-入 At+o(At) 口 At+o(At)Pn+1(t)(1-入At)( 口 At)Cn-1VXn入 At+o(At)1- 口 At+o(At)Pn-1(t)(入 At)(1-口 At)DnVVn入 At+o(At)口 At+o(At)Pn(t)(入 At)( 口At)由于这四种情况是互不相容的，所以Pn(t+At)应是这四项之和，将所有的高阶无 穷小合并，则有：P (t + At) P (t)(1 - XAt - pAt)+ P (t) pAt + P (t)XAt+oAtnnn+1nl令At-0,得关于Pn(t)的微分差分方程：匚(九p (t)+pp (t)(九+p)P (t)dtn 1n +1n当n=0时，只有表中的(A)、(B)两种情况。P (t + At)= P (1 九At)+ P (t)(1 九At) (pAt)0 0 1所以dP(t)=九P (t) + yP (t) _(九+ 卩)P (t)dtn-in+indPo(t) = pP (t)-九 P (t)I dt 10(1)(2)稳态时，Pn(t)与时间无关，可以写成Pn,它对时间的导数为0,所以由、两式得：九P +pP -(X + )P 二 0(3)n-1n+1n九P + pP 二 0(4)01上式即为关于Pn的差分方程。由此可得该排队系统的状态转移图:状态转换图这种系统状态(n)随时间变化的过程就是生灭过程，它可以描述细菌的生灭过程。得到：=P nP0(5)2P=- 1 (否则排队无限远，无法服务完)p(6)P =1- PP = (1- p). Pn n上式就是系统稳态概率，以它为基础可以算出系统的运行指标。2. 系统的运行指标计算(1) 系统中的平均顾客数(队长期望值Ls)：L =艺n-P =另n.(1p).pn =(0 P 0） = 1 P = p02.2 实例2.2.1 问题提出与模型说明问题提出顾客排队等待接受服务，在任何一个服务系统中都是不可避免的。在存取款机排 队等待取钱或存钱的排队问题也非常严重，为此, 这里拟用排队论的理论和方法, 建 立评价指标,通过实例来探究如何提高工作效率？如何使系统更加优化？模型说明某街道口只有一个自动存取款机，从而该种情况是单列单服务台的情况，即为M/M/1模型的情况。2.2.2 调查方法及数据处理调查内容（1）顾客到达时间。（2）服务时间。调查方法顾客到达的频率与时间段有关，一般在9： OOlO： 30和下午2： 304： 00顾客到 达率比其它的时间高。我们把时间分成两段，考虑08： 009： 00、9： OO一1O： 00的 情况，分别代表了一般情况和繁忙时的情况。（1）服务时间：顾客开始用自动存取款机到服务完成。（2）顾客到达时间：顾客进入排队系统排队。以上两项调查，抽样的时间均是分散的、随机的。不可连续和集中抽样。具体数据如下：其中，顾客编号i,到达时间T,服务时间S，到达间隔t，排队等待时间w。i i i i表1 08：009：00的统计123456789101112Ti028121925293442495460Si325731624294ti23476458756wi010110010003表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 （人;分钟）2、根据表2计算得：平均时间间隔为60 一 17 = 3.53（分钟;人） 平均到达率为16 一 60=0.27（人分钟）平均服务时间为57 一 16=3.56（分钟,；人）平均服务率为16 一 57=0.25 (人分钟)把以上两表结合起来为表3，分析服务时间的分布规律，求出均值和方差表3 服务时间和频数服务时间X12345679频率P27644221服务时间的期望值为：E( X )= X - p = (2 x 2 + 2 x 7 + 3 x 6 + 4 x 4 + 5 x 4 + 6 x 2 + 7 x 2 + 9 x1)+ 28 = 3.82服务率期望值：卩=28 +(2 x 2 + 2 x 7 + 3 x 6 + 4 x 4 + 5 x 4 + 6 x 2 + 7 x 2 + 9 x1)= 0.262.2.4 讨论理论上讲，顾客到达会形成泊松流，因为：(1)在不相重叠的时间内顾客到达数是 相互独立的，即无后效性；(2)对于充分小的时间区间内有一个顾客到达的概率与时刻 无关，而与区问长成正比；在我们把时问段分开之后来分析，这一点也是满足的；(3) 对于充分小的时间区间，有2个或2个以上顾客到达的概率极小。顾客到达满足以上三 个条件，形成泊松流；所以顾客到达率服从负指数分布。而服务时问可看作服从正态 分布。然而在统计数据比较少的情况下，并不能得出一一般规律，来精确的算出参数 (到达率)和(服务率)。本文对此问题只做简单的分析。从表1中可以看出，在8： 009： 00时间区问内，有12个顾客到达，其中有5 个顾客必须等待，平均等待W =(1 +1 +1 +1+3)一 12 = 0.58(分钟)。而在表2中可以得 q出，在9：0010：00时间区间内，有16个顾客到达，有11个顾客必须等待，平均 等待时间：W =(1 + 2 + 6 + 5 + 4+4+2+4+6+3+1)一 16 = 2.375(分钟)。q根据以上分析，在8： 009： 00时间区间内，顾客平均到达率0.2人./分钟，平均服务率是0.25人f分钟，在9： 00 1O： 00时问区问内分别为0.27人分钟和0.28人J分钟。可以看出，平均服务律是高于平均到达率的。但是，通过表3的数据分析，在8： 001O： OO时间区间内平均服务率为0.26人;分钟，由于表3中的数据量比较 大，所以更具有代表性。如果这样分析，平均服务率就小于9： 001O： OO的顾客平均 到达率027，这样就会使排队越来越长而直到高峰期过后才能得到缓解。我们认为在 这个系统中，当平均等待时间超过1分钟，系统被视为效率低下，而低于1分钟被视为 系统有闲置。通过以上分析，在9：0010：00时间区间内，等待问题比较严重，而在 8； 009： 00系统有闲置现象。现实中，合理的把等待时间控制在（1-61 + 8）内很难（8为很小的数）。2.3 MM1 模型中的最优服务率问题已知有设进入系统的顾客单位时间带来的损失为 c ,单位时间服务台每服务一位1顾客的服务成本为C，则单位时间总费用的期望值为:2C(P)= cL(|LI) + c |LI=12由 dC = c - 行 =0解得：土乞dL 2(L-X)2V c耳2由二 2 八 0 及 P= / L 1d L 2(L-入)3最优服务率为L* =九+ ;乞1V 2最优服务率L*随着进入系统的顾客数九和损失费c的增加而增加，随着服务成本 1c 的增加而减小。2某生产厂家有多台机器，每台机器连续运转的时间服从指数分布，平均为1小时， 每台故障机器的损失费为3200元/小时.有1个维修工人，每次维修时间服从指数分布， 每台故障机器的修理费用为10 0元/小时，求最优的每台机器维修时间。由题意知：最优服务率为：Xc3200卩*=九+ 1 = 1 += 5（台/小时）c2x100 2即最优的机器维修时间为：=1 = 0.2小时=12分钟L *5第三章 中式快餐店排队系统的优化3.1 理论分析当系统容量最大为N时，排队系统中多于N个的顾客将被拒绝。当N =1时，即 为瞬时制；Nf*时，即为容量无限制的情况。n0n=l,2, N-1时，也仍能成立。但当n=N时，有下面两种情况:情况时刻t的顾客区间t, t+A t时亥0 t+ At的顾客数AN无离去（肯定不到达）NBN-1一人到达（无离去）NP (t) 入 AtN-1P (t) (1-UA t)N概率P (t + At)二 P (t) - (1-必t) + P (t皿NNdP (t)N -dtN-1=-卩P (t) + 尢P (t)N-1其状态转移图为:N状态转换图在稳态情况下有:九 P + 卩 P = 00 1九P +yP -(九+ 卩)P = 0 n-1n +1n-卩P +尢P=0NN -11 P= 1-0解得 ：0 1 - P N+1,、. (pHl,nWN)P = 11 -P P nn 1 P N+1下面计算其运行指标(1) 平均队长 Ls：L =迓 n - Psnn=0迓上L1 - 0 N+1n=0(PHI)=1 - P yv= P(N +1) P N+11 一 p N+11 - p1 一 p N+1n=02)队列长(期望值)：L =迓(n 1)P = L - (1-P )qns0n =1当研究顾客在系统平均逗留时间和在队列中平均等待时间，要注意平均到达率九 是在系统中有空时的平均到达率，当系统已满是则到达率为 0，因此可以验证：有效到 达率九=卩(1-P)。e0(3) 顾客逗留时间(期望值)：LL 1W =s=q+ s 卩(1- P )九(1-P )卩0N(4) 顾客等待时间(期望值)：w = w - yqs /卩3.2 实例3.2.1 问题提出与模型分析问题提出 随着经济水平的提高,外出用餐的人越来越多,由于服务生产与消费的同步性、服 务的不可储藏性,以及顾客到达的随机性,让顾客进行排队等待是不可避免的。文中以学校附近一个中式快餐店为例,针对其周末晚上人满为患的现象并结合工作日的客流 状况对其排队系统进行研究,进而提出优化策略。模型分析本文中小型饭店的排队模型是单队单服务台模型，即为M/M/1模型。由于快餐店容 量有限为7桌，所以其排队模型M/M/1/K/FCFS（K=7）,为单服务台模型：顾客的相继到达 时间服从参数为九的的负指数分布（顾客到达过程为Poisson流），服务时间服从参数 为口的负指数分布，服务台数为1,系统空间为K,客源容量无限，实行先到先服务的排 队规则。3.2.2 数据调查与模型求解调查方法：对该中式快餐店客流量进行连续一周人工调查统计,由于其主要客源是学生,所以 分别调查周末和工作日两种情况下的客流量变化。对每晚（客流高峰期）两小时的顾 客数进行调查记录。数据处理：根据调查数据可以得出：平均到达率九（周末）=3（人/小时）九（工作日）=2（人小时）根据统计服务员对每位顾客的服务时间可得该中式快餐店的平均服务率为卩=4 （人小时）通过计算可以得出：1、周末的服务指标23服务强度p=一 = 一= = 0.78卩 4没有顾客的概率P二0二 0.2778系统中的平均顾客数L- PS 1 - P 1 - p N+1队列中等待的平均顾客数L - L -（1-P ）-1.39（人）q s0系统中顾客逗留时间的期望值W =rs严0.73（小时）=43.8（分钟）s 卩（1-P ）0在队列中排队等待时间的期望W = W -丄=0.73-0.24 = 0.49（小时）=29.4（分钟）q s 卩2、工作日的服务指标服务强度p= = 2=0.5 卩 41 - 2/没有顾客的概率P =（令=0.50系统中的平均顾客数L- PS 1 - P1 - p N+1队列中等待的平均顾客数L - L - （1 - P ）- 0.37（人）q s0系统中顾客逗留时间的期望值W -匕-0.44（小时）=20.4（分钟）s P（1-P 丿0在队列中排队等待时间的期望W - W -丄-0.44-0.24 - 0.2（小时）-12（分钟）q s 卩3.2.3 讨论一般情况下,顾客等待 1015 分钟是可以忍耐的，上述情况下顾客在周末的等待 时间为29.4 分钟，这很容易造成顾客的不满。下面我们将从两个角度对该快餐店排队 系统进行优化：（1） 服务效率的提高 中式饭店的服务流程包含很多细节,内容也非常广泛。如果我们认真对其流程进行 调查研究,找出服务的潜在失败点和等待点并着手进行流程优化设计,就能大大提高服 务效率。通过观察并进行对比发现该快餐店服务效率卩-4存在问题，仍可提高。该饭 店也通过引进标准化设备并对服务人员进行培训以实行标准化流程的规范操作,带来 效率和品质的提升。服务效率的提高必然会使顾客排队等待的时间降低，这里不再作 定量的分析。2） 在忙期适当的增加桌子这也是排队系统的常规优化方案设计。在上例的分析中我们看到在周末排队等候 的队列较长，等待时间也较长，这不但会使顾客产生不满，而且一些顾客由于不愿等 待如此长的时间而离开，从而使饭店蒙受损失，适当的增加桌子会使队长和等待时间 都有所增加。第四章 排队论在门诊注射室管理中的应用4.1 理论分析标准的M/M/C模型与标准的M/M/1 模型的各特征规定相同，另外，各服务台工 作是相互独立且平均服务率相同，即u1=u2=u3=-=uc=u，于是整个服务机构的平 均服务率为：c 口（n三c时），n 口（nc时）。2 2令p=，只有当 c时，为c，故可得差分方程：卩 P = 2 P(1WnWc) (nc)1 0c), P =-( n C ! Cn-c 卩系统的运行指标为：=L +?qL=q (1.58)21+.0!1!2!1 - 0.79K +丄.C!1-丿-1二 0.12反映患者排队情况指标1、队列长：等待注射的患者数。期望值 L =2.68 （人）q C!（1- P）2 02、队长：队列长+正在接受注射的患者数。期望值 L = L + C p = 2.68+1.58 = 4.26 （人）sq3、平均等待时间心=篇=釘7 （分钟）4、平均逗留时间W = W + 丄=3.77 + 2.22 = 5.99 (分钟)s q -现假设只配备一名护士负责注射,即C=1 那么服务强度P=-二需心。在排队 论中，当p 1时，说明系统处于超负荷状态，将会持续出现排队成龙现象。故此时不 可取的。4.2.4 讨论1、排队论的应用， 可以为合理使用人力、物力提供客观依据。由下表可见注射室现有的服务台C=2时，注射室有71%的时间被利用，在等注射的 人数为2.68个，等待时间为3.77分钟。如果服务台增为3个时，注射室将53%的时间被 利用， 排队等待的平均人数小于1，平均等待时间不足半分钟。若服务台增为4 个， 排 队人数和排队时间几乎为0 ， 但是注射室被利用的时间只有39% ， 61%的时间处于空闲， 造成人力浪费。因此， 设两个服务台， 基本合理，若条件允许， 设三个服务台， 将是最佳选 择。指标名称服务台个数（C）234服务强度p0.790.530.39空闲概率P00.120.190.20等待人数Lq2.680.310.05等待时间Wq3.770.440.072、排队论的应用， 可以建立和完善评价注射室运行效率和服务质量的数量指标。1）患者排队人数及排队时间的指标：据心理学调查结果表明， 在就诊中， 等待时 间是患者最敏感的问题， 长时间排队会形成心理压力，产生不良情绪， 是患护 产生矛盾冲突的重要原因。同时， 由于排队所浪费的时间称为误工费用， 据有 关部门报道， 我国每一名全民所有制工业企业职工日创产值38.67元， 每耽误 一小时， 国家损失4.83 元。因此， 无论从心理因素还是经济因素， 等待时间都 应成为反映注射室服务质量的指标之一。2）服务时间指标：患者接受注射的时间，不同于卖票、收款等服务， 不能越快越 好。因此也应成为评价服务质量的另一项指标， 以免求速度请效率。3、排队论的应用， 为决策人员制定工作规划提供预见性资料。注射室现配有三名护士, 但因建筑面积狭窄, 无法安排三套注射桌凳及物品, 服务台只有两个, 人力未能得到最大限度的发挥。如果门诊健全各项指标统 计, 积累资料, 就可以较客观地掌握在本院服务半径内,在一定的人口密度下, 所承受的患者源有多大,为医院建设和发展提供预见性资料。第五章 结束语排队现象是日常生活中经常会遇到的现象，排队论是专门研究带有随机因素，产 生拥挤现象的优化理论而发展的一门学科。在上述理论及实例运用中，充分体现了用 排队论模型求解的优越性。排队论应用十分广泛，虽然，在实际的应用中它还存在许 多的不足之处，众多的科学工作者都在这个领域，不懈努力，孜孜以求，相信随着这 些问题的不断的得到解决，排队论这门学科将不断的完善和进步，排队论必将更好的 应用到诸多领域中去，这必将为现代科技的进步，为国民经济的发展作出新的贡献。