前言:这是之前上《信号与系统》课程时做的一个作业。

摘要:本文从生活中很普通的食堂麻辣烫排队问题出发,研究两种不同排队方式的区别,粗略比较两种排队方式的优劣。

关键词:排队论

一、问题描述

买麻辣烫的同学服从服从参数为\(\lambda\)的泊松分布,每人只许买一份麻辣烫,买完就走。并行做麻辣烫的厨师有\(r\)个,每位厨师任何时刻只能做一份麻辣烫,不同厨师做麻辣烫时间长度独立,且都服从参数为\(\mu\)的负指数分布。同学到达麻辣烫窗口与厨师做麻辣烫相互独立。

有两种排队方式

  • A:排成一个大队列。只要有某位厨师空闲,他就给排在队列中的第一个同学做麻辣烫。新到达的同学排到队尾,直到排在他前面的所有同学都买到麻辣烫之后,他才有资格买。按照这种方式,当\(r\)个厨师都忙碌时,同学们按照先到先得的原则在排一个大队列。
  • B:自选排成多个队列。每个厨师前面各排一个队列,厨师只给他负责的队列中的同学做麻辣烫。新到达的同学自行选择排哪一个队列。按照这种方式,当\(r\)个厨师都忙碌时,同学们排成了\(r\)个队列。

对于不同排队方式的优劣有一下几个评判指标

  • 平均同学人数\(L\)
  • 平均等待同学人数\(L_Q\)
  • 每个同学花费的平均时间\(W\)
  • 每个同学在系统中等待时间\(W_Q\)

在麻辣烫问题中,每个同学花费的平均时间和等待时间不会有本质的不同,因为即使是“服务时间”,同学也是在等待麻辣烫的制作。所以我们只取平均同学人数\(L\)和每个同学花费的平均时间\(W\)两个参量描述排队方式的优劣。

二、计算推导

1. 单队列方式

由于所有厨师做麻辣烫的时间是相互独立的,且都是参数为\(\mu\)的负指数分布;买麻辣烫的同学服从参数为\(\lambda\)的泊松分布。因此这就是一个标准的\(M/M/r\)模型,即输入输出过程是Markov的,有\(r\)个服务台。因为厨师总数是\(r\),所以当排队同学人数 \(n< r\) 时,所有同学都处在等待厨师做完麻辣烫(即被服务)的状态,这时做麻辣烫的平均速率为\(n\mu\);而当排队同学人数\(n\leq r\)时, 所有厨师都在工作, 这时做麻辣烫的平均速率是\(r\mu\)。

因此\(M/M/r\)单队列方式,生灭过程的状态转移图如下图。

考虑系统进入平衡状态后,系统满足的状态平衡方程如下

