排队论及应用举例-

《排队论及应用举例-》由会员分享，可在线阅读，更多相关《排队论及应用举例-（25页珍藏版）》请在金锄头文库上搜索。

1、第六章 排队论关键词排队（Queue）指数分布（Exponential Distribution）单通道、单阶段（Single Channel, single Phase）排队系统（Queuing System）泊松分布（Poisson Distribution）多通道、多阶段（Multichannel, Multiphase ）到达率（Arrival Rate）服务率（Service Rate）有限队列（Finite Queue）一、排队问题的经济含义n 在日常经济生活中，经常遇到排队现象，如：在超市等待结帐、工厂中等待加工 的工件或待修理的机器、开车上班等，排队论是运作管理中重要的方法，它

2、是计 划、工作设计、存货控制以及其他问题的基础。n 每一个排队事例的核心问题就是对不同因素作权衡决策，管理者必须衡量为提供 更快捷服务而增加的成本和等待费用之间的关系。n 一种情况是：直接对成本进行权衡决策，例如考虑到顾客排队等待可以增加设备 ，就要权衡增加设备的成本与多服务顾客所带来的价值的大小，决策比较直观和 容易；另一种情况是：排队问题是对医院床位的需求，可以估算增加床位带来的房屋建 筑、附加设备以及增加的维护费用等成本，但衡量标准时什么？因为用金钱成本 来度量病人对病床的需求显然是徒劳的，尽管可以估计出医院因病床不足会损失 多少收入，但无法估计病人因得不到适当的医护所遭受的损失。n 解

3、决排队问题的基本目标是平衡等待成本与增加资源引起的成本之间的关系。对 于一个服务系统来说，这意味着若要给顾客创造很短的等待时间，服务台的利用 率将回降低。排队问题中一个关键问题是用什么样的程序或优先规则来选择下一 个产品或顾客作为服务对象。成本效益平衡服务成本总成本最小值等待成本最佳能力成 本 服务设施能力图6-1 服务成本与等待成本的关系如图6-1所示，是一个典型（稳定）的客运 问题中的权衡。等待成本随着服务能力的增大而减小，可 以用负指数曲线描述；服务成本可以简单地 用线性变化表示；总成本或复合成本则是U 型曲线。所以，理想的最优化（最小）成本 位于服务成本曲线和等待成本曲线的交点上 。

4、排队问题的实际应用顾客到达服务需求量 到 达 的 数 目时间服务 时间普通 能力时间 图6-2 到达与服务的关系如图6-2表示的是到达某一服务机构（银 行）的人数和对这一机构服务的需求（信 贷人员）。在服务系统营业过程中，每一小时到达 系统的顾客人数是一个很重要的变量。从 提供服务的观点来看，顾客对于服务的需 求是不断变化的，而且经常超过正常的服 务能力。可以通过不同的方法对到达人数 加以控制。如特殊顾客通道、临时加班、 设定等待座位数等。一般服务时间受到服 务速度、机器运转速度的影响，另外，服 务时间也会因使用的工具、材料或计划的 不同而变化。二、排队系统服务系统服务机构等待队列离开顾客源图

5、6-3 排队系统的组成如图5-3所示，一个排队系统有三个主要部分 组成： 一是：顾客源和顾客到达系统的方式 二是：服务系统 三是：顾客离开系统的方式(是否回到顾客源？)顾客到达到达服务系统的顾客可以分为两类：有限总体和无限总体。1. 有限总体。要求服务的顾客数是有限的，通常是排成一队的。顾客总体中的某一位离开其位置 （如一台设备停机待修理），顾客就少一个，同时减少了下一次要求服务的概率。相反，当被服 务的顾客回到顾客总体中，总体人数对服务需求的概率也就增加了。2. 无限总体。对于服务系统来说顾客数量足够大，由于人数增减而引起的总体规模的变化不会对 系统的概率分布产生显著的影响。 3. 顾客到达

6、的分布。这是一个到达率或单位时间到达数的问题。固定到达的分布呈周期性的，即 相继到达的两个顾客之间的时间间隔几乎相同。在生产系统中，通常运用一些技术控制顾客在固 定的时间间隔内到达。多数情况下，顾客的到达呈随机分布。首先，分析相邻两个顾客到达的时间间隔是否服从某些统计分布？通常假定相邻两次到达的时 间间隔服从指数分布其次，在设定时间长度为T，然后确定在时间T段内有多少顾客到达并进入系统？通常假定单位 时间到达的人数服从泊松分布。4. 第一种情况：指数分布。当顾客已完全随机 方式到达服务机构时，相邻到达时间间隔服 从指数分布。如图5-4所示。其概率密度函 数为：（6-1）式中 代表单位时间段到达

7、的顾客数量。 图5-4中曲线下方的阴影区域即为函数5-1在正数范围内的积分，即 。通过这种方法，就可以计算出某一特定时间顾客到达的概率。例如：在顾客是单个到达服务系统（ ）时，可通过两种方法得到表5-1。一种是根据 式，另一种可以应用负指数分布 。表的第二栏是下一个到达的顾客时间间隔超过 分钟的概率；第三栏为下一个顾客到达时间小于 分钟的概率。 图6-4 指数分布（1） （2） （3）下一个顾客将在 下一个顾客将在小于 t 分钟 大于t分钟内 分钟内到达的概率到达的概率 (3)=(1)-(2) 0 1.00 00.5 0.61 0.391.0 0.37 0.631.5 0.22 0.782.0

8、 0.14 0.86期望值方 差5. 第二种情况:泊松分布。主要针 对某一时段T内有n人到达的概 率，到达过程是随机的，则服 从泊宋分布。如图5-5所示。计 算公式为：（6-2）式5-2表示在T时间内有n个顾客 到达的概率。例如，如果一个 系统的平均到达率是每分钟有3 个顾客到达（ ），要求1 分钟内有5个人到达的概率为：.149.168.224.102.050.224.20.10.05期望值方 差平滑曲线12345681012时间T内 有n人到 达的概率到达人数n图6-5 泊松分布（ ）0这就是说，在任何一分钟的间隔期内有5人到达的概率是10.1%。泊松分布是一类离散型 的分布，但通常用一条

9、平滑曲线来表示（n越大，曲线越平滑）。在这个实例中，n指的是 到达系统的人熟，因而该分布是离散的，且必须为整数。排队系统 1.队列 考虑的因素：队长、队列数、排队规则 2.队长 无限队列：即指相对于服务系统来说是相当长的队列。如：堵塞在立交桥上的车辆 、绕这街道排列成队购买商品的顾客等。有限队列：是指由于法律或实际空间特点制约， 排队等待服务的队长受到限制。如：停车厂、加油站等，但是有可能出现到达后离开，过 一会有可能再来或到其他地方寻求服务。这是有限总体条件下的两种不同表现。 3.队列数 单列队是指只有一个队列。多列队指排在两个或两个以上服务台前的多个单列队 ，或者指在中间某点汇集的多个单列

10、队。多列队的缺点是如果前面的几个服务时间短或者 那些在其他队的顾客需要短服务时间时，到达的顾客将会挪动队列。 4.排队规划 是指决定队列中顾客接受服务次序的一个或一系列优先法则。直接影响着队列 中顾客人数、平均等待时间、等待时间变化范围以及服务设施的效率等。在使用任何优先法则时，两大现实问题： 一是确保顾客了解并遵守法则； 二是保证有一个能使雇员对队列进行管理的系统。排队规则先来先服务最短过程时间预订优先紧急优先最优顾客优先其 他最大需求优先最大盈利优先5.服务时间分布 在排队问题中，服务率通常是指单位时间内服务台完成服务的顾客数，而不是指每位顾客的服务时间。固定服务时间是指每次服务的 时间完

