Queueing Processes

Probabilistic processes are described according to their models, which will be one of:

• Deterministic (D)
• Markov (M)
• General (G)

We focus on Markov processes where:

• The number of arrivals follow a Poisson Distribution
• Inter-arrival times follow Exponential Distribution
• Service times follow Exponential Distribution

In Kendall notation, our order is $\alpha /\sigma /m/\beta /N/Q$.

• $\alpha$ = The type of distribution
• $\sigma$ = The type of probability distribution for service time
• m = The number of servers
• $\beta$ = Buffer size
• N = Allowed population size
• Q = Queueing policy

Note

We often leave off the last three assuming that there is an infinite buffer, infinite population, and FIFO queueing policy. Therefore, we only care about the first three.

Utilization

$\rho$ = utilization $\in$ [0,1] which is the amount of time the server is busy.
$\rho =\lambda \times s$.

For $M/M/1$ systems (Markov arrival, exponential queueing system, single server):

• $T_q=\frac{s}{(1-\rho )}$ which is the average completion time
• $W=\frac{{\rho }^2}{1-\rho }$ which is the average length o f queue For $M/M/k$ systems (Markov arrival, exponential queueing system, k servers):
• Jobs arrive in a single queue
• When a server is ready, it takes the first job from the front of the queue
• Servers are identical and jobs can be serve dby any server
• $\rho =\frac{\lambda s}{N}$
• $K=\frac{{\sum }_{i=0}^{N-1}\frac{(\lambda s{)}^i}{i!}}{{\sum }_{i=0}^N\frac{(\lambda s{)}^i}{i!}}$, this is just some intermediate value
• $C=\frac{1-K}{1-\frac{\lambda sK}{N}}$ which is the probability a new job will have to wait in the queue
• $T_q=\frac{Cs}{k(1-\rho )}+s$
• $W=C\frac{\rho }{1-\rho }$