Queueing Theory and Operations Management Problems

Posted on May 1, 2024 in Mathematics

Section A: Multiple Choice

Instructions:

Please write your answer in the underlined space in front of each problem.

Question 1:

Which of the following will increase the waiting time in a call center in which the incoming call gets assigned to the first available server?

  • A) Add more servers
  • B) Increase the service time coefficient of variation
  • C) Increase the average service time
  • D) Decrease the average inter-arrival time
  • E) Both (a) and (c)
  • F) Both (b) and (c)
  • G) All (b), (c), and (d)

Answer: (G). Recall the Tq waiting formula: Tq = (λ/μ) * (CVp^2 + CVa^2) / (2(1-ρ)) * (1/m). Adding more servers (increasing m) makes Tq smaller. Increasing CVp makes Tq larger. Increasing average service time (ρ) makes Tq larger. Decreasing the avg inter-arrival time (λ) makes utilization ρ = λ/(mμ) larger and makes Tq larger.

Question 2:

Jack and Lisa are two workers in a Starbucks store. They are each in charge of different tasks. Jack has a capacity of 12 orders/hour and Lisa has a capacity of 6 orders/hour. What would be their capacity after cross-training?

  • A) Both of them will have a capacity of 9 orders/hour.
  • B) Jack’s capacity increases to 15 orders/hour and Lisa’s capacity increases to 8 orders/hour
  • C) Jack’s capacity reduces to 10 orders/hour and Lisa’s capacity increases to 8 orders/hour.
  • D) Both of them will have a capacity of 8 orders/hour.

Answer: (D) Jack is spending 60/12 = 5 mins on each job and Lisa is spending 60/6 = 10 mins on each job. After cross-training, each will spend (5+10)/2 = 7.5 min on average on each order. Therefore, both have a capacity of 60/7.5 = 8 orders/hour.

Question 3:

Consider the following process that has three workstations manned by Tom, Dick, and Harry, whose capacities are given below. The system flow rate is 12 units per hour. Which of the following statements is FALSE?

  • A) Tom will be idle for 20 minutes every hour.
  • B) Dick will be busy all the time.
  • C) Harry will be idle 1/3 of the time.
  • D) The process capacity is 12 units per hour.

Answer: (A). Tom’s utilization is 12/16 = 75%, so he is idle for 60*(1-0.75) = 15 minutes per hour. Dick’s utilization is 12/12 = 100%. Harry’s utilization is 12/18 = 2/3. Dick is the bottleneck. Therefore the process capacity is 12 units/hr.

Workstation Capacities:
  • Tom: 16 units/hour
  • Dick: 12 units/hour
  • Harry: 18 units/hour

Question 4:

Sam is a very popular instructor and all five seats in his office are taken during office hours. Each student, on average, stays 20 minutes in his office. How many students can he help within the two-hour window of his office hours?

  • A) 15 students
  • B) 20 students
  • C) 25 students
  • D) 30 students

Answer (D) We have WIP = 5, FT = 20 min = 1/3 hour. By Little’s law, FR = WIP/FT = 15 students per hour. So in two hours, 30 students can come to his office.

Question 5:

The Gaughan & Tiberti Library wants to provide computers for students to check emails. There will be one common queue for all computers, and each computer is used by one student at a time. On average, there are 15 student arrivals per hour, and each student spends 10 minutes on the computer. To control the waiting time, the library wants no more than 90% utilization of the computers. What is the minimum number of computers they should have?

  • A) 3 computers
  • B) 6 computers
  • C) 9 computers
  • D) 12 computers

Answer: (A). p = 10 min. a = 60/15= 4 min. To ensure at most 90% utilization, i.e. u = p/(m*a) = 10/(m * 4) <= 0.9, we need m >= 10/(4*0.9) = 2.78. That is, we need at least 3 computers.

Question 6:

Which of the following statements are FALSE?

  1. When the Shadow Price is zero the associated constraint is always non-binding at an optimal solution.
  2. If the change in the RHS of a constraint is within the allowable range, then the optimal objective function value always stays the same.
  3. If the change in an Objective Function Coefficient is within the allowable range, then the optimal objective function value always stays the same.
  4. If the decrease in an Objective Function Coefficient is within the allowable range, then the optimal solution always stays the same.
  5. Adding a constraint in a linear optimization problem can only result in the optimal objective function value being the same or worse (lower for a maximization problem or higher for a minimization problem).
  • A. I, II, III
  • B. II, IV, V
  • C. III, IV, V
  • D. IV, V

