0.3 Queues with poisson arrivals, exponential servers

A standard model of a queueing system with a single waiting line and one or more servers assumes that “customers” arrive according to a Poisson process withrate $\left(\lambda \right)$ . The customer at the head of the line goes to the first available server, if there are more than one, or to the single server as soonas available, if there is only one. The servers operate independently (of each other and the arrival process), each with exponential service time. We supposeeach server has the same distribution, exponential $\left(\mu \right)$ . Such a system may be analyzed as a Markov birth-death process. An analysis of the long-runprobabilities and expectations of various quantities after the system has settled down to equilibrium yields the results below.

Calculation of these quantities is straightforward, but somewhat tedious if various cases are considered. Matlab procedures for single-server andtwo-server systems are utilized to make these calculations quickly and to present them in a useful way.

Notation

• $N_t=$ number in system (in service and waiting) at time t
• $Q_t=$ number waiting to be served at time t
• ${\displaystyle {\pi }_j=\underset{t\to \infty }{lim}{p}_{i}j\left(t\right)=}$ long-run probability of being in state j
• $W_t=$ waiting time for service for customer who arrives at time t
• $D_t=$ waiting time plus service time for customer who arrives at time t

• $A=$ random variable with distribution of interarrival times
• $S=$ random variable with distribution of service times

Long-run probabilities ${\pi }_j=P(N_t=j)$ for large $t,s$ servers, $E\left[A\right]=1/\lambda ,E\left[S\right]=1/\mu$

For $s=1$ ,

• $\rho =E\left[S\right]/E\left[A\right]=\lambda /\mu$
• ${\pi }_0=1-\rho {\pi }_n=(1-\rho ){\rho }^n$
• $N_t\text{is}\text{approximately}\text{geometric}(1-\rho )$

For $s>1$ ,

• $\rho =E\left[S\right]/sE\left[A\right]=\lambda /s\mu$
• ${\displaystyle {\pi }_n=\left\{\begin{array}{cc}{\pi }_0{\left(s\rho \right)}^n/n!={\pi }_0{(\lambda /\mu )}^n/n!\hfill & 0\le n\le s\hfill \\ {\pi }_0(s^s/s!){\rho }^n={\pi }_0[{\left(s\rho \right)}^s/s!]{\rho }^{n-s}\hfill & s<n\hfill \end{array}\right)}$

For $s=2$

• ${\displaystyle {\pi }_0=\frac{1-\rho }{1+\rho }=\frac{2\mu -\lambda }{2\mu +\lambda }}$

For $s=3$

• ${\displaystyle {\pi }_0=\frac{1-\rho }{1+2\rho +\frac{3}{2}{\rho }^2}}$

For $s=4$

• ${\displaystyle {\pi }_0=\frac{1-\rho }{1+3\rho +8{\rho }^2+\frac{8}{3}{\rho }^3}}$

For large t , with the system in equilibrium

For $s=1$

• ${\displaystyle E\left[N_t\right]=\frac{\rho }{1-\rho }=\frac{\lambda }{\mu -\lambda }}$
• $E\left[Q_t\right]=\rho E\left[N_t\right]P(N_t>0)=\rho$
• ${\displaystyle E\left[W_t\right]=E\left[S\right]E\left[N_t\right]=\frac{\lambda /\mu }{\mu -\lambda }}$
• D _t is approximately exponential $(\mu -\lambda )$

For $s>1$

• ${\displaystyle C=P(W_t>0)={\pi }_0\frac{{\left(s\rho \right)}^s}{s!(1-\rho )}=E\left[Q_t\right]\frac{1-\rho }{\rho }=s\mu (1-\rho )E\left[W_t\right]}$
• $P(W_t>v)=C{e}^{-(\mu s-\lambda )v}v\ge 0$
• ${\displaystyle P(D_t>v)=e^{-\mu v}\left[1,+,C,\mu ,\frac{1-e^{-\left[\mu \right(s-1)-\lambda ]v}}{\mu (s-1)-\lambda }\right]\text{for}\lambda \ne \mu (s-1)}$
• $P(D_t>v)=e^{-\mu v}[1+\mu Cv]\text{for}\lambda =\mu (s-1)$
• ${\displaystyle E\left[Q_t\right]={\pi }_0\frac{{\left(s\rho \right)}^s}{s!}\frac{\rho }{{(1-\rho )}^2}}$
• ${\displaystyle E\left[N_t\right]\approx E\left[Q_t\right]+\frac{\lambda }{\mu }=E\left[Q_t\right]+s\rho }$

Matlab calculations for single server queue (in file queue1.m)