From BoykinWiki

Jump to: navigation, search

EEL6507 Spring 2009, Lecture 20, Monday 2009/02/25 (Notes created by Gustavo Vejarano)

M/G/1

Looking back M/M/1

- We tracked the number of customers in the queue: $\mbox{Prob} \left [ N(t) = k \right ]\,\!$

- Transitions only add or substract 1. This leads to

- For markovian arrivals (Poisson process)

$\mbox{Prob} \left [ N(t) = k \right ] = \mbox{Prob} \left [ \mbox{arrival at time } t \mbox{ there are } k \mbox{ in system} \right ]\,\!$

$P_k(t) = R_k(t)\,\!$ , in limit $p_k = r_k\,\!$

- $d_k = \lim_{t \to \infty} \mbox{Prob} \left [ \mbox{departure leaves } k \right ] = r_k = p_k\,\!$

Recall some queueing variables:

$c_n \dot= n^{th}\,\!$ customer

$\tau_n \dot= \,\!$ arrival time of $c_n \,\!$

$t_n = \tau_n - \tau_{n-1} \dot= \,\!$ interarrival time for $c_n \,\!$

$x_n \dot= \,\!$ service time for $c_n \,\!$

$q_n \dot= \,\!$ number of customers left behind by $c_n \,\!$

$v_n \dot= \,\!$ number of customers arrive while $c_n \,\!$ is in service

Semi-Markov Process (SMP)

- In a Markov process, transitions happen at regular intervals

- In an SMP, the transition times are themselves random variables:

Transition $n^{th}\,\!$ happened at time $\tau_n\,\!$ . Therefore, two random variables

1. sate system at transition n

2. time that transition n occurs

Just look at state transitions. This is the Embedded Markov Chain.

Solving M/G/1

- Solve for $\mbox{Prob} \left [ q_n = k \right ] \mbox{ as } n \to \infty (t \to \infty)\,\!$

- Since $d_k = p_k\,\!$ , we have the usual probability distribution on queue length.

- Define:

$p_{ij}^{(n)} = \mbox{P} \left [q_{n+1} = j \big| q_n = i \right ]\,\!$

$\alpha_k = \mbox{Prob}\left [ v_{n+1} = k \right ]\,\!$

SMP on $q_n\,\!$

What about $q_n = 0\,\!$

Since we look at departure time, we have to wait for arrival then the next departure, but that's just what we have above.

What is $\alpha_k\,\!$ ?

$\begin{align} \alpha_k & = \mbox{Prob}\left [ v_{n+1} = k \right ] \\ & = \int_{0}^{\infty} \mbox{Prob} \left [v_{n+1} = k \mbox{, } x_{n+1} = t \right ] dt \\ & = \int_{0}^{\infty} \mbox{Prob} \left [v_{n+1} = k \big| x_{n+1} = x \right ] \mbox{Prob} \left [ x_{n+1} = x \right ] dx \\ \end{align}\,\!$

$\mbox{Prob} \left [v_{n+1} = k \big| x_{n+1} = x \right ] = \frac{(\lambda x)^k}{k!} e^{- \lambda x} \,\!$

$\alpha_k = \int_{0}^{\infty} \frac{(\lambda x)^k}{k!} e^{- \lambda x} b(x) dx \,\!$

Solving for $\lim_{n \to \infty} \mbox{Prob} \left [ q_n = k \right ] \,\!$

$\begin{align} \mbox{Prob} \left [ q_{n+1} = k \right ] & = \sum_j \mbox{Prob} \left [ q_{n+1} = k \mbox{, } q_n = j \right ] \\ & = \sum_j \mbox{Prob} \left [ q_{n+1} = k \big| q_n = j \right ] \mbox{Prob} \left [q_n = j \right ] \end{align}\,\!$

$\overrightarrow{q_{n+1}} \dot= \left [ \mbox{Prob} \left [ q_{n+1} = 0 \right ] \mbox{, Prob} \left [ q_{n+1} = 1 \right ] \mbox{, } \cdots \right ] \,\!$

$\overrightarrow{q_{n+1}} = \overrightarrow{q_n} \cdot P \,\!$ , where $\left [ P \right ]_{ij} = \mbox{Prob} \left [ q_{n+1} = j \big| q_n = i \right ] \,\!$