Simple Markovian
Queueing Systems
Part IV
2
Markovian Queues with
Finite Source
3
Finite Source Queues
In previous models, we have assumed that the population from which arrivals
come (the calling population) is infinite, since the number of arrivals in any
time interval is a Poisson random variable with a denumerably infinite sample
space.
We now treat a problem where the calling population is finite of size M, and
future event occurrence probabilities are functions of the system state.
A typical application of this model is that of machine repair, where the
calling population is the machines, an arrival corresponds to a machine
breakdown, and the repair technicians are the servers.
We assume that c servers are available and that the service times are
identical exponential random variables with mean 1/μ.
The arrival process is described as follows: If a calling unit is not in the
system at time t, the probability it will have entered by time t+Δt is λΔt +
o(Δt); that is, the time a calling unit spends outside the system is
exponential with mean 1/λ.
4 M/M/c queue with finite source
With these assumptions, we can use the birth-death
theory developed previously.
The birth and death rates are
Also called as Machine-Repairmen Model.
5 M/M/c queue with finite source
The state transition diagram
6 M/M/c queue with finite source (cont’d)
7 M/M/c queue with finite source (cont’d)
In the long run as t → ∞, the system of differential
equations get reduced to system of balance equations.
On solving the balance equations we get,
M/M/c queue with finite source (cont’d)
8
The algebraic form of the {pn} does not allow an easy closed-form
calculation of p0.
Instead, we first calculate each of the coefficients multiplying p o.
That is, let an be the coefficient in front of po (so pn = anpo). Then,
To find the average number of customers in the system (if we are
dealing with the machine breakdown problem, we are interested in
machines “down” for repair), we use the definition of expected value
and get
9 M/M/c queue with finite source (cont’d)
To obtain Lq and the expected waiting-time measures, W and Wq
we first find the effective mean rate of arrivals into the system.
As noted earlier, the mean arrival rate when the system is in
state n is (M−n) λ.
The overall arrival rate is the sum of the state-dependent rates
weighted by pn. That is,
Above equation is certainly intuitive, since, on average, L are in
the system and hence, on average, M−L are outside and each has
a mean arrival rate of λ.
10 M/M/c queue with finite source (cont’d)
Lq is now given as
And, using Little’s formula we get
11 M/M/c queue with finite source (Example)
The Train Semiconductor Company uses five robots in the
manufacture of its circuit boards. The robots break down
periodically, and the company has two repair people to do service
when robots fail. When one is fixed, the time until the next
breakdown is thought to be exponentially distributed with a mean of
30 h. The shop always has enough of a work backlog to ensure that
all robots in operating condition will be working. The repair time for
each service is thought to be exponentially distributed with a mean
of 3 h. The shop manager wishes to know the average number of
robots operational at any given time, the expected downtime of a
robot that requires repair, and the expected percentage of idle
time of each repairer.
12 M/M/c queue with finite source (Example)
To answer any of these questions, we must first calculate p 0.
In this example,
M = 5, c = 2, λ = 1/30 , and μ = 1/3 and thus r = λ/μ = 1/10.
We first obtain the five {an} multipliers as
a1 = 5/10 = 1/2 ; a2 = 1/10 ; a3 =15/1000 = 3/200 ;
a4 =15/10,000 = 3/2000; and a5 =15/2,00,000 = 3/40000.
It thus follows that
13 M/M/c queue with finite source (Example)
The average number of operational robots is M−L, where
Thus 5−0.465, or 4.535, robots are in operating condition on average.
The expected downtime is
The average fraction of idle time of each server is
1 - ρ = 1 - λeff/2µ = 1 - λ(M - L)/2µ
so each repair person is idle approximately 77% of the time.
14
Markovian Queues with
State Dependent Service Rates
15 State Dependent Service
Markovian queues with state-dependent service are queues
in which mean service rate depends on the state of the
system (number in the system).
In many real situations, the server (or servers) may speed
up when seeing a long line forming.
But it may happen if the server is inexperienced that
he/she/it becomes flustered and the mean service rate
actually decreases as the system becomes more congested.
It is these types of situations that are now considered.
16 M/M/1 Queue with State Dependent Service
The first model we consider is one in which a single server has two
mean rates, say, slow and fast.
Work is performed at the slow rate (μ1) until there are k in the
system, at which point there is a switch to the fast rate (μ)
Example of such service mechanism might be a machine with two
speeds.
We still assume that the service times are Markovian, but the
mean rate μn now explicitly depends on the system state n.
Furthermore, no limit on the number in the system is imposed.
Thus, μn is given as
17
18
State Dependent Service (M/M/1 queue) (cont’d)
Assuming the arrival process is Poisson with parameter λ
and utilizing the formula for pn for a birth-death model,
we have
where ρ1 = λ/μ1 and ρ = λ/μ < 1.
Because the probabilities must sum to 1, it follows that
19 State Dependent Service (cont’d)
which on further simplification gives
Note that if μ1 = μ, then the formula for pn and p0
reduce to the equations of the M/M/c queue.
20
Measures of performance
Measures of performance (cont’d)
21
We can find Lq as
and W and Wq from Little’s law as
Note that the relation W = Wq + 1/μ cannot be used here,
since μ is not constant but depends on the system-state switch
point k.
However, by combining the above equations, we see that
which implies that the expected service time is (1−po)/λ.
22 Example
Sonia Schine and John B. Goode have invented and applied for a patent on a
machine that polishes automobiles. They have formed a partnership called the
Goode-Schine Garage and have rented an old building in which they have set up
their machine. Since this is a part-time job for both partners, the garage is open
on Saturdays only. Customers are taken on a first-come, first-served basis, and
since their garage is in a low-density population and traffic area, there is virtually
no limit on the number of customers who can wait. The car-polishing machine can
run at two speeds. At the low speed, it takes 40 min, on average, to polish a car.
On the high speed, it takes only 20 min on average. Once a switch is made, the
actual times can be assumed to follow an exponential distribution.
It is estimated that customers will arrive according to a Poisson process with a
mean interarrival time of 30 min. Ms. Schine has had a course in queueing theory
and decides to calculate the effect of two policies: switching to high speed if
there are any customers waiting (i.e., two or more in the system) versus switching
to high speed only when more than one customer is waiting (three or more in the
system). The machine speeds can be switched at any time, even while the machine
is in operation. It is desired to know the average waiting time under the two
policies.
Example (Solution)
23
It is therefore necessary to calculate W for the case when k = 2 and
then for k = 3.
We must first calculate p0, then L, and finally W from Little’s formula.
Before doing these computations, we first calculate ρ1 and ρ to be
For case 1, k=2 and
For case 2, k=3 and
Example (Solution)
24
Schine feels that the average wait of 17 more minutes for switching
speeds at three rather than two might not have an adverse effect on
their clientele.
However, it costs more to run the machine at the higher speed.
In fact, it is estimated that it costs $15 per operating hour to operate
the machine at low speed and $24 per operating hour to operate at high
speed.
Thus the expected cost of operation when switching at k is given by
25 Example (Solution)
For case 1, we have
while for case 2, the average operating cost per hour is
Thus it is cheaper to switch at k = 2 even though the hourly cost per
operating hour is higher, since switching at k = 2 yields a higher idle-time
probability po, which more than makes up for the higher highspeed operating
cost.
Also, this provides better customer service in that W is reduced by 17 min.
If, however, the high-speed operating cost were even higher, it might turn
out that switching at k = 3 could be more economical.
26
Markovian Queues with
Impatient Customers
27 Impatient Customers
Customers are said to be impatient if they tend to join the queue only
when a short wait is expected and tend to remain in line if the wait has
been sufficiently small.
The impatience that results from an excessive wait is just as important in
the total queueing process as the arrivals and departures.
When this impatience becomes sufficiently strong and customers leave
before being served, the manager of the enterprise involved must take
action to reduce the congestion to levels that customers can tolerate.
Impatience generally takes three forms.
First is balking, reluctance of a customer to join a queue upon arrival;
Second reneging, reluctance to remain in line after joining and waiting;
Third jockeying between lines when each of a number of parallel lines
has its own queue.
28 Markovian Queues with Balking
In real practice, it often happens that arrivals become
discouraged when the queue is long and do not wish to wait.
One such model is the M/M/c/K; that is, if people see K
ahead of them in the system, they do not join.
Another approach to balking is to employ a series of
monotonically decreasing functions of the system size
multiplying the average rate λ.
Let bn be this function, so that λn = bn .λ and
0 ≤ bn+1 ≤ bn ≤1 (n > 0, b0 ≡ 1).
29 M/M/1 with Balking
For an M/M/1 queue with balking, the formula for pn can
be obtained using the formula for pn for a BDP in which
λn = bn.λ, and µn = µ for all n.
30 Markovian Queues with Balking (cont’d)
Possible examples that may be useful for the discouragement
function bn are 1/(n+1), 1/(n2+1), and e−an.
People are not always discouraged because of queue size, but may
attempt to estimate how long they would have to wait.
If the queue is moving quickly, then the person may join a long one.
On the other hand, if the queue is slow-moving, a customer may
become discouraged even if the line is short.
Now if n people are in the system, an estimate for the average
waiting time might be n/μ, if the customer had an idea of μ.
So a plausible balking function might thus be bn = e−an/μ .
The M/M/1/K model is a special case of balking where b i = 1 for
0≤i≤K−1 and 0 otherwise.
31 Markovian Queues with Reneging
After joining the queue, if a customer abandons its desire
to be served and leaves the system, the customer is said to
have reneged.
One way to incorporate this factor in modeling is to assume
a distribution, normally an exponential distribution in
between successive customer reneging events.
Let β be the rate, independent of the number in the
system, at which reneging occurs.
32 M/M/1 Queue with Reneging
Then, assuming a constant arrival rate λ and service rate μ,
we can give the birth-and-death parameters for the model
as
λn = λ, n = 0, 1, 2, . . . ,
μn = μ + β, n = 1, 2, 3, . . . .
Writing μ + β = γ and ρ = λ/γ for the limiting probabilities,
we have pn = (1 − ρ).ρn, n = 0, 1, 2, . . with ρ < 1.