# NTUEE QUEUEING THEORY 2021 FALL FINAL

## 1

Consider the departure process of an $M/M/1$ queue with arrival rate $\lambda$ and service rate $\mu$. In addition, we assume $\rho = \frac{\lambda}{\mu} < 1$.

1. Show that the probability that a departing customer observes an idle server after its departure is $1 - \rho$. (3%)
2. Show that the LST(Laplace-Stieltjes Transform) of its exponential service time distribution is given by $\frac{\mu}{\mu + s}$. (4%)
3. Show that the inter-departure time of this $M/M/1$ is a random variable with the following property: with probability $\rho$, it is exponential with density function $\mu e^{-\mu t}$, and with probability $1 - \rho$ it is the sum of two exponential random variables: the first one is with density function $\lambda e^{-\lambda t}$ and the second one is with density function $\mu e^{-\mu t}$. (5%)
4. Use the fact in 1.2. and 3. to show that the inter-departure time of an $M/M/1$ is an exponential random variable with mean equal to $\frac{1}{\lambda}$. (6%) (Hint: you may use LST to finish the proof in 4. or use convolution of probability density functions)

## 2

Please compare Mean Waiting Time before Service ($W_q$) and Serve Utilization (U) of the following queues. All queues are with exponential service time and Poisson arrival process. For simplicity, we assume $\mu_1 < \mu_2$, and total traffic intensity is always less than $1$.

Q1: a 2-class FCFS single server queue, each class with service rate $\mu_i$ and arrival rate $\lambda_i, i=1,2$.
Q2: a single class FCFS single server queue, with arrival rate equal to $\lambda_1 + \lambda_2$ and mean service time $\frac{1}{\mu_1} \cdot (\frac{\lambda_1}{\lambda_1 + \lambda_2}) + \frac{1}{\mu_2} \cdot (\frac{\lambda_2}{\lambda_1 + \lambda_2})$
Q3: a 2-class non-preemptive priority queue with single serve. Each class is with service rate $\mu_i$ and arrival rate $\lambda_i, i=1,2$. Class 1 has higher priority.

1. Please compare Q1 and Q2 for their $W_q$ and U. (10%)
2. Please compare Q1 and Q3 for their $W_q$ and U. (10%)
3. Give a final conclusion for their order in $W_q$ and U, or comment that no conclusion can be made about the comparison of 3 queues. (2%)

Hint: you may complete the comparison using the $M/G/1$ formula and priority queue formula, and if you have difficulty to prove the general case, complete the comparison using a specific numerical example.

## 3

If we consider $p_n, q_n$ and $\pi_n$ of an $M/D/1/k$, where $p_n$ is the steady state system size probability, $q_n$ is the system size probability observed by admitted customers upon their arrivals, and $\pi_n$ the system-size probability observed by departing customers. Assume arrival rate is $\lambda$, service time is $\frac{1}{\mu}$ and $\pi_n$ is already solved.

1. Please express $q_n$ using $\pi_n$. (5%)
2. Please express $p_n$ using $\pi_n$, $\lambda$ and $\mu$ for $n = 0,1,2,\cdots, k$ (8%)
3. Can your formula in 1. and 2. be applied to any $M/G/1/k$? (2%)

## 4

Consider a preemptive resume 2-class $M/M/1/2$ queue. Suppose the system state is defined as $(n_1, n_2)$, where $n_i$ represents the number of class-i customers. Let $\lambda_i$ be the arrival rate of class-i and service rate is $\mu$ for both classes. Notice that if the system has reached its system size limit($=2$), customers of both classes are blocked.

1. Please draw the complete system transition diagram. (5%)
2. Please write all global balance equations. (6%)
3. Please derive its server utilization. (4%)

## 5

Use Mean Value Analysis to solve the following queueing with fixed population $M=3$. There are 2 single-server queueing nodes in the system, and all nodes are with exponential service time. Suppose the service rates are: $\mu_1 = 1, \mu_2 = 3$ for node 1 and 2 respectively.

1. Please derive the mean system size of each queueing node (8%)
2. Please derive the arrival rate at each node (6%)
3. Please derive the server utilization of each node (3%)
4. Please derive the mean cycle time, if the customer starts at node $i, i =1 \text{ or } 2$ (3%)


## 6

Please derive the system size distribution of an $M/M/1$ queue with arrival rate $\lambda$ and service rate $\mu$, via the departure-point system-size approach in $M/G/1$. (20%)

1. Let $k(n)$ be the probability that n customers arrived during a service time period. And $K(z) = \sum_{n=0}^{\infty} k(n) z^n$. Please show that $K(z) = (1 + \rho(1 - z))^{-1}$
2. Please use the result in 1. to derive $\prod (z)$ of $M/M/1$ and then derive $\pi_n$ (Hint: You my reuse the general formula $\prod (z)$ for $M/G/1$ directly in 2.)