M/M/1

M/M/1排队模型(M/M/1 model)是一种单一服务台(single-server)的(排队模型),可用作模拟不少系统的运作。

M/M/1 schema

依据开恩特罗符号英语Kendall's notation必须有下列的条件:

  • 到达时间卜瓦松过程(Poisson process);
  • 服务时间是指数分布(exponentially distributed);
  • 只有一个服务台(server),遵循先到先服务规则
  • 队列长度无限制
  • 可加入队列的人数为无限

分析

这种模型是一种出生-死亡过程,此随机过程中的每一个状态代表模型中人数的数目。因为模型的队列长度无限且参与人数亦无限,故此状态数目亦为无限。例如状态0表示模型闲置、状态1表示模型有一人在接受服务、状态2表示模型有二人(一人正接受服务、一人在等候),如此类推。 在此模型中,出生率(即加入队列的速率)λ在各状态中均相同,死亡率(即完成服务离开队列的速率)μ亦在各状态中相同(除了状态0,因其不可能有人离开队列)。 故此,在任何状态下,只有两种事情可能发生:

  • 有人加入队列。如果模型在状态k,它会以速率λ进入状态k + 1
  • 有人离开队列。如果模型在状态kk不等于0),它会以速率μ进入状态k − 1

由此可见,模型的隐定条件为λ < μ。如果死亡率小于出生率,则队列中的平均人数为无限大,故此这种系统没有平衡点。

此模型中有几项数值常被测量,例如:

  • 一人在系统中的平均逗留时间
  • 一人在接受服务前的平均等候时间
  • 整个系统中的平均人数
  • 等候队列的平均人数
  • 单位时间内系统完成服务人数,即服务速度

稳定状态下的公式

缓冲效用   表示服务被占用的平均概率

平稳过程在状态i(“i”个总人数,包括正在被服务的)的几率为

 

由此,可给出各测量数值的公式:

  • 整个系统的平均人数N
 ,且其方差为
 .
  • 一单位时间内系统完成服务的人数:
 
  • 在队列中等候服务的人数:
 
  • 一人在系统中的平均逗留(等候+接受服务)时间:
 
  • 一人的平均等候时间:
 

可用M/M/1模型的例子众多,例如只有一位员工的邮局,只有一队列。客人进来,排队、接受服务、离开。如果客人进来的数目符合泊松过程,且服务时间是指数分布,则可用M/M/1模拟,并算出平均队列长度、不同等候时间的几率等。

M/M/1可一般化成为M/M/n模型,使可用时接受服务的人数为大于一。历史上,M/M/n模型首先被用来模拟电话系统,因为一个在丹麦哥本哈根电话局工作的工程师Erlang发现客人打电话的速率符合泊松过程,且通话时间是指数分布,所以占用通讯线路的数目和等待接线的人数符合M/M/n模型。

关联项目

  • 排队理论
  • 马尔科夫链