Worked Examples for Chapter 17
Example for Section 17.4
A queueing system has two servers whose service times are independent random variables with an exponential distribution with a mean of 15 minutes. Customer X arrives when both servers are idle. Five minutes later, customer Y arrives and customer X still is being served. Another 10 minutes later, customer Z arrives and both customer X and Y are still being served. No other customer arrived during this 15minute interval.
(a) What is the probability that customer X will complete service before customer Y?
By Property 2 of the exponential distribution (the lackofmemory property) given in Sec. 17.4, when customer Y arrives, the remaining time until customer X completes service has the same distribution as the service time for customer Y, so they are equally likely to finish first. Thus, the probability that customer X will complete service before customer Y is 0.5.
(b) What is the probability that customer Z will complete service before customer X?
Customer Z cannot begin service until either customer X or customer Y completes service. Given that customer Y completes service first (which has probability 0.5 from part (a)), then the reasoning of part (a) implies that the probability that customer Z completes service before customer X is 0.5. Therefore, the unconditional probability that customer Z will complete service before customer X is 0.5(0.5) = 0.25.
(c) What is the probability that customer Z will complete service before customer Y?
By the same reasoning as in part (b), the probability that customer Z will complete service before customer Y is 0.5(0.5) = 0.25.
(d) Determine the cumulative distribution function of the waiting time in the system for customer X. Also determine the mean and standard deviation.
We are given that customer X has not completed service after 15 minutes. By Property 2, the remaining time until service is completed still has an exponential distribution with a mean (and standard deviation) of 15 minutes. Therefore, in units of minutes, the CDF of the waiting time in the system for customer X is
P{T ≤ t} = _{.}
Since the remaining time after 15 minutes has a mean and standard deviation of 15 minutes, the mean of the total time is 15 + 15 = 30 minutes. The first 15 minutes are a fixed constant, so the standard deviation of the total time continues to be the standard deviation of the remaining time, namely, 15 minutes.
(e) Repeat part (d) for customer Y.
The reasoning is the same as for part (d), except now the given time without completing service is 10 minutes instead of 15 minutes.
Therefore,
P{T ≤ t} = _{.}
The mean is 10 + 15 = 25 minutes and the standard deviation is 15 minutes.
(f) Determine the expected value and standard deviation of the waiting time in the system for customer Z.
The waiting time in the system for customer Z is
= _{q} + T,
where W_{q} is the waiting time in the queue and T is the service time. The waiting time in the queue is the time until either customer X or customer Y completes service after customer Z arrives. By Properties 2 and 3 in Sec. 17.4, this time until either customer X or customer Y completes service after customer Z arrives has an exponential distribution with a mean (and standard deviation) of
E = = 7.5 minutes.
Consequently, since E (T) = 15 minutes and Var (T) = (15)^{2},
E() = E + E(T) = 7.5 + 15 = 22.5 minutes,
Var () = Var ( + T) = (7.5)^{2} + (15)^{2} = 281.25,
so the standard deviation of is = 16.77 minutes.
(g) Determine the probability of exactly 2 more customers arriving during the next 15minute interval.
By Property 4 in Sec. 17.4, we can simply use the Poisson distribution with a mean of
E{X(t)} = t = (15) = 1
to find the probability of 2 arrivals,
P{X(t) = 2} = = = 0.1839.
Example for Section 17.5
Consider a single server queueing system where some potential customers balk (refuse to enter the system) and some customers who enter the system later get impatient and renege (leave without being served). Potential customers arrive according to a Poisson process with a mean rate of 4 per hour. An arriving potential customer who finds n customers already there will balk with the following probabilities:
P{balk  n already there} =
Service times have an exponential distribution with a mean of 1 hour.
A customer already in service never reneges, but the customers in the queue may renege. In particular, the remaining time that the customer at the front of the queue is willing to wait in the queue before reneging has an exponential distribution with a mean of 1 hour. For a customer in the second position in the queue, the time that she or he is willing to wait in this position before reneging has an exponential distribution with a mean of 1/2 hour.
(a) Construct the rate diagram for this queueing system.
The rate diagram is shown next.
(b) Obtain the steadystate distribution of the number of customers in the system.
Using the general solution for the steadystate distribution given in Sec. 17.5, we use the following equations to obtain this distribution for this system:
,
Hence, the steadystate probability distribution is
P_{0} = 5/53, P_{1}=20/53, P_{2} = 20/53, P_{3} = 8/53.
(c) Find the expected fraction of arriving potential customers who are lost due to balking.
Using the probabilities of balking, we have
Fraction of lost customers = P_{1} + P_{2} + 1P_{3} = .
(d) Find L_{q} and L.
L = 1P_{1} + 2P_{2} + 3P_{3 }= = 1.585 customers.
L_{q} =1P_{2} + 2P_{3 }= = 0.679 customer.
Example 1 for Section 17.6
Jerry Jansen, Materials Handling Manager at the CasperEdison Corporation’s new factory, needs to make a purchasing decision. He needs to choose between two types of materialshandling equipment, a small tractortrailer train and a heavyduty forklift truck, for transporting heavy goods between certain producing centers in the factory. Calls for the materialshandling unit to move a load occur according to a Poisson process at a mean rate of 4 per hour. The total time required to move a load has an exponential distribution, where the expected time would be 12 minutes for the tractortrailer train and 9 minutes for the forklift truck. The total equivalent uniform hourly cost (capital recovery cost plus operating cost) would be $50 for the tractortrailer train and $150 for the forklift truck. The estimated cost of idle goods (waiting to be moved or in transit) because of increased inprocess inventory is $20 per load per hour.
Jerry also has established certain criteria that he would like the materialshandling unit to satisfy in order to keep production flowing on schedule as much as possible. He would like to average no more than half an hour for completing the move of a load after receiving the call requesting the move. He also would like the time for completing the move to be no more than 1 hour 80 percent of the time. Finally, he would like to have no more than three loads waiting to start their move at least 80 percent of the time.
(a) Obtain the various measures of performance if the tractortrailer train were to be chosen. Evaluate how well these measures meet the above criteria.
If the tractortrailer train were to be chosen, then
mean arrival rate, = 4,
mean service rate, = 60/12 = 5.
We use the Excel template for the M/M/s model with s = 1 to obtain the expected waiting time,
W = 1 hr 0.5 hr.
The percentage of time for completing the move within one hour is
Pr(W 1) = 1 – Pr(W >1) = 1 – 0.3678 = 0.6322 80%.
The percentage of time that no more than three loads are waiting to start their move (plus one currently being moved) is
P_{0} + P_{1} + P_{2} + P_{3} + P_{4} = 0.2 + 0.16 + 0.128 + 0.1024 + 0.08192 = 0.6723 80%.
Therefore, the tractortrailer train does not meet any of the criteria.
(b) Repeat part (a) if the forklift truck were to be chosen.
If the forklift truck were to be chosen, then
mean arrival rate, = 4,
mean service rate, = 60/9 = 6.67.
We use the Excel template for the M/M/s model with s = 1 to obtain
the expected waiting time,
W = 0.37 hr 0.5 hr.
The percentage of time for completing the move within one hour is
Pr(W 1) = 1 – Pr(W >1) = 1 – 0.069= 0.931 80%.
The percentage of time that no more than three loads are waiting to start their move (plus one currently being moved) is
P_{0} + P_{1} + P_{2} + P_{3} + P_{4} = 0.400 + 0.240 + 0.144 + 0.086 + 0.052 = 0.922 80%.
Therefore, the forklift truck meets all the criteria.
(c) Compare the two alternatives in terms of their expected total cost per hour (including the cost of idle goods).
For the tractortrailer train, we calculate
expected total cost per hour = $20L+ $50 = $20(4) + $50 = $130.
For the forklift truck, we obtain
expected total cost per hour = $20L+ $150 = $20(1.5) + $150 = $180.
(d) Which alternative do you think Jerry should choose?
This is a judgment decision, depending on whether you think it is more important to meet the criteria (which favors the forklift truck) or to minimize what has been quantified as the expected total cost per hour (which does not include the extra cost of production facilities having to wait for an excessive number of loads needing to be moved).
Example 2 for Section 17.6
Greg is making plans to open a new fastfood restaurant soon. He is estimating that customers will arrive randomly (a Poisson process) at a mean rate of 150 per hour during the busiest times of the day. He is planning to have three employees directly serving the customers. He now needs to make a decision about how to organize these employees.
Option 1 is to have three cash registers with one employee at each to take the orders and get the food and drinks. In this case, it is estimated that the average time to serve each customer would be 1 minute, and the distribution of service times is assumed to be exponential.
Option 2 is to have one cash register with the three employees working together to serve each customer. One would take the order, a second would get the food, and the third would get the drinks. Greg estimates that this would reduce the average time to serve each customer down to 20 seconds, with the same assumption of exponential service times.
Greg wants to choose the option that would provide the best service to his customers. However, since Option 1 has three cash registers, both options would serve the customers at a mean rate of 3 per minute when everybody is busy serving customers, so it is not clear which option is better.
(a) Use the main measures of performance — L, L_{q}, W, W_{q}— to compare the two options.
The mean arrival rate is = 150.
For Option 1, the mean service rate for each server is = 60/1 = 60/hr and s = 3.
For Option 2, the mean service rate is = 60mins/20secs = 180/hr and s = 1.
We use the Excel template for the M/M/s model to calculate L, L_{q}, W, W_{q} for each of the two options. These measures are given in the figures below.
Option 1:
Option 2:
(b Explain why these comparisons make sense intuitively.
W and L are smaller for Option 2 because it is a more efficient system. This is true because when there are only 1 or 2 customers in the system, Option 2 is operating at full efficiency, while Option 1 will have idle servers. W_{q} and L_{q} are larger for Option 2 because there are fewer people in service (only 1 register) and, therefore, more people in the queue.
(c) Which measure do you think would be most important to Greg’s customers? Why? Which option is better with respect to this measure?
W should be the most important measure to customers because they should be most concerned with the total time spent in the queueing system, since this is the total time that customers must wait in the restaurant before receiving their food. Given this, Option 2 is better.
Example 3 for Section 17.6
The reservation office for Central Airlines has two agents answering incoming phone calls for flight reservations. In addition, one caller can be put on hold until one of the agents is available to take the call. If all three phone lines (both agent lines and the hold line) are busy, a potential customer gets a busy signal, in which case the call may go to another airline. The calls and attempted calls occur randomly (i.e., according to a Poisson process) at a mean rate of 15 per hour. The length of a telephone conversation has an exponential distribution with a mean of 4 minutes.
(a) Construct the rate diagram for this queueing system.
Since this queueing system has two servers (the agents) and the maximum number of customers (the incoming calls) allowed in the system is 3, the applicable model is the finite queue variation of the M/M/s model with
K = 3, = 15, and = 60/4 = 15.
The rate diagram is shown below:
(b) Find the steadystate probability that
(i) A caller will get to talk to an agent immediately,
(ii) The caller will be put on hold, and
(iii) The caller will get a busy signal.
We use the Excel template for the finite queue variation of the M/M/s model to calculate the steadystate probabilities and obtain
P_{0} = 0.36364, P_{1}= 0.36364, P_{2} = 0.18182, P_{3} = 0.09091.
Hence,
(i) the steadystate probability that a caller will get to talk to an agent immediately
= P_{0} + P_{1}= 0.727.
(ii) the steadystate probability that a caller will be put on hold = P_{2} = 0.182.
(iii) the steadystate probability that a caller will get a busy signal = P_{3 }= 0.091.
Example for Section 17.7
An airline maintenance base wants to make a change in its overhaul operation. The present situation is that only one airplane can be repaired at a time, and the expected repair time is 36 hours, whereas the expected time between arrivals is 45 hours. This situation has led to frequent and prolonged delays in repairing incoming planes, even through the base operates continuously. The average cost of an idle plane to the airline is $3,000 per hour. It is estimated that each plane goes into the maintenance shop 5 times per year. It is believed that the input process for the base is essentially Poisson and that the probability distribution of repair times is Erlang, with shape parameter k = 2.
Alternative A is to provide a duplicate maintenance shop, so that two planes can be repaired simultaneously. The cost, amortized over 5 years, is $400,000 per year for each of the airline’s airplanes.
Alternative B is to replace the present maintenance equipment by the most efficient (and expensive) equipment available, thereby reducing the expected repair time to 18 hours. The cost, amortized over 5 years, is $550,000 per year for each airplane.
Which alternative should the airline choose?
For Alternative A, the system has Poisson input with
= 1/45, Erlang service with k = 2, = 1/36, and s = 2.
For Alternative B, the system has Poisson input with
= 1/45, Erlang service with k = 2, = 1/18, and s = 1.
Planes arrive at the rate of one every 45 hours or, equivalently,
8760/45 195 arrivals per year.
Since each plane goes to the maintenance shop five times a year, there are approximately 195/5 = 39 planes.
Therefore, the expected service cost per hour is
E[SC] = $400,000(39) / 8760 = $1780.82 per hour, for Alternative A,
E[SC] = $550,000(39) / 8760 = $2448.63 per hour, for Alternative B.
We now need to evaluate the expected waiting cost per hour, which requires first determining L. For Alternative A,
L = 0.91 (estimated from Fig. 17.10).
For Alternative B, using the formula for the M/E_{k}/1 model (based on the PollaczekKhintchine formula) given in Sec. 17.7,
L = .
The resulting calculation of the expected total cost per hour for the two alternatives is shown in the following table.
Alternative

E[SC]

E[WC] = $3000L

E[TC]

A

$1780.82

$2730

$4510.82

B

$2448.63

$1800

$4248.83

The conclusion is that the airline should choose Alternative B since it has a significantly smaller expected total cost per hour E(TC).
Example for Section 17.8
The Becker Company factory has been experiencing long delays in jobs going through the turret lathe department because of inadequate capacity. The head of this department contends that five machines are required, as opposed to the three machines now in place. However, because of pressure from management to hold down capital expenditures, only one additional machine will be authorized unless there is solid evidence that a second one is necessary.
This shop does three kinds of jobs, namely, government jobs, commercial jobs, and standard products. Whenever a turret lathe operator finishes a job, he starts a government job if one is waiting; if not, he starts a commercial job is any are waiting; if not, he starts on a standard product if any are waiting. Jobs of the same type are taken on a firstcomefirstserved basis.
Although much overtime work is required currently, management wants the turret lathe department to operate on an 8hour 5dayperweek basis. The probability distribution of the time required by a turret lathe operator for a job appears to be approximately exponential, with a mean of 10 hours. Jobs come into the shop randomly (a Poisson process) at a mean rate of 6 per week for government jobs, 4 per week for commercial jobs, and 2 per week for standard products. (These figures are expected to remain the same for the indefinite future.)
Management feels that the average waiting time before work begins in the turret lathe department should not exceed 0.25 (working) day for government jobs, 0.5 day for commercial jobs, and 2 days for standard products.
(a) Determine how many additional turret lathes need to be obtained to satisfy these management guidelines.
Using weeks as the unit of time, this system is a nonpreemptive queueing system with
= 4, _{1} = 6, _{2} = 4, and _{3} = 2,
where class 1 is government jobs, class 2 is commercial jobs, and class 3 is standard jobs. The problem is to determine whether s = 4 or s = 5 would be best.
For s = 4: A = 31.41,
B_{0} = 1,
B_{1} = 5/8,
B_{2} = 3/8,
B_{3} = 1/4.
Thus, using the equation for W_{k} given in Sec. 17.8, we have
W_{1} = 0.30094, W_{2} = 0.38585, and W_{3} = 0.58962.
Using units of weeks, management has set the following guidelines for the average waiting time before work begins:
No more than 0.05 week for government jobs.
No more than 0.1 week for commercial jobs.
No more than 0.4 week for standard jobs.
These refer to waiting times in the queue, whereas the W_{k} calculated above are expected waiting times in the system, so we need to subtract the expected service time (0.25 week) to obtain the expected waiting time in the queue, as shown below.
Government jobs: W_{1}  = 0.05094 > 0.05 week.
Commercial jobs: W_{2}  = 0.13585 > 0.1 week.
Standard jobs: W_{3}  = 0.33962 < 0.4 week.
Therefore, government jobs barely fail the management guidelines and commercial jobs fail these guidelines by a substantial amount.
For s = 5: A = 52.35,
B_{0} = 1,
B_{1} = 7/10,
B_{2} = 1/2,
B_{3} = 2/5.
Thus, we have
W_{1} = 0.27729, W_{2} = 0.30458, and W_{3} = 0.34552.
To check whether this satisfies the management guidelines, the corresponding expected waiting times in the queue are calculated below.
Government jobs: W_{1}  = 0.02729 < 0.05 week.
Commercial jobs: W_{2}  = 0.05458 < 0.1 week.
Standard jobs: W_{3}  = 0.09552 < 0.4 week.
Therefore, these waiting times would be well within the management guidelines with 5 turret lathes.
(b) It is worth about $750, $450, and $150 to avoid a delay of 1 additional (working) day in a government, commercial, and standard job, respectively. The incremental capitalized cost of providing each turret lathe (including the operator and so on) is estimated to be $250 per working day. Determine the number of additional turret lathes that should be obtained to minimize the expected total cost.
Converting to units of weeks (with 5 working days per week), it is worth about $3,750, $2,250, and $750 to avoid a delay of 1 additional week in a government, commercial, and standard job, respectively. For each job type, this amount then needs to be multiplied by _{k}W_{k} to obtain the expected waiting cost per week E(WC). The expected service cost per week E(SC) is the number of turret lathes times 5($250).
Performing these calculations and then adding E(SC) and the total E(WC) over all three job types gives the expected total cost per week E(TC), as shown in the following table.
s

E[WC]

E[SC]

E[TC]

Government

Commercial

Standard

Total

4

6771.15

3472.65

884.43

11128.23

5000

16128.23

5

6239.02

2741.22

518.28

94985.2

6250

15748.52

Therefore, two additional turret lathes should be obtained (bringing the total to 5) to minimize the expected total cost per week. 