M/M/c queue

An M/M/c queue is a stochastic process whose state space is the set {0, 1, 2, 3, ...} where the value corresponds to the number of customers in the system, including any currently in service. • Arrivals occur at rate according to a Poisson process and move the process from state to +1. • Service times have an exponential distribution with parameter . If there are fewer than jobs, some of the servers will be idle. If there are more than jobs, the jobs queue in a buffer. • The buffer is of infinite size, so there is no limit on the number of customers it can contain. The model can be described as a continuous time Markov chain with transition rate matrix {{block indent|1=Q=\begin{pmatrix} -\lambda & \lambda \\ \mu & -(\mu+\lambda) & \lambda \\ &2\mu & -(2\mu+\lambda) & \lambda \\ &&3\mu & -(3\mu+\lambda) & \lambda \\ &&&&\ddots\\ &&&&c\mu & -(c\mu+\lambda) & \lambda \\ &&&&&c\mu & -(c\mu+\lambda) & \lambda \\ &&&&&&c\mu & -(c\mu+\lambda) & \lambda \\ &&&&&&&\ddots\\ \end{pmatrix}}} on the state space {{nowrap|{0, 1, 2, 3, ...}.}} The model is a type of birth–death process. We write  = /() for the server utilization and require  < 1 for the queue to be stable. represents the average proportion of time which each of the servers is occupied (assuming jobs finding more than one vacant server choose their servers randomly). The state space diagram for this chain is as below. ==Stationary analysis==

Number of customers in the system If the traffic intensity is greater than one then the queue will grow without bound but if server utilization \rho = \frac{\lambda}{c\mu} then the system has a stationary distribution with probability mass function {{block indent|1= \pi_0 = \left[\left(\sum_{k=0}^{c-1}\frac{(c\rho)^k}{k!} \right) + \frac{(c\rho)^c}{c!}\frac{1}{1-\rho}\right]^{-1} \pi_k = \begin{cases} \pi_0\dfrac{(c\rho)^k}{k!}, & \mbox{if }0 }} where is the probability that the system contains customers. The probability that an arriving customer is forced to join the queue (all servers are occupied) is given by {{block indent|1=\text{ C}(c,\lambda/\mu)=\frac{\left( \frac{(c\rho)^c}{c!}\right) \left( \frac{1}{1-\rho} \right)}{\sum_{k=0}^{c-1} \frac{(c\rho)^k}{k!} + \left( \frac{(c\rho)^c}{c!} \right) \left( \frac{1}{1-\rho} \right)}=\frac{1}{1+\left( 1-\rho \right) \left( \frac{c!}{(c\rho)^c} \right) \sum_{k=0}^{c-1} \frac{(c\rho)^k}{k!}}}} which is referred to as Erlang's C formula and is often denoted C(, /) or E2,(/). {{block indent|1=\frac{\rho}{1-\rho} \text{ C}(c,\lambda/\mu) + c \rho.}} Busy period of server The busy period of the M/M/c queue can either refer to: • full busy period: the time period between an arrival which finds −1 customers in the system until a departure which leaves the system with −1 customers • partial busy period: the time period between an arrival which finds the system empty until a departure which leaves the system again empty. Write  = min( t:  jobs in the system at time 0+ and  − 1 jobs in the system at time ) and () for the Laplace–Stieltjes transform of the distribution of . Then Customers in processor sharing discipline In a processor sharing queue the service capacity of the queue is split equally between the jobs in the queue. In the M/M/c queue this means that when there are or fewer jobs in the system, each job is serviced at rate . However, when there are more than jobs in the system the service rate of each job decreases and is \frac{c\mu}{n} where is the number of jobs in the system. This means that arrivals after a job of interest can impact the service time of the job of interest. The Laplace–Stieltjes transform of the response time distribution has been shown to be a solution to a Volterra integral equation from which moments can be computed. An approximation has been offered for the response time distribution. ==Finite capacity==

In an M/M// queue only customers can queue at any one time (including those in service and Stadje for busy period results. Stationary analysis Stationary probabilities are given by {{block indent|1=\pi_0 = \left[\sum_{k=0}^{c} \frac{\lambda^k}{\mu^k k!} + \frac{\lambda^c}{\mu^c c!}\sum_{k=c+1}^K \frac{\lambda^{k-c}}{\mu^{k-c} c^{k-c}}\right]^{-1}}} {{block indent|1=\pi_k = \begin{cases} \frac{(\lambda/\mu)^k}{k!}\pi_0 & \text{for } k=1,2,\ldots,c \\ \frac{(\lambda/\mu)^k}{c^{k-c} c!}\pi_0 & \text{for } k=c+1,\ldots,K. \end{cases} }} The average number of customers in the system is {{block indent|1= L = \frac{\lambda}{\mu} + \pi_0 \frac{\rho (c\rho)^c}{(1-\rho)^2 c!}}} and the average time in the system for a customer is {{block indent|1= W = \frac{1}{\mu} + \pi_0 \frac{\rho (c\rho)^c}{\lambda (1-\rho)^2 c!}}} The average time in the queue for a customer is {{block indent|1= W_q = \pi_0 \frac{\rho (c\rho)^c}{\lambda (1-\rho)^2 c!}}} The average number of customers in the queue can be obtained by using the effective arrival rate. The effective arrival rate is calculated by {{block indent|1= \mathbb{\lambda_a} = \lambda(1-p_K)}} Thus we can obtain the average number of customers in the queue by ==Heavy-traffic limits==

Writing () for the number of customers in the system at time , it can be shown that under three different conditions the process {{block indent|1=\hat X_n(t) = \frac{X(nt) - \mathbb E(X(nt))}{\sqrt{n}}}} converges to a diffusion process. ==See also==