D.4 Summary of Queueing Formulas
This section provides the formulas for basic single queue stations and is meant simply as a resource where the formulas are readily available for potential applicaiton. The following notation is used within this section.
Let \(N\) represent the steady state number of customers in the system, where \(N \in \{0,1,2,...,k\}\) where \(k\) is the maximum number of customers in the system and may be infinite (\(\infty\)).
Let \(\lambda_{n}\) be the arrival rate when there are \(N=n\) customers in the system.
Let \(\mu_{n}\) be the service rate when there are \(N=n\) customers in the system.
Let \(P_n = P[N=n]\) be the probability that there are \(n\) customers in the system in steady state.
When \(\lambda_{n}\) is constant for all \(n\), we write \(\lambda_{n} = \lambda\).
When \(\mu_{n}\) is constant for all \(n\), we write \(\mu_{n} = \mu\).
Let \(\lambda_e\) be the effective arrival rate for the system, where
\[\lambda_e = \sum_{n=0}^{\infty} \lambda_n P_n\] Since \(\lambda_n = 0\) for \(n \geq k\) for a finite system size, \(k\), we have:
\[\lambda_e = \sum_{n=0}^{k-1} \lambda_n P_n\]
Let \(\rho = \frac{\lambda}{c\mu}\) be the utilization.
Let \(r = \frac{\lambda}{\mu}\) be the offered load.
D.4.1 M/M/1 Queue
\[\begin{aligned} \lambda_n & =\lambda \\ \mu_n & = \mu \\ r & = \lambda/\mu \end{aligned} \]
\[P_0 = 1 - r\] \[P_n = P_0 r^n\] \[L_q = \dfrac{r^2}{1 - r}\]
| Model | Parameters | \(L_q\) |
|---|---|---|
| M/G/1 | \(E[ST] = \dfrac{1}{\mu}\); \(Var[ST] = \sigma^2\); \(r = \lambda/\mu\) | \(L_q = \dfrac{\lambda^2 \sigma^2 + r^2}{2(1 - r)}\) |
| M/D/1 | \(E[ST] = \dfrac{1}{\mu}\); \(Var[ST] = 0\); \(r = \lambda/\mu\) | \(L_q = \dfrac{r^2}{2(1 - r)}\) |
D.4.2 M/M/c Queue
\[ \begin{aligned} \lambda_n & =\lambda \\ \mu_n & = \begin{cases} n \mu & 0 \leq n < c \\ c \mu & n \geq c \end{cases} \\ \rho & = \lambda/c\mu \quad r = \lambda/\mu \end{aligned} \]
\[P_0 = \biggl[\sum\limits_{n=0}^{c-1} \dfrac{r^n}{n!} + \dfrac{r^c}{c!(1 - \rho)}\biggr]^{-1} \] \[ L_q = \biggl(\dfrac{r^c \rho}{c!(1 - \rho)^2}\biggl)P_0 \]
\[ P_n = \begin{cases} \dfrac{(r^n)^2}{n!} P_0 & 1 \leq n < c \\[1.5ex] \dfrac{r^n}{c!c^{n-c}} P_0 & n \geq c \end{cases} \]
| \(c\) | \(P_0\) | \(L_q\) |
|---|---|---|
| 1 | \(1 - \rho\) | \(\dfrac{\rho^2}{1 - \rho}\) |
| 2 | \(\dfrac{1 - \rho}{1 + \rho}\) | \(\dfrac{2 \rho^3}{1 - \rho^2}\) |
| 3 | \(\dfrac{2(1 - \rho)}{2 + 4 \rho + 3 \rho^2}\) | \(\dfrac{9 \rho^4}{2 + 2 \rho - \rho^2 - 3 \rho^3}\) |
D.4.3 M/M/c/k Queue
\[ \begin{aligned} \lambda_n & = \begin{cases} \lambda & n < k \\ 0 & n \geq k \end{cases} \\ \mu_n & = \begin{cases} n \mu & 0 \leq n < c \\ c \mu & c \leq n \leq k \end{cases} \\ \rho & = \lambda/c\mu \quad r = \lambda/\mu \\ \lambda_e & = \lambda (1 - P_k) \end{aligned} \] \[ P_0 = \begin{cases} \biggl[\sum\limits_{n=0}^{c-1} \dfrac{r^n}{n!} + \dfrac{r^c}{c!} \dfrac{1-\rho^{k-c+1}}{1 - \rho}\biggr]^{-1} & \rho \neq 1\\[1.5ex] \biggl[\sum\limits_{n=0}^{c-1} \dfrac{r^n}{n!} + \dfrac{r^c}{c!} (k-c+1)\biggl]^{-1} & \rho = 1 \end{cases} \] \[ P_n = \begin{cases} \dfrac{r^n}{n!} P_0 & 1 \leq n < c \\[1.5ex] \dfrac{r^n}{c!c^{n-c}} P_0 & c \leq n \leq k \end{cases} \]
D.4.4 M/G/c/c Queue
\[ \begin{aligned} \lambda_n & = \begin{cases} \lambda & n < c \\ 0 & n \geq c \end{cases} \\ \mu_n & = \begin{cases} n \mu & 0 \leq n \leq c \\ 0 & n > c \end{cases} \\ \rho & = \lambda/c\mu \quad r = \lambda/\mu \\ \lambda_e & = \lambda (1 - P_k) \end{aligned} \]
\[P_0 = \biggr[\sum\limits_{n=0}^c \dfrac{r^n}{n!}\biggl]^{-1}\] \[ \begin{array}{c} P_n = \dfrac{r^n}{n!} P_0 \\ 0 \leq n \leq c \end{array} \] \[L_q = 0\]
D.4.5 M/M/1/k Queue
\[ \begin{aligned} \lambda_n & = \begin{cases} (k - n)\lambda & 0 \leq n < k \\ 0 & n \geq k \end{cases} \\ \mu_n & = \begin{cases} (k - n)\lambda & 0 \leq n \leq k \\ 0 & n > k \end{cases} \\ r & = \lambda/\mu \quad \lambda_e = \lambda(k - L) \end{aligned} \] \[ P_0 = \biggl[\sum\limits_{n=0}^k \prod\limits_{j=0}^{n-1} \biggl(\dfrac{\lambda_j}{\mu_{j+1}}\biggr)\biggr]^{-1} \] \[ P_n = \binom{k}{n} n! r^n P_0 \]
\[ L_q = \begin{cases} \dfrac{\rho}{1 - \rho} - \dfrac{\rho (k \rho^k + 1)}{1 - \rho^{k+1}} & \rho \neq 1 \\ \dfrac{k(k - 1)}{2(k + 1)} & \rho = 1 \end{cases} \]
D.4.6 M/M/c/k Queue
\[ \begin{aligned} \lambda_n & = \begin{cases} (k - n)\lambda & 0 \leq n < k \\ 0 & n \geq k \\ \end{cases} \\ \mu_n & = \begin{cases} n \mu & 0 \leq n < c \\ c \mu & n \geq c \\ \end{cases} \\ r & = \lambda/\mu \quad \lambda_e = \lambda(k - L) \end{aligned} \]
\[P_0 = \biggl[\sum\limits_{n=0}^k \prod\limits_{j=0}^{n-1} (\dfrac{\lambda_j}{\mu_{j+1}})\biggr]^{-1}\] \[ P_n = \begin{cases} \binom{k}{n} r^n P_0 & 1 \leq n < c \\[2ex] \binom{k}{n} \dfrac{n!}{c^{n-c} c!} r^n P_0 & c \leq n \leq k \end{cases} \]
\[ L_q = \begin{cases} \dfrac{P_0 r^c \rho}{c!(1 - \rho)^2}[1 - \rho^{k-c} - (k-c) \rho^{k-c} (1 - \rho)] & \rho < 1 \\[2ex] \dfrac{r^c (k - c)(k - c + 1)}{2c!} P_0 & \rho = 1 \end{cases} \]
D.4.7 M/M/1/k/k Queue
\[\begin{aligned} \lambda_n & = \begin{cases} (k - n)\lambda & 0 \leq n < k \\ 0 & n \geq k \\ \end{cases} \\ \mu_n & = \begin{cases} (k - n)\lambda & 0 \leq n \leq k \\ 0 & n > k \\ \end{cases} \\ r & = \lambda/\mu \quad \lambda_e = \lambda(k - L) \end{aligned} \] \[P_0 = \biggl[\sum\limits_{n=0}^k \prod\limits_{j=0}^{n-1} \biggl(\dfrac{\lambda_j}{\mu_{j+1}}\biggr)\biggr]^{-1}\] \[\begin{array}{c} P_n = \binom{k}{n} n! r^n P_0 \\[1.5ex] 0 \leq n \leq k \end{array}\]
\[ L_q = k - \biggl(\dfrac{\lambda + \mu}{\lambda}\biggr)(1 - P_0) \]
D.4.8 M/M/c/k/k Queue
\[\begin{aligned} \lambda_n & = \begin{cases} (k - n)\lambda & 0 \leq n < k \\ 0 & n \geq k \\ \end{cases} \\ \mu_n & = \begin{cases} n \mu & 0 \leq n < c \\ c \mu & n \geq c \\ \end{cases} \\ r & = \lambda/\mu \quad \lambda_e = \lambda(k - L) \end{aligned} \] \[ P_0 = \biggl[\sum\limits_{n=0}^k \prod\limits_{j=0}^{n-1} (\dfrac{\lambda_j}{\mu_{j+1}})\biggr]^{-1} \]
\[P_n = \begin{cases} \binom{k}{n} r^n P_0 & 1 \leq n < c \\[2ex] \binom{k}{n} \dfrac{n!}{c^{n-c} c!} r^n P_0 & c \leq n \leq k \end{cases} \]
\[ L_q = \sum\limits_{n=c}^k (n - c) P_n \]