0
$\begingroup$

Most of the reading on queueing theory I've done focuses on when the arrival rate is less than the service rate so that the queue doesn't explode. However, if I have a queueing system (either M/M/1 or M/M/c) where the arrival rate is greater than the service rate, how can I find properties such as the following:

  • How large will the queueing system grow after a certain amount of time?
  • What is the probability that the expected wait time upon arrival will be greater than a certain amount of time at time t?
  • How many servers should the system have so that the queue never grows beyond a certain size in a fixed amount of time?
$\endgroup$
0
$\begingroup$

I'm many years removed from messing with queuing systems, so take this with a grain of salt. I think you can (theoretically) answer the first two questions, and the third with some trial and error (iterating over server counts), using the backward Kolmogorov equations. That requires solving a system of simultaneous PDEs. Alternatively, if you are asking about a specific system rather than asking a general theoretical question, you could probably get reasonably accurate results (while consuming fewer brain cells) doing it via discrete event simulation.

$\endgroup$
0
$\begingroup$

You can set up a Continuous Time Markov Chain to do the first two; the last one is infinite, since however many servers you have, there will always be some positive probability that there will be N customers coming (for any N). (In an M/M/c queue, the probability that 1000000 customers show up in 0.5 seconds is positive so long as the arrival rate is)

$\endgroup$
5
  • $\begingroup$ continuous time markov chain $\endgroup$ – E-A Jun 15 '18 at 20:17
  • $\begingroup$ I realize that an M/M/c queueing system can be modeled as a continuous time markov chain - more specifically, a birth-death process - however, in everything that I've read so far, I haven't found anything about determining the size of the system after a certain amount of time. $\endgroup$ – Tanner Jun 15 '18 at 20:20
  • $\begingroup$ The steady-state behavior of M/M/c queues has been extensively studied. Balance eqns can be solved to give the steady-state distn based on the arrival rate $\lambda$ and the service rate $\mu\, (\lambda < c\mu)$ of each of the $c$ servers. Then one can find the avg nr $L$ of people in the system, the avglength $W = L/\lambda$ of time a customer spends in the system, the avg nr of people waiting for service and the avg length of time a customer spends waiting for service. The eqn $L = \lambda W$ is called Little's Law. See books and sites on queues, Operations Rsch, and Stochastic Processes. $\endgroup$ – BruceET Jun 16 '18 at 3:49
  • $\begingroup$ I'm not interested in the steady-state behavior of the queueing system in question, as the arrival rate is time dependent. I want to know how it behaves during peak hours, to see how long it can handle increased traffic. Therefore, Little's Law is not helpful in this situation. $\endgroup$ – Tanner Jun 18 '18 at 22:44
  • $\begingroup$ Hmm, the fact that it is time dependent really messes things up; your best bet is to solve a bunch of ODEs. $\endgroup$ – E-A Jun 21 '18 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.