5.5 Queues (Consider a Markov Chain with continuous time)

Let \[P_{ij} (t) = P\left (X(t + s) = j\, |\, X(s) = i\right ).\] Can a Queue be regarded as an irreducible chain?
Answer: Yes!
Hence a queue (M.C) possesses a limiting (stationary distribution) and we say that the queue is in statistical equilibrium.

If a Markov chain is irreducible then \(P_{ij}(t)\) as \(t\longrightarrow \infty \) exists and is independent of \(i\). Hence we can take \[\lim _{t\rightarrow \infty }P_{ij}(t) = P_j.\] Also \[\lim _{t\rightarrow \infty } P_{ij}(t) = \lim _{t\rightarrow \infty }P_j(t) = P_j\] or \[\lim _{t\rightarrow \infty }\frac {d\, P_j(t)}{dt} = 0.\]

5.5.2. A queue system is defined in terms of

(i)

Input process (It can be Poisson or by appointment).

(ii)

the queue discipline (First come First serve, ladies first).

(iii)

Service mechanism.

5.5.3 A queue system with one server and no waiting positions.
Assume that chance of a sequence in \((t, t+\Delta t)\) is \(\lambda \, \Delta t + O(\Delta t)\). Every customer who finds the server occupied leaves the system immediately. If a server is busy with a customer at time \(t\) then the customer will end in \((t, t + \Delta t)\) with probability \(\mu \, \Delta t + O(\Delta t)\).

