排队系统模拟仿真中对空间有限的处理

魏焕东

摘 要 等待空间有限的模型在排队系统中是十分常见的，本文将等待空间有限的条件转化为算法中更新的向量，为等待空间有限的模型的模拟仿真提供一条可行的思路，并用matlab进行模拟仿真。

关键词 等待空间有限 排队系统 模拟仿真

中图分类号：U495 文献标识码：A

1研究背景和意义

排队在日常生产和生活中十分常见，关于排队系统的理论研究国内外学者做了大量的工作，ward whitt作为该领域的领军人在他的专注[1]中做了大量的工作，模拟仿真研究作为理论研究的补充和验证同样有许多人进行研究。本文主要是将等待空间有限的条件数学化，转化为算法可以操作的向量，为等待空间有限的排队模型的研究提供一条新的思路。

2对等待空间的处理

在等待空间无限的排队模型中，每一个到达的顾客都可以进入系统，若顾客到达时服务台有空位，则顾客可以直接接受服务；若无空位，则进入队列等待。不考虑顾客放弃，顾客的等待时间可以借助上一个顾客的信息来计算，为上一个顾客进入服务台的时间与该顾客到达时间之差，顾客的离开时间为顾客到达时间、等待时间与服务时间之和。对于顾客数据的的处理详细可见文献[2，3]。

若系统的等待空间有限，考虑G/G/n/K模型，模型具有n个服务台，等待空间有限为K。本文中的等待空间指的是队列的中的人数，则系统中最多可以容纳的顾客数为n+K。当系统中人数达到系统可容纳的上限时顾客便不能进入，此时到达的顾客被阻塞而不能进入系统，顾客的离开时间等于顾客的到达时间。若顾客可以进入系统，顾客的等待时间借助上一个进入系统的顾客的信息来计算。用ui表示第i个顾客的到达时间，vi表示第i个顾客的服务时间，wi代表第i个顾客的等待时间。用表i示顾客的离开时间，则

i=ui+vi+wi

为了辅助算法的实现，创建一个向量queue。首先对向量进行初始化，前n个顾客无论以怎样的路径到达都可以直接进入服务台，所以前n个顾客的等待时间必然为0，计算出前n个顾客的离开时间。初始化的向量queue保存前n个顾客的离开时间，此时最新的一个成功进入系统的顾客为第n个顾客。

当第i（i>n）个顾客到达系统时，首先判断此时队列中剩余的顾客数，即在第i个顾客到达时尚未离开系统的顾客数，即离开时间大于第i个顾客到达时间的顾客数。计算向量queue中大于第i个顾客到达时间ui的元素的个数，若该值小于n+K，说明此时系统中的人数没有到达上限，第i個顾客可以进入系统中；若该值等于n+K，则第i个顾客被阻塞而不能进入系统。

若第i个顾客可以进入系统，计算出该顾客的等待时间和离开时间，此时需要更新向量queue，用向量中大于ui的元素以及第i个顾客的离开时间i组成新的向量queue，新的向量queue由大于离开时间大于第i个顾客到达时间的顾客的离开时间和第i个顾客的离开时间组成。若顾客被阻塞则不需要更新向量queue。

对向量queue的更新操作，保存每个顾客进入系统后剩余顾客的离开时间，通过比较前面顾客的离开时间与顾客到达时间判断顾客到达时系统中剩余的顾客数，来控制等待空间有限的条件。

3模拟仿真

以M/M/n/K模型为例，令顾客到达率为20，每个服务台服务率为1，系统具有20个服务台，模拟出前1000个顾客的到达时间和服务时间，取等待空间为5，等待空间有限和无限的系统中人数如图1所示：

4总结

本文研究和分析了排队系统的模拟仿真中对等待空间有限的处理方法，通过matlab的模拟仿真可以看出该处理方式是有效的，为研究等待空间有限的排队系统的提供了一条新的思路。

参考文献

[1] WhittWard. Stochastic-Process Limits[M]. New York， Springer， 2002.

[2] 宋振峰，席志红，刘飞.基于Matlab的排队模型的仿真[J].现代电子技术，2005，28（06）：29—30.

[3] 秦海林，刘建民.带优先权与不耐烦顾客排队模型的模拟仿真[J].现代电子技术，2012，35（20）：91-94.

[4] 张建航，李宗成，宋晓峰.单服务员排队模型及其蒙特卡洛模拟[J].现代电子技术，2006，29（24）：44-46.