运筹学排队论1.ppt

第十章排队论
引言
排队论是研究排队系统(又称随机服务系统)的数学理论和方法,是运筹学的一个重要分支。
有形排队现象:进餐馆就餐,到图书馆借书,车站等车,去医院看病,售票处售票,到工具房领物品等现象。
无形排队现象:如几个旅客同时打电话订车票;如果有一人正在通话,其他人只得在各自的电话机前等待,他们分散在不同的地方,形成一个无形的队列在等待通电话。
排队的不一定是人,也可以是物。如生产线上的原材料,半成品等待加工;因故障而停止运行的机器设备在等待修理;码头上的船只等待装货或卸货;要下降的飞机因跑道不空而在空中盘旋等。
当然,进行服务的也不一定是人,可以是跑道,自动售货机,公共汽车等。顾客可以走向服务机构,也可以相反(如送货上门)。
顾客——要求服务的对象。
服务员——提供服务的服务者(也称服务机构)。
顾客、服务员的含义是广义的。
如果增添服务设备,就要增加投资或发生空闲浪费;如果服务设备太少,排队现象就会严重,对顾客个人和对社会都会带来不利影响。因此,管理人员必须考虑如何在这两者之间取得平衡,经常检查目前处理是否得当,研究今后改进对策,以期提高服务质量,降低成本。
2、排队系统类型:
服务台
顾客到达
服务完成后离开
单服务台排队系统
服务台2
顾客到达
服务完成后离开
服务台s
服务台1
S个服务台,一个队列的排队系统
S个服务台, S个队列的排队系统
服务台2
顾客到达
服务完成后离开
服务台s
服务台1
服务完成后离开
服务完成后离开
服务台1
顾客到达
离开
服务台s
多服务台串联排队系统
随机聚散服务系统
服务机构
聚
散
(输入)
(输出)
随机性——顾客到达情况与顾客接受服务的时间是随机的。
一般来说,排队论所研究的排队系统中,顾客相继到达时间间隔和服务时间这两个量中至少有一个是随机的,因此,排队论又称随机服务理论。
3、排队系统的组成和特征
实际中的排队系统各不相同,但概括起来都由三个基本部分组成:输入过程,排队规则和服务机构。
输入过程—即顾客到达排队系统。
顾客总体(顾客源)数:可能是有限,也可能是无限。河流上游流入水库的水量可认为是无限的;车间内停机待修的机器显然是有限的。
到达方式:是单个到达还是成批到达。库存问题中,若把进来的货看成顾客,则为成批到达的例子。
顾客(单个或成批)相继到达的时间间隔,可以是确定型的,也可以是随机型的。这是刻划输入过程的最重要内容。令T0=0,Tn表示第n顾客到达的时刻,则有T0T1  T2…..  Tn ……记Xn= Tn –Tn-1 n=1,2,…,则Xn是第n顾客与第n-1顾客到达的时间间隔。对于随机型的,要知道其分布:一般假定{Xn}是独立(非关联)同分布,并记分布函数为A(t)。
{Xn}的分布A(t)常见的有:
定常分布(D):顾客相继到达的时间间隔为确定的。如产品通过传送带进入包装箱就是定常分布。
最简流(或称Poisson)(M):顾客相继到达的时间间隔{Xn}为独立的,同为负指数分布,其密度函数为:
a(t)=
e- t t0
0 t < 0
排队规则
排队
有限排队——排队系统中顾客数是有限的。有限排队还可以分成:
损失制排队系统:排队空间为零的系统,即不允许排队。(顾客到达时,服务台占满,顾客自动离开,不再回来)(电话系统)
混合制排队系统:是等待制与损失制结合,即允许排队,但不允许队列无限长。
混合制排队系统:
队长有限。即系统等待空间是有限的。例:最多只能容纳K个顾客在系统中,当新顾客到达时,若系统中的顾客数(又称为队长)小于K,则可进入系统排队或接受服务;否则,便离开系统,并不再回来。如水库的库容是有限的,旅馆的床位是有限的。等待时间有限。即顾客在系统中等待时间不超过某一给定的长度T,当等待时间超过T时,顾客将自动离开,不再回来。如易损失的电子元件的库存问题,超过一定存储时间的元器件被自动认为失效。
逗留时间(等待时间与服务时间之和)有限。例:用高射炮射击飞机,当敌机飞越射击有效区域的时间为t时,若这个时间内未被击落,也就不可能再被击落了。