Average queue length under FCFS and LCFS simultaneously

481 Views Asked by At

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.

1

There are 1 best solutions below

9
On

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.