M12排队论分解.ppt

Poisson过程与排队论模型 1 到银行取钱，发现前面有几十个人在排着队，你掉头就走：不能忍受啊！怎么不多开几家银行、再增加几个服务窗口啊！ 假如你是工作人员，你觉得应根据什么来决定是否需要开设新的银行或增加新的服务窗口——要知道一次的排队人多具有随机性（偶然性）啊。 2 银行一般都有几个服务窗口，过去是顾客每个窗口分别排队等待服务，而现在几乎都改为叫号制，这相当于多个窗口只排一队的服务规则。银行为什么要这么做? 有什么好处？ 引例 排队是日常生活中经常遇到的现象，如顾客到商店购物，病人到医院看病等等，常要遇到排队。 排队的目的是要求另外的人或事物为其服务，而一旦不能立即被服务就必然形成排队。 这种现象不仅在个人日常生活中出现，电信局的占线问题，车站、码头等交通枢纽的车船堵塞和疏导，故障机器待修等都是有形无形的排队现象。 研究这些排队现象的规律的学科就是排队论，也叫随机服务系统。 主要内容 一、排队论的几个基本概念 排队可以是有形的，也可以是无形的。 如几个顾客打电话到出租车站要车，如果出租车站无足够车辆，则部分顾客只得在要车处等待，他们分散在不同地方，形成一个无形的排队序列。 排队论就是研究排队现象及其规律的一门学科，是运筹学的一个分支。如同数学的特质那样，排队论研究的内容比我们感觉中的排队现象要广泛得多，它是研究那些本质上都有排队特征的一类现象。具体表现在： 到达的顾客 要求服务内容 服务机构 1.不能运转的机器 2.修理技工 3.病人 4.电话呼唤 5.文件稿 6.提货单 7.到达机场上空的飞机 8.驶入港口的货船 9.上游河水进入水库 10.进入我方阵地的敌机 修理 领取修配零件 诊断或动手术 通话 打字 提取存货 降落 装(卸)货装(卸) 放水，调整水位 我方高射炮进行射击 修理技工 发放修配零件的管理员 医生(或包括手术台) 交换台 打字员 仓库管理员 跑道 货码头(泊位) 水闸管理员 我方高射炮 形形色色的排队系统 排队论是1909年由丹麦工程师爱尔朗(A.K．Erlang)在研究电活系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图2-1至图2-3。 图2-1 单服务台排队系统 图2-2 单队列——S个服务台并联的排队系统 图2-3 S个队列——S个服务台的并联排队系统 我们把要求服务的人或事物称为顾客，把为顾客服务的人或事物叫做服务机构（服务员或服务台），顾客排队要求服务的过程或现象称为排队系统或服务系统。由于顾客到达的时刻与进行服务的时间一般来说都是随机的，所以服务系统又称随机服务系统。 排队系统的组成与特征 排队系统一般有三个基本组成部分：1.输入过程；2.排队规则；3.服务机构。 各种随机服务系统都有3个共同的组成部分 （1）输入系统: 即各种类型的顾客按照怎样的规律到达服务系统要求服务； （2）排队规则: 指到达系统的顾客按什么次序接受服务； （3）服务机构: 指同一时刻有多少服务设备可以接纳顾客，每个顾客须服务多少时间。 输入即顾客的到达，可有下列情况： 1）顾客源可能是有限的，也可能是无限的。 2）顾客是成批到达或是单个到达。 3）顾客到达间隔时间可能是随机的或确定的。 4）顾客到达可能是相互独立或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。 5）输入过程可以是平稳的（stationary），也可以是非平稳的。输入过程平稳的指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则与时间相关。 1 输入过程 分为损失制、等待制、混合制三大类。 (1)损失制 指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。 典型例子是，如电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号。 2. 排队规则 (2)等待制 当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。 例如，排队等待售票，故障设备等待维修等。 等待制中，服务台在选择顾客进行服务时，常有如下四种规则：