\[\left\{\begin{array}{llll} \lambda P_0 &= \mu P_1 & &(1)\\ \lambda P_{n-1}+(n+1)\mu P_{n+1}&=(\lambda+n\mu)P_n & 1\leq n< r &(2)\\ \lambda P_{n-1}+r\mu P_{n+1}&=(\lambda+r\mu)P_n & n\geq r &(3) \end{array}\right.\]

将(1)带入式(2),从\(n=1\)开始有

\(\left.\begin{array}{lll} 2\mu P_2&=P_1(\lambda+\mu)-\lambda P_0&=\lambda P_1 \\ 3\mu P_3&=P_2(\lambda+2\mu)-\lambda P_1&=\lambda P_2 \\ \dots\\ n\mu P_n&=P_{n-1}(\lambda+(n-1)\mu)-\lambda P_{n-2} &=\lambda P_{n-1} \end{array}\right.\)
设\(\rho=\frac\lambda\mu\)

所以

\[P_n=\frac{1}{n!}(\rho)^{n-1}P_1=\frac{1}{n!}(\rho)^{n}P_0 \qquad n< r\]

式(3)就是M/M/1模型中的稳态方程,计算得到

\[P_n=(\frac\rho{r})^{n-r}P_r=\frac{1}{r!r^{n-r}}(\rho)^nP_0\qquad n\geq r\]

又因为\(\sum_{i=0}^{\infty}P_i=1\),所以

\[P_0=(\sum_{i=0}^{\infty}\frac{P_i}{P_0})^{-1} =\left[\sum_{i=0}^{r-1}\frac{1}{i!}(\rho)^i+\frac1{r!}\frac{r}{r-\rho}(\rho)^r\right]^{-1}\]

综上所述, 有

\[\left\{\begin{array}{ll} P_0=\left[\sum_{i=0}^{r-1}\frac{1}{i!}(\rho)^i+\frac1{r!}\frac{r}{r-\rho}(\rho)^r\right]^{-1}\\ P_n=\frac{1}{n!}(\rho)^{n}P_0 &1\leq n< r\\ P_n=\frac{1}{r!r^{n-r}}(\rho)^nP_0 &r\leq n \end{array}\right.\]

上式成立需要\(\rho< r\)

其他指标

  • 平均同学人数
\[\begin{array}{ll}L&=\sum_{n=0}^\infty {nP_n}\\ &=P_0\left( \sum_{n=1}^{r-1}{\frac{1}{(n-1)!}(\rho)^{n}}+\sum_{r}^{\infty}{\frac{n}{r!r^{n-r}}(\rho)^n} \right)\\ &=P_0\left( \rho\sum_{n=0}^{r-2}{\frac{1}{n!}(\rho)^{n}}+\frac{1}{(r-1)!}(\rho)^{r}+\sum_{n=r+1}^{\infty}{\frac{n}{r!r^{n-r}}(\rho)^n}\right)\\ &=P_0\rho\left( \sum_{n=0}^{r-1}{\frac{1}{n!}(\rho)^{n}}+\sum_{n=r}^{\infty}{\frac{1}{r!r^{n-r}}(\rho)^n}\right)+P_0\sum_{n=r+1}^{\infty}(n-r)\frac{1}{r!r^{n-r}}(\rho)^n\\ &=\rho+\left(\left(\rho\right)^{r+1}\frac1{(r-1)!}(\frac1{r-\rho})^2\right)P_0 \end{array}\]
  • 每个同学花费的平均时间,由Little公式有 \(W=\frac{L}\lambda\)
  • 关于上式的理解:平均花费的时间就是同学排到队尾后,他后面再排上平均队长所用的时间(这时他就“平均”拿到麻辣烫走了)

2. 多队列方式

多队列方式比单队列方式要复杂一点,主要因为每次来到同学会根据队伍长度做一个选择。根据选择方式,得到的平均等待人数和平均等待时间也会有所不同。

无选择均匀随机排布

如果来的同学根本不关心队伍长度,只是排队的话,这样这就是\(r\)个标准的\(M/M/1\)模型,可以直接利用\(M/M/1\)的公式进行计算。

此时每个队列同学来的速度是\(\frac\lambda{r}\),厨师处理速度是\(\mu\)。

  • 平均同学人数
\[L=r\frac{(\lambda/r)/\mu}{1-(\lambda/r)/\mu}=\frac{r\rho}{r-\rho}\]
  • 每个同学花费平均时间
\[W=\frac1{\mu-\lambda/r}=\frac{r}{r\mu-\lambda}\]

注意到这里依旧满足\(W=\frac{L}\lambda\)

比较

因为\(W=\frac{L}\lambda\),所以只比较平均同学人数即可。

\[\begin{array}{lll} P_0 &=\left[\sum_{i=0}^{r-1}\frac{1}{i!}(\rho)^i+\frac1{r!}\frac1{1-\frac\lambda{r\mu}}(\rho)^r\right]^{-1}\\ &=\left[\sum_{i=0}^{r-2}\frac{1}{i!}(\rho)^i+\frac1{(r-1)!}(\rho)^{r-1}+\frac1{(r-1)!}\frac{\rho}{r-\rho}(\rho)^{r-1}\right]^{-1}\\ &< \left[\frac1{(r-1)!}(\rho)^{r-1}+\frac1{(r-1)!}\frac{\rho}{r-\rho}(\rho)^{r-1}\right]^{-1}\\ &= \frac{r-\rho}{r}(r-1)!(\rho)^{-(r-1)} \end{array}\] \[\begin{array}{lll} L_1-L_r &=\left(\rho+\left(\left(\rho\right)^{r+1}\frac1{(r-1)!}(\frac\mu{r\mu-\lambda})^2\right)P_0\right)-\left(\frac{r\lambda}{r\mu-\lambda}\right)\\ &<\rho+\frac{(\rho)^2}{r(r-\rho)}-\frac{r\rho}{r-\rho}\\ &=\frac{(\rho)^2(1-r)}{r(r-\rho)}\\ &<0 \qquad \text{for $1 < r$} \end{array}\]