麻辣烫排队问题

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

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

关键词：排队论

一、问题描述

买麻辣烫的同学服从服从参数为$\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}\]