COE 755 – Queuing Theory
Welcome to Exam II
Tuesday April 16, 2013
Instructor: Dr. Wissam F. Fawaz
Student ID: ________________
1. This exam is Closed Book. Please do not forget to write your
name and ID on the first page.
2. You have exactly 140 minutes to complete the 8 required
3. Read each problem carefully. If something appears
ambiguous, please write your assumptions.
4. Put your answers in the space provided only. No other spaces
will be graded or even looked at.
Problem 1: Machine Interference Problem (20 minutes) [15 Points]
Consider a machine interference problem where a maintenance repair person has the job of keeping two machines in working order. The amount of time that a machine works before breaking down has an exponential distribution with a mean of 10 hours. The time spent by the maintenance person to repair the machine has an exponential distribution with a mean of 8 hours.
1. The average number of broken down machines
L = 1.0725
2. The average number of machines waiting to be repaired
Lq = 0.3305
3. The average breakdown rate of the machines
4. The average repair rate of the machines (throughput of repair man)
5. The proportion of time that there is at least one machine working
Problem 2: Rate diagrams (15 minutes) [15 Points]
Consider a queuing system whose rate diagram is given below. Branch labels are birth
and death rates. Node labels give the number of customers in the system.
0 1 2 λ λ
1. Find P, where Pis the probability of being in state k (k=0, 1, 2). kk ???，
?? ；?? ；?? ??????????????，??，??，
2. Find the average number of customers in the system.
???，???！ ?? ?????，??
3. For λ = μ, what values do we get for parts (a) and (b)? Try to interpret these
Problem 3: Poisson distribution (15 minutes) [10 Points]
1. Changes in airport procedures require considerable planning. Arrival rates of
aircrafts are an important factor that must be taken into account. Suppose that
small aircrafts arrives at a certain airport, according to a Poisson process, at the
rate of 6 per hour.
a. What is the probability that exactly 4 small aircrafts arrive during a 1-hour
The probability that exactly 4 small aircrafts arrive during a 1-hour period is calculated using Poisson distribution with ( = 6 airplanes/hour as follows:
b. What is the probability that at least 4 arrive during a 1-hour period? The probability that at least 4 small aircrafts arrive during a 1-hour period is:
c. If we define a working day as 12 hours, what is the probability that at least
75 small aircrafts arrive during a day?
The probability that at least 75 small aircrafts arrive during a day is calculated using a Poisson distribution with ( = ，t = 6*12 = 72 airplanes/day as follows:
2. An electronic switching device occasionally malfunctions and may need to be
replaced. It is known that the device is satisfactory if it makes, on the average, no
more than 0.20 errors per hour. A particular 5-hour period is chosen as a "test" on
the device. If no more than 1 error occurs, the device is considered satisfactory.
a. What is the probability that a satisfactory device will be considered
unsatisfactory on the basis of the test? Assume that a Poisson process
This is a Poisson process with ( = ，t = 0.20*5 = 1.0 errors/5-hour. A satisfactory
device that is Poisson distributed with ( = 1.0 errors/5-hour will considered
unsatisfactory if more than 1 error occurs in the test.
b. What is the probability that a device will be accepted as satisfactory when,
in fact, the mean number of errors is 0.25 per hour? Again, assume that a
Poisson process exists.
If the mean number of errors is 0.25 errors per hour, the new process will be Poisson distributed with ( = ，t = 0.25*5 = 1.25 errors/5-hour and a device will be
accepted as satisfactory if no more than 1 error occurs in the test.
Problem 4: Queues with finite waiting space (25 minutes) [15 Points]
1) Consider the queueing system shown below. The arrival process is Poisson with a
rate of λ. The buffer (i.e., waiting room) has space for one packet only. There are
two servers each with a service rate of µ. Packet service times are assumed to be
exponentially distributed. Compute the throughput of the system when λ=µ.
Hint: Recall how we computed the throughput of a repair man.
，，！，??；??；??；?? ????，，，，，，，，???; (?，??)?：??? ??
2) The queueing system below is similar to the one considered in (1), except that the
two servers become one, with a combined service rate of 2µ. After this change,
what will the throughput of the system become? Again, assume that λ=µ.
3) Variable length packets arrive at a network switching node at an average rate of
125 packets per second. If the packet lengths are exponentially distributed with a
mean of 88 bits and the single outgoing link is operating at 19.2 kb/s.
a. What is the probability of buffer overflow if the waiting room is only big
enough to hold 21 packets? -3Given λ=125 packets/s, 1/μ=88/19200=4.6x10 s => ρ=0.575
S；；(1？ ).？4 P，，5.353；10bS？1；1？
b. How big should the waiting room be in terms of number of packets to -6keep the packet loss below 10?
Problem 5: Queues with finite waiting room (15 minutes) [10 Points]
An airline ticket office has two ticket 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, and it is assumed that he/she calls another ticket office. Calls arrive in a Poisson fashion at the rate of 12 per hour. The length of a telephone conversation has an exponential distribution with a mean of 4 minutes.
1. Construct the state transition rate diagram for this queueing system λ=12/hr and µ=15/hr
The balance equations for the system:
2. Find the steady-state probability that
a. A caller will get to talk to an agent immediately
The probability to talk to an agent immediately is the probability to have less customers than agents in the system. Thus:
b. The caller will be put on hold
The probability the caller will be put on hold is the probability both agents are occupied and the hold line is free. Therefore:
c. The caller will get a busy signal
The probability the caller will be lost is the probability both agents are occupied and the hold line is also taken. Therefore:
Problem 6: Queues with infinite buffer (10 minutes) [10 Points]
Consider a transmission link with fixed link capacity C=1.5 Mbps, an infinite buffer, and a Poisson packet arrival process with rate λ=1000 packets/s. Assume that the packet length distribution is exponential with mean L = 1000 bit/packet.
1. Compute the mean number of packets in the system. Compute the mean delay for
We use the M/M/1 formula here. μ=1500p/s. ρ=0.67
The expected number in the system: E[n] = ρ/(1- ρ)=2 packets
From Little’s formula, the expected delay:
E[T] = E[n] / λ = 2.0 ms
2. Now assume that the arrival rate of packets has risen to 2000 packets/s, so we
double the transmission capacity to 3 Mbps.
a. What happens to the mean number of packets in the system? What
happens to the mean delay for a packet?
Problem 7: Queues with infinite buffer (15 minutes) [15 Points]
At a neighborhood polyclinic, patients arrive according to a Poisson process with an average inter-arrival time of 18 minutes. These patients are given a queue number upon arrival and will be seen, by the only doctor in the clinic according to their queue number (on a FIFO basis). The length of a typical consultation session is found from historical data to be exponentially distributed with a mean of 7 minutes.
a. What is the probability that a patient arriving at the clinic has to wait to
see the doctor?
λ=1/18 calls/min, and μ=1/7 calls/min => ρ=traffic intensity=7/18
Prob[newcomer has to wait] = ρ = 1-P = 7/18. 0
b. What is the average number of patients waiting to see the doctor?
2The queue length: L= ρ/(1-ρ)=49/198=0.247 q
c. What is the probability that there are more than 5 patients in the clinic,
including the one in consultation with the doctor?
5234P[N>=5] = ρ = 0.0089; since P[N>=5] = 1 – P (1+ ρ+ ρ+ ρ + ρ ) and 0
P = 1- ρ. 0
d. If a second doctor is employed to serve the patient, find the average
number of patients in the clinic (including the ones in consultation).