Last modified 2/1/99
In working with queuing systems, it is easiest to analyze the system in steady state (after the system has started up and things have settled down). Time-dependent or transient analysis is more difficult and is not treated here.
A/B/c/K/m/Z systems,
where
A and B may be
Customers arrive one at a time into the system, at times t_0 < t_1 < .... The differences between consecutive arrivals is the interarrival time, d_i = t_i - t_(i-1). We assume these k_i's to be independent and identically distributed random variables. Lambda is the mean interarrival time, and the expected interarrival time is E(d) = 1/lambda.
Arrivals in the system may follow any process, but in elementary queuing theory arrivals are assumed to be Poisson, that is,
Prob(d <= t) = 1 - e^(-l t),
where d is an interarrival time, t is a particular time, e is the base of the natural logarithm, and l (lambda) is the average arrival rate (in customers per unit time). So Poisson interarrival times follow an exponential distribution with mean lambda. The probability that exactly n customers will arrive in a time interval of duration t is
Prob(exactly n arrivals in time t) = [e^(-l t)(l t)^n]/n!
The expected number of arrivals in time t is
E(n) = lambda t
with variance
sigma^2_n = lambda t.
A very nice property of Poisson processes is that the sum of N independent Poisson processes is also a Poisson process, with its mean arrival rate the sum of the means.
Service times are also often assumed to be random. The mean service rate is mu, and the expected service time is E(s) = 1/mu.
Queue capacity may be infinite (approximating systems with large queues), finite (in which a customer may only wait if there is room in the queue), or zero (if all servers are busy, the customer is refused; a zero-capacity system is also known as a loss system).
Systems may have one server (most common model), or multiple servers, usually considered to be identical.
Traffic intensity is a measure of how busy a system is, and is defined as the ratio of mean service time to mean interarrival time,
u = lambda/mu.
Server utilization, the traffic intensity per server, is defined as
rho = u/c = lambda/(c mu)
for a c server system. The Law of Large Numbers indicates that this approximates the fraction of time a server is busy.
A state diagram for such systems appears as a linear sequence of states, labeled with the number of customers in that state 0, 1, 2, ..., i, ... and with arcs between states with consecutive numbers (i and i+1). The arc from state i to i+1 is labeled lambda (for mean arrival rate) and that from i+1 to i is labeled mu (for mean service rate). Let the probability that a particular state i is occupied be p_i. Then the expected rate at which transitions are made from state i to state i+1 is lambda p_i, while the expected rate at which transitions are made from state i+1 to state i is mu p_(i+1). At steady state, these must be equal,
mu p_(i+1) = lambda p_i, i=0,1,2,...
So
p_(i+1) = (lambda/mu) p_i = (lambda/mu)^(i+1) p_0, i=0,1,2,...
Since the sum of probabilities of existence over all states must be 1, we have
Sum [i=0 to inf] p_i = 1 = p_0 + rho p_0 + rho^2 p_0 + rho^3 p_0 + ...
= Sum [i=1 to inf] rho^i p_0 = p_0 Sum [i=1 to inf] rho^i
where rho = lambda/mu. Thus, by telescoping the series,
p_0 = (1 - rho),
which represents the probability that there are no customers in the system. The probability that there are one or more customers in the system, and thus that a new arrival must wait, is simply 1 - p_0 = rho.
To compute the mean number of customers in the system, we take the weighted sum
L = Sum [i=0 to inf] i p_i = Sum [i=1 to inf] i p_i = p_0 Sum [i=1 to inf] i rho^i
Again, by telescoping the series, we obtain
L = rho/(1 - rho)
By applying Little's result, we get the mean waiting time
W = L/lambda = E(s)/(1 - rho) = 1/(mu - lambda),
recalling that rho = lambda/mu and E(s) = 1/mu.
General formulas for M/M/1 systems are as follows: