M/D/1 queue: Difference between revisions

Revision as of 02:58, 12 May 2016

Revision as of 03:04, 12 May 2016

Line 10:

* The buffer is of infinite size, so there is no limit on the number of customers it can contain.

The [[state space]] diagram for M/D/1 queue is as below:

[[File:Flow_chart111.png|link=https://en.wikipedia.org/wiki/File:Flow_chart111.png|left|thumb|602x602px|Stage Space Diagram of M/D/1 Queue|none]]

=== Transition Matrix: ===

<math>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}</math> ， <math>a_n=\frac{\lambda^n}{n!}e^{-\lambda}</math>, n = 0,1,....

=== Classic performance metrics: ===

<math>L=\rho+\frac{1}{2}\left ( \frac{\rho^2}{1-\rho} \right );

</math>

<math>L_Q=\frac{1}{2}\left ( \frac{\rho^2}{1-\rho} \right );

</math>

<math>\omega= \frac{1}{\mu}+\frac{\rho}{2\mu(1-\rho)};

</math>

<math>\omega_Q=\frac{\rho}{2\mu(1-\rho)}</math>

=== Example: ===

Customers arrive a Starbucks line at a rate of 20 per hour, and follows an exponential distribution. There is only one server, the service rate is at a constant of 30 per hour.

Arrival Rate: 20 per hour

Service Rate: 60 per hour

ρ=20/30=2/3

Using the queueing theory equations, the results are as following:

Average number in line= 0.6667

Average number in system: 1.333

Average time in line: 0.033

Average time in system: 0.067

=== Relation for Mean Waiting Time in M/M/1 and M/D/1 queues<ref>{{Cite book|title=Introduction to Queuing Theory|last=Cooper|first=Robert B.|publisher=Elsevier Science Publishing Co.|year=1981|isbn=0-444-00379-7|___location=|pages=189}}</ref>: ===

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

<math>E(W)=\frac{\rho\tau}{2(1-\rho)}(1+\frac{\sigma^2}{\tau^2})</math>

where τ is the mean service time; <math display="inline">\sigma^2</math> 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 <math display="inline">\sigma^2</math>=<math display="inline">\tau^2</math> and the mean waiting time in the queue denoted by WM is given by the following equation

<math>\overline{W_M}=\frac{\rho\tau}{1-\rho}</math>

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.  <math display="inline">\sigma^2</math>=0.  The mean waiting time in the M/D/1 queue denoted as WD is given by the following equation

<math>\overline{W_D}=\frac{\rho\tau}{2(1-\rho)}</math>

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.

==Stationary distribution==

Line 41 ⟶ 92:

==References==

<references />{{Queueing theory}}

{{Reflist}}

{{Queueing theory}}

{{Stochastic processes}}