Let \(N(t)\) be the length of the queue system at time \(t\). \[N(t) = 0, \hspace {0.3cm} 1.\] Let \[P_n(t) = P\left (N(t) = n\right )\] \[P_0(t + \Delta t) = P_0(t) (1 - \lambda \, \Delta t) + P_1(t) (\mu \, \Delta t)(1 - \lambda \, \Delta t)\] \[P'_0(t) = -\lambda \, P_0(t) + \mu \, P_1(t).\] As \(t \longrightarrow \infty \)

\[0 = -\lambda \, P_0 + \mu \, P_1\]

\[P_1 = \frac {\lambda }{\mu }\, P_0\] since \(\, P_0 + P_1 = 1.\) \[P_0 + \frac {\lambda }{\mu }\, P_0 = 1 \, \implies \, P_0 = \frac {\mu }{\mu + \lambda }\hspace {0.5cm}\text {and}\hspace {0.5cm} P_1 = \frac {\lambda }{\mu + \lambda }.\]

Hence when the queue system reaches statistical equilibrium, the probability distribution of the length of queue system is \[P_0 = \frac {\mu }{\lambda + \mu }\hspace {1cm} , \hspace {1cm} P_1 = \frac {\lambda }{\lambda + \mu }.\]

bf 5.5.4 Customers arrive at a two shoe shine stand at rate 10 per hour. The average length of a shoe shine is 6 minutes. There is only one attendant so that one chair is used as a waiting positions. Customers who find both chairs occupied go away.

i.

Assuming Poisson input and exponential service times find the probability distribution of the queue is statistical equilibrium.

\(\lambda = 10 \) per hour, \(\mu = 10\) per hour, \(N(t) = 0, 1, 2\).

\[P_0(t + \Delta t) = P_0(t) (1 - 10\Delta t) + P_1(t) (1 - 10\Delta t)(10\Delta t)\]

\[P_1(t + \Delta t) = P_1(t) (10 \Delta t)(10\Delta t) + P_1(t) (1 - 10\Delta t)(1 - 10\Delta t) + P_2(t)(1 - 10\Delta t)(10\Delta t)\] \[+ P_0(t) (10\Delta t).\] As \(\, \Delta t \, \longrightarrow 0,\) \[P'_0(t) = -10P_0(t) + 10 P_1(t)\] \[P'_1(t) = -10P_1(t) + 10 P_0(t) + 10 P_2(t).\] As \(\, t\longrightarrow \, \infty \) \[-10P_0 + 10 P_1 = 0 \, \implies \, P_0 = P_1.\] \[-20P_1 + 10 P_0 + 10 P_2 = 0\, \implies \, P_2 = 2P_0 - P_0 = P_0.\] Since \(P_0 + P_1 + P_2 = 1\). We get \(3P_0 = 1\). Hence limiting distribution of the queue system is \(\left (\frac {1}{3}, \, \frac {1}{3}, \, \frac {1}{3}\right ).\)

5.5.5 M/M/1 Queue. \(M/M/1\), exponential interarrival time/ exponential service/0ne hour.
Suppose that customers arrive at a single server service station in accordance with a Poisson Process of rate \(\lambda \). That is time between two consecutive arrival are independent exponential random variables having mean \(\frac {1}{\lambda }\).
Each customer upon arrival, goes directly into service of the server is free and if not the customer joins the queue. When the customer leaves the system and the next customer in line, if there is any entries services.
Suppose that the customer service station rate \(\lambda \). That is independent. The successive service times are assumed to be independent exponentially distributed random variables having mean \(\frac {1}{\mu }\).

\(X(t) = \) number of customers in the queue system at time \(t\).
Let \(P_n(t) = P(X(t) = n)\) \[P_0(t + \Delta t) = P_0(t) (1 - \lambda \, \Delta t) + P_1(t) (1 - \lambda \, \Delta t)(\mu \, \Delta t).\] Let \(n\geq 1\) \[P_n(t + \Delta t) = P_n(t)(1 - \lambda \, \Delta t) (1 - \mu \, \Delta t) + P_{n - 1}(t)(\lambda \, \Delta t)(1 - \mu \, \Delta t) + P_{n+1}(t)(1 - \lambda \, \Delta t)(\mu \, \Delta t).\] As \(\, \Delta t \, \longrightarrow \, 0\), \[P'_0(t) = - \lambda \, P_0(t) + \mu \, P_1(t)\] \[P'_1(t) = -(\lambda \mu )\, P_n(t) + \lambda \, P_{n - 1}(t) + \mu \, P_{n + 1}(t)\, , \hspace {0.3cm} n\geq 1.\]

As \(\, t\longrightarrow \infty \),
the queue system will enter into limiting distribution implying \[P'_n(t) = 0, \hspace {0.5cm} P_n(t) \longrightarrow P_n.\] Hence we have \[-\lambda \, P_0 + \mu \, P_1 = 0\, \implies \, P_1 = \frac {\lambda }{\mu }\, P_0\] \[-(\lambda + \mu )\, P_n + \lambda \, P_{n - 1} + \mu \, P_{n + 1} = 0\, , \hspace {0.3cm} n\geq 1\]

\[\mu \, P_{n + 1} = (\lambda + \mu )\, P_n - \lambda \, P_{n - 1}\, , \hspace {0.3cm} n\geq 1\] when \(n = 1\), \begin {align*} P_2 & = \frac {\lambda + \mu }{\mu }\, P_1 - \frac {\lambda }{\mu }\, P_0\\ & = \frac {\lambda + \mu }{\mu }\cdot \left (\frac {\lambda }{\mu }\right )\, P_0 - \frac {\lambda }{\mu }\, P_0\\ & = \frac {\lambda }{\mu }\left (\frac {\lambda + \mu }{\mu } - 1\right )\, P_0\\ & = \frac {\lambda }{\mu }\, \left (\frac {\lambda }{\mu }\right )\, P_0\\ & = \left (\frac {\lambda }{\mu }\right )^2\, P_0 \end {align*}

generalizing \[P_n = \left (\frac {\lambda }{\mu }\right )^n\, P_0.\] But \(P_0 + P_1 + P_2 + \cdots \, = 1\). Hence \[P_0 + \frac {\lambda }{\mu }\, P_0 + \left (\frac {\lambda }{\mu }\right )^2 \, P_0 + \cdots \, = 1\] i.e \[\left (1 + \frac {\lambda }{\mu } + \left (\frac {\lambda }{\mu }\right )^2 + \cdots \cdots \right )\, P_0 = 1\] \[\left (\frac {1}{1 - \dfrac {\lambda }{\mu }}\right )\, P_0 = 1\hspace {0.5cm} \text {provided}\hspace {0.3cm} 0 < \frac {\lambda }{\mu } < 1\] \begin {align*} P_0 & = \frac {\mu - \lambda }{\mu }\\\\ P_1 & = \left (\frac {\lambda }{\mu }\right )\, \left (\frac {\mu - \lambda }{\mu }\right )\\\\ P_2 & = \left (\frac {\lambda }{\mu }\right )^2\, \left (\frac {\mu - \lambda }{\mu }\right )\\ \vdots & \end {align*}

where \(0 < \frac {\lambda }{\mu } < 1\).

Expected number of customers in the queue system in long run \[ = \sum ^{\infty }_{n = 0} n\, P_n.\]

Example. Consider a server in which probability that exactly one customer arrive in time \(\Delta t\) is \(\lambda \, \Delta t\).
If there are \(j\) customers in service at time \(t\), the probability that exactly one customer will complete service in time \((t , t + \Delta t)\) is \(j\, \mu \, \Delta t\). \[P_0(t + \Delta t) = P_0(t) (1 - \lambda \, \Delta t) + P_1(t) (1 - \lambda \, \Delta t)(\mu \, \Delta t).\] Let \(n\geq 1\) \begin {align*} P_n(t + \Delta t) = & P_n(t) (1 - \lambda \, \Delta t)(1 - n\, \mu \, \Delta t) + P_{n -1}(t)(\lambda \, \Delta t)(1 - \overline {n - 1}\, \mu \, \Delta t)\\ & + P_{n + 1}(t) (1 - \lambda \, \Delta t)(\overline {n + 1}\, \mu \, \Delta t). \end {align*}

\[P_j = \frac {\left (\frac {\lambda }{\mu }\right )^j\, e^{-\frac {\lambda }{\mu }}}{j!}\hspace {0.3cm} , \hspace {0.5cm} j = 0, \, 1, \, \cdots \cdots \]

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.