第13章排队论

《第13章排队论》由会员分享，可在线阅读，更多相关《第13章排队论（102页珍藏版）》请在文档大全上搜索。

1、第13章 排队论本章主要内容：本章主要内容： 排队论中的基本概念 排队系统的主要数量指标 普阿松过程 单服务台负指数分布排队系统的分析方法和结果 其他模型的应用重点掌握重点掌握：基本概念、单服台负指数分布排队系统文化的例子文化的例子0 000000serverline of peopleserver美国的售美国的售 票窗口票窗口许多其他许多其他国家的售国家的售 票窗口票窗口人们怎么利用时间人们怎么利用时间Source: U.S. News & World Report, January 30, 1989, p. 81.在美国，一份六在美国，一份六千人的调查试图千人的调查试图算出平均一个

2、美算出平均一个美国人一生中参与国人一生中参与各种活动的总时各种活动的总时间，这份调查表间，这份调查表明如下情况：明如下情况：排队安排排队安排单通道单通道多通道多通道排队论中的平衡排队论中的平衡服务成本与等待成本的权衡服务成本与等待成本的权衡排队系统中的因素排队系统中的因素服务机构服务机构服务系统服务系统顾客到达顾客到达离开离开等待队列等待队列队列模型的特征队列模型的特征 主要因素主要因素 顾客源顾客源 顾客到达方式顾客到达方式 队列结构队列结构 排队规则排队规则 服务特征服务特征 顾客离开队列的条件顾客离开队列的条件顾客源顾客源有限的有限的无限的无限的举例：公司里有且举例：公司里有且仅有三台机

3、器需要仅有三台机器需要修理修理举例：队列中等举例：队列中等待加油的人数待加油的人数顾客源顾客源服务模式服务模式不变的不变的可变的可变的举例：自动装配线举例：自动装配线上流动的产品上流动的产品举例：人们花时举例：人们花时间去购物间去购物服务模式服务模式排队系统排队系统排队规划排队规划 队长队长 排队规则排队规则服务时间分布服务时间分布队列数和队列结构队列数和队列结构排队系统排队系统队列结构举例队列结构举例 单通道单通道多通道多通道单阶段单阶段多阶段多阶段只有一个理发师的只有一个理发师的理发店理发店洗车洗车医院的进入医院的进入银行出纳窗口银行出纳窗口 耐心程度耐心程度No Way!望而却步望而却步

4、No Way!中途离队中途离队顾客到达特征顾客到达特征 到达方式到达方式 可控或不可控可控或不可控 到达的规模到达的规模 单个到达或是成批到达单个到达或是成批到达 分布分布 到达率的均匀或统计分布到达率的均匀或统计分布 耐心程度耐心程度 顾客是一直等待或是离开顾客是一直等待或是离开 望而却步或是中途离队望而却步或是中途离队队列结构队列结构 队长队长 无限队长无限队长 有限队长有限队长 队列数队列数 单列或多列单列或多列 对排队问题的建议对排队问题的建议1. 为顾客确定一个可接受的等待时间为顾客确定一个可接受的等待时间2. 在顾客等待过程中尽量分散他们的注意力在顾客等待过程中尽量分散他们的注意力

5、3. 及时告诉顾客他们期望了解的情况及时告诉顾客他们期望了解的情况4. 决不能让顾客看到雇员并未在工作决不能让顾客看到雇员并未在工作5. 对顾客进行分类对顾客进行分类6. 对服务人员进行培训对服务人员进行培训7. 鼓励顾客在非高峰期到达鼓励顾客在非高峰期到达8. 对于消除排队有一个长期的计划对于消除排队有一个长期的计划1 基本概念一、排队系统的特征及排队论一、排队系统的特征及排队论 排队论是研究排队系统的数学理论和方法，是运筹学的一个重要分支。日常生活中，我们遇到各种各样的排队问题。这些问题中，餐馆服务员与顾客，公共汽车与乘客，图书馆的工作人员与借阅者，医生和病人，售票员与乘客等均分别构成一个

