Queueing theory problems

Problem 1

Customers of two types arrive to a system according to independent Poisson processes with rates {\lambda_A} and {\lambda_B} , respectively. The system has two servers, each serving only one customer type with rates {\mu_A} for customer type {A} and {\mu_B} for customer type {B}. There is room for only one customer to wait in a queue which is shared by the two servers. When the queue position is occupied, arriving customers are lost.

Let {\{X(t):t\geqslant 0\}} be a CTMC describing this process

  1. Define the state space.
  2. Write the balance equations.
  3. What is the long-run utilization of server {A}?

Let the state space be {\mathcal S=\{000,010,001,011,A10,A11,B01,B11 \}} where the first symbol in each state denotes the buffer status, the second symbol denotes the status of server {A}, and the third symbol the status of server {B}. The generator matrix of transition rates is given by

\displaystyle \scriptsize G=\begin{pmatrix} -(\lambda_A+\lambda_B) & \lambda_A & \lambda_B & 0 & 0 & 0 & 0 & 0\\ \mu_A & -(\lambda_A+\lambda_B+\mu_A) & 0 & \lambda_B & \lambda_A & 0 & 0 & 0\\ \mu_B & 0 & -(\lambda_A+\lambda_B+\mu_B) & \lambda_A & 0 & 0 & \lambda_B & 0\\ 0 & \mu_B & \mu_A & -(\lambda_A+\lambda_B+\mu_A+\mu_B) & 0 & \lambda_A & 0 & \lambda_B\\ 0 & \mu_A & 0 & 0 & -\mu_A & 0 & 0 & 0\\ 0 & 0 & 0 & \mu_A & \mu_B & -(\mu_A+\mu_B) & 0 & 0\\ 0 & 0 & \mu_B & 0 & 0 & 0 & -\mu_B & 0\\ 0 & 0 & 0 & \mu_B & 0 & 0 & \mu_A & -(\mu_A+\mu_B)\\ \end{pmatrix}\normalsize

The global balance equations are given by

\displaystyle  \begin{aligned} 	(\lambda_A+\lambda_B)\pi_{000} &= \mu_A\pi_{010}+\mu_B\pi_{001}\\ 	(\lambda_A+\lambda_B+\mu_A)\pi_{010} &= \lambda_A\pi_{000} + \mu_A\pi_{A10}+\mu_B\pi_{011}\\ (\lambda_A+\lambda_B+\mu_B)\pi_{001} &= \lambda_B\pi_{000} + \mu_A\pi_{011}+\mu_B\pi_{B01}\\ (\lambda_A+\lambda_B+\mu_A+\mu_B)\pi_{011} &= \lambda_A\pi_{001} + \lambda_B\pi_{010} + \mu_A\pi_{A11} + \mu_B\pi_{B11}\\ \mu_A\pi_{A10} &= \lambda_A\pi_{010} + \mu_B\pi_{A11}\\ (\mu_A+\mu_B)\pi_{A11} &= \lambda_A\pi_{011}\\ \mu_B\pi_{B01} &= \lambda+B\pi_{001}+\mu_A\pi_{B11}\\ (\mu_A+\mu_B)\pi_{B11} &= \lambda_b\pi_{011}. \end{aligned}

The utilization of server {A} is given by

\displaystyle \pi_{010}+\pi_{011}+\pi_{A10}+\pi_{A11}.

Problem 2


Consider a single server queue where customers arrive according to a Poisson process with intensity {\lambda} and request i.i.d. {\mathsf{Exp}(\mu)} service times. The server is subject to failures and repairs. The lifetime of a working server is an {\mathsf{Exp}(\theta)} random variable, while the repair time is an {\mathsf{Exp}(\alpha)}. random variable. Successive lifetimes and repair times are independent, and are independent of the number of customers in the queue. When the server fails, all the customers in the queue are forced to leave, and while the server is under repair no new customers are allowed to join. Model this as a CTMC.

  1. What is the state space?
  2. What are the balance equations? Show how to solve them.
  3. What is the long run fraction of time the server is idle but not operational?
  4. What fraction of incoming customers leave without service?

Let {\{X(t):t\geqslant 0\}} be a CTMC on state space {\mathcal S=\{D\}\cup\{0,1,2,\ldots\}} with transition rates

\displaystyle  q_{i,j} = \begin{cases} \lambda,& j=i+1\\ \mu,& j=i-1\\ \theta,& i\ne D\text{ and } j=D\\ \alpha,& i=D\text{ and } j=0. \end{cases}

The balance equations are

\displaystyle  \begin{aligned} \mu\pi_{n+1} + \alpha\pi_D &= \lambda\pi_n + \theta\sum_{i=0}^n \pi_i,\ n\geqslant 0\\ \alpha\pi_D &= \theta\sum_{i=0}^\infty \pi_i. \end{aligned}

Since {\sum_{i\in S}\pi_i=1}, we have {\alpha\pi_D = \theta(1-\pi_D)} and hence {\pi_D=\frac{\theta}{\alpha+\theta}}. It follows that

