Page 85 - A First Course In Stochastic Models

76 RENEWAL-REWARD PROCESSES

expectation. Let p j denote the long-run fraction of time that j customers are in the system
and let L denote the long-run average number of customers in the system. Apply the result
∞

of Exercise 2.27 to conclude that L = j=1 jp j .
2.29 Verify that the Pollaczek–Khintchine formula for the average waiting time in the
M/G/1 queue can also be written as
2 2
W q = (1 − c )W q (det) + c W q (exp).
S S
This interpolation formula is very useful and goes back to Cox (1955).
2.30 A professional cleaner in the harbour of Rotterdam is faced with the decision to acquire
a new clean installation for oil tankers. Oil tankers requiring a clean arrive according to a
Poisson process with rate λ. The amount of time needed to clean a tanker has a given
probability distribution with mean α and standard deviation β when the standard Fadar
installation is used. Cleaning costs at a rate of c > 0 are incurred for each time unit this
installation is in use. However, it is also possible to buy another installation. An installation
that works z times as fast as the standard Fadar installation involves cleaning costs at a rate
2
of cz per time unit. In addition to the cleaning costs, a holding cost at rate of h > 0 is
incurred for each tanker in the harbour. What is the long-run average cost per time unit as
function of z? Assume that the cleaning installation can handle only one tanker at a time
and assume that the cleaner has ample berths for tankers.
2.31 Liquid is put into an infinite-capacity buffer at epochs generated by a Poisson process
with rate λ. The successive amounts of liquid that are put in the buffer are independent and
identically distributed random variables with finite first two moments µ 1 and µ 2 . The buffer
is emptied at a constant rate of σ > 0 whenever it is not empty. Use the PASTA property
to give an expression for the long-run average buffer content.
2.32 Consider the M/G/1 queue with two types of customers. Customers of the types 1 and
2 arrive according to independent Poisson processes with respective rates λ 1 and λ 2 . The
service times of the customers are independent of each other, where the service times of
type i customers are distributed as the random variable S i having finite first two moments.
Customers of type 1 have priority over customers of type 2 when the server is ready to
start a new service. It is not allowed to interrupt the service of a type 2 customer when a
higher-priority customer arrives. This queueing model is called the non-pre-emptive priority
M/G/1 queue. Letting ρ i = λ i E(S i ), it is assumed that ρ 1 + ρ 2 < 1.
(a) Use Little’s formula to argue that the long-run fraction of time the server is servicing
type i customers equals ρ i for i = 1, 2. What is the long-run fraction of customers finding
the server servicing a type i customer upon arrival?
(b) Extend the heuristic derivation of the Pollaczek–Khintchine formula to show
2 2 2 2
λ 1 E(S ) + λ 2 E(S ) λ 1 E(S ) + λ 2 E(S )
1
2
2
1
W q1 = and W q2 = ,
2(1 − ρ 1 ) 2(1 − ρ 1 )(1 − ρ 1 − ρ 2 )
where W qi is defined as the long-run average waiting time in queue per type i customer for
i = 1, 2.
(c) Use Little’s formula to give a direct argument for the result that the overall average
waiting time W q1 λ 1 /(λ 1 + λ 2 ) + W q2 λ 2 /(λ 1 + λ 2 ) per customer is the same as the average
waiting time per customer in the M/G/1 queue in which customers are served in order of
arrival (view the non-pre-emptive priority rule as a rule that merely changes the order in
which the customers are served).
2.33 Customers arrive at a single-server station according to a Poisson process with rate
λ. A customer finding the server idle upon arrival gets served immediately, otherwise the
customer enters a so-called orbit. A customer in orbit tries whether the server is idle after an