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

实用标准文档第一章 排队论问题的基本理论知识排队是日常生活中经常遇到的现象，本章将介绍排队论的一些基本知识和常见的排队论的模型，使我们对排队论有一个基本的认识。1.1 预备知识下图是排队过程的一般模型：各个顾客由顾客源（总体）出发，到达服务机构（服务台、服务员）前排队等候接受服务，服务完成后离开。我们说的排队系统就是图中虚线所包括的部分。排队结构服务机构顾客源顾客到达排队规则服务规则离去 排队系统示意图 一般的排队系统都有三个基本组成部分：输入过程；排队规则；服务机构。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）队长：系统中排队等待服务和正在服务的顾客总数，其期望值记为；排队长（队列长）：系统中排队等待服务的顾客数，其期望值记为；系统中顾客数=在队列中等待服务的顾客数+正被服务的顾客数（2）逗留时间：一个顾客在系统中停留时间，包括等待时间和服务时间，其其期望值记为； 等待时间：一个顾客在系统中排队等待时间,其期望值记为； 逗留时间=等待时间+服务时间（3）忙期：从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度；系统状态：即指系统中的顾客数；状态概率：用表示,即在t时刻系统中有n个顾客的概率；要解决排队问题，首先要确定排队系统的到达间隔时间分布与服务时间分布。要研究到达间隔时间分布与服务时间分布需要首先根据现有系统原始资料统计出它们的经验分布，然后与理论分布拟合，若能对应，我们就可以得出上述的分布情况。1、经验分布经验分布是对排队系统的某些时间参数根据经验数据进行的统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数的经验数据服从该假设分布。2、泊松分布下面我们在一定的假设条件下，推出顾客的到达过程就是一个泊松过程。若设表示在时间区间0,t)内到达的顾客数(t0)，表示在时间区间(t2t1)内有n(0)个顾客到达的概率，即 （t2t1，n0）当符合于下述三个条件时，我们说顾客到达过程就是泊松过程。(1)再不相重叠的的时间区间内顾客到达数是相互独立的。(2)对于足够小的t，在时间区间t，t+Dt)内有1个顾客到达的概率为（0 是常数，称为概率强度）。(3)对充分小的t,在时间区间t,t+t）内有2个或2个以上顾客到达的概率是t一高阶无穷小，即为了求，即，需要研究它在时刻t到t+t时刻的改变量，也就是要建立的微分方程。就可以得到： t0，n=0,1,2,负指数分布设T为时间间隔，分布函数为，即：。此概率等价于在0，t）区间内至少有1个顾客到达的概率。没有顾客到达的概率为： ，则 （t0），其概率密度函数为： （t0）。由前知，表示单位时间内顾客平均到达数，这里1/表示顾客到达的平均间隔时间，两者是吻合的。下面我们再谈一下服务时间的分布：对顾客的服务时间，实际是系统处于忙期时两顾客相继离开系统的时间间隔，一般地也服从负指数分布，即： 。其中：m表示单位时间内能被服务完成的顾客数，即平均服务率。1/m表示一个顾客的平均服务时间。令则称为服务强度。第二章 单服务员排队模型在自动存取款机服务中的应用2.1理论分析1. 稳态概率的计算已知顾客到达服从参数为的泊松过程，服务时间服从参数为的负指数分布。在间刻t+t，系统中有n个顾客不外乎有下列四种情况。情况时刻的t顾客区间(t, t+Dt)时刻t+Dt的顾客(t, t+Dt)的概率0, t+Dt的概率(略去o(Dt)到达离去Ann1-Dt+o(Dt)1Dt+o(Dt)Pn(t)(1-Dt)(1-Dt)Bn+1n1-Dt+o(Dt)Dt+o(Dt)Pn+1(t) (1-Dt)(Dt)Cn-1nDt+o(Dt)1-Dt+o(Dt)Pn-1(t) (Dt)(1-Dt)DnnDt+o(Dt)Dt+o(Dt)Pn(t) (Dt)(Dt)由于这四种情况是互不相容的，所以Pn(t+t)应是这四项之和，将所有的高阶无穷小合并，则有： 令t0，得关于Pn(t)的微分差分方程：当n=0时，只有表中的（A）、（B）两种情况。 (1)所以 (2)稳态时，Pn(t)与时间无关，可以写成Pn， 它对时间的导数为0，所以由(1)、(2)两式得： (3) (4)上式即为关于Pn的差分方程。由此可得该排队系统的状态转移图：这种系统状态(n)随时间变化的过程就是生灭过程,它可以描述细菌的生灭过程。得到： (5) (否则排队无限远，无法服务完) (6)上式就是系统稳态概率，以它为基础可以算出系统的运行指标。2. 系统的运行指标计算(1) 系统中的平均顾客数（队长期望值Ls）： (01) (7)(2) 队列中等待的平均顾客数Lq（队列长期望值）： (8) (3) 顾客在系统中的平均逗留时间Ws： (4)顾客在队列中的等待时间的期望值： 3. 系统的忙期与闲期：系统处于空闲状态的概率：系统处于繁忙状态的概率：2.2实例2.2.1 问题提出与模型说明问题提出顾客排队等待接受服务，在任何一个服务系统中都是不可避免的。在存取款机排队等待取钱或存钱的排队问题也非常严重，为此, 这里拟用排队论的理论和方法, 建立评价指标,通过实例来探究如何提高工作效率？如何使系统更加优化？ 模型说明某街道口只有一个自动存取款机，从而该种情况是单列单服务台的情况，即为M/M/1模型的情况。2.2.2 调查方法及数据处理调查内容（1）顾客到达时间。（2）服务时间。调查方法顾客到达的频率与时间段有关，一般在9：00lO：30和下午2：3O一4：00顾客到达率比其它的时间高。我们把时间分成两段，考虑08：009：00、9：OO一1O：00的情况，分别代表了一般情况和繁忙时的情况。（1）服务时间：顾客开始用自动存取款机到服务完成。 （2）顾客到达时间：顾客进入排队系统排队。以上两项调查，抽样的时间均是分散的、随机的。不可连续和集中抽样。具体数据如下：其中，顾客编号i，到达时间，服务时间，到达间隔，排队等待时间。表1 08：009：00的统计12345678910111202812192529344249546032573162429423476458756010110010003表2 09：0010：00的统计123456789101112131415100269111519222836414548505660324723325165432524334436854326401026544000246312.2.3模型求解1、根据表1计算得：平均时间间隔为平均到达率为平均服务时间为平均服务率为2、根据表2计算得：平均时间间隔为平均到达率为平均服务时间为平均服务率为把以上两表结合起来为表3，分析服务时间的分布规律，求出均值和方差。表3 服务时间和频数服务时间X12345679频率P27644221服务时间的期望值为：服务率期望值：2.2.4 讨论理论上讲，顾客到达会形成泊松流，因为：(1)在不相重叠的时间内顾客到达数是相互独立的，即无后效性；(2)对于充分小的时间区间内有一个顾客到达的概率与时刻无关，而与区问长成正比；在我们把时问段分开之后来分析，这一点也是满足的；(3)对于充分小的时间区间，有2个或2个以上顾客到达的概率极小。顾客到达满足以上三个条件，形成泊松流；所以顾客到达率服从负指数分布。而服务时问可看作服从正态分布。然而在统计数据比较少的情况下，并不能得出一一般规律，来精确的算出参数 (到达率)和(服务率)。本文对此问题只做简单的分析。从表1中可以看出，在8：009：00时间区问内，有l2个顾客到达，其中有5个顾客必须等待，平均等待。而在表2中可以得出，在9：0010：00时间区间内，有16个顾客到达，有11个顾客必须等待，平均等待时间：。根据以上分析，在8：009：00时间区间内，顾客平均到达率，平均服务率是，在9：00 1O：00时问区问内分别为和。可以看出，平均服务律是高于平均到达率的。但是，通过表3的数据分析，在8：001O：OO时间区间内平均服务率为，由于表3中的数据量比较大，所以更具有代表性。如果这样分析，平均服务率就小于9：001O：OO的顾客平均到达率027，这样就会使排队越来越长而直到高峰期过后才能得到缓解。我们认为在这个系统中，当平均等待时间超过1分钟，系统被视为效率低下，而低于1分钟被视为系统有闲置。通过以上分析，在9：0010：00时间区间内，等待问题比较严重，而在8；009：00系统有闲置现象。现实中，合理的把等待时间控制在内很难(为很小的数)。2.3 MM1模型中的最优服务率问题已知有设进入系统的顾客单位时间带来的损失为,单位时间服务台每服务一位顾客的服务成本为,则单位时间总费用的期望值为：由 解得：由 及 最优服务率为最优服务率随着进入系统的顾客数和损失费的增加而增加,随着服务成本的增加而减小。某生产厂家有多台机器,每台机器连续运转的时间服从指数分布,平均为1小时,每台故障机器的损失费为3200元/小时.有1个维修工人,每次维修时间服从指数分布, 每台故障机器的修理费用为100元/小时,求最优的每台机器维修时间。由题意知：最优服务率为： 即最优的机器维修时间为：第三章 中式快餐店排队系统的优化3.1 理论分析当系统容量最大为N时，排队系统中多于N个的顾客将被拒绝。当N=1时，即为瞬时制；N时，即为容量无限制的情况。 现在研究系统中有n个顾客的概率. 对于，前面的式子仍然成立，当n=1,2,N-1时，也仍能成立。但当n=N时，有下面两种情况：情况时刻t的顾客区间t, t+t时刻t+t的顾客数概率AN无离去（肯定不到达）NPN(t)(1-t)BN-1一人到达（无离去）NPN-1(t)t其状态转移图为:在稳态情况下有：解得 ： (1,nN) 下面计算其运行指标：(1) 平均队长Ls： (1) （2）队列长（期望值）：当研究顾客在系统平均逗留时间和在队列中平均等待时间，要注意平均到达率 是在系统中有空时的平均到达率，当系统已满是则到达率为0，因此可以验证：有效到达率 。（3）顾客逗留时间（期望值）：（4）顾客等待时间（期望值）：3.2 实例3.2.1 问题提出与模型分析问题提出随着经济水平的提高,外出用餐的人越来越多,由于服务生产与消费的同步性、服务的不可储藏性,以及顾客到达的随机性,让顾客进行排队等待是不可避免的。文中以学校附近一个中式快餐店为例,针对其周末晚上人满为患的现象并结合工作日的客流状况对其排队系统进行研究,进而提出优化策略。模型分析本文中小型饭店的排队模型是单队单服务台模型，即为M/M/1模型。由于快餐店容量有限为7桌，所以其排队模型M/M/1/K/FCFS(K=7),为单服务台模型：顾客的相继到达时间服从参数为的的负指数分布(顾客到达过程为Poisson 流)，服务时间服从参数为的负指数分布,服务台数为1，系统空间为K，客源容量无限,实行先到先服务的排队规则。3.2.2数据调查与模型求解调查方法：对该中式快餐店客流量进行连续一周人工调查统计,由于其主要客源是学生,所以分别调查周末和工作日两种情况下的客流量变化。对每晚（客流高峰期）两小时的顾客数进行调查记录。数据处理：根据调查数据可以得出：平均到达率 根据统计服务员对每位顾客的服务时间可得该中式快餐店的平均服务率为：通过计算可以得出：1、周末的服务指标服务强度没有顾客的概率系统中的平均顾客数队列中等待的平均顾客数系统中顾客逗留时间的期望值在队列中排队等待时间的期望2、工作日的服务指标服务强度没有顾客的概率系统中的平均顾客数队列中等待的平均顾客数系统中顾客逗留时间的期望值在队列中排队等待时间的期望3.2.3讨论一般情况下,顾客等待1015分钟是可以忍耐的，上述情况下顾客在周末的等待时间为29.4分钟，这很容易造成顾客的不满。下面我们将从两个角度对该快餐店排队系统进行优化：（1） 服务效率的提高中式饭店的服务流程包含很多细节,内容也非常广泛。如果我们认真对其流程进行调查研究,找出服务的潜在失败点和等待点并着手进行流程优化设计,就能大大提高服务效率。通过观察并进行对比发现该快餐店服务效率存在问题，仍可提高。该饭店也通过引进标准化设备并对服务人员进行培训以实行标准化流程的规范操作,带来效率和品质的提升。服务效率的提高必然会使顾客排队等待的时间降低，这里不再作定量的分析。（2） 在忙期适当的增加桌子这也是排队系统的常规优化方案设计。在上例的分析中我们看到在周末排队等候的队列较长，等待时间也较长，这不但会使顾客产生不满，而且一些顾客由于不愿等待如此长的时间而离开，从而使饭店蒙受损失，适当的增加桌子会使队长和等待时间都有所增加。第四章 排队论在门诊注射室管理中的应用4.1 理论分析标准的M/M/C模型与标准的M/M/1模型的各特征规定相同，另外，各服务台工作是相互独立且平均服务率相同，即1=2=3=c=，于是整个服务机构的平均服务率为：c(nc时) ，n(nc时，为c，故可得差分方程： (1nc) (nc)这里： ， 1利用递推法解该差分方程可求得状态概率为：当(nc), 当(nc)， 系统的运行指标为：4.2实例4.2.1 问题提出排队论, 就是对排队现象进行数学研究的理论,也称随机服务理论, 是运筹学中一个独立的分支。作为一种工具或方法, 已在许多行业的管理领域包括医院的管理领域应用。门诊注射室的服务工作, 是一种随机性服务, 即患者的到达时间、到达数量、注射所用时间, 都是一种随机现象。这种服务以什么指标才能比较客观地表示、反映注射室的工作质、工作效率？如何评价注射室的人员、设备配备的合理性？为此, 笔者拟用排队论的理论和方法, 建立评价指标, 为寻求既不使患者排队成龙, 又不浪费医院人力物力的最优方案,提供科学依据, 使注射室管理从经验管理转为科学管理。4.2.2 调查方法及数据处理调查内容：（1）单位时间内到达的患者数。（2）服务时间。调查方法(1)服务时间：从某患者进人注射室开始记时, 到该患者接受注射后走出注射室止。共随机记录了593人次的服务时间。(2)单位时间内到达的患者数：以5分钟为一个时间单位,任意选取若干个时间单位，记录每个5分钟到达的患者数。共随机抽取了168个时间单位。以上两项调查，抽样的时间均是分散的、随机的，不可连续和集中抽样。调查资料经统计处理后如下：1、 单位时间内到达的患者数单位时间（5分钟）内到达的患者数（人）频数概率060.041150.092300.183340.204430.265160.096100.06790.05840.02910.01合计1681.002、 服务时间服务时间(分钟)频数概率11700.2922030.3431520.264560.09560.01660.01合计5931.00经曲线拟合检验, 服务时间的概率分布服从负指数分布, 单位时间内到达患者数的概率分布服从泊松分布。从而求出排队系统的两个重要参数, 患者平均到达率和平均服务率。又因注射室内有两个注射凳服务台C=2，故符合排队论中M/M/C型排队模型。应用M/M/C型计算公式计算各项指标。4.2.3模型求解（1）基本参数 1、患者平均到达率 2、平均服务率（2）注射室运行状态指标（C=2） 1、服务强度说明注射室有79%的时间是忙期，21%的时间是空闲的。2、空闲概率：即注射室没有病人的概率。 （3）反映患者排队情况指标 1、队列长：等待注射的患者数。 期望值 2、队长：队列长+正在接受注射的患者数。 期望值 3、 平均等待时间 4、平均逗留时间现假设只配备一名护士负责注射,即C=1,那么服务强度。在排队论中，当时，说明系统处于超负荷状态, 将会持续出现排队成龙现象。故此时不可取的。4.2.4 讨论1、排队论的应用, 可以为合理使用人力、物力提供客观依据。由下表可见注射室现有的服务台C=2时，注射室有71%的时间被利用，在等注射的人数为2.68个，等待时间为3.77分钟。如果服务台增为3个时，注射室将53%的时间被利用, 排队等待的平均人数小于1，平均等待时间不足半分钟。若服务台增为4 个, 排队人数和排队时间几乎为0 , 但是注射室被利用的时间只有39% , 61%的时间处于空闲, 造成人力浪费。因此, 设两个服务台, 基本合