\displaystyle  \begin{aligned} \pi_{n+1} &= \frac1\mu \left(\lambda\pi_n +\theta\sum_{i=0}^n\pi_i -\frac{\alpha\theta}{\alpha+\theta} \right)\\ &= \left(\frac{\lambda+\mu\theta}{\mu} \right)\pi_n + \frac\theta\mu\sum_{i=0}^{n-1}\pi_i -\frac{\alpha\theta}{\mu(\alpha+\theta)} \end{aligned}

Problem 3

Consider an M/M/1/2 queue with impatient customers. As soon as customer {j}’s sojourn time in the system exceeds {\tau_j}, he/she leaves the system without receiving service. (Customers can leave the system even when they are in service.) Suppose that {\{\tau_j :j \geqslant 1\}} are i.i.d. random variables exponentially distributed with rate {\gamma}. Customers arrive with rate {\lambda} and the service rate is {\mu}.

  1. Model this system as a CTMC and give the steady-state equations.
  2. Give an expression for the long-run average fraction of customers who are not admitted to the queue or choose to leave with either no service or incomplete service after they join.

Let {\{X(t):t\geqslant 0\}} be a CTMC on state space {\mathcal S=\{0, 1,2, 0_B,1_B\}}. Transitions to states {0_B} and {1_B} occur when a customer abandons. The transition rates are

\displaystyle  q_{ij} = \begin{cases} \lambda,& (i,j)\in\{(0,1), (1,2), (0_B,1), (1_B,2) \}\\ \mu,& (i,j)\in\{(1,0), (2,1)), (1_B,0) \}\\ \gamma,& (i,j) \in\{(1,0_B), (1_B, 0_B) \}\\ 2\gamma,& (i,j) = (2,1_B). \end{cases}

The transition matrix of the embedded Markov chain is

\displaystyle  P=\left( \begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ \frac{\mu }{\gamma +\lambda +\mu } & 0 & \frac{\lambda }{\gamma +\lambda +\mu } & \frac{\gamma }{\gamma +\lambda +\mu } & 0 \\ 0 & \frac{\mu }{2 \gamma +\mu } & 0 & 0 & \frac{2 \gamma }{2 \gamma +\mu } \\ 0 & 1 & 0 & 0 & 0 \\ \frac{\mu }{\gamma +\lambda +\mu } & 0 & \frac{\lambda }{\gamma +\lambda +\mu } & \frac{\gamma }{\gamma +\lambda +\mu } & 0 \\ \end{array} \right)

Solving {\pi P=\pi} and {\sum_{i\in\mathcal S}\pi_i=1} yields

\displaystyle  \begin{aligned} \pi_0 &= \frac{\mu }{2 (\gamma +\lambda +\mu )}\\ \pi_1 &= \frac{\gamma(2\gamma+3\mu)+\mu(\lambda+\mu)}{2 (2 \gamma +\mu ) (\gamma +\lambda +\mu )}\\ \pi_2 &= \frac{\lambda }{2 (\gamma +\lambda +\mu )}\\ \pi_{0_B} &= \frac{\gamma }{2 (\gamma +\lambda +\mu )}\\ \pi_{1_B} &= \frac{\gamma \lambda }{(2 \gamma +\mu ) (\gamma +\lambda +\mu )}. \end{aligned}

The long run fraction of customers who are not admitted is {\pi_2} and the effective arrival rate is

\displaystyle \lambda(1-\pi_2) = \frac{\lambda (\gamma +\mu ) (2 \gamma +\lambda +\mu )}{(2 \gamma +\mu ) (\gamma +\lambda +\mu )}.

The long run fraction of customers who abandon is

\displaystyle  \left(\frac{\gamma }{\gamma +\lambda +\mu }\right)\pi_1 + \left(\frac{2\gamma}{\mu+2\gamma}\right)\pi_2 + \left(\frac\gamma{\lambda+\mu+\gamma}\right)\pi_{1_B} = \frac{\gamma (4 \gamma +\mu )}{2 (2 \gamma +\mu ) (\gamma +\lambda +\mu )}. \\

Adding this two quantities yields

\displaystyle \frac{\gamma \lambda (4 \gamma +\mu )}{4 (2 \gamma +\mu ) (\gamma +\lambda +\mu )^2},

the long run fraction of throughput lost.

Problem 4


Customers arrive at a service station according to a Poisson process with rate {\lambda}. Servers arrive at this station according to an independent renewal process with i.i.d. interarrival times with mean {\tau} and second moment {s^2} . Each incoming server removes each of the waiting customers with probability {\alpha>0} in an independent fashion, and departs immediately. Let {X_n} be the number of customers at the service station after the {n^{\mathrm{th}}} server departs, and let {X(t)} be the number of customers at the station at time {t}.

  1. Show that {\{X_n:n\geqslant 0\}} is a DTMC.
  2. Compute the limiting value of {\mathbb E[X_n]} as {n\rightarrow\infty}.
  3. Show that {\{X(t):t\geqslant 0\}} is a Markov regenerative process.
  4. Compute the limiting value of {\mathbb E[X(t)]} as {\rightarrow\infty}.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s