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