Answer: A

  1. False: If a constraint is non-binding for the optimal solution, the Shadow Price=0, however, the reverse is not always true. It could be that a binding constraint at the optimal solution can have a Shadow Price of 0 if that resource does not contribute to the Objective Function. A good example is: Max 0x Subject to x <= 1 Where the optimal solution is x = 1 and the shadow price of the constraint is 0.
  2. False: If the change in a resource is allowable and there is a nonzero shadow price, the optimal objective value changes.
  3. False: If we change objective coefficients within the allowable range, the optimal solution (or optimal decision variables) stays the same. However, because we’ve changed the coefficients, the objective value (which multiplies the coefficients and solution) usually does change.
  4. True.
  5. True.

Question 7:

For the next two questions, consider the following linear optimization problem:

max 3x + 4y + z subject to 2x + 3y + 10z ≤ 100
x + y ≤ 1
x, y, z ≥ 0

Please take note of the bold-faced “5” and “100”. You solve the linear optimization problem in Excel. Which of the following statements is true?

  1. If we increase the number 5, the optimal objective value cannot decrease.
  2. If we increase the number 5, the optimal objective value could increase, decrease, or stay the same depending on whether the increase is in the allowable range.
  3. If we increase the number 100, the optimal objective value cannot decrease.
  4. If we increase the number 100, we cannot say anything about the optimal objective value.
  • A. I and III
  • B. I and IV
  • C. II and III
  • D. II and IV

Answer: A Notice we are maximizing and all our decision-variables are non-negative. Suppose we first solve the problem at “5” and then start increasing the value “5”. Our original solution remains feasible, but the objective value increases or stays the same. (It stays the same if y = 0 in the optimal solution.) Since we’re maximizing, the optimal solution has to be at LEAST as good as this feasible solution, so the optimal solution either increases or stays the same. That means statement I is true. Similar logic applies to statement III. As we increase the “100” the problem becomes less constrained. If you think of this constraint as being a resource constraint and 100 is the amount of that resource you have available, increasing the amount of resource you have can only improve the optimal solution. Hence, it should be “easier” to solve, and since we’re maximizing, the objective value should either increase or stay the same. (It stays the same if the original constraint was not tight.)

Question 8:

(Continued from above) Your friend solves the above optimization problem in Excel and tells you that at the optimal solution x = 0 and y = 1. They do not tell you what z is in the optimal solution. What can you say about the value of z in the optimal solution?

  • A. z = 9.7
  • B. z might be 9.7 but might also be strictly less than 9.7.
  • C. There is no way to know the value of z in the optimal solution without more information.
  • D. There is no feasible solution with x = 0 and y = 1. Therefore, your friend made a mistake when solving the problem in Excel.

Answer: A We can first check that when x = 0 and y = 1, the second constraint is satisfied since x + y = 1. Also, they’re both non-negative. Substituting x = 0 and y = 1 into the first constraint gives 0 + 3 + 10z ≤ 100 Which is the same as z ≤ 9.7. Notice we’re maximizing, and the objective coefficient of z is positive, so we want z to be as large as possible. Therefore, the optimal solution is z = 9.7, and this solution is feasible.

Section B: Problems

Question 1:

In an emergency room, there are two types of patients:

  • Seriously ill or injured patients. They arrive at an average rate of 0.5 patients per hour and stay in the emergency room for 36 hours on average.
  • Moderately ill or injured patients. They arrive at an average rate of 2 patients per hour and stay in the emergency room for 8 hours on average.
(a) On average, how many moderately ill or injured patients are in the emergency room?

FRM=2 patients/hr
FTM=8 hrs
WIPM=2*8=16 patients

(b) On average, what is the total number of patients in the emergency room?

FRS=0.5 patients/hr
FTS=36 hrs
WIPS=0.5*36=18 patients
Total WIP=18+16=34 patients

Alternatively,

Average FT = (2/2.5)*8 + (0.5/2.5)*36 = 6.4 + 7.2 =13.6 hrs
FR=0.5+2 = 2.5 patients/hr
WIP = 2.5patients/hr * 13.6hrs = 34 patients

