# Queueing Theory (M/M/1 with priorities)

• TaPaKaH
In summary, the problem involves two types of customers with different arrival and service time distributions, sharing one server with preemptive priority given to type 1 customers. The fraction of time in which there are no type 1 customers in the system and exactly one type 2 customer in the server and queue is difficult to compute due to the varying lengths and start times of observation periods. Various methods, such as multi-dimensional generating function methods and considering the system from the perspective of type 2 customers, may be used to solve this problem.
TaPaKaH

## Homework Statement

Suppose we have two types of customers, whose interarrival times are exponentially distributed with parameters ##\lambda_1## and ##\lambda_2##.
These customers have to share one server that gives preemptive priority to customers of type 1.
The service times are exponentially distributed with parameters ##\mu_1## and ##\mu_2##.

How can one compute the fraction of time, during which there are no type 1 customers in server+queue given that there is exactly one type 2 customer in server+queue?

## The Attempt at a Solution

I tried to approach the problem via balance equations for the number of type 1 customers, but couldn't figure out a way to implement "having exactly one type 2 customer" into the transition rates.

TaPaKaH said:

## Homework Statement

Suppose we have two types of customers, whose interarrival times are exponentially distributed with parameters ##\lambda_1## and ##\lambda_2##.
These customers have to share one server that gives preemptive priority to customers of type 1.
The service times are exponentially distributed with parameters ##\mu_1## and ##\mu_2##.

How can one compute the fraction of time, during which there are no type 1 customers in server+queue given that there is exactly one type 2 customer in server+queue?

## The Attempt at a Solution

I tried to approach the problem via balance equations for the number of type 1 customers, but couldn't figure out a way to implement "having exactly one type 2 customer" into the transition rates.

You need to show your work: what are the balance equations you tried to use?

Last edited:
The unconditioned number of type 1 customers in the system is a Markov chain with the following transition rates:

This yields balance equations ##p_n=\left(\frac{\lambda_1}{\mu_1}\right)p_{n-1}## that are easy to solve.

