Simple Markovian
Queueing Systems
Part II
2
Multi-server Queue (M/M/c)
3
Multi-server Queue (M/M/c)
Arrivals are Poisson with rate λ, i.e., inter-arrival times are
exponential.
There are c servers, and each server has an independently
and identically distributed exponential service-time
distribution with mean 1/μ.
Like the M/M/1 queue, this queue can be modeled as a birth–
death process as shown below
4 Multi-server Queue (M/M/c)
Since the arrival rate is constant, the “birth” rate is λn = λ for all
n, regardless of the number of customers in the system.
In contrast, the rate of service completions (or “deaths”) depends
on the number in the system.
If there are c or more customers in the system, then all c servers
must be busy. Since each server processes customers with rate μ,
the combined service-completion rate for the system is cμ.
When there are fewer than c customers in the system, n < c, only
n of the c servers are busy and the combined service completion
rate for the system is nμ. Hence μn may be written as
5 Multi-server Queue (M/M/c)
Construct
Differential
What is Equations
the Obtain
objective System of
Balance
of Equations
studying Solve to
M/M/c find pn
queue?
Using pn,
obtain L, Lq,
W, Wq.
6
7
8
9
10
11
12
13 Derivation of pn for M/M/c queue
Also, using the prior theory developed for birth–death processes,
we can insert the values for λn and μn in the formula for pn for
general BDP to obtain the steady-state probabilities pn
Note that pn has the form of a Poisson random variable for
0≤n<c and the form of a geometric random variable for n≥c.
14
Derivation of pn for M/M/c queue (cont.)
In order to find p0, we again use the condition that the
probabilities must sum to 1, which gives
If we let r = λ/μ and ρ = r/c = λ/cμ , then we have
15 Derivation of pn for M/M/c queue (cont.)
Now consider the infinite series in the above equation:
16
Derivation of pn for M/M/c queue (cont.)
Therefore we can write
Here, the condition for the existence of a steady-state
solution is λ/cμ < 1.
That is, the mean arrival rate must be less than the mean
maximum potential service rate of the system.
Also, when c = 1, the above formula for po reduces to the
analogous equation for the M/M/1 queue.
Measures of Performance of M/M/c Queue
17
We can now derive measures of effectiveness for the M/M/c model
utilizing the steady-state probabilities pn in a manner similar to
that used for the M/M/1 model.
However, unlike M/M/1 queue, we first consider the expected
queue size Lq, as it is computationally easier to determine than L,
since we have only to deal with pn for n ≥ c. Thus
Measures of Performance of M/M/c Queue (cont.)
18
To find L, we employ Little’s formula to get Wq, then use Wq to find W =
Wq + 1/μ, and finally employ Little’s formula again to calculate L = λW.
Thus we get,
19 An Example
City Hospital’s eye clinic offers free vision tests every Wednesday
evening. There are three ophthalmologists on duty. A test takes, on
average, 20 min, and the actual time is found to be approximately
exponentially distributed around this average. Clients arrive
according to a Poisson process with a mean of 6/h, and patients are
taken on a first-come, first-served basis. The hospital planners are
interested in knowing:
(1) the average number of people waiting
(2) the average amount of time a patient spends at the clinic
(3) the average percentage idle time of each of the doctors.
Thus we wish to calculate Lq, W, and the percentage idle time of a
server.
Solution
20
We begin by calculating po, since this factor appears in all the
formulas derived for the measures of effectiveness. We have
that c = 3, λ = 6/h, and μ = 1/(20 min) = 3/h. Thus r = λ/μ = 2,
ρ = 2/3 , and, from the p0 formula we get,
Now using p0 we can evaluate the other measures as follows:
21
Solution
Next, the long-term average fraction of idle time for any
server in an M/M/c is equal to 1−ρ.
For this problem, therefore, each physician is idle 1/3 of the
time, since the traffic intensity is ρ = 2/3 .
[Alternatively, Given the three servers on duty, two of them will be
busy at any time (on average), since r = 2 (since, r gives the average
number of customers in service)]
Furthermore, the fraction of time that there is at least one
idle doctor can be computed here as
p0 + p1 + p2 = Pr{Tq = 0} = 5/9.
ASSIGNMENT-1
22 1. Derive the CDF for the time spent waiting in the system in an M/M/1 queueing
system with average arrival rate λ and average service rate µ.
2. Derive the steady state system size probabilities for M/M/1/K queueing model.
Also
obtain the performance measures for the system.
3. Construct the differential equations for an M/M/2/infinity queue. Hence obtain the
steady state system size probabilities for the same. Also obtain the expected
number of customers in the system.
4. Compare M/M/1/infinity and M/M/2/infinity queueing models having the same
traffic
intensity and find out which system is better (w.r.t. number of units in the system in
steady state)
5. Derive the steady state system size probabilities for a single server model with
Poisson input and exponential state-dependent service with mean rates:
µn = µ1 (0 < n < k), µn = µ (k ≤ n )
Also obtain L, Lq , W, Wq