M/D/1 queue

The transition probability matrix for an M/D/1 queue with arrival rate λ and service time 1, such that λ <1 (for stability of the queue) is given by P as below:[4]

${\displaystyle P={\begin{pmatrix}a_{0}&a_{1}&a_{2}&a_{3}&...\\a_{0}&a_{1}&a_{2}&a_{3}&...\\0&a_{0}&a_{1}&a_{2}&...\\0&0&a_{0}&a_{1}&...\\...&...&...&...&...\\\end{pmatrix}}}$ ， ${\displaystyle a_{n}={\frac {\lambda ^{n}}{n!}}e^{-\lambda }}$, n = 0,1,....

The following expressions present the classic performance metrics of a single server queuing system such as M/D/1, with:

• arrival rate ${\displaystyle =\lambda }$,
• service rate ${\displaystyle =\mu }$, and
• utilization ${\displaystyle =\rho ={\frac {\lambda }{\mu }}}$

The average number of entities in the system, L is given by:

${\displaystyle L=\rho +{\frac {1}{2}}\left({\frac {\rho ^{2}}{1-\rho }}\right);}$

The average number of entities in the queue (line), L_Q is given by:

${\displaystyle L_{Q}={\frac {1}{2}}\left({\frac {\rho ^{2}}{1-\rho }}\right);}$

The average waiting time in the system, ω is given by:

${\displaystyle \omega ={\frac {1}{\mu }}+{\frac {\rho }{2\mu (1-\rho )}};}$

The average waiting time in the queue (line), ω _Q is given by:

${\displaystyle \omega _{Q}={\frac {\rho }{2\mu (1-\rho )}}}$

Considering a system that has only one server, with an arrival rate of 20 entities per hour and the service rate is at a constant of 30 per hour.

So the utilization of the server is: ρ=20/30=2/3. Using the metrics shown above, the results are as following: 1) Average number in line L_Q= 0.6667; 2) Average number in system L =1.333; 3) Average time in line ω_Q = 0.033 hour; 4) Average time in system ω = 0.067 hour.

For an equilibrium M/G/1 queue, the expected value of the time W spent by a customer in the queue are given by Pollaczek-Khintchine formula as below:[5]

${\displaystyle E(W)={\frac {\rho \tau }{2(1-\rho )}}\left(1+{\frac {\sigma ^{2}}{\tau ^{2}}}\right)}$

where τ is the mean service time; σ² is the variance of service time; and ρ=λτ < 1, λ being the arrival rate of the customers.

For M/M/1 queue, the service times are exponentially distributed, then σ² = τ² and the mean waiting time in the queue denoted by W_M is given by the following equation:[5]

${\displaystyle {W_{M}}={\frac {\rho \tau }{1-\rho }}}$

Using this, the corresponding equation for M/D/1 queue can be derived, assuming constant service times. Then the variance of service time becomes zero, i.e. σ² = 0. The mean waiting time in the M/D/1 queue denoted as W_D is given by the following equation:[5]

${\displaystyle {W_{D}}={\frac {\rho \tau }{2(1-\rho )}}}$

From the two equations above, we can infer that Mean queue length in M/M/1 queue is twice that in M/D/1 queue.

A stationary distribution for the number of customers in the queue and mean queue length can be computed using probability generating functions.[9]

The transient solution of an M/D/1 queue of finite capacity N, often written M/D/1/N, was published by Garcia et al. in 2002.[10]