(c) When a patient is discharged from the emergency room, it takes 2 hours to clean his/her bed for the next patient. How many beds are needed, in the emergency room, to meet the average demand for beds?

FTM for beds=8+2=10 hrs
FTS for beds=36+2=38 hrs
Average FT for beds= (2/2.5)*10 + (0.5/2.5)*38=8 + 7.6=15.6 hrs
FR=0.5+2 = 2.5 patients/hr
WIP=2.5*15.6=39 beds

(d) Employing a more sophisticated diagnostic system will reduce the number of seriously ill or injured patients by 50%; they will instead be classified as moderately ill or injured. How many beds are needed, in the emergency room, to meet the modified average demand? (Note: It still takes 2 hours to clean a bed after a patient is discharged.)

FRS = 0.5*0.5 = 0.25 patients/hr
FRM = 2 + 0.25 = 2.25 patients/hr

Average FT for beds= (2.25/2.5)*10 + (0.25/2.5)*38 = 9 + 3.8 = 12.8 hrs
FR=2.5 patients/hr
WIP = 2.5*12.8 = 32 beds

Alternatively, note that the new diagnostic system will reduce the flow time by 38-10=28 hours for 0.5*0.5 = 0.25 patients/hr. Therefore, compared to (c), the reduction in WIP is 28*0.25=7 beds, so the total number of beds needed is 39 – 7 = 32 beds.

Question 2:

Trojan Pharmaceuticals develops new technological products to be used in health care. Their development process is as follows.

  • When a new technology meets the requisite market potential, a new patent is filed. On average, Trojan Pharmaceuticals files a new patent every 5 months, with a standard deviation of 5 months.
  • Once the patent is filed, the new technology is assigned to the first available development center and is launched to market after development. There are 3 development centers. Each product is developed at only one center, and each center can only develop a single patented technology at a time. If all centers are occupied, the technologies are assigned in the order that the patents were filed. The average development process lasts 12 months, with a standard deviation of 24 months.
  • Patents are granted for a period of 12 years starting from the date of filing.
(a) What is the utilization of Trojan Pharmaceuticals’ development facilities?

a = 5 months
p = 12 months
m = 3
u = p / (m*a) = 12 / (3(5)) = 0.8

(b) What is the average time (in months) between filing a patent and being assigned to a development center?

λ = 1/5 = 0.2 products/month, CVa = σa / a = 1
μ = 1/12 = 0.0833 products/month, CVp = σp / p = 2
Tq = (λ/μ^2) * (CVp^2 + CVa^2) / (2(1-ρ)) * (1/m) = 33.25 months

(c) On average, how many patented products are undergoing development or waiting to be developed?

T = Tq + p = 33.25 + 12 = 45.25 months
I = λ * T = 0.2 * 45.25 = 9.05 products

(d) How many months of patent life are left for an average product launched to the market?

Patent Life left = Total Patent Life – Time spent in the system = 144 months (12 years) – 45.25 months = 98.75 months

(e) After a product is launched to the market, it generates gross margins of $40 million per year of patent life. After the patent expires, the product generates no gross margins. What is Trojan Pharmaceuticals’ average total annual gross margins?

The flow rate in the market is 1/5 = 0.2 products per month. By applying Little’s Law we find that the inventory of products in the market is 0.2 products/month*98.75month = 19.75 products.
So the average total annual gross margins is 19.75 products * $40 million = $ 790 million.

(f) Trojan Pharmaceuticals is considering the option of building a fourth development center that has the same capacity as the other three. Omitting the initial capital investment, the estimated cost of running the new center is $150 million per year. Is this a profitable option to pursue? Provide numbers to justify your answer.

With the new center, we have m=4 while λ, μ, CVa, CVp remains the same as before.
The new utilization is ρ = λ / (mμ) = 0.6 and the new waiting time is Tq = (λ/μ^2) * (CVp^2 + CVa^2) / (2(1-ρ)) * (1/m) = 6.21 months

The flow rate in the market is still 1/5 = 0.2 products per month. Applying Little’s Law again finds the inventory of products in the market is 0.2 products/month * (144-6.21-12) = 25.158 products.
So the new average total annual gross margins is 25.158 products * $40 million = $1006.32 million

The additional gross margin is $216.32 million per year. This is greater than the cost of $150 per year, so building the new center is a profitable option to pursue.