排队论(脱产).ppt

排队论 例 某火车站售票处有三个窗口，同时售各车次的车票。顾客到达服从泊松分布，平均每小时到达λ=54人，服务时间服从负指数分布，平均服务率μ=24（人/h），分两种情况： 1. 顾客排成一队，依次购票； 2. 顾客每个窗口排一队，不准串队。 考虑: 1、售票处空闲的概率； 2、顾客在系统中平均等待时间和逗留时间 3、系统中平均总顾客数和排队的顾客数。 排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory),是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。 例：上、下班搭乘公共汽车； 顾客到商店购买物品； 病员到医院看病； 旅客到售票处购买车票； 食堂、饭店就餐； 打电话； 通讯卫星与地面传递信息； 生产线上的原料、半成品等待加工； 因故障停止运转的机器等待工人修理； 码头的船只等待装卸货物； 要降落的飞机因跑道不空而在空中盘旋等等； 防空系统向敌机射击。 1.基 本 概 念 一 排队系统的描述 （一）系统特征和基本排队过程 实际的排队系统有以下的共同特征： (1)有请求服务的人或物——顾客； (2)有为顾客服务的人或物，即服务员或服务台； (3)顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的。排队系统的这种随机性造成某个阶段顾客排队较长，而另外一些时候服务员(台)又空闲无事。 1.基 本 概 念 （二）排队系统的基本组成部分 通常，排队系统都有输入过程、服务规则和服务台等3个组成部分： 1．输入过程．一般可以从3个方面来描述—个输入过程。 (1)顾客总体数，又称顾客源、输入源。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。例如，到售票处购票的顾客总数可以认为是无限的，而某个工厂因故障待修的机床则是有限的。 (2)顾客到达方式。这是描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。病人到医院看病是顾客单个到达的例子。在库存问题中如将生产器材进货或产品入库看作是顾客，那么这种顾客则是成批到达的。 1.基 本 概 念 (3)顾客流的概率分布，或称相继顾客到达的时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。这也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、? )的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若干种。 1.基 本 概 念 2.服务规则。一般可以分为损失制、等待制和混合制等3大类。 (1)损失制。指如果顾客到达排队系统时，所有服务台都已被先来的顾客占用，那么他们就自动离开系统永不再来。例如,电话拔号后出现忙音，顾客不愿等待而自动挂断电话，如要再打，就需重新拔号，这种服务规则即为损失制。 1.基 本 概 念 (2)等待制。指当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。例如，排队等待售票，故障设备等待维修等。服务台在选择顾客进行服务时，常有如下四种规则： ①先到先服务。按顾客到达的先后顺序对顾客进行服务，是最普遍的情形。 ②后到先服务。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。 1.基 本 概 念 ③随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。 ④优先权服务。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。 1.基 本 概 念 (3)混合制．这是等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种： ① 队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。例如最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数(又称为队长)小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。 1.基 本 概 念 ② 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另