Suppose customers join a queue with a poisson arrival rate 𝑚. If a customer is not served within a unit of time, she abandons the queue. Customers are served by two servers: one of the servers runs the first-come-first-served (FCFS) policy and the other one the last-come-first-served (LCFS) policy. The FCFS server has a service time that is iid exponentially with mean $\lambda m$, where $\lambda<1$. The LCFS server has a service time that is iid exponentially with mean $\delta m$, where $\delta<1-\lambda$. A customer departs the queue after being served by either of the servers. I would like to show that the average length of the queue is at least $(1-\delta)m -o(m)$. Any input will be appreciated!

P.S. A special case of this problem when $\delta=0$ has been solved here Average queue length with impatient customers while the intuition seems similar, I have not been able to adapt this approach.


The system you are describing is the simple $M/M/2/\infty$ queue with heterogeneous servers (one with service rate $1/(\lambda m)$, the other with the service rate $1/(\delta m)$) and the arrival rate $m$.

This queue can be solved analytically. Although the formulas will be cumbersome. The full solution for your case you can find here https://www.jstor.org/stable/167292. Although there are also matrix-geometric solutions available out there, which may be somewhat simpler.

Since you are interested only in the queue length, i would suggest the following answer. Let $b$ be the minimum service rate among the two i.e. $b=\max(1/(\lambda m), 1/(\delta m))$. Then the average queue length (I mean here TOTAL number of jobs in the system i.e. queue + servers) in your queue will be $\ge $ than the average queue length in the similar queue but with identical servers working at rate $b$. But for identical servers it is known (see, for example, page 152 here https://pdfs.semanticscholar.org/848f/a1f48ad9d3edb24b05667f15cfc633eb8f69.pdf ) that the average queue length is equal to $$ {2 {m \over 2 b} \over 1 - ({m \over 2 b})^2}. $$

Now, probably, some algebra will help you get the result you are looking for.

  • $\begingroup$ I'm probably missing something, but (1) what does the $\infty$ in $M/M/2/\infty$ represent? And (2) how does this model incorporate the "impatient customer" aspect of the OP, i.e. "If a customer is not served within a unit of time, she abandons the queue."? $\endgroup$ – antkam Sep 19 '19 at 18:23
  • $\begingroup$ $M/M/2$ is the notation describing the specific queueing system. Please check what is "Kendall notation" in Wikipedia. I was answering your question and in your question there are no impatient customers. $\endgroup$ – rrv Sep 19 '19 at 20:39
  • $\begingroup$ sorry, I am not the OP so I dont know what you mean by "my question". :) The OP did include impatient customers (see 2nd sentence). Also, I did check Kendall notation in wiki and the $\infty$ just means no restriction on queue length, which is the default anyway, so I was surprised to see you write $M/M/2/\infty$ instead of simply $M/M/2$ and hence I was wondering if you meant something else by the $\infty$... $\endgroup$ – antkam Sep 19 '19 at 20:46
  • $\begingroup$ @rrv thanks for your note, but there are some differences with my setting and the settings you refer to. 1) in my setting there's a one FCFS and one LCFS server. 2) the impatience plays a significant role in the analysis. the M/M/2 queuing model does not include impatience $\endgroup$ – afshi7n Sep 20 '19 at 1:58
  • $\begingroup$ @afshi7n 1) in your setting the type of server does not matter. this follows from the fact that FCFS or LCFS policies are equivalent with respect to the average queue size. 2) in your setting there is no impatience. $\endgroup$ – rrv Sep 20 '19 at 14:00

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.