11、全相同，这仅限于机器受控运作。当服务时 间比较随机时，则近似指数分布，一般用 作为 每时间段内被服务的平均顾客数。6.队列结构 见图5-6所示7.单通道、单阶段：最简单的队列结构形式。用简单的公式可以解决到达人数和服务时间的 标准分布问题。如单人理发店。 8.单通道、多阶段：由一系列以非常标准的顺序进行的服务构成。如：洗车服务的吸尘、打 湿、冲洗、晾干、洗车窗和停车。重要的因素是该服务由多少个步骤组成，在各个不同步 骤中又分别形成了队列。 9.多通道、单阶段：如：银行的出纳窗口、大型商场的收银台等。每个顾客不均匀的服务时 间会引起队列流动不均匀，导致某些顾客先于早到的顾客接受服务，一定程度上影

12、响顾客 挪动队列。为了保证顾客按到达时间顺序接受服务，则要排成一个单队，当一个服务台空 出来时，队列最前面的顾客就可以去接受服务，如银行自动抽号排队。最大的问题在于需 要对队列进行刻板的控制以维持秩序和引导顾客到空闲的服务台。 10. 多通道、多阶段：服务由多个步骤组成，完成每个服务步骤有两个或多个服务台，一般可 有多个顾客同时被服务。如：医院里接待病人的系统：挂号（有多个窗口，病历上填写病 人信息）、就诊（同一科室有多位大夫）、化验、检查（同一化验、检查有多个窗口和设 施）、回复就诊（同一科室有多位大夫）、处方划价（多个窗口）、缴费（多个窗口）、 取药（多个窗口）。 11. 混合型：两种情况

13、：1）多通道单通道结构；2）交错通道结构。考虑到阶段问题，如：单阶段服务的多通道变成了单通道（如过桥时多队变成一队）；多阶段服务的多通道变成 了单通道（如多条子装配线汇成一条主装配线）上述形式的选择，一方面依赖于被服务顾客数；另一方面，依赖于服务顺序的特殊要求。队列结构单阶段多通道单通道混合式多阶段单阶段多阶段单阶段多阶段从多通道到单通道交 错 通 道图5-6 队列结构队列结构单阶段多通道单通道混合式多阶段单阶段多阶段单阶段多阶段从多通道到单通道交 错 通 道图6-6 队列结构顾客离开“经常发生事件（recurring-common-cold case）”：顾客回到顾 客源，马上成为一名新的顾

14、客要求服务。如：机器例行修理后重新 使用，可能再次出现故障而需要修理。“只发生一次事件（appendectomy-only once case）”：顾客重 新要求服务的可能性极小，即不可能重新要求服务。如：机器进 行彻底检查和修理后，在一段时间内不会重新维修。顾客接受服务后，离 开的情况可能有两种顾客源有限时，对回头客服务的任何改变都会改变顾客到达率，引起排队问题的特征的改变。 三、排队模型问题一：顾客等待。银行希望知道有多少顾客在等待其服务到车（drive-in）出纳员的服务？出纳员的效率 是多少？如果要求在95%的时间内，任一时刻系统中不超过三辆车，则其服务率应达到什 么水平？ 问题二：设

15、备选择。公司有三中不同的设备可以提供同一种服务，设备功率越大，成本也越高，但服务速度 越快。因此作决策时，成本与收入是紧密相联的。 问题三：服务人数决策。经销公司的一个销售部门必须决定一个柜台雇佣多少职员。职员越多，成本也越高，但 服务等待时间的减少能带来部分成本的节约。 问题四：有限总体。前述都是无限总体，而对于有限顾客总体，如：车间有若干台设备，一名维修工负责4 台设备的运转，在充分考虑设备闲置成本和维修工的服务成本的基础上，决定应该雇佣多 少名维修工？四种典型 的问题模型分布服务务 阶阶段顾顾客 源到达人 数分布排队规则队规则服务时务时 间间分布允许许的 队队列长长度典型例子1单通 道单一无限泊松先来先服 务指数无限银行出纳员服务系统；单 道收费桥系统2单通 道单一无限泊松先来先服 务常数无