6、排队系统，或服务系统。顾客顾客要求的服务要求的服务服务机构服务机构1借书的学生借书的学生2打电话打电话3提货者提货者4待降落的飞行待降落的飞行器器5储户储户6河水进入水库河水进入水库7购票旅客购票旅客8十字路口的汽十字路口的汽车车借书借书通话通话提货提货降落降落存款、取款存款、取款放水、调整水位放水、调整水位购票购票通过路口通过路口图书管理员图书管理员交换台交换台仓库管理员仓库管理员指挥塔台指挥塔台储蓄窗口、储蓄窗口、ATMD取款机取款机水库管理员水库管理员售票窗口售票窗口红绿灯或交警红绿灯或交警排队系统的例子排队系统的例子排队问题表现形式是拥挤现象，随着生产与服务的日益社会化，由排队引起的拥

7、挤现象会越来越普遍。排队除了是有形的队列外，还可以是无形的队列。如几个旅客同时打电话到火车站订票，如有一个人正在通话，则其他人只得在各自的电话机前等待，他们分散在不同地方，却形成了一个无形的队列在等待通话。排队的不一定是人，也可以是物，如生产线上的原材料，半成品等待加工；因故障而停止运转的机器在等待修理；码头上的船只等待装货或卸货，降落的飞机因跑道不空而在空中盘旋等，进行服务的也不一定是人，可以是跑道、自动售货机、公共汽车等。 为了一致起见，将要求服务的对象统称为“顾顾客客”，将提供服务的服务者统称为“服务员服务员”或或“服服务机构务机构”，是广义的。实际上排队系统千差万别，但都可以一般地描可

8、以一般地描述如下：述如下：顾客为了得到某种服务而到达系统，若不能立即获得服务而又允许排队等候，则加入等待队伍，待获得服务后离开系统。顾客到达服务台服务完成后离去顾客到达服务台2服务完成后离去服务台1服务台n顾客到达服务台2服务完成后离去服务台1服务台n00.000.000.0顾客到达服务台1服务台n服务完后离去尽管各种排队系统的具体形式不同，但可用下图加以一般性的描述：服务机构服务机构服务系统服务系统顾客到达顾客到达离开离开二、排队系统的描述二、排队系统的描述 实际中的排队系统各不同，但概括起来都由三个基本部分组成三个基本部分组成：输入过程、排队规则、服务机构。1.输入过程输入过程 输入过程是

9、说明顾客按怎样的规律到达系统。 完全刻划一个输入过程需以下几个方面:(1)顾客总体数：有限的或无限的。流入水库的水量是无限的，车间内等待维修的机器是有限的。(2)到达方式：是单个到达还是成批到达(3)顾客相继到达的时间间隔的分布：记Xn是第n个顾客与第n-1个顾客到达的时间间隔，关于Xn的分布。 常见的有常见的有： 定长分布定长分布(D)：顾客有规则地等距到达，如自动生产线上的装配件。 负指数分布负指数分布(M) k阶爱尔朗分布阶爱尔朗分布(Ek) GI：一般相互独立(General Independent)的时间间隔的分布 G：一般(General)服务时间的分布。(4)顾客到达可以是相互独

10、立的，即以前到达情况对以后顾客的到达没有影响。(5)输入过程可以是平稳的。即相继到达的间隔时间分布和所含参数（如期望值、方差等）都是与时间无关的。2. 排队规则排队规则 排队：排队：有限排队和无限排队。 有限排队：有限排队：指排队系统中的顾客数是有限的，即系统的空间是有限的，当系统被占满时，后面再来的顾客将不能进入系统了。 无限排队：无限排队：指系统中顾客数可以是无限的，队列可以排到无限长，顾客到达系统后均可进入系统排队或接受服务，又称等待制排队系统。有限排队又可分为：损失制排队系统和混合制排队系统。损失制排队系统：指排队空间为0的系统，实实际上是不允许排队际上是不允许排队。当顾客到达系统时，

11、如所有服务台均被占用则自动离去，并不再回来，称这部分顾客被损失掉了。混合制排队系统：指等待制与损失制系统的混合，一般是指允许排队，但又不允许队列无限长下去。具体包括三种：队长有限队长有限：即系统的等待空间是有限的，例如最多只能容纳k个顾客在系统中，当新顾客到达时，若系统中的顾客数小于k，则可进入系统排队或接受服务；否则，便 离开系统，并不再回来，如水库的库容是有限的、旅馆的床位是有限的。等待时间有限等待时间有限：即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。逗留时间逗留时间