1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Queueing Theory (M/M/1 with priorities)

  1. Mar 13, 2014 #1
    1. The problem statement, all variables and given/known data
    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?

    3. 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.
     
  2. jcsd
  3. Mar 13, 2014 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You need to show your work: what are the balance equations you tried to use?
     
    Last edited: Mar 13, 2014
  4. Mar 13, 2014 #3
    The unconditioned number of type 1 customers in the system is a Markov chain with the following transition rates:
    1adj47.png
    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.
     
  5. Mar 13, 2014 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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, ... .
     
  6. Mar 13, 2014 #5
    Two-dimensional diagram is what I initially started with but it eventually reduced to this, which I thought might be "easier" to solve.
     
  7. Mar 13, 2014 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    /
    "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##.
     
  8. Mar 14, 2014 #7

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
    [tex] p_j = \sum_{i=0}^{\infty} \pi_{i,j}[/tex]
    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)##.
     
  9. Mar 16, 2014 #8
    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.
     
  10. Mar 16, 2014 #9

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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
    [tex] M(u,v) = \sum_{i=0}^{\infty} \sum_{j=0}^{\infty} p_{i,j} u^i v^j [/tex]
    You can look at this as either
    [tex] 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 [/tex]
    or as
    [tex] 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 [/tex]
    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 lets 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: Mar 16, 2014
  11. Mar 16, 2014 #10
    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.
     
  12. Mar 16, 2014 #11

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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: Mar 16, 2014
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Queueing Theory (M/M/1 with priorities)
  1. M/M/1 Systems (Replies: 6)

Loading...