But, when we condition on there being exactly one type 2 customer, the "observation periods" have different lengths (which is ~##exp(\lambda_2)## for ##p_n,n\in\mathbb{N}## until another customer of type 2 arrives and ~##exp(\lambda_2+\mu_2)## for ##p_0## until either another type 2 customer arrives or current type 2 customer goes through their service) and might not start at "random times", which is causing me problems.

TaPaKaH said:
The unconditioned number of type 1 customers in the system is a Markov chain with the following transition rates:

This yields balance equations ##p_n=\left(\frac{\lambda_1}{\mu_1}\right)p_{n-1}## that are easy to solve.

But, when we condition on there being exactly one type 2 customer, the "observation periods" have different lengths (which is ~##exp(\lambda_2)## for ##p_n,n\in\mathbb{N}## until another customer of type 2 arrives and ~##exp(\lambda_2+\mu_2)## for ##p_0## until either another type 2 customer arrives or current type 2 customer goes through their service) and might not start at "random times", which is causing me problems.

This transition diagram does not include any type-2 customers. I think you need a 2-dimensional diagram with nodes of the form (i,j), i = number of type 2 present and j = number of type 1. You have drawn the diagram for the first "row" (0,j), j = 0,1,2, ... .

Two-dimensional diagram is what I initially started with but it eventually reduced to this, which I thought might be "easier" to solve.

/
TaPaKaH said:
Two-dimensional diagram is what I initially started with but it eventually reduced to this, which I thought might be "easier" to solve.

"Easier" ≠ "correct". The type-2 customers make an important contribution to the system: for example, if ##\lambda_2 / \mu_2 > 1## the system will be unstable (having no finite steady-state distribution) even though the type-1 queue might be stable, with ##\lambda_1 / \mu_2 < 1##.

Ray Vickson said:
/

"Easier" ≠ "correct". The type-2 customers make an important contribution to the system: for example, if ##\lambda_2 / \mu_2 > 1## the system will be unstable (having no finite steady-state distribution) even though the type-1 queue might be stable, with ##\lambda_1 / \mu_2 < 1##.

Just to clarify: assuming a stable system and states of the form (i,j), where i = number of type-2 customers present in the system, and j = number of type-1, the two-dimensional transitition diagram can be analyzed using principles of balance, to conclude that the quantities
$$p_j = \sum_{i=0}^{\infty} \pi_{i,j}$$
do, indeed satisfy ##\lambda_1 p_j = \mu_1 p_{j+1}##, giving ##p_0 = 1/(1-\rho_1)## and ##p_j = {\rho_1}^j\, p_0, \; j = 1, 2, \ldots .## Here, ##p_j## is the equilibrium probability that there are ##j## type-1 customers present in the system (in queue + in service). However, in terms of the 2-dimensional state space (i,j), you are asked to compute ##P(j=0|i=1)##.

Well, the global balance equations system is as follows$$\begin{cases}\begin{array}{rl}(\lambda_1+\lambda_2)p_{0,0}=\mu_2p_{0,1}+\mu_1p_{1,0}\\(\lambda_1+\lambda_2+\mu_1)p_{i,0}=\lambda_1p_{i-1,0}+\mu_1p_{i+1,0}&i\in\mathbb{N}\\(\lambda_1+\lambda_2+\mu_2)p_{0,j}=\lambda_2p_{0,j-1}+\mu_2p_{0,j+1}+\mu_1p_{1,j}&j\in\mathbb{N}\\(\lambda_1+\lambda_2+\mu_1)p_{i,j}=\lambda_1p_{i-1,j}+\lambda_2p_{i,j-1}+\mu_1p_{i+1,j}&(i,j)\in\mathbb{N}^2\end{array}\end{cases}$$In addition, we have the normalisation ##\sum_{i,j=0}^\infty p_{i,j}=1## and from analysis of queue 1 that doesn't "see" queue 2 we have ##\sum_{j=0}^\infty p_{i,j}=\left(1-\frac{\lambda_1}{\mu_1}\right)\left(\frac{\lambda_1}{\mu_1}\right)^i## for ##i\in\mathbb{N}_0##.
But I still can't see how this whole system could be explicitly solved to obtain ##p_{i,j}## and ##p_{0,1}## in particular.

TaPaKaH said:
Well, the global balance equations system is as follows$$\begin{cases}\begin{array}{rl}(\lambda_1+\lambda_2)p_{0,0}=\mu_2p_{0,1}+\mu_1p_{1,0}\\(\lambda_1+\lambda_2+\mu_1)p_{i,0}=\lambda_1p_{i-1,0}+\mu_1p_{i+1,0}&i\in\mathbb{N}\\(\lambda_1+\lambda_2+\mu_2)p_{0,j}=\lambda_2p_{0,j-1}+\mu_2p_{0,j+1}+\mu_1p_{1,j}&j\in\mathbb{N}\\(\lambda_1+\lambda_2+\mu_1)p_{i,j}=\lambda_1p_{i-1,j}+\lambda_2p_{i,j-1}+\mu_1p_{i+1,j}&(i,j)\in\mathbb{N}^2\end{array}\end{cases}$$In addition, we have the normalisation ##\sum_{i,j=0}^\infty p_{i,j}=1## and from analysis of queue 1 that doesn't "see" queue 2 we have ##\sum_{j=0}^\infty p_{i,j}=\left(1-\frac{\lambda_1}{\mu_1}\right)\left(\frac{\lambda_1}{\mu_1}\right)^i## for ##i\in\mathbb{N}_0##.
But I still can't see how this whole system could be explicitly solved to obtain ##p_{i,j}## and ##p_{0,1}## in particular.

This is not an easy problem. Perhaps you can try to use multi-dimensional generating function methods, in which you use the balance equations to obtain the mgf
$$M(u,v) = \sum_{i=0}^{\infty} \sum_{j=0}^{\infty} p_{i,j} u^i v^j$$
You can look at this as either
$$M(u,v) = \sum_{i=0}^{\infty} B_i(v) u^i, \text{ where } B_i(v) = \sum_{j=0}^{\infty} p_{i,j} v^j$$
or as
$$M(u,v) = \sum_{j=0}^{\infty} A_j(u) v^j, \text{ where } A_j(u) = \sum_{i=0}^{\infty} p_{i,j} u^i$$
The balance equations might yield a solution for M(u,v) in terms of some undetermined constants, which could then be determined by using auxiliary information about system stability, etc. It might work; try it and see.

Another approach you might try is to look at the system from the point of view of type-2 customers. They see an M/M/1 queue with server 'vacations'. Vacations are periods during which the server is unavailable = times when it is serving customers of type-1. However, unlike many vacational queueing models, this one let's the server abandon service (to start a vacation) during the service of a customer (if a type-1 arrival kicks out the type-2 customer); most vacational queueing models allow the current service to be completed before the server goes on vacation. Anyway, the length of a server vacation is equal to the busy period of the M/M/1 queue for type-1 customers; this random variable (busy period length) has a complicated, non-exponential distribution involving Bessel functions, although its Laplace transform is not too bad.

Another, related approach is to note that the service time of a type-2 customer will be some very complicated thing consisting of a sum of iid exponentials and a random number of iid type-1 busy periods. (This corresponds to a number if iid exponential attempts, plus a number of type-1 busy periods during our poor type-2 customer is told to go and wait.) I think it might be possible to get the Laplace transform of the type-2 customer service time, and if so, the problem for type-2 customers becomes a simple M/G/1 queue with a horribly complicated service time distribution. However, getting from there to anything like a distribution of the number of type-2 customers present still seems difficult.

Last edited:
I tried the second approach: the busy period ##BP## for type-1 customers has the following Laplace-Stieltjes transform: ##\tilde{BP}(s)=\frac{\lambda_1+\mu_1+s-\sqrt{(\lambda_1+\mu_1+s)^2-4\lambda_1\mu_1}}{2\lambda}## so we can indeed model the type-2 queue as a queue, in which server uptimes are i.i.d. ~##\exp(\lambda_1)## and downtimes have LST above. However, this didn't yield any progress as computing type-2 distribution was too technically difficult.

I will try the first approach you suggested and see what comes out of it.

TaPaKaH said:
I tried the second approach: the busy period ##BP## for type-1 customers has the following Laplace-Stieltjes transform: ##\tilde{BP}(s)=\frac{\lambda_1+\mu_1+s-\sqrt{(\lambda_1+\mu_1+s)^2-4\lambda_1\mu_1}}{2\lambda}## so we can indeed model the type-2 queue as a queue, in which server uptimes are i.i.d. ~##\exp(\lambda_1)## and downtimes have LST above. However, this didn't yield any progress as computing type-2 distribution was too technically difficult.

I will try the first approach you suggested and see what comes out of it.

I found the following (free) paper that does all this:
http://arxiv.org/ftp/arxiv/papers/0902/0902.2086.pdf

It uses the 2-dimensional state space and finds the bivariate mgf. I have not checked it for correctness.

Note added in edit: I checked more carefully, and see that the above paper assumes ##\mu_1 = \mu_2##, although ##\lambda_1, \lambda_2## may differ. Also: the priority is non-preemptive. So, the your case has still not been done, but the paper perhaps points out a way of getting started, and the types of arguments that may be involved.

Last edited:

## 1. What is "Queueing Theory (M/M/1 with priorities)"?

"Queueing Theory (M/M/1 with priorities)" is a mathematical theory used to study the behavior and performance of queues, or waiting lines, in systems with a single server and multiple types of customers with different priorities. This theory is commonly used in various fields such as computer science, telecommunications, and operations research.

## 2. What does the "M/M/1" notation represent in this theory?

The "M/M/1" notation in "Queueing Theory (M/M/1 with priorities)" represents the characteristics of the queueing system being studied. The first "M" stands for Markovian, meaning that the arrival and service times of customers follow a Poisson process. The second "M" also stands for Markovian, indicating that the service discipline is memoryless, or that the server does not take into account past service times. The "1" represents the number of servers in the system, which in this case is one.

## 3. How are priorities incorporated into the "M/M/1 with priorities" model?

In the "M/M/1 with priorities" model, customers are classified into different priority levels based on their importance or urgency. The higher priority customers are served before the lower priority ones, and if there are multiple customers with the same priority level, they are served on a first-come-first-served basis. This allows for more efficient and fair service in systems where certain customers may require faster service than others.

## 4. What are some real-life applications of "Queueing Theory (M/M/1 with priorities)"?

Queueing theory is used in a wide range of industries and systems, including call centers, airports, hospitals, and computer networks. In these applications, the theory helps to optimize resources and improve customer satisfaction by analyzing factors such as waiting times, service times, and queue lengths. The incorporation of priorities in the "M/M/1 with priorities" model allows for better management of different types of customers in these systems.

## 5. What are some limitations of the "M/M/1 with priorities" model?

One of the main limitations of the "M/M/1 with priorities" model is that it assumes a single server, which may not accurately reflect real-world systems with multiple servers. Additionally, the model assumes that customers arrive and are served according to a Poisson process, which may not always be the case. Furthermore, the model does not account for factors such as customer impatience, balking (leaving the queue), and reneging (leaving the system before being served), which can affect the overall performance of the system.

Replies
1
Views
2K
Replies
1
Views
4K
Replies
12
Views
2K
Replies
6
Views
1K
Replies
1
Views
3K
Replies
18
Views
2K
Replies
2
Views
1K
Replies
1
Views
2K
Replies
1
Views
2K
Replies